5e53b4050e8a7b31e6095fdcfdcffdddba6fd39e
1 /**************************************************************************
3 * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas.
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 **************************************************************************/
29 * Binning code for triangles
32 #include "lp_setup_context.h"
34 #include "util/u_math.h"
35 #include "util/u_memory.h"
37 #define NUM_CHANNELS 4
40 * Compute a0 for a constant-valued coefficient (GL_FLAT shading).
42 static void constant_coef( struct lp_rast_triangle
*tri
,
47 tri
->inputs
.a0
[slot
][i
] = value
;
48 tri
->inputs
.dadx
[slot
][i
] = 0;
49 tri
->inputs
.dady
[slot
][i
] = 0;
53 * Compute a0, dadx and dady for a linearly interpolated coefficient,
56 static void linear_coef( struct lp_rast_triangle
*tri
,
65 float a1
= v1
[vert_attr
][i
];
66 float a2
= v2
[vert_attr
][i
];
67 float a3
= v3
[vert_attr
][i
];
71 float dadx
= (da12
* tri
->dy31
- tri
->dy12
* da31
) * oneoverarea
;
72 float dady
= (da31
* tri
->dx12
- tri
->dx31
* da12
) * oneoverarea
;
74 tri
->inputs
.dadx
[slot
][i
] = dadx
;
75 tri
->inputs
.dady
[slot
][i
] = dady
;
77 /* calculate a0 as the value which would be sampled for the
78 * fragment at (0,0), taking into account that we want to sample at
79 * pixel centers, in other words (0.5, 0.5).
81 * this is neat but unfortunately not a good way to do things for
82 * triangles with very large values of dadx or dady as it will
83 * result in the subtraction and re-addition from a0 of a very
84 * large number, which means we'll end up loosing a lot of the
85 * fractional bits and precision from a0. the way to fix this is
86 * to define a0 as the sample at a pixel center somewhere near vmin
87 * instead - i'll switch to this later.
89 tri
->inputs
.a0
[slot
][i
] = (v1
[vert_attr
][i
] -
90 (dadx
* (v1
[0][0] - 0.5f
) +
91 dady
* (v1
[0][1] - 0.5f
)));
96 * Compute a0, dadx and dady for a perspective-corrected interpolant,
98 * We basically multiply the vertex value by 1/w before computing
99 * the plane coefficients (a0, dadx, dady).
100 * Later, when we compute the value at a particular fragment position we'll
101 * divide the interpolated value by the interpolated W at that fragment.
103 static void perspective_coef( struct lp_rast_triangle
*tri
,
106 const float (*v1
)[4],
107 const float (*v2
)[4],
108 const float (*v3
)[4],
112 /* premultiply by 1/w (v[0][3] is always 1/w):
114 float a1
= v1
[vert_attr
][i
] * v1
[0][3];
115 float a2
= v2
[vert_attr
][i
] * v2
[0][3];
116 float a3
= v3
[vert_attr
][i
] * v3
[0][3];
117 float da12
= a1
- a2
;
118 float da31
= a3
- a1
;
119 float dadx
= (da12
* tri
->dy31
- tri
->dy12
* da31
) * oneoverarea
;
120 float dady
= (da31
* tri
->dx12
- tri
->dx31
* da12
) * oneoverarea
;
122 tri
->inputs
.dadx
[slot
][i
] = dadx
;
123 tri
->inputs
.dady
[slot
][i
] = dady
;
124 tri
->inputs
.a0
[slot
][i
] = (a1
-
125 (dadx
* (v1
[0][0] - 0.5f
) +
126 dady
* (v1
[0][1] - 0.5f
)));
131 * Special coefficient setup for gl_FragCoord.
132 * X and Y are trivial, though Y has to be inverted for OpenGL.
133 * Z and W are copied from position_coef which should have already been computed.
134 * We could do a bit less work if we'd examine gl_FragCoord's swizzle mask.
137 setup_fragcoord_coef(struct lp_rast_triangle
*tri
,
140 const float (*v1
)[4],
141 const float (*v2
)[4],
142 const float (*v3
)[4])
145 tri
->inputs
.a0
[slot
][0] = 0.0;
146 tri
->inputs
.dadx
[slot
][0] = 1.0;
147 tri
->inputs
.dady
[slot
][0] = 0.0;
149 tri
->inputs
.a0
[slot
][1] = 0.0;
150 tri
->inputs
.dadx
[slot
][1] = 0.0;
151 tri
->inputs
.dady
[slot
][1] = 1.0;
153 linear_coef(tri
, oneoverarea
, slot
, v1
, v2
, v3
, 0, 2);
155 linear_coef(tri
, oneoverarea
, slot
, v1
, v2
, v3
, 0, 3);
159 static void setup_facing_coef( struct lp_rast_triangle
*tri
,
163 constant_coef( tri
, slot
, 1.0f
- frontface
, 0 );
164 constant_coef( tri
, slot
, 0.0f
, 1 ); /* wasted */
165 constant_coef( tri
, slot
, 0.0f
, 2 ); /* wasted */
166 constant_coef( tri
, slot
, 0.0f
, 3 ); /* wasted */
171 * Compute the tri->coef[] array dadx, dady, a0 values.
173 static void setup_tri_coefficients( struct setup_context
*setup
,
174 struct lp_rast_triangle
*tri
,
176 const float (*v1
)[4],
177 const float (*v2
)[4],
178 const float (*v3
)[4],
183 /* Allocate space for the a0, dadx and dady arrays
187 bytes
= (setup
->fs
.nr_inputs
+ 1) * 4 * sizeof(float);
188 tri
->inputs
.a0
= lp_bin_alloc_aligned( &setup
->data
, bytes
, 16 );
189 tri
->inputs
.dadx
= lp_bin_alloc_aligned( &setup
->data
, bytes
, 16 );
190 tri
->inputs
.dady
= lp_bin_alloc_aligned( &setup
->data
, bytes
, 16 );
193 /* The internal position input is in slot zero:
195 setup_fragcoord_coef(tri
, oneoverarea
, 0, v1
, v2
, v3
);
197 /* setup interpolation for all the remaining attributes:
199 for (slot
= 0; slot
< setup
->fs
.nr_inputs
; slot
++) {
200 unsigned vert_attr
= setup
->fs
.input
[slot
].src_index
;
203 switch (setup
->fs
.input
[slot
].interp
) {
204 case LP_INTERP_CONSTANT
:
205 for (i
= 0; i
< NUM_CHANNELS
; i
++)
206 constant_coef(tri
, slot
+1, v3
[vert_attr
][i
], i
);
209 case LP_INTERP_LINEAR
:
210 for (i
= 0; i
< NUM_CHANNELS
; i
++)
211 linear_coef(tri
, oneoverarea
, slot
+1, v1
, v2
, v3
, vert_attr
, i
);
214 case LP_INTERP_PERSPECTIVE
:
215 for (i
= 0; i
< NUM_CHANNELS
; i
++)
216 perspective_coef(tri
, oneoverarea
, slot
+1, v1
, v2
, v3
, vert_attr
, i
);
219 case LP_INTERP_POSITION
:
220 /* XXX: fix me - duplicates the values in slot zero.
222 setup_fragcoord_coef(tri
, oneoverarea
, slot
+1, v1
, v2
, v3
);
225 case LP_INTERP_FACING
:
226 setup_facing_coef(tri
, slot
+1, frontface
);
237 static inline int subpixel_snap( float a
)
239 return util_iround(FIXED_ONE
* a
);
243 #define MIN3(a,b,c) MIN2(MIN2(a,b),c)
244 #define MAX3(a,b,c) MAX2(MAX2(a,b),c)
247 * Do basic setup for triangle rasterization and determine which
248 * framebuffer tiles are touched. Put the triangle in the bins for the
249 * tiles which we overlap.
252 do_triangle_ccw(struct setup_context
*setup
,
253 const float (*v1
)[4],
254 const float (*v2
)[4],
255 const float (*v3
)[4],
256 boolean frontfacing
)
258 /* x/y positions in fixed point */
259 const int x1
= subpixel_snap(v1
[0][0]);
260 const int x2
= subpixel_snap(v2
[0][0]);
261 const int x3
= subpixel_snap(v3
[0][0]);
262 const int y1
= subpixel_snap(v1
[0][1]);
263 const int y2
= subpixel_snap(v2
[0][1]);
264 const int y3
= subpixel_snap(v3
[0][1]);
266 struct lp_rast_triangle
*tri
= lp_bin_alloc( &setup
->data
, sizeof *tri
);
267 float area
, oneoverarea
;
268 int minx
, maxx
, miny
, maxy
;
278 area
= (tri
->dx12
* tri
->dy31
-
279 tri
->dx31
* tri
->dy12
);
281 /* Cull non-ccw and zero-sized triangles.
283 * XXX: subject to overflow??
286 lp_bin_putback_data( &setup
->data
, sizeof *tri
);
290 /* Bounding rectangle (in pixels) */
291 tri
->minx
= (MIN3(x1
, x2
, x3
) + 0xf) >> FIXED_ORDER
;
292 tri
->maxx
= (MAX3(x1
, x2
, x3
) + 0xf) >> FIXED_ORDER
;
293 tri
->miny
= (MIN3(y1
, y2
, y3
) + 0xf) >> FIXED_ORDER
;
294 tri
->maxy
= (MAX3(y1
, y2
, y3
) + 0xf) >> FIXED_ORDER
;
296 if (tri
->miny
== tri
->maxy
||
297 tri
->minx
== tri
->maxx
) {
298 lp_bin_putback_data( &setup
->data
, sizeof *tri
);
304 oneoverarea
= ((float)FIXED_ONE
) / (float)area
;
306 /* Setup parameter interpolants:
308 setup_tri_coefficients( setup
, tri
, oneoverarea
, v1
, v2
, v3
, frontfacing
);
310 /* half-edge constants, will be interated over the whole
313 tri
->c1
= tri
->dy12
* x1
- tri
->dx12
* y1
;
314 tri
->c2
= tri
->dy23
* x2
- tri
->dx23
* y2
;
315 tri
->c3
= tri
->dy31
* x3
- tri
->dx31
* y3
;
317 /* correct for top-left fill convention:
319 if (tri
->dy12
< 0 || (tri
->dy12
== 0 && tri
->dx12
> 0)) tri
->c1
++;
320 if (tri
->dy23
< 0 || (tri
->dy23
== 0 && tri
->dx23
> 0)) tri
->c2
++;
321 if (tri
->dy31
< 0 || (tri
->dy31
== 0 && tri
->dx31
> 0)) tri
->c3
++;
323 tri
->dy12
*= FIXED_ONE
;
324 tri
->dy23
*= FIXED_ONE
;
325 tri
->dy31
*= FIXED_ONE
;
327 tri
->dx12
*= FIXED_ONE
;
328 tri
->dx23
*= FIXED_ONE
;
329 tri
->dx31
*= FIXED_ONE
;
331 /* find trivial reject offsets for each edge for a single-pixel
332 * sized block. These will be scaled up at each recursive level to
333 * match the active blocksize. Scaling in this way works best if
334 * the blocks are square.
337 if (tri
->dy12
< 0) tri
->eo1
-= tri
->dy12
;
338 if (tri
->dx12
> 0) tri
->eo1
+= tri
->dx12
;
341 if (tri
->dy23
< 0) tri
->eo2
-= tri
->dy23
;
342 if (tri
->dx23
> 0) tri
->eo2
+= tri
->dx23
;
345 if (tri
->dy31
< 0) tri
->eo3
-= tri
->dy31
;
346 if (tri
->dx31
> 0) tri
->eo3
+= tri
->dx31
;
348 /* Calculate trivial accept offsets from the above.
350 tri
->ei1
= tri
->dx12
- tri
->dy12
- tri
->eo1
;
351 tri
->ei2
= tri
->dx23
- tri
->dy23
- tri
->eo2
;
352 tri
->ei3
= tri
->dx31
- tri
->dy31
- tri
->eo3
;
355 int xstep1
= -tri
->dy12
;
356 int xstep2
= -tri
->dy23
;
357 int xstep3
= -tri
->dy31
;
359 int ystep1
= tri
->dx12
;
360 int ystep2
= tri
->dx23
;
361 int ystep3
= tri
->dx31
;
370 for (iy
= 0; iy
< 4; iy
++) {
375 for (ix
= 0; ix
< 4; ix
++, i
++) {
376 tri
->step
[0][i
] = cx1
;
377 tri
->step
[1][i
] = cx2
;
378 tri
->step
[2][i
] = cx3
;
391 * All fields of 'tri' are now set. The remaining code here is
392 * concerned with binning.
395 /* Convert to tile coordinates:
397 minx
= tri
->minx
/ TILE_SIZE
;
398 miny
= tri
->miny
/ TILE_SIZE
;
399 maxx
= tri
->maxx
/ TILE_SIZE
;
400 maxy
= tri
->maxy
/ TILE_SIZE
;
402 /* Determine which tile(s) intersect the triangle's bounding box
404 if (miny
== maxy
&& minx
== maxx
)
406 /* Triangle is contained in a single tile:
408 lp_bin_command( &setup
->tile
[minx
][miny
], lp_rast_triangle
,
409 lp_rast_arg_triangle(tri
) );
414 tri
->dx12
* miny
* TILE_SIZE
-
415 tri
->dy12
* minx
* TILE_SIZE
);
417 tri
->dx23
* miny
* TILE_SIZE
-
418 tri
->dy23
* minx
* TILE_SIZE
);
420 tri
->dx31
* miny
* TILE_SIZE
-
421 tri
->dy31
* minx
* TILE_SIZE
);
423 int ei1
= tri
->ei1
<< TILE_ORDER
;
424 int ei2
= tri
->ei2
<< TILE_ORDER
;
425 int ei3
= tri
->ei3
<< TILE_ORDER
;
427 int eo1
= tri
->eo1
<< TILE_ORDER
;
428 int eo2
= tri
->eo2
<< TILE_ORDER
;
429 int eo3
= tri
->eo3
<< TILE_ORDER
;
431 int xstep1
= -(tri
->dy12
<< TILE_ORDER
);
432 int xstep2
= -(tri
->dy23
<< TILE_ORDER
);
433 int xstep3
= -(tri
->dy31
<< TILE_ORDER
);
435 int ystep1
= tri
->dx12
<< TILE_ORDER
;
436 int ystep2
= tri
->dx23
<< TILE_ORDER
;
437 int ystep3
= tri
->dx31
<< TILE_ORDER
;
441 /* Trivially accept or reject blocks, else jump to per-pixel
444 for (y
= miny
; y
<= maxy
; y
++)
451 for (x
= minx
; x
<= maxx
; x
++)
461 else if (cx1
+ ei1
> 0 &&
466 /* triangle covers the whole tile- shade whole tile */
467 lp_bin_command( &setup
->tile
[x
][y
],
469 lp_rast_arg_inputs(&tri
->inputs
) );
474 /* shade partial tile */
475 lp_bin_command( &setup
->tile
[x
][y
],
477 lp_rast_arg_triangle(tri
) );
480 /* Iterate cx values across the region:
487 /* Iterate c values down the region:
496 static void triangle_cw( struct setup_context
*setup
,
497 const float (*v0
)[4],
498 const float (*v1
)[4],
499 const float (*v2
)[4] )
501 do_triangle_ccw( setup
, v1
, v0
, v2
, !setup
->ccw_is_frontface
);
504 static void triangle_ccw( struct setup_context
*setup
,
505 const float (*v0
)[4],
506 const float (*v1
)[4],
507 const float (*v2
)[4] )
509 do_triangle_ccw( setup
, v0
, v1
, v2
, setup
->ccw_is_frontface
);
512 static void triangle_both( struct setup_context
*setup
,
513 const float (*v0
)[4],
514 const float (*v1
)[4],
515 const float (*v2
)[4] )
517 /* edge vectors e = v0 - v2, f = v1 - v2 */
518 const float ex
= v0
[0][0] - v2
[0][0];
519 const float ey
= v0
[0][1] - v2
[0][1];
520 const float fx
= v1
[0][0] - v2
[0][0];
521 const float fy
= v1
[0][1] - v2
[0][1];
523 /* det = cross(e,f).z */
524 if (ex
* fy
- ey
* fx
< 0)
525 triangle_ccw( setup
, v0
, v1
, v2
);
527 triangle_cw( setup
, v0
, v1
, v2
);
530 static void triangle_nop( struct setup_context
*setup
,
531 const float (*v0
)[4],
532 const float (*v1
)[4],
533 const float (*v2
)[4] )
539 lp_setup_choose_triangle( struct setup_context
*setup
)
541 switch (setup
->cullmode
) {
542 case PIPE_WINDING_NONE
:
543 setup
->triangle
= triangle_both
;
545 case PIPE_WINDING_CCW
:
546 setup
->triangle
= triangle_cw
;
548 case PIPE_WINDING_CW
:
549 setup
->triangle
= triangle_ccw
;
552 setup
->triangle
= triangle_nop
;