s_aaline.c revision 27558a160a9fe91745728d7626995cd88f8fe339
1/* $Id: s_aaline.c,v 1.20 2003/03/01 01:50:25 brianp Exp $ */ 2 3/* 4 * Mesa 3-D graphics library 5 * Version: 5.0.1 6 * 7 * Copyright (C) 1999-2003 Brian Paul All Rights Reserved. 8 * 9 * Permission is hereby granted, free of charge, to any person obtaining a 10 * copy of this software and associated documentation files (the "Software"), 11 * to deal in the Software without restriction, including without limitation 12 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 13 * and/or sell copies of the Software, and to permit persons to whom the 14 * Software is furnished to do so, subject to the following conditions: 15 * 16 * The above copyright notice and this permission notice shall be included 17 * in all copies or substantial portions of the Software. 18 * 19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 20 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 22 * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 23 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 24 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 */ 26 27 28#include "glheader.h" 29#include "imports.h" 30#include "swrast/s_aaline.h" 31#include "swrast/s_context.h" 32#include "swrast/s_span.h" 33#include "swrast/swrast.h" 34#include "mtypes.h" 35 36 37#define SUB_PIXEL 4 38 39 40/* 41 * Info about the AA line we're rendering 42 */ 43struct LineInfo 44{ 45 GLfloat x0, y0; /* start */ 46 GLfloat x1, y1; /* end */ 47 GLfloat dx, dy; /* direction vector */ 48 GLfloat len; /* length */ 49 GLfloat halfWidth; /* half of line width */ 50 GLfloat xAdj, yAdj; /* X and Y adjustment for quad corners around line */ 51 /* for coverage computation */ 52 GLfloat qx0, qy0; /* quad vertices */ 53 GLfloat qx1, qy1; 54 GLfloat qx2, qy2; 55 GLfloat qx3, qy3; 56 GLfloat ex0, ey0; /* quad edge vectors */ 57 GLfloat ex1, ey1; 58 GLfloat ex2, ey2; 59 GLfloat ex3, ey3; 60 61 /* DO_Z */ 62 GLfloat zPlane[4]; 63 /* DO_FOG */ 64 GLfloat fPlane[4]; 65 /* DO_RGBA */ 66 GLfloat rPlane[4], gPlane[4], bPlane[4], aPlane[4]; 67 /* DO_INDEX */ 68 GLfloat iPlane[4]; 69 /* DO_SPEC */ 70 GLfloat srPlane[4], sgPlane[4], sbPlane[4]; 71 /* DO_TEX or DO_MULTITEX */ 72 GLfloat sPlane[MAX_TEXTURE_COORD_UNITS][4]; 73 GLfloat tPlane[MAX_TEXTURE_COORD_UNITS][4]; 74 GLfloat uPlane[MAX_TEXTURE_COORD_UNITS][4]; 75 GLfloat vPlane[MAX_TEXTURE_COORD_UNITS][4]; 76 GLfloat lambda[MAX_TEXTURE_COORD_UNITS]; 77 GLfloat texWidth[MAX_TEXTURE_COORD_UNITS]; 78 GLfloat texHeight[MAX_TEXTURE_COORD_UNITS]; 79 80 struct sw_span span; 81}; 82 83 84 85/* 86 * Compute the equation of a plane used to interpolate line fragment data 87 * such as color, Z, texture coords, etc. 88 * Input: (x0, y0) and (x1,y1) are the endpoints of the line. 89 * z0, and z1 are the end point values to interpolate. 90 * Output: plane - the plane equation. 91 * 92 * Note: we don't really have enough parameters to specify a plane. 93 * We take the endpoints of the line and compute a plane such that 94 * the cross product of the line vector and the plane normal is 95 * parallel to the projection plane. 96 */ 97static void 98compute_plane(GLfloat x0, GLfloat y0, GLfloat x1, GLfloat y1, 99 GLfloat z0, GLfloat z1, GLfloat plane[4]) 100{ 101#if 0 102 /* original */ 103 const GLfloat px = x1 - x0; 104 const GLfloat py = y1 - y0; 105 const GLfloat pz = z1 - z0; 106 const GLfloat qx = -py; 107 const GLfloat qy = px; 108 const GLfloat qz = 0; 109 const GLfloat a = py * qz - pz * qy; 110 const GLfloat b = pz * qx - px * qz; 111 const GLfloat c = px * qy - py * qx; 112 const GLfloat d = -(a * x0 + b * y0 + c * z0); 113 plane[0] = a; 114 plane[1] = b; 115 plane[2] = c; 116 plane[3] = d; 117#else 118 /* simplified */ 119 const GLfloat px = x1 - x0; 120 const GLfloat py = y1 - y0; 121 const GLfloat pz = z0 - z1; 122 const GLfloat a = pz * px; 123 const GLfloat b = pz * py; 124 const GLfloat c = px * px + py * py; 125 const GLfloat d = -(a * x0 + b * y0 + c * z0); 126 if (a == 0.0 && b == 0.0 && c == 0.0 && d == 0.0) { 127 plane[0] = 0.0; 128 plane[1] = 0.0; 129 plane[2] = 1.0; 130 plane[3] = 0.0; 131 } 132 else { 133 plane[0] = a; 134 plane[1] = b; 135 plane[2] = c; 136 plane[3] = d; 137 } 138#endif 139} 140 141 142static INLINE void 143constant_plane(GLfloat value, GLfloat plane[4]) 144{ 145 plane[0] = 0.0; 146 plane[1] = 0.0; 147 plane[2] = -1.0; 148 plane[3] = value; 149} 150 151 152static INLINE GLfloat 153solve_plane(GLfloat x, GLfloat y, const GLfloat plane[4]) 154{ 155 const GLfloat z = (plane[3] + plane[0] * x + plane[1] * y) / -plane[2]; 156 return z; 157} 158 159#define SOLVE_PLANE(X, Y, PLANE) \ 160 ((PLANE[3] + PLANE[0] * (X) + PLANE[1] * (Y)) / -PLANE[2]) 161 162 163/* 164 * Return 1 / solve_plane(). 165 */ 166static INLINE GLfloat 167solve_plane_recip(GLfloat x, GLfloat y, const GLfloat plane[4]) 168{ 169 const GLfloat denom = plane[3] + plane[0] * x + plane[1] * y; 170 if (denom == 0.0) 171 return 0.0; 172 else 173 return -plane[2] / denom; 174} 175 176 177/* 178 * Solve plane and return clamped GLchan value. 179 */ 180static INLINE GLchan 181solve_plane_chan(GLfloat x, GLfloat y, const GLfloat plane[4]) 182{ 183 const GLfloat z = (plane[3] + plane[0] * x + plane[1] * y) / -plane[2]; 184#if CHAN_TYPE == GL_FLOAT 185 return CLAMP(z, 0.0F, CHAN_MAXF); 186#else 187 if (z < 0) 188 return 0; 189 else if (z > CHAN_MAX) 190 return CHAN_MAX; 191 return (GLchan) IROUND_POS(z); 192#endif 193} 194 195 196/* 197 * Compute mipmap level of detail. 198 */ 199static INLINE GLfloat 200compute_lambda(const GLfloat sPlane[4], const GLfloat tPlane[4], 201 GLfloat invQ, GLfloat width, GLfloat height) 202{ 203 GLfloat dudx = sPlane[0] / sPlane[2] * invQ * width; 204 GLfloat dudy = sPlane[1] / sPlane[2] * invQ * width; 205 GLfloat dvdx = tPlane[0] / tPlane[2] * invQ * height; 206 GLfloat dvdy = tPlane[1] / tPlane[2] * invQ * height; 207 GLfloat r1 = dudx * dudx + dudy * dudy; 208 GLfloat r2 = dvdx * dvdx + dvdy * dvdy; 209 GLfloat rho2 = r1 + r2; 210 /* return log base 2 of rho */ 211 if (rho2 == 0.0F) 212 return 0.0; 213 else 214 return (GLfloat) (log(rho2) * 1.442695 * 0.5);/* 1.442695 = 1/log(2) */ 215} 216 217 218 219 220/* 221 * Fill in the samples[] array with the (x,y) subpixel positions of 222 * xSamples * ySamples sample positions. 223 * Note that the four corner samples are put into the first four 224 * positions of the array. This allows us to optimize for the common 225 * case of all samples being inside the polygon. 226 */ 227static void 228make_sample_table(GLint xSamples, GLint ySamples, GLfloat samples[][2]) 229{ 230 const GLfloat dx = 1.0F / (GLfloat) xSamples; 231 const GLfloat dy = 1.0F / (GLfloat) ySamples; 232 GLint x, y; 233 GLint i; 234 235 i = 4; 236 for (x = 0; x < xSamples; x++) { 237 for (y = 0; y < ySamples; y++) { 238 GLint j; 239 if (x == 0 && y == 0) { 240 /* lower left */ 241 j = 0; 242 } 243 else if (x == xSamples - 1 && y == 0) { 244 /* lower right */ 245 j = 1; 246 } 247 else if (x == 0 && y == ySamples - 1) { 248 /* upper left */ 249 j = 2; 250 } 251 else if (x == xSamples - 1 && y == ySamples - 1) { 252 /* upper right */ 253 j = 3; 254 } 255 else { 256 j = i++; 257 } 258 samples[j][0] = x * dx + 0.5F * dx; 259 samples[j][1] = y * dy + 0.5F * dy; 260 } 261 } 262} 263 264 265 266/* 267 * Compute how much of the given pixel's area is inside the rectangle 268 * defined by vertices v0, v1, v2, v3. 269 * Vertices MUST be specified in counter-clockwise order. 270 * Return: coverage in [0, 1]. 271 */ 272static GLfloat 273compute_coveragef(const struct LineInfo *info, 274 GLint winx, GLint winy) 275{ 276 static GLfloat samples[SUB_PIXEL * SUB_PIXEL][2]; 277 static GLboolean haveSamples = GL_FALSE; 278 const GLfloat x = (GLfloat) winx; 279 const GLfloat y = (GLfloat) winy; 280 GLint stop = 4, i; 281 GLfloat insideCount = SUB_PIXEL * SUB_PIXEL; 282 283 if (!haveSamples) { 284 make_sample_table(SUB_PIXEL, SUB_PIXEL, samples); 285 haveSamples = GL_TRUE; 286 } 287 288#if 0 /*DEBUG*/ 289 { 290 const GLfloat area = dx0 * dy1 - dx1 * dy0; 291 assert(area >= 0.0); 292 } 293#endif 294 295 for (i = 0; i < stop; i++) { 296 const GLfloat sx = x + samples[i][0]; 297 const GLfloat sy = y + samples[i][1]; 298 const GLfloat fx0 = sx - info->qx0; 299 const GLfloat fy0 = sy - info->qy0; 300 const GLfloat fx1 = sx - info->qx1; 301 const GLfloat fy1 = sy - info->qy1; 302 const GLfloat fx2 = sx - info->qx2; 303 const GLfloat fy2 = sy - info->qy2; 304 const GLfloat fx3 = sx - info->qx3; 305 const GLfloat fy3 = sy - info->qy3; 306 /* cross product determines if sample is inside or outside each edge */ 307 GLfloat cross0 = (info->ex0 * fy0 - info->ey0 * fx0); 308 GLfloat cross1 = (info->ex1 * fy1 - info->ey1 * fx1); 309 GLfloat cross2 = (info->ex2 * fy2 - info->ey2 * fx2); 310 GLfloat cross3 = (info->ex3 * fy3 - info->ey3 * fx3); 311 /* Check if the sample is exactly on an edge. If so, let cross be a 312 * positive or negative value depending on the direction of the edge. 313 */ 314 if (cross0 == 0.0F) 315 cross0 = info->ex0 + info->ey0; 316 if (cross1 == 0.0F) 317 cross1 = info->ex1 + info->ey1; 318 if (cross2 == 0.0F) 319 cross2 = info->ex2 + info->ey2; 320 if (cross3 == 0.0F) 321 cross3 = info->ex3 + info->ey3; 322 if (cross0 < 0.0F || cross1 < 0.0F || cross2 < 0.0F || cross3 < 0.0F) { 323 /* point is outside quadrilateral */ 324 insideCount -= 1.0F; 325 stop = SUB_PIXEL * SUB_PIXEL; 326 } 327 } 328 if (stop == 4) 329 return 1.0F; 330 else 331 return insideCount * (1.0F / (SUB_PIXEL * SUB_PIXEL)); 332} 333 334 335 336typedef void (*plot_func)(GLcontext *ctx, struct LineInfo *line, 337 int ix, int iy); 338 339 340 341/* 342 * Draw an AA line segment (called many times per line when stippling) 343 */ 344static void 345segment(GLcontext *ctx, 346 struct LineInfo *line, 347 plot_func plot, 348 GLfloat t0, GLfloat t1) 349{ 350 const GLfloat absDx = (line->dx < 0.0F) ? -line->dx : line->dx; 351 const GLfloat absDy = (line->dy < 0.0F) ? -line->dy : line->dy; 352 /* compute the actual segment's endpoints */ 353 const GLfloat x0 = line->x0 + t0 * line->dx; 354 const GLfloat y0 = line->y0 + t0 * line->dy; 355 const GLfloat x1 = line->x0 + t1 * line->dx; 356 const GLfloat y1 = line->y0 + t1 * line->dy; 357 358 /* compute vertices of the line-aligned quadrilateral */ 359 line->qx0 = x0 - line->yAdj; 360 line->qy0 = y0 + line->xAdj; 361 line->qx1 = x0 + line->yAdj; 362 line->qy1 = y0 - line->xAdj; 363 line->qx2 = x1 + line->yAdj; 364 line->qy2 = y1 - line->xAdj; 365 line->qx3 = x1 - line->yAdj; 366 line->qy3 = y1 + line->xAdj; 367 /* compute the quad's edge vectors (for coverage calc) */ 368 line->ex0 = line->qx1 - line->qx0; 369 line->ey0 = line->qy1 - line->qy0; 370 line->ex1 = line->qx2 - line->qx1; 371 line->ey1 = line->qy2 - line->qy1; 372 line->ex2 = line->qx3 - line->qx2; 373 line->ey2 = line->qy3 - line->qy2; 374 line->ex3 = line->qx0 - line->qx3; 375 line->ey3 = line->qy0 - line->qy3; 376 377 if (absDx > absDy) { 378 /* X-major line */ 379 GLfloat dydx = line->dy / line->dx; 380 GLfloat xLeft, xRight, yBot, yTop; 381 GLint ix, ixRight; 382 if (x0 < x1) { 383 xLeft = x0 - line->halfWidth; 384 xRight = x1 + line->halfWidth; 385 if (line->dy >= 0.0) { 386 yBot = y0 - 3.0F * line->halfWidth; 387 yTop = y0 + line->halfWidth; 388 } 389 else { 390 yBot = y0 - line->halfWidth; 391 yTop = y0 + 3.0F * line->halfWidth; 392 } 393 } 394 else { 395 xLeft = x1 - line->halfWidth; 396 xRight = x0 + line->halfWidth; 397 if (line->dy <= 0.0) { 398 yBot = y1 - 3.0F * line->halfWidth; 399 yTop = y1 + line->halfWidth; 400 } 401 else { 402 yBot = y1 - line->halfWidth; 403 yTop = y1 + 3.0F * line->halfWidth; 404 } 405 } 406 407 /* scan along the line, left-to-right */ 408 ixRight = (GLint) (xRight + 1.0F); 409 410 /*printf("avg span height: %g\n", yTop - yBot);*/ 411 for (ix = (GLint) xLeft; ix < ixRight; ix++) { 412 const GLint iyBot = (GLint) yBot; 413 const GLint iyTop = (GLint) (yTop + 1.0F); 414 GLint iy; 415 /* scan across the line, bottom-to-top */ 416 for (iy = iyBot; iy < iyTop; iy++) { 417 (*plot)(ctx, line, ix, iy); 418 } 419 yBot += dydx; 420 yTop += dydx; 421 } 422 } 423 else { 424 /* Y-major line */ 425 GLfloat dxdy = line->dx / line->dy; 426 GLfloat yBot, yTop, xLeft, xRight; 427 GLint iy, iyTop; 428 if (y0 < y1) { 429 yBot = y0 - line->halfWidth; 430 yTop = y1 + line->halfWidth; 431 if (line->dx >= 0.0) { 432 xLeft = x0 - 3.0F * line->halfWidth; 433 xRight = x0 + line->halfWidth; 434 } 435 else { 436 xLeft = x0 - line->halfWidth; 437 xRight = x0 + 3.0F * line->halfWidth; 438 } 439 } 440 else { 441 yBot = y1 - line->halfWidth; 442 yTop = y0 + line->halfWidth; 443 if (line->dx <= 0.0) { 444 xLeft = x1 - 3.0F * line->halfWidth; 445 xRight = x1 + line->halfWidth; 446 } 447 else { 448 xLeft = x1 - line->halfWidth; 449 xRight = x1 + 3.0F * line->halfWidth; 450 } 451 } 452 453 /* scan along the line, bottom-to-top */ 454 iyTop = (GLint) (yTop + 1.0F); 455 456 /*printf("avg span width: %g\n", xRight - xLeft);*/ 457 for (iy = (GLint) yBot; iy < iyTop; iy++) { 458 const GLint ixLeft = (GLint) xLeft; 459 const GLint ixRight = (GLint) (xRight + 1.0F); 460 GLint ix; 461 /* scan across the line, left-to-right */ 462 for (ix = ixLeft; ix < ixRight; ix++) { 463 (*plot)(ctx, line, ix, iy); 464 } 465 xLeft += dxdy; 466 xRight += dxdy; 467 } 468 } 469} 470 471 472#define NAME(x) aa_ci_##x 473#define DO_Z 474#define DO_FOG 475#define DO_INDEX 476#include "s_aalinetemp.h" 477 478 479#define NAME(x) aa_rgba_##x 480#define DO_Z 481#define DO_FOG 482#define DO_RGBA 483#include "s_aalinetemp.h" 484 485 486#define NAME(x) aa_tex_rgba_##x 487#define DO_Z 488#define DO_FOG 489#define DO_RGBA 490#define DO_TEX 491#include "s_aalinetemp.h" 492 493 494#define NAME(x) aa_multitex_rgba_##x 495#define DO_Z 496#define DO_FOG 497#define DO_RGBA 498#define DO_MULTITEX 499#include "s_aalinetemp.h" 500 501 502#define NAME(x) aa_multitex_spec_##x 503#define DO_Z 504#define DO_FOG 505#define DO_RGBA 506#define DO_MULTITEX 507#define DO_SPEC 508#include "s_aalinetemp.h" 509 510 511 512void 513_swrast_choose_aa_line_function(GLcontext *ctx) 514{ 515 SWcontext *swrast = SWRAST_CONTEXT(ctx); 516 517 ASSERT(ctx->Line.SmoothFlag); 518 519 if (ctx->Visual.rgbMode) { 520 /* RGBA */ 521 if (ctx->Texture._EnabledUnits != 0) { 522 if (ctx->Texture._EnabledUnits > 1) { 523 /* Multitextured! */ 524 if (ctx->Light.Model.ColorControl==GL_SEPARATE_SPECULAR_COLOR || 525 ctx->Fog.ColorSumEnabled) 526 swrast->Line = aa_multitex_spec_line; 527 else 528 swrast->Line = aa_multitex_rgba_line; 529 } 530 else { 531 swrast->Line = aa_tex_rgba_line; 532 } 533 } 534 else { 535 swrast->Line = aa_rgba_line; 536 } 537 } 538 else { 539 /* Color Index */ 540 swrast->Line = aa_ci_line; 541 } 542} 543