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