1/* 2 * Mesa 3-D graphics library 3 * 4 * Copyright (C) 1999-2007 Brian Paul All Rights Reserved. 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a 7 * copy of this software and associated documentation files (the "Software"), 8 * to deal in the Software without restriction, including without limitation 9 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 10 * and/or sell copies of the Software, and to permit persons to whom the 11 * Software is furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included 14 * in all copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 17 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 20 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 21 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 22 * OTHER DEALINGS IN THE SOFTWARE. 23 */ 24 25/* 26 * Triangle Rasterizer Template 27 * 28 * This file is #include'd to generate custom triangle rasterizers. 29 * 30 * The following macros may be defined to indicate what auxillary information 31 * must be interpolated across the triangle: 32 * INTERP_Z - if defined, interpolate integer Z values 33 * INTERP_RGB - if defined, interpolate integer RGB values 34 * INTERP_ALPHA - if defined, interpolate integer Alpha values 35 * INTERP_INT_TEX - if defined, interpolate integer ST texcoords 36 * (fast, simple 2-D texture mapping, without 37 * perspective correction) 38 * INTERP_ATTRIBS - if defined, interpolate arbitrary attribs (texcoords, 39 * varying vars, etc) This also causes W to be 40 * computed for perspective correction). 41 * 42 * When one can directly address pixels in the color buffer the following 43 * macros can be defined and used to compute pixel addresses during 44 * rasterization (see pRow): 45 * PIXEL_TYPE - the datatype of a pixel (GLubyte, GLushort, GLuint) 46 * BYTES_PER_ROW - number of bytes per row in the color buffer 47 * PIXEL_ADDRESS(X,Y) - returns the address of pixel at (X,Y) where 48 * Y==0 at bottom of screen and increases upward. 49 * 50 * Similarly, for direct depth buffer access, this type is used for depth 51 * buffer addressing (see zRow): 52 * DEPTH_TYPE - either GLushort or GLuint 53 * 54 * Optionally, one may provide one-time setup code per triangle: 55 * SETUP_CODE - code which is to be executed once per triangle 56 * 57 * The following macro MUST be defined: 58 * RENDER_SPAN(span) - code to write a span of pixels. 59 * 60 * This code was designed for the origin to be in the lower-left corner. 61 * 62 * Inspired by triangle rasterizer code written by Allen Akin. Thanks Allen! 63 * 64 * 65 * Some notes on rasterization accuracy: 66 * 67 * This code uses fixed point arithmetic (the GLfixed type) to iterate 68 * over the triangle edges and interpolate ancillary data (such as Z, 69 * color, secondary color, etc). The number of fractional bits in 70 * GLfixed and the value of SUB_PIXEL_BITS has a direct bearing on the 71 * accuracy of rasterization. 72 * 73 * If SUB_PIXEL_BITS=4 then we'll snap the vertices to the nearest 74 * 1/16 of a pixel. If we're walking up a long, nearly vertical edge 75 * (dx=1/16, dy=1024) we'll need 4 + 10 = 14 fractional bits in 76 * GLfixed to walk the edge without error. If the maximum viewport 77 * height is 4K pixels, then we'll need 4 + 12 = 16 fractional bits. 78 * 79 * Historically, Mesa has used 11 fractional bits in GLfixed, snaps 80 * vertices to 1/16 pixel and allowed a maximum viewport height of 2K 81 * pixels. 11 fractional bits is actually insufficient for accurately 82 * rasterizing some triangles. More recently, the maximum viewport 83 * height was increased to 4K pixels. Thus, Mesa should be using 16 84 * fractional bits in GLfixed. Unfortunately, there may be some issues 85 * with setting FIXED_FRAC_BITS=16, such as multiplication overflow. 86 * This will have to be examined in some detail... 87 * 88 * For now, if you find rasterization errors, particularly with tall, 89 * sliver triangles, try increasing FIXED_FRAC_BITS and/or decreasing 90 * SUB_PIXEL_BITS. 91 */ 92 93 94#ifndef MAX_GLUINT 95#define MAX_GLUINT 0xffffffffu 96#endif 97 98 99/* 100 * Some code we unfortunately need to prevent negative interpolated colors. 101 */ 102#ifndef CLAMP_INTERPOLANT 103#define CLAMP_INTERPOLANT(CHANNEL, CHANNELSTEP, LEN) \ 104do { \ 105 GLfixed endVal = span.CHANNEL + (LEN) * span.CHANNELSTEP; \ 106 if (endVal < 0) { \ 107 span.CHANNEL -= endVal; \ 108 } \ 109 if (span.CHANNEL < 0) { \ 110 span.CHANNEL = 0; \ 111 } \ 112} while (0) 113#endif 114 115 116static void NAME(struct gl_context *ctx, const SWvertex *v0, 117 const SWvertex *v1, 118 const SWvertex *v2 ) 119{ 120 typedef struct { 121 const SWvertex *v0, *v1; /* Y(v0) < Y(v1) */ 122 GLfloat dx; /* X(v1) - X(v0) */ 123 GLfloat dy; /* Y(v1) - Y(v0) */ 124 GLfloat dxdy; /* dx/dy */ 125 GLfixed fdxdy; /* dx/dy in fixed-point */ 126 GLfloat adjy; /* adjust from v[0]->fy to fsy, scaled */ 127 GLfixed fsx; /* first sample point x coord */ 128 GLfixed fsy; 129 GLfixed fx0; /* fixed pt X of lower endpoint */ 130 GLint lines; /* number of lines to be sampled on this edge */ 131 } EdgeT; 132 133 const SWcontext *swrast = SWRAST_CONTEXT(ctx); 134#ifdef INTERP_Z 135 const GLint depthBits = ctx->DrawBuffer->Visual.depthBits; 136 const GLint fixedToDepthShift = depthBits <= 16 ? FIXED_SHIFT : 0; 137 const GLfloat maxDepth = ctx->DrawBuffer->_DepthMaxF; 138#define FixedToDepth(F) ((F) >> fixedToDepthShift) 139#endif 140 EdgeT eMaj, eTop, eBot; 141 GLfloat oneOverArea; 142 const SWvertex *vMin, *vMid, *vMax; /* Y(vMin)<=Y(vMid)<=Y(vMax) */ 143 GLfloat bf = SWRAST_CONTEXT(ctx)->_BackfaceSign; 144 const GLint snapMask = ~((FIXED_ONE / (1 << SUB_PIXEL_BITS)) - 1); /* for x/y coord snapping */ 145 GLfixed vMin_fx, vMin_fy, vMid_fx, vMid_fy, vMax_fx, vMax_fy; 146 147 SWspan span; 148 149 (void) swrast; 150 151 INIT_SPAN(span, GL_POLYGON); 152 span.y = 0; /* silence warnings */ 153 154#ifdef INTERP_Z 155 (void) fixedToDepthShift; 156#endif 157 158 /* 159 printf("%s()\n", __func__); 160 printf(" %g, %g, %g\n", 161 v0->attrib[VARYING_SLOT_POS][0], 162 v0->attrib[VARYING_SLOT_POS][1], 163 v0->attrib[VARYING_SLOT_POS][2]); 164 printf(" %g, %g, %g\n", 165 v1->attrib[VARYING_SLOT_POS][0], 166 v1->attrib[VARYING_SLOT_POS][1], 167 v1->attrib[VARYING_SLOT_POS][2]); 168 printf(" %g, %g, %g\n", 169 v2->attrib[VARYING_SLOT_POS][0], 170 v2->attrib[VARYING_SLOT_POS][1], 171 v2->attrib[VARYING_SLOT_POS][2]); 172 */ 173 174 /* Compute fixed point x,y coords w/ half-pixel offsets and snapping. 175 * And find the order of the 3 vertices along the Y axis. 176 */ 177 { 178 const GLfixed fy0 = FloatToFixed(v0->attrib[VARYING_SLOT_POS][1] - 0.5F) & snapMask; 179 const GLfixed fy1 = FloatToFixed(v1->attrib[VARYING_SLOT_POS][1] - 0.5F) & snapMask; 180 const GLfixed fy2 = FloatToFixed(v2->attrib[VARYING_SLOT_POS][1] - 0.5F) & snapMask; 181 if (fy0 <= fy1) { 182 if (fy1 <= fy2) { 183 /* y0 <= y1 <= y2 */ 184 vMin = v0; vMid = v1; vMax = v2; 185 vMin_fy = fy0; vMid_fy = fy1; vMax_fy = fy2; 186 } 187 else if (fy2 <= fy0) { 188 /* y2 <= y0 <= y1 */ 189 vMin = v2; vMid = v0; vMax = v1; 190 vMin_fy = fy2; vMid_fy = fy0; vMax_fy = fy1; 191 } 192 else { 193 /* y0 <= y2 <= y1 */ 194 vMin = v0; vMid = v2; vMax = v1; 195 vMin_fy = fy0; vMid_fy = fy2; vMax_fy = fy1; 196 bf = -bf; 197 } 198 } 199 else { 200 if (fy0 <= fy2) { 201 /* y1 <= y0 <= y2 */ 202 vMin = v1; vMid = v0; vMax = v2; 203 vMin_fy = fy1; vMid_fy = fy0; vMax_fy = fy2; 204 bf = -bf; 205 } 206 else if (fy2 <= fy1) { 207 /* y2 <= y1 <= y0 */ 208 vMin = v2; vMid = v1; vMax = v0; 209 vMin_fy = fy2; vMid_fy = fy1; vMax_fy = fy0; 210 bf = -bf; 211 } 212 else { 213 /* y1 <= y2 <= y0 */ 214 vMin = v1; vMid = v2; vMax = v0; 215 vMin_fy = fy1; vMid_fy = fy2; vMax_fy = fy0; 216 } 217 } 218 219 /* fixed point X coords */ 220 vMin_fx = FloatToFixed(vMin->attrib[VARYING_SLOT_POS][0] + 0.5F) & snapMask; 221 vMid_fx = FloatToFixed(vMid->attrib[VARYING_SLOT_POS][0] + 0.5F) & snapMask; 222 vMax_fx = FloatToFixed(vMax->attrib[VARYING_SLOT_POS][0] + 0.5F) & snapMask; 223 } 224 225 /* vertex/edge relationship */ 226 eMaj.v0 = vMin; eMaj.v1 = vMax; /*TODO: .v1's not needed */ 227 eTop.v0 = vMid; eTop.v1 = vMax; 228 eBot.v0 = vMin; eBot.v1 = vMid; 229 230 /* compute deltas for each edge: vertex[upper] - vertex[lower] */ 231 eMaj.dx = FixedToFloat(vMax_fx - vMin_fx); 232 eMaj.dy = FixedToFloat(vMax_fy - vMin_fy); 233 eTop.dx = FixedToFloat(vMax_fx - vMid_fx); 234 eTop.dy = FixedToFloat(vMax_fy - vMid_fy); 235 eBot.dx = FixedToFloat(vMid_fx - vMin_fx); 236 eBot.dy = FixedToFloat(vMid_fy - vMin_fy); 237 238 /* compute area, oneOverArea and perform backface culling */ 239 { 240 const GLfloat area = eMaj.dx * eBot.dy - eBot.dx * eMaj.dy; 241 242 if (IS_INF_OR_NAN(area) || area == 0.0F) 243 return; 244 245 if (area * bf * swrast->_BackfaceCullSign < 0.0F) 246 return; 247 248 oneOverArea = 1.0F / area; 249 250 /* 0 = front, 1 = back */ 251 span.facing = oneOverArea * bf > 0.0F; 252 } 253 254 /* Edge setup. For a triangle strip these could be reused... */ 255 { 256 eMaj.fsy = FixedCeil(vMin_fy); 257 eMaj.lines = FixedToInt(FixedCeil(vMax_fy - eMaj.fsy)); 258 if (eMaj.lines > 0) { 259 eMaj.dxdy = eMaj.dx / eMaj.dy; 260 eMaj.fdxdy = SignedFloatToFixed(eMaj.dxdy); 261 eMaj.adjy = (GLfloat) (eMaj.fsy - vMin_fy); /* SCALED! */ 262 eMaj.fx0 = vMin_fx; 263 eMaj.fsx = eMaj.fx0 + (GLfixed) (eMaj.adjy * eMaj.dxdy); 264 } 265 else { 266 return; /*CULLED*/ 267 } 268 269 eTop.fsy = FixedCeil(vMid_fy); 270 eTop.lines = FixedToInt(FixedCeil(vMax_fy - eTop.fsy)); 271 if (eTop.lines > 0) { 272 eTop.dxdy = eTop.dx / eTop.dy; 273 eTop.fdxdy = SignedFloatToFixed(eTop.dxdy); 274 eTop.adjy = (GLfloat) (eTop.fsy - vMid_fy); /* SCALED! */ 275 eTop.fx0 = vMid_fx; 276 eTop.fsx = eTop.fx0 + (GLfixed) (eTop.adjy * eTop.dxdy); 277 } 278 279 eBot.fsy = FixedCeil(vMin_fy); 280 eBot.lines = FixedToInt(FixedCeil(vMid_fy - eBot.fsy)); 281 if (eBot.lines > 0) { 282 eBot.dxdy = eBot.dx / eBot.dy; 283 eBot.fdxdy = SignedFloatToFixed(eBot.dxdy); 284 eBot.adjy = (GLfloat) (eBot.fsy - vMin_fy); /* SCALED! */ 285 eBot.fx0 = vMin_fx; 286 eBot.fsx = eBot.fx0 + (GLfixed) (eBot.adjy * eBot.dxdy); 287 } 288 } 289 290 /* 291 * Conceptually, we view a triangle as two subtriangles 292 * separated by a perfectly horizontal line. The edge that is 293 * intersected by this line is one with maximal absolute dy; we 294 * call it a ``major'' edge. The other two edges are the 295 * ``top'' edge (for the upper subtriangle) and the ``bottom'' 296 * edge (for the lower subtriangle). If either of these two 297 * edges is horizontal or very close to horizontal, the 298 * corresponding subtriangle might cover zero sample points; 299 * we take care to handle such cases, for performance as well 300 * as correctness. 301 * 302 * By stepping rasterization parameters along the major edge, 303 * we can avoid recomputing them at the discontinuity where 304 * the top and bottom edges meet. However, this forces us to 305 * be able to scan both left-to-right and right-to-left. 306 * Also, we must determine whether the major edge is at the 307 * left or right side of the triangle. We do this by 308 * computing the magnitude of the cross-product of the major 309 * and top edges. Since this magnitude depends on the sine of 310 * the angle between the two edges, its sign tells us whether 311 * we turn to the left or to the right when travelling along 312 * the major edge to the top edge, and from this we infer 313 * whether the major edge is on the left or the right. 314 * 315 * Serendipitously, this cross-product magnitude is also a 316 * value we need to compute the iteration parameter 317 * derivatives for the triangle, and it can be used to perform 318 * backface culling because its sign tells us whether the 319 * triangle is clockwise or counterclockwise. In this code we 320 * refer to it as ``area'' because it's also proportional to 321 * the pixel area of the triangle. 322 */ 323 324 { 325 GLint scan_from_left_to_right; /* true if scanning left-to-right */ 326 327 /* 328 * Execute user-supplied setup code 329 */ 330#ifdef SETUP_CODE 331 SETUP_CODE 332#endif 333 334 scan_from_left_to_right = (oneOverArea < 0.0F); 335 336 337 /* compute d?/dx and d?/dy derivatives */ 338#ifdef INTERP_Z 339 span.interpMask |= SPAN_Z; 340 { 341 GLfloat eMaj_dz = vMax->attrib[VARYING_SLOT_POS][2] - vMin->attrib[VARYING_SLOT_POS][2]; 342 GLfloat eBot_dz = vMid->attrib[VARYING_SLOT_POS][2] - vMin->attrib[VARYING_SLOT_POS][2]; 343 span.attrStepX[VARYING_SLOT_POS][2] = oneOverArea * (eMaj_dz * eBot.dy - eMaj.dy * eBot_dz); 344 if (span.attrStepX[VARYING_SLOT_POS][2] > maxDepth || 345 span.attrStepX[VARYING_SLOT_POS][2] < -maxDepth) { 346 /* probably a sliver triangle */ 347 span.attrStepX[VARYING_SLOT_POS][2] = 0.0; 348 span.attrStepY[VARYING_SLOT_POS][2] = 0.0; 349 } 350 else { 351 span.attrStepY[VARYING_SLOT_POS][2] = oneOverArea * (eMaj.dx * eBot_dz - eMaj_dz * eBot.dx); 352 } 353 if (depthBits <= 16) 354 span.zStep = SignedFloatToFixed(span.attrStepX[VARYING_SLOT_POS][2]); 355 else 356 span.zStep = (GLint) span.attrStepX[VARYING_SLOT_POS][2]; 357 } 358#endif 359#ifdef INTERP_RGB 360 span.interpMask |= SPAN_RGBA; 361 if (ctx->Light.ShadeModel == GL_SMOOTH) { 362 GLfloat eMaj_dr = (GLfloat) (vMax->color[RCOMP] - vMin->color[RCOMP]); 363 GLfloat eBot_dr = (GLfloat) (vMid->color[RCOMP] - vMin->color[RCOMP]); 364 GLfloat eMaj_dg = (GLfloat) (vMax->color[GCOMP] - vMin->color[GCOMP]); 365 GLfloat eBot_dg = (GLfloat) (vMid->color[GCOMP] - vMin->color[GCOMP]); 366 GLfloat eMaj_db = (GLfloat) (vMax->color[BCOMP] - vMin->color[BCOMP]); 367 GLfloat eBot_db = (GLfloat) (vMid->color[BCOMP] - vMin->color[BCOMP]); 368# ifdef INTERP_ALPHA 369 GLfloat eMaj_da = (GLfloat) (vMax->color[ACOMP] - vMin->color[ACOMP]); 370 GLfloat eBot_da = (GLfloat) (vMid->color[ACOMP] - vMin->color[ACOMP]); 371# endif 372 span.attrStepX[VARYING_SLOT_COL0][0] = oneOverArea * (eMaj_dr * eBot.dy - eMaj.dy * eBot_dr); 373 span.attrStepY[VARYING_SLOT_COL0][0] = oneOverArea * (eMaj.dx * eBot_dr - eMaj_dr * eBot.dx); 374 span.attrStepX[VARYING_SLOT_COL0][1] = oneOverArea * (eMaj_dg * eBot.dy - eMaj.dy * eBot_dg); 375 span.attrStepY[VARYING_SLOT_COL0][1] = oneOverArea * (eMaj.dx * eBot_dg - eMaj_dg * eBot.dx); 376 span.attrStepX[VARYING_SLOT_COL0][2] = oneOverArea * (eMaj_db * eBot.dy - eMaj.dy * eBot_db); 377 span.attrStepY[VARYING_SLOT_COL0][2] = oneOverArea * (eMaj.dx * eBot_db - eMaj_db * eBot.dx); 378 span.redStep = SignedFloatToFixed(span.attrStepX[VARYING_SLOT_COL0][0]); 379 span.greenStep = SignedFloatToFixed(span.attrStepX[VARYING_SLOT_COL0][1]); 380 span.blueStep = SignedFloatToFixed(span.attrStepX[VARYING_SLOT_COL0][2]); 381# ifdef INTERP_ALPHA 382 span.attrStepX[VARYING_SLOT_COL0][3] = oneOverArea * (eMaj_da * eBot.dy - eMaj.dy * eBot_da); 383 span.attrStepY[VARYING_SLOT_COL0][3] = oneOverArea * (eMaj.dx * eBot_da - eMaj_da * eBot.dx); 384 span.alphaStep = SignedFloatToFixed(span.attrStepX[VARYING_SLOT_COL0][3]); 385# endif /* INTERP_ALPHA */ 386 } 387 else { 388 assert(ctx->Light.ShadeModel == GL_FLAT); 389 span.interpMask |= SPAN_FLAT; 390 span.attrStepX[VARYING_SLOT_COL0][0] = span.attrStepY[VARYING_SLOT_COL0][0] = 0.0F; 391 span.attrStepX[VARYING_SLOT_COL0][1] = span.attrStepY[VARYING_SLOT_COL0][1] = 0.0F; 392 span.attrStepX[VARYING_SLOT_COL0][2] = span.attrStepY[VARYING_SLOT_COL0][2] = 0.0F; 393 span.redStep = 0; 394 span.greenStep = 0; 395 span.blueStep = 0; 396# ifdef INTERP_ALPHA 397 span.attrStepX[VARYING_SLOT_COL0][3] = span.attrStepY[VARYING_SLOT_COL0][3] = 0.0F; 398 span.alphaStep = 0; 399# endif 400 } 401#endif /* INTERP_RGB */ 402#ifdef INTERP_INT_TEX 403 { 404 GLfloat eMaj_ds = (vMax->attrib[VARYING_SLOT_TEX0][0] - vMin->attrib[VARYING_SLOT_TEX0][0]) * S_SCALE; 405 GLfloat eBot_ds = (vMid->attrib[VARYING_SLOT_TEX0][0] - vMin->attrib[VARYING_SLOT_TEX0][0]) * S_SCALE; 406 GLfloat eMaj_dt = (vMax->attrib[VARYING_SLOT_TEX0][1] - vMin->attrib[VARYING_SLOT_TEX0][1]) * T_SCALE; 407 GLfloat eBot_dt = (vMid->attrib[VARYING_SLOT_TEX0][1] - vMin->attrib[VARYING_SLOT_TEX0][1]) * T_SCALE; 408 span.attrStepX[VARYING_SLOT_TEX0][0] = oneOverArea * (eMaj_ds * eBot.dy - eMaj.dy * eBot_ds); 409 span.attrStepY[VARYING_SLOT_TEX0][0] = oneOverArea * (eMaj.dx * eBot_ds - eMaj_ds * eBot.dx); 410 span.attrStepX[VARYING_SLOT_TEX0][1] = oneOverArea * (eMaj_dt * eBot.dy - eMaj.dy * eBot_dt); 411 span.attrStepY[VARYING_SLOT_TEX0][1] = oneOverArea * (eMaj.dx * eBot_dt - eMaj_dt * eBot.dx); 412 span.intTexStep[0] = SignedFloatToFixed(span.attrStepX[VARYING_SLOT_TEX0][0]); 413 span.intTexStep[1] = SignedFloatToFixed(span.attrStepX[VARYING_SLOT_TEX0][1]); 414 } 415#endif 416#ifdef INTERP_ATTRIBS 417 { 418 /* attrib[VARYING_SLOT_POS][3] is 1/W */ 419 const GLfloat wMax = vMax->attrib[VARYING_SLOT_POS][3]; 420 const GLfloat wMin = vMin->attrib[VARYING_SLOT_POS][3]; 421 const GLfloat wMid = vMid->attrib[VARYING_SLOT_POS][3]; 422 { 423 const GLfloat eMaj_dw = wMax - wMin; 424 const GLfloat eBot_dw = wMid - wMin; 425 span.attrStepX[VARYING_SLOT_POS][3] = oneOverArea * (eMaj_dw * eBot.dy - eMaj.dy * eBot_dw); 426 span.attrStepY[VARYING_SLOT_POS][3] = oneOverArea * (eMaj.dx * eBot_dw - eMaj_dw * eBot.dx); 427 } 428 ATTRIB_LOOP_BEGIN 429 if (swrast->_InterpMode[attr] == GL_FLAT) { 430 ASSIGN_4V(span.attrStepX[attr], 0.0, 0.0, 0.0, 0.0); 431 ASSIGN_4V(span.attrStepY[attr], 0.0, 0.0, 0.0, 0.0); 432 } 433 else { 434 GLuint c; 435 for (c = 0; c < 4; c++) { 436 GLfloat eMaj_da = vMax->attrib[attr][c] * wMax - vMin->attrib[attr][c] * wMin; 437 GLfloat eBot_da = vMid->attrib[attr][c] * wMid - vMin->attrib[attr][c] * wMin; 438 span.attrStepX[attr][c] = oneOverArea * (eMaj_da * eBot.dy - eMaj.dy * eBot_da); 439 span.attrStepY[attr][c] = oneOverArea * (eMaj.dx * eBot_da - eMaj_da * eBot.dx); 440 } 441 } 442 ATTRIB_LOOP_END 443 } 444#endif 445 446 /* 447 * We always sample at pixel centers. However, we avoid 448 * explicit half-pixel offsets in this code by incorporating 449 * the proper offset in each of x and y during the 450 * transformation to window coordinates. 451 * 452 * We also apply the usual rasterization rules to prevent 453 * cracks and overlaps. A pixel is considered inside a 454 * subtriangle if it meets all of four conditions: it is on or 455 * to the right of the left edge, strictly to the left of the 456 * right edge, on or below the top edge, and strictly above 457 * the bottom edge. (Some edges may be degenerate.) 458 * 459 * The following discussion assumes left-to-right scanning 460 * (that is, the major edge is on the left); the right-to-left 461 * case is a straightforward variation. 462 * 463 * We start by finding the half-integral y coordinate that is 464 * at or below the top of the triangle. This gives us the 465 * first scan line that could possibly contain pixels that are 466 * inside the triangle. 467 * 468 * Next we creep down the major edge until we reach that y, 469 * and compute the corresponding x coordinate on the edge. 470 * Then we find the half-integral x that lies on or just 471 * inside the edge. This is the first pixel that might lie in 472 * the interior of the triangle. (We won't know for sure 473 * until we check the other edges.) 474 * 475 * As we rasterize the triangle, we'll step down the major 476 * edge. For each step in y, we'll move an integer number 477 * of steps in x. There are two possible x step sizes, which 478 * we'll call the ``inner'' step (guaranteed to land on the 479 * edge or inside it) and the ``outer'' step (guaranteed to 480 * land on the edge or outside it). The inner and outer steps 481 * differ by one. During rasterization we maintain an error 482 * term that indicates our distance from the true edge, and 483 * select either the inner step or the outer step, whichever 484 * gets us to the first pixel that falls inside the triangle. 485 * 486 * All parameters (z, red, etc.) as well as the buffer 487 * addresses for color and z have inner and outer step values, 488 * so that we can increment them appropriately. This method 489 * eliminates the need to adjust parameters by creeping a 490 * sub-pixel amount into the triangle at each scanline. 491 */ 492 493 { 494 GLint subTriangle; 495 GLfixed fxLeftEdge = 0, fxRightEdge = 0; 496 GLfixed fdxLeftEdge = 0, fdxRightEdge = 0; 497 GLfixed fError = 0, fdError = 0; 498#ifdef PIXEL_ADDRESS 499 PIXEL_TYPE *pRow = NULL; 500 GLint dPRowOuter = 0, dPRowInner; /* offset in bytes */ 501#endif 502#ifdef INTERP_Z 503# ifdef DEPTH_TYPE 504 struct gl_renderbuffer *zrb 505 = ctx->DrawBuffer->Attachment[BUFFER_DEPTH].Renderbuffer; 506 DEPTH_TYPE *zRow = NULL; 507 GLint dZRowOuter = 0, dZRowInner; /* offset in bytes */ 508# endif 509 GLuint zLeft = 0; 510 GLfixed fdzOuter = 0, fdzInner; 511#endif 512#ifdef INTERP_RGB 513 GLint rLeft = 0, fdrOuter = 0, fdrInner; 514 GLint gLeft = 0, fdgOuter = 0, fdgInner; 515 GLint bLeft = 0, fdbOuter = 0, fdbInner; 516#endif 517#ifdef INTERP_ALPHA 518 GLint aLeft = 0, fdaOuter = 0, fdaInner; 519#endif 520#ifdef INTERP_INT_TEX 521 GLfixed sLeft=0, dsOuter=0, dsInner; 522 GLfixed tLeft=0, dtOuter=0, dtInner; 523#endif 524#ifdef INTERP_ATTRIBS 525 GLfloat wLeft = 0, dwOuter = 0, dwInner; 526 GLfloat attrLeft[VARYING_SLOT_MAX][4]; 527 GLfloat daOuter[VARYING_SLOT_MAX][4], daInner[VARYING_SLOT_MAX][4]; 528#endif 529 530 for (subTriangle=0; subTriangle<=1; subTriangle++) { 531 EdgeT *eLeft, *eRight; 532 int setupLeft, setupRight; 533 int lines; 534 535 if (subTriangle==0) { 536 /* bottom half */ 537 if (scan_from_left_to_right) { 538 eLeft = &eMaj; 539 eRight = &eBot; 540 lines = eRight->lines; 541 setupLeft = 1; 542 setupRight = 1; 543 } 544 else { 545 eLeft = &eBot; 546 eRight = &eMaj; 547 lines = eLeft->lines; 548 setupLeft = 1; 549 setupRight = 1; 550 } 551 } 552 else { 553 /* top half */ 554 if (scan_from_left_to_right) { 555 eLeft = &eMaj; 556 eRight = &eTop; 557 lines = eRight->lines; 558 setupLeft = 0; 559 setupRight = 1; 560 } 561 else { 562 eLeft = &eTop; 563 eRight = &eMaj; 564 lines = eLeft->lines; 565 setupLeft = 1; 566 setupRight = 0; 567 } 568 if (lines == 0) 569 return; 570 } 571 572 if (setupLeft && eLeft->lines > 0) { 573 const SWvertex *vLower = eLeft->v0; 574 const GLfixed fsy = eLeft->fsy; 575 const GLfixed fsx = eLeft->fsx; /* no fractional part */ 576 const GLfixed fx = FixedCeil(fsx); /* no fractional part */ 577 const GLfixed adjx = (GLfixed) (fx - eLeft->fx0); /* SCALED! */ 578 const GLfixed adjy = (GLfixed) eLeft->adjy; /* SCALED! */ 579 GLint idxOuter; 580 GLfloat dxOuter; 581 GLfixed fdxOuter; 582 583 fError = fx - fsx - FIXED_ONE; 584 fxLeftEdge = fsx - FIXED_EPSILON; 585 fdxLeftEdge = eLeft->fdxdy; 586 fdxOuter = FixedFloor(fdxLeftEdge - FIXED_EPSILON); 587 fdError = fdxOuter - fdxLeftEdge + FIXED_ONE; 588 idxOuter = FixedToInt(fdxOuter); 589 dxOuter = (GLfloat) idxOuter; 590 span.y = FixedToInt(fsy); 591 592 /* silence warnings on some compilers */ 593 (void) dxOuter; 594 (void) adjx; 595 (void) adjy; 596 (void) vLower; 597 598#ifdef PIXEL_ADDRESS 599 { 600 pRow = (PIXEL_TYPE *) PIXEL_ADDRESS(FixedToInt(fxLeftEdge), span.y); 601 dPRowOuter = -((int)BYTES_PER_ROW) + idxOuter * sizeof(PIXEL_TYPE); 602 /* negative because Y=0 at bottom and increases upward */ 603 } 604#endif 605 /* 606 * Now we need the set of parameter (z, color, etc.) values at 607 * the point (fx, fsy). This gives us properly-sampled parameter 608 * values that we can step from pixel to pixel. Furthermore, 609 * although we might have intermediate results that overflow 610 * the normal parameter range when we step temporarily outside 611 * the triangle, we shouldn't overflow or underflow for any 612 * pixel that's actually inside the triangle. 613 */ 614 615#ifdef INTERP_Z 616 { 617 GLfloat z0 = vLower->attrib[VARYING_SLOT_POS][2]; 618 if (depthBits <= 16) { 619 /* interpolate fixed-pt values */ 620 GLfloat tmp = (z0 * FIXED_SCALE 621 + span.attrStepX[VARYING_SLOT_POS][2] * adjx 622 + span.attrStepY[VARYING_SLOT_POS][2] * adjy) + FIXED_HALF; 623 if (tmp < MAX_GLUINT / 2) 624 zLeft = (GLfixed) tmp; 625 else 626 zLeft = MAX_GLUINT / 2; 627 fdzOuter = SignedFloatToFixed(span.attrStepY[VARYING_SLOT_POS][2] + 628 dxOuter * span.attrStepX[VARYING_SLOT_POS][2]); 629 } 630 else { 631 /* interpolate depth values w/out scaling */ 632 zLeft = (GLuint) (z0 + span.attrStepX[VARYING_SLOT_POS][2] * FixedToFloat(adjx) 633 + span.attrStepY[VARYING_SLOT_POS][2] * FixedToFloat(adjy)); 634 fdzOuter = (GLint) (span.attrStepY[VARYING_SLOT_POS][2] + 635 dxOuter * span.attrStepX[VARYING_SLOT_POS][2]); 636 } 637# ifdef DEPTH_TYPE 638 zRow = (DEPTH_TYPE *) 639 _swrast_pixel_address(zrb, FixedToInt(fxLeftEdge), span.y); 640 dZRowOuter = (ctx->DrawBuffer->Width + idxOuter) * sizeof(DEPTH_TYPE); 641# endif 642 } 643#endif 644#ifdef INTERP_RGB 645 if (ctx->Light.ShadeModel == GL_SMOOTH) { 646 rLeft = (GLint)(ChanToFixed(vLower->color[RCOMP]) 647 + span.attrStepX[VARYING_SLOT_COL0][0] * adjx 648 + span.attrStepY[VARYING_SLOT_COL0][0] * adjy) + FIXED_HALF; 649 gLeft = (GLint)(ChanToFixed(vLower->color[GCOMP]) 650 + span.attrStepX[VARYING_SLOT_COL0][1] * adjx 651 + span.attrStepY[VARYING_SLOT_COL0][1] * adjy) + FIXED_HALF; 652 bLeft = (GLint)(ChanToFixed(vLower->color[BCOMP]) 653 + span.attrStepX[VARYING_SLOT_COL0][2] * adjx 654 + span.attrStepY[VARYING_SLOT_COL0][2] * adjy) + FIXED_HALF; 655 fdrOuter = SignedFloatToFixed(span.attrStepY[VARYING_SLOT_COL0][0] 656 + dxOuter * span.attrStepX[VARYING_SLOT_COL0][0]); 657 fdgOuter = SignedFloatToFixed(span.attrStepY[VARYING_SLOT_COL0][1] 658 + dxOuter * span.attrStepX[VARYING_SLOT_COL0][1]); 659 fdbOuter = SignedFloatToFixed(span.attrStepY[VARYING_SLOT_COL0][2] 660 + dxOuter * span.attrStepX[VARYING_SLOT_COL0][2]); 661# ifdef INTERP_ALPHA 662 aLeft = (GLint)(ChanToFixed(vLower->color[ACOMP]) 663 + span.attrStepX[VARYING_SLOT_COL0][3] * adjx 664 + span.attrStepY[VARYING_SLOT_COL0][3] * adjy) + FIXED_HALF; 665 fdaOuter = SignedFloatToFixed(span.attrStepY[VARYING_SLOT_COL0][3] 666 + dxOuter * span.attrStepX[VARYING_SLOT_COL0][3]); 667# endif 668 } 669 else { 670 assert(ctx->Light.ShadeModel == GL_FLAT); 671 rLeft = ChanToFixed(v2->color[RCOMP]); 672 gLeft = ChanToFixed(v2->color[GCOMP]); 673 bLeft = ChanToFixed(v2->color[BCOMP]); 674 fdrOuter = fdgOuter = fdbOuter = 0; 675# ifdef INTERP_ALPHA 676 aLeft = ChanToFixed(v2->color[ACOMP]); 677 fdaOuter = 0; 678# endif 679 } 680#endif /* INTERP_RGB */ 681 682 683#ifdef INTERP_INT_TEX 684 { 685 GLfloat s0, t0; 686 s0 = vLower->attrib[VARYING_SLOT_TEX0][0] * S_SCALE; 687 sLeft = (GLfixed)(s0 * FIXED_SCALE + span.attrStepX[VARYING_SLOT_TEX0][0] * adjx 688 + span.attrStepY[VARYING_SLOT_TEX0][0] * adjy) + FIXED_HALF; 689 dsOuter = SignedFloatToFixed(span.attrStepY[VARYING_SLOT_TEX0][0] 690 + dxOuter * span.attrStepX[VARYING_SLOT_TEX0][0]); 691 692 t0 = vLower->attrib[VARYING_SLOT_TEX0][1] * T_SCALE; 693 tLeft = (GLfixed)(t0 * FIXED_SCALE + span.attrStepX[VARYING_SLOT_TEX0][1] * adjx 694 + span.attrStepY[VARYING_SLOT_TEX0][1] * adjy) + FIXED_HALF; 695 dtOuter = SignedFloatToFixed(span.attrStepY[VARYING_SLOT_TEX0][1] 696 + dxOuter * span.attrStepX[VARYING_SLOT_TEX0][1]); 697 } 698#endif 699#ifdef INTERP_ATTRIBS 700 { 701 const GLuint attr = VARYING_SLOT_POS; 702 wLeft = vLower->attrib[VARYING_SLOT_POS][3] 703 + (span.attrStepX[attr][3] * adjx 704 + span.attrStepY[attr][3] * adjy) * (1.0F/FIXED_SCALE); 705 dwOuter = span.attrStepY[attr][3] + dxOuter * span.attrStepX[attr][3]; 706 } 707 ATTRIB_LOOP_BEGIN 708 const GLfloat invW = vLower->attrib[VARYING_SLOT_POS][3]; 709 if (swrast->_InterpMode[attr] == GL_FLAT) { 710 GLuint c; 711 for (c = 0; c < 4; c++) { 712 attrLeft[attr][c] = v2->attrib[attr][c] * invW; 713 daOuter[attr][c] = 0.0; 714 } 715 } 716 else { 717 GLuint c; 718 for (c = 0; c < 4; c++) { 719 const GLfloat a = vLower->attrib[attr][c] * invW; 720 attrLeft[attr][c] = a + ( span.attrStepX[attr][c] * adjx 721 + span.attrStepY[attr][c] * adjy) * (1.0F/FIXED_SCALE); 722 daOuter[attr][c] = span.attrStepY[attr][c] + dxOuter * span.attrStepX[attr][c]; 723 } 724 } 725 ATTRIB_LOOP_END 726#endif 727 } /*if setupLeft*/ 728 729 730 if (setupRight && eRight->lines>0) { 731 fxRightEdge = eRight->fsx - FIXED_EPSILON; 732 fdxRightEdge = eRight->fdxdy; 733 } 734 735 if (lines==0) { 736 continue; 737 } 738 739 740 /* Rasterize setup */ 741#ifdef PIXEL_ADDRESS 742 dPRowInner = dPRowOuter + sizeof(PIXEL_TYPE); 743#endif 744#ifdef INTERP_Z 745# ifdef DEPTH_TYPE 746 dZRowInner = dZRowOuter + sizeof(DEPTH_TYPE); 747# endif 748 fdzInner = fdzOuter + span.zStep; 749#endif 750#ifdef INTERP_RGB 751 fdrInner = fdrOuter + span.redStep; 752 fdgInner = fdgOuter + span.greenStep; 753 fdbInner = fdbOuter + span.blueStep; 754#endif 755#ifdef INTERP_ALPHA 756 fdaInner = fdaOuter + span.alphaStep; 757#endif 758#ifdef INTERP_INT_TEX 759 dsInner = dsOuter + span.intTexStep[0]; 760 dtInner = dtOuter + span.intTexStep[1]; 761#endif 762#ifdef INTERP_ATTRIBS 763 dwInner = dwOuter + span.attrStepX[VARYING_SLOT_POS][3]; 764 ATTRIB_LOOP_BEGIN 765 GLuint c; 766 for (c = 0; c < 4; c++) { 767 daInner[attr][c] = daOuter[attr][c] + span.attrStepX[attr][c]; 768 } 769 ATTRIB_LOOP_END 770#endif 771 772 while (lines > 0) { 773 /* initialize the span interpolants to the leftmost value */ 774 /* ff = fixed-pt fragment */ 775 const GLint right = FixedToInt(fxRightEdge); 776 span.x = FixedToInt(fxLeftEdge); 777 if (right <= span.x) 778 span.end = 0; 779 else 780 span.end = right - span.x; 781 782#ifdef INTERP_Z 783 span.z = zLeft; 784#endif 785#ifdef INTERP_RGB 786 span.red = rLeft; 787 span.green = gLeft; 788 span.blue = bLeft; 789#endif 790#ifdef INTERP_ALPHA 791 span.alpha = aLeft; 792#endif 793#ifdef INTERP_INT_TEX 794 span.intTex[0] = sLeft; 795 span.intTex[1] = tLeft; 796#endif 797 798#ifdef INTERP_ATTRIBS 799 span.attrStart[VARYING_SLOT_POS][3] = wLeft; 800 ATTRIB_LOOP_BEGIN 801 GLuint c; 802 for (c = 0; c < 4; c++) { 803 span.attrStart[attr][c] = attrLeft[attr][c]; 804 } 805 ATTRIB_LOOP_END 806#endif 807 808 /* This is where we actually generate fragments */ 809 /* XXX the test for span.y > 0 _shouldn't_ be needed but 810 * it fixes a problem on 64-bit Opterons (bug 4842). 811 */ 812 if (span.end > 0 && span.y >= 0) { 813 const GLint len = span.end - 1; 814 (void) len; 815#ifdef INTERP_RGB 816 CLAMP_INTERPOLANT(red, redStep, len); 817 CLAMP_INTERPOLANT(green, greenStep, len); 818 CLAMP_INTERPOLANT(blue, blueStep, len); 819#endif 820#ifdef INTERP_ALPHA 821 CLAMP_INTERPOLANT(alpha, alphaStep, len); 822#endif 823 { 824 RENDER_SPAN( span ); 825 } 826 } 827 828 /* 829 * Advance to the next scan line. Compute the 830 * new edge coordinates, and adjust the 831 * pixel-center x coordinate so that it stays 832 * on or inside the major edge. 833 */ 834 span.y++; 835 lines--; 836 837 fxLeftEdge += fdxLeftEdge; 838 fxRightEdge += fdxRightEdge; 839 840 fError += fdError; 841 if (fError >= 0) { 842 fError -= FIXED_ONE; 843 844#ifdef PIXEL_ADDRESS 845 pRow = (PIXEL_TYPE *) ((GLubyte *) pRow + dPRowOuter); 846#endif 847#ifdef INTERP_Z 848# ifdef DEPTH_TYPE 849 zRow = (DEPTH_TYPE *) ((GLubyte *) zRow + dZRowOuter); 850# endif 851 zLeft += fdzOuter; 852#endif 853#ifdef INTERP_RGB 854 rLeft += fdrOuter; 855 gLeft += fdgOuter; 856 bLeft += fdbOuter; 857#endif 858#ifdef INTERP_ALPHA 859 aLeft += fdaOuter; 860#endif 861#ifdef INTERP_INT_TEX 862 sLeft += dsOuter; 863 tLeft += dtOuter; 864#endif 865#ifdef INTERP_ATTRIBS 866 wLeft += dwOuter; 867 ATTRIB_LOOP_BEGIN 868 GLuint c; 869 for (c = 0; c < 4; c++) { 870 attrLeft[attr][c] += daOuter[attr][c]; 871 } 872 ATTRIB_LOOP_END 873#endif 874 } 875 else { 876#ifdef PIXEL_ADDRESS 877 pRow = (PIXEL_TYPE *) ((GLubyte *) pRow + dPRowInner); 878#endif 879#ifdef INTERP_Z 880# ifdef DEPTH_TYPE 881 zRow = (DEPTH_TYPE *) ((GLubyte *) zRow + dZRowInner); 882# endif 883 zLeft += fdzInner; 884#endif 885#ifdef INTERP_RGB 886 rLeft += fdrInner; 887 gLeft += fdgInner; 888 bLeft += fdbInner; 889#endif 890#ifdef INTERP_ALPHA 891 aLeft += fdaInner; 892#endif 893#ifdef INTERP_INT_TEX 894 sLeft += dsInner; 895 tLeft += dtInner; 896#endif 897#ifdef INTERP_ATTRIBS 898 wLeft += dwInner; 899 ATTRIB_LOOP_BEGIN 900 GLuint c; 901 for (c = 0; c < 4; c++) { 902 attrLeft[attr][c] += daInner[attr][c]; 903 } 904 ATTRIB_LOOP_END 905#endif 906 } 907 } /*while lines>0*/ 908 909 } /* for subTriangle */ 910 911 } 912 } 913} 914 915#undef SETUP_CODE 916#undef RENDER_SPAN 917 918#undef PIXEL_TYPE 919#undef BYTES_PER_ROW 920#undef PIXEL_ADDRESS 921#undef DEPTH_TYPE 922 923#undef INTERP_Z 924#undef INTERP_RGB 925#undef INTERP_ALPHA 926#undef INTERP_INT_TEX 927#undef INTERP_ATTRIBS 928 929#undef S_SCALE 930#undef T_SCALE 931 932#undef FixedToDepth 933 934#undef NAME 935