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) \
104 do { \
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
NAME(struct gl_context * ctx,const SWvertex * v0,const SWvertex * v1,const SWvertex * v2)116 static 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