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