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 "util/u_math.h"
33 #include "util/u_memory.h"
35 #include "lp_setup_context.h"
37 #include "lp_state_fs.h"
39 #define NUM_CHANNELS 4
43 * Compute a0 for a constant-valued coefficient (GL_FLAT shading).
45 static void constant_coef( struct lp_setup_context
*setup
,
46 struct lp_rast_triangle
*tri
,
51 tri
->inputs
.a0
[slot
][i
] = value
;
52 tri
->inputs
.dadx
[slot
][i
] = 0.0f
;
53 tri
->inputs
.dady
[slot
][i
] = 0.0f
;
58 * Compute a0, dadx and dady for a linearly interpolated coefficient,
61 static void linear_coef( struct lp_setup_context
*setup
,
62 struct lp_rast_triangle
*tri
,
71 float a1
= v1
[vert_attr
][i
];
72 float a2
= v2
[vert_attr
][i
];
73 float a3
= v3
[vert_attr
][i
];
77 float dadx
= (da12
* tri
->dy31
- tri
->dy12
* da31
) * oneoverarea
;
78 float dady
= (da31
* tri
->dx12
- tri
->dx31
* da12
) * oneoverarea
;
80 tri
->inputs
.dadx
[slot
][i
] = dadx
;
81 tri
->inputs
.dady
[slot
][i
] = dady
;
83 /* calculate a0 as the value which would be sampled for the
84 * fragment at (0,0), taking into account that we want to sample at
85 * pixel centers, in other words (0.5, 0.5).
87 * this is neat but unfortunately not a good way to do things for
88 * triangles with very large values of dadx or dady as it will
89 * result in the subtraction and re-addition from a0 of a very
90 * large number, which means we'll end up loosing a lot of the
91 * fractional bits and precision from a0. the way to fix this is
92 * to define a0 as the sample at a pixel center somewhere near vmin
93 * instead - i'll switch to this later.
95 tri
->inputs
.a0
[slot
][i
] = (a1
-
96 (dadx
* (v1
[0][0] - setup
->pixel_offset
) +
97 dady
* (v1
[0][1] - setup
->pixel_offset
)));
102 * Compute a0, dadx and dady for a perspective-corrected interpolant,
104 * We basically multiply the vertex value by 1/w before computing
105 * the plane coefficients (a0, dadx, dady).
106 * Later, when we compute the value at a particular fragment position we'll
107 * divide the interpolated value by the interpolated W at that fragment.
109 static void perspective_coef( struct lp_setup_context
*setup
,
110 struct lp_rast_triangle
*tri
,
113 const float (*v1
)[4],
114 const float (*v2
)[4],
115 const float (*v3
)[4],
119 /* premultiply by 1/w (v[0][3] is always 1/w):
121 float a1
= v1
[vert_attr
][i
] * v1
[0][3];
122 float a2
= v2
[vert_attr
][i
] * v2
[0][3];
123 float a3
= v3
[vert_attr
][i
] * v3
[0][3];
124 float da12
= a1
- a2
;
125 float da31
= a3
- a1
;
126 float dadx
= (da12
* tri
->dy31
- tri
->dy12
* da31
) * oneoverarea
;
127 float dady
= (da31
* tri
->dx12
- tri
->dx31
* da12
) * oneoverarea
;
129 tri
->inputs
.dadx
[slot
][i
] = dadx
;
130 tri
->inputs
.dady
[slot
][i
] = dady
;
131 tri
->inputs
.a0
[slot
][i
] = (a1
-
132 (dadx
* (v1
[0][0] - setup
->pixel_offset
) +
133 dady
* (v1
[0][1] - setup
->pixel_offset
)));
138 * Special coefficient setup for gl_FragCoord.
139 * X and Y are trivial
140 * Z and W are copied from position_coef which should have already been computed.
141 * We could do a bit less work if we'd examine gl_FragCoord's swizzle mask.
144 setup_fragcoord_coef(struct lp_setup_context
*setup
,
145 struct lp_rast_triangle
*tri
,
148 const float (*v1
)[4],
149 const float (*v2
)[4],
150 const float (*v3
)[4],
154 if (usage_mask
& TGSI_WRITEMASK_X
) {
155 tri
->inputs
.a0
[slot
][0] = 0.0;
156 tri
->inputs
.dadx
[slot
][0] = 1.0;
157 tri
->inputs
.dady
[slot
][0] = 0.0;
161 if (usage_mask
& TGSI_WRITEMASK_Y
) {
162 tri
->inputs
.a0
[slot
][1] = 0.0;
163 tri
->inputs
.dadx
[slot
][1] = 0.0;
164 tri
->inputs
.dady
[slot
][1] = 1.0;
168 if (usage_mask
& TGSI_WRITEMASK_Z
) {
169 linear_coef(setup
, tri
, oneoverarea
, slot
, v1
, v2
, v3
, 0, 2);
173 if (usage_mask
& TGSI_WRITEMASK_W
) {
174 linear_coef(setup
, tri
, oneoverarea
, slot
, v1
, v2
, v3
, 0, 3);
180 * Setup the fragment input attribute with the front-facing value.
181 * \param frontface is the triangle front facing?
183 static void setup_facing_coef( struct lp_setup_context
*setup
,
184 struct lp_rast_triangle
*tri
,
189 /* convert TRUE to 1.0 and FALSE to -1.0 */
190 if (usage_mask
& TGSI_WRITEMASK_X
)
191 constant_coef( setup
, tri
, slot
, 2.0f
* frontface
- 1.0f
, 0 );
193 if (usage_mask
& TGSI_WRITEMASK_Y
)
194 constant_coef( setup
, tri
, slot
, 0.0f
, 1 ); /* wasted */
196 if (usage_mask
& TGSI_WRITEMASK_Z
)
197 constant_coef( setup
, tri
, slot
, 0.0f
, 2 ); /* wasted */
199 if (usage_mask
& TGSI_WRITEMASK_W
)
200 constant_coef( setup
, tri
, slot
, 0.0f
, 3 ); /* wasted */
205 * Compute the tri->coef[] array dadx, dady, a0 values.
207 static void setup_tri_coefficients( struct lp_setup_context
*setup
,
208 struct lp_rast_triangle
*tri
,
210 const float (*v1
)[4],
211 const float (*v2
)[4],
212 const float (*v3
)[4],
215 unsigned fragcoord_usage_mask
= TGSI_WRITEMASK_XYZ
;
218 /* setup interpolation for all the remaining attributes:
220 for (slot
= 0; slot
< setup
->fs
.nr_inputs
; slot
++) {
221 unsigned vert_attr
= setup
->fs
.input
[slot
].src_index
;
222 unsigned usage_mask
= setup
->fs
.input
[slot
].usage_mask
;
225 switch (setup
->fs
.input
[slot
].interp
) {
226 case LP_INTERP_CONSTANT
:
227 if (setup
->flatshade_first
) {
228 for (i
= 0; i
< NUM_CHANNELS
; i
++)
229 if (usage_mask
& (1 << i
))
230 constant_coef(setup
, tri
, slot
+1, v1
[vert_attr
][i
], i
);
233 for (i
= 0; i
< NUM_CHANNELS
; i
++)
234 if (usage_mask
& (1 << i
))
235 constant_coef(setup
, tri
, slot
+1, v3
[vert_attr
][i
], i
);
239 case LP_INTERP_LINEAR
:
240 for (i
= 0; i
< NUM_CHANNELS
; i
++)
241 if (usage_mask
& (1 << i
))
242 linear_coef(setup
, tri
, oneoverarea
, slot
+1, v1
, v2
, v3
, vert_attr
, i
);
245 case LP_INTERP_PERSPECTIVE
:
246 for (i
= 0; i
< NUM_CHANNELS
; i
++)
247 if (usage_mask
& (1 << i
))
248 perspective_coef(setup
, tri
, oneoverarea
, slot
+1, v1
, v2
, v3
, vert_attr
, i
);
249 fragcoord_usage_mask
|= TGSI_WRITEMASK_W
;
252 case LP_INTERP_POSITION
:
254 * The generated pixel interpolators will pick up the coeffs from
255 * slot 0, so all need to ensure that the usage mask is covers all
258 fragcoord_usage_mask
|= usage_mask
;
261 case LP_INTERP_FACING
:
262 setup_facing_coef(setup
, tri
, slot
+1, frontface
, usage_mask
);
270 /* The internal position input is in slot zero:
272 setup_fragcoord_coef(setup
, tri
, oneoverarea
, 0, v1
, v2
, v3
,
273 fragcoord_usage_mask
);
278 static INLINE
int subpixel_snap( float a
)
280 return util_iround(FIXED_ONE
* a
- (FIXED_ONE
/ 2));
286 * Alloc space for a new triangle plus the input.a0/dadx/dady arrays
287 * immediately after it.
288 * The memory is allocated from the per-scene pool, not per-tile.
289 * \param tri_size returns number of bytes allocated
290 * \param nr_inputs number of fragment shader inputs
291 * \return pointer to triangle space
293 static INLINE
struct lp_rast_triangle
*
294 alloc_triangle(struct lp_scene
*scene
, unsigned nr_inputs
, unsigned *tri_size
)
296 unsigned input_array_sz
= NUM_CHANNELS
* (nr_inputs
+ 1) * sizeof(float);
297 struct lp_rast_triangle
*tri
;
301 assert(sizeof(*tri
) % 16 == 0);
303 bytes
= sizeof(*tri
) + (3 * input_array_sz
);
305 tri
= lp_scene_alloc_aligned( scene
, bytes
, 16 );
308 inputs
= (char *) (tri
+ 1);
309 tri
->inputs
.a0
= (float (*)[4]) inputs
;
310 tri
->inputs
.dadx
= (float (*)[4]) (inputs
+ input_array_sz
);
311 tri
->inputs
.dady
= (float (*)[4]) (inputs
+ 2 * input_array_sz
);
321 * Print triangle vertex attribs (for debug).
324 print_triangle(struct lp_setup_context
*setup
,
325 const float (*v1
)[4],
326 const float (*v2
)[4],
327 const float (*v3
)[4])
331 debug_printf("llvmpipe triangle\n");
332 for (i
= 0; i
< setup
->fs
.nr_inputs
; i
++) {
333 debug_printf(" v1[%d]: %f %f %f %f\n", i
,
334 v1
[i
][0], v1
[i
][1], v1
[i
][2], v1
[i
][3]);
336 for (i
= 0; i
< setup
->fs
.nr_inputs
; i
++) {
337 debug_printf(" v2[%d]: %f %f %f %f\n", i
,
338 v2
[i
][0], v2
[i
][1], v2
[i
][2], v2
[i
][3]);
340 for (i
= 0; i
< setup
->fs
.nr_inputs
; i
++) {
341 debug_printf(" v3[%d]: %f %f %f %f\n", i
,
342 v3
[i
][0], v3
[i
][1], v3
[i
][2], v3
[i
][3]);
348 * Do basic setup for triangle rasterization and determine which
349 * framebuffer tiles are touched. Put the triangle in the scene's
350 * bins for the tiles which we overlap.
353 do_triangle_ccw(struct lp_setup_context
*setup
,
354 const float (*v1
)[4],
355 const float (*v2
)[4],
356 const float (*v3
)[4],
357 boolean frontfacing
)
359 /* x/y positions in fixed point */
360 const int x1
= subpixel_snap(v1
[0][0] + 0.5 - setup
->pixel_offset
);
361 const int x2
= subpixel_snap(v2
[0][0] + 0.5 - setup
->pixel_offset
);
362 const int x3
= subpixel_snap(v3
[0][0] + 0.5 - setup
->pixel_offset
);
363 const int y1
= subpixel_snap(v1
[0][1] + 0.5 - setup
->pixel_offset
);
364 const int y2
= subpixel_snap(v2
[0][1] + 0.5 - setup
->pixel_offset
);
365 const int y3
= subpixel_snap(v3
[0][1] + 0.5 - setup
->pixel_offset
);
367 struct lp_scene
*scene
= lp_setup_get_current_scene(setup
);
368 struct lp_rast_triangle
*tri
;
371 int minx
, maxx
, miny
, maxy
;
375 print_triangle(setup
, v1
, v2
, v3
);
377 tri
= alloc_triangle(scene
, setup
->fs
.nr_inputs
, &tri_bytes
);
382 tri
->v
[0][0] = v1
[0][0];
383 tri
->v
[1][0] = v2
[0][0];
384 tri
->v
[2][0] = v3
[0][0];
385 tri
->v
[0][1] = v1
[0][1];
386 tri
->v
[1][1] = v2
[0][1];
387 tri
->v
[2][1] = v3
[0][1];
398 area
= (tri
->dx12
* tri
->dy31
- tri
->dx31
* tri
->dy12
);
402 /* Cull non-ccw and zero-sized triangles.
404 * XXX: subject to overflow??
407 lp_scene_putback_data( scene
, tri_bytes
);
408 LP_COUNT(nr_culled_tris
);
412 /* Bounding rectangle (in pixels) */
413 minx
= (MIN3(x1
, x2
, x3
) + (FIXED_ONE
-1)) >> FIXED_ORDER
;
414 maxx
= (MAX3(x1
, x2
, x3
) + (FIXED_ONE
-1)) >> FIXED_ORDER
;
415 miny
= (MIN3(y1
, y2
, y3
) + (FIXED_ONE
-1)) >> FIXED_ORDER
;
416 maxy
= (MAX3(y1
, y2
, y3
) + (FIXED_ONE
-1)) >> FIXED_ORDER
;
418 if (setup
->scissor_test
) {
419 minx
= MAX2(minx
, setup
->scissor
.current
.minx
);
420 maxx
= MIN2(maxx
, setup
->scissor
.current
.maxx
);
421 miny
= MAX2(miny
, setup
->scissor
.current
.miny
);
422 maxy
= MIN2(maxy
, setup
->scissor
.current
.maxy
);
427 lp_scene_putback_data( scene
, tri_bytes
);
428 LP_COUNT(nr_culled_tris
);
434 oneoverarea
= ((float)FIXED_ONE
) / (float)area
;
436 /* Setup parameter interpolants:
438 setup_tri_coefficients( setup
, tri
, oneoverarea
, v1
, v2
, v3
, frontfacing
);
440 tri
->inputs
.facing
= frontfacing
? 1.0F
: -1.0F
;
442 /* half-edge constants, will be interated over the whole render target.
444 tri
->c1
= tri
->dy12
* x1
- tri
->dx12
* y1
;
445 tri
->c2
= tri
->dy23
* x2
- tri
->dx23
* y2
;
446 tri
->c3
= tri
->dy31
* x3
- tri
->dx31
* y3
;
448 /* correct for top-left fill convention:
450 if (tri
->dy12
< 0 || (tri
->dy12
== 0 && tri
->dx12
> 0)) tri
->c1
++;
451 if (tri
->dy23
< 0 || (tri
->dy23
== 0 && tri
->dx23
> 0)) tri
->c2
++;
452 if (tri
->dy31
< 0 || (tri
->dy31
== 0 && tri
->dx31
> 0)) tri
->c3
++;
454 tri
->dy12
*= FIXED_ONE
;
455 tri
->dy23
*= FIXED_ONE
;
456 tri
->dy31
*= FIXED_ONE
;
458 tri
->dx12
*= FIXED_ONE
;
459 tri
->dx23
*= FIXED_ONE
;
460 tri
->dx31
*= FIXED_ONE
;
462 /* find trivial reject offsets for each edge for a single-pixel
463 * sized block. These will be scaled up at each recursive level to
464 * match the active blocksize. Scaling in this way works best if
465 * the blocks are square.
468 if (tri
->dy12
< 0) tri
->eo1
-= tri
->dy12
;
469 if (tri
->dx12
> 0) tri
->eo1
+= tri
->dx12
;
472 if (tri
->dy23
< 0) tri
->eo2
-= tri
->dy23
;
473 if (tri
->dx23
> 0) tri
->eo2
+= tri
->dx23
;
476 if (tri
->dy31
< 0) tri
->eo3
-= tri
->dy31
;
477 if (tri
->dx31
> 0) tri
->eo3
+= tri
->dx31
;
479 /* Calculate trivial accept offsets from the above.
481 tri
->ei1
= tri
->dx12
- tri
->dy12
- tri
->eo1
;
482 tri
->ei2
= tri
->dx23
- tri
->dy23
- tri
->eo2
;
483 tri
->ei3
= tri
->dx31
- tri
->dy31
- tri
->eo3
;
485 /* Fill in the inputs.step[][] arrays.
486 * We've manually unrolled some loops here.
489 const int xstep1
= -tri
->dy12
;
490 const int xstep2
= -tri
->dy23
;
491 const int xstep3
= -tri
->dy31
;
492 const int ystep1
= tri
->dx12
;
493 const int ystep2
= tri
->dx23
;
494 const int ystep3
= tri
->dx31
;
496 #define SETUP_STEP(i, x, y) \
498 tri->inputs.step[0][i] = x * xstep1 + y * ystep1; \
499 tri->inputs.step[1][i] = x * xstep2 + y * ystep2; \
500 tri->inputs.step[2][i] = x * xstep3 + y * ystep3; \
515 SETUP_STEP(10, 0, 3);
516 SETUP_STEP(11, 1, 3);
518 SETUP_STEP(12, 2, 2);
519 SETUP_STEP(13, 3, 2);
520 SETUP_STEP(14, 2, 3);
521 SETUP_STEP(15, 3, 3);
526 * All fields of 'tri' are now set. The remaining code here is
527 * concerned with binning.
530 /* Convert to tile coordinates:
532 minx
= minx
/ TILE_SIZE
;
533 miny
= miny
/ TILE_SIZE
;
534 maxx
= maxx
/ TILE_SIZE
;
535 maxy
= maxy
/ TILE_SIZE
;
538 * Clamp to framebuffer size
540 minx
= MAX2(minx
, 0);
541 miny
= MAX2(miny
, 0);
542 maxx
= MIN2(maxx
, scene
->tiles_x
- 1);
543 maxy
= MIN2(maxy
, scene
->tiles_y
- 1);
545 /* Determine which tile(s) intersect the triangle's bounding box
547 if (miny
== maxy
&& minx
== maxx
)
549 /* Triangle is contained in a single tile:
551 lp_scene_bin_command( scene
, minx
, miny
, lp_rast_triangle
,
552 lp_rast_arg_triangle(tri
) );
557 tri
->dx12
* miny
* TILE_SIZE
-
558 tri
->dy12
* minx
* TILE_SIZE
);
560 tri
->dx23
* miny
* TILE_SIZE
-
561 tri
->dy23
* minx
* TILE_SIZE
);
563 tri
->dx31
* miny
* TILE_SIZE
-
564 tri
->dy31
* minx
* TILE_SIZE
);
566 int ei1
= tri
->ei1
<< TILE_ORDER
;
567 int ei2
= tri
->ei2
<< TILE_ORDER
;
568 int ei3
= tri
->ei3
<< TILE_ORDER
;
570 int eo1
= tri
->eo1
<< TILE_ORDER
;
571 int eo2
= tri
->eo2
<< TILE_ORDER
;
572 int eo3
= tri
->eo3
<< TILE_ORDER
;
574 int xstep1
= -(tri
->dy12
<< TILE_ORDER
);
575 int xstep2
= -(tri
->dy23
<< TILE_ORDER
);
576 int xstep3
= -(tri
->dy31
<< TILE_ORDER
);
578 int ystep1
= tri
->dx12
<< TILE_ORDER
;
579 int ystep2
= tri
->dx23
<< TILE_ORDER
;
580 int ystep3
= tri
->dx31
<< TILE_ORDER
;
584 /* Test tile-sized blocks against the triangle.
585 * Discard blocks fully outside the tri. If the block is fully
586 * contained inside the tri, bin an lp_rast_shade_tile command.
587 * Else, bin a lp_rast_triangle command.
589 for (y
= miny
; y
<= maxy
; y
++)
594 boolean in
= FALSE
; /* are we inside the triangle? */
596 for (x
= minx
; x
<= maxx
; x
++)
603 LP_COUNT(nr_empty_64
);
605 break; /* exiting triangle, all done with this row */
607 else if (cx1
+ ei1
> 0 &&
611 /* triangle covers the whole tile- shade whole tile */
612 LP_COUNT(nr_fully_covered_64
);
614 if (setup
->fs
.current
.variant
->opaque
&&
616 lp_scene_bin_reset( scene
, x
, y
);
617 lp_scene_bin_command( scene
, x
, y
,
619 lp_rast_arg_state(setup
->fs
.stored
) );
621 lp_scene_bin_command( scene
, x
, y
,
623 lp_rast_arg_inputs(&tri
->inputs
) );
627 /* rasterizer/shade partial tile */
628 LP_COUNT(nr_partially_covered_64
);
630 lp_scene_bin_command( scene
, x
, y
,
632 lp_rast_arg_triangle(tri
) );
635 /* Iterate cx values across the region:
642 /* Iterate c values down the region:
653 * Draw triangle if it's CW, cull otherwise.
655 static void triangle_cw( struct lp_setup_context
*setup
,
656 const float (*v0
)[4],
657 const float (*v1
)[4],
658 const float (*v2
)[4] )
660 do_triangle_ccw( setup
, v1
, v0
, v2
, !setup
->ccw_is_frontface
);
665 * Draw triangle if it's CCW, cull otherwise.
667 static void triangle_ccw( struct lp_setup_context
*setup
,
668 const float (*v0
)[4],
669 const float (*v1
)[4],
670 const float (*v2
)[4] )
672 do_triangle_ccw( setup
, v0
, v1
, v2
, setup
->ccw_is_frontface
);
678 * Draw triangle whether it's CW or CCW.
680 static void triangle_both( struct lp_setup_context
*setup
,
681 const float (*v0
)[4],
682 const float (*v1
)[4],
683 const float (*v2
)[4] )
685 /* edge vectors e = v0 - v2, f = v1 - v2 */
686 const float ex
= v0
[0][0] - v2
[0][0];
687 const float ey
= v0
[0][1] - v2
[0][1];
688 const float fx
= v1
[0][0] - v2
[0][0];
689 const float fy
= v1
[0][1] - v2
[0][1];
691 /* det = cross(e,f).z */
692 if (ex
* fy
- ey
* fx
< 0.0f
)
693 triangle_ccw( setup
, v0
, v1
, v2
);
695 triangle_cw( setup
, v0
, v1
, v2
);
699 static void triangle_nop( struct lp_setup_context
*setup
,
700 const float (*v0
)[4],
701 const float (*v1
)[4],
702 const float (*v2
)[4] )
708 lp_setup_choose_triangle( struct lp_setup_context
*setup
)
710 switch (setup
->cullmode
) {
712 setup
->triangle
= triangle_both
;
715 setup
->triangle
= setup
->ccw_is_frontface
? triangle_ccw
: triangle_cw
;
717 case PIPE_FACE_FRONT
:
718 setup
->triangle
= setup
->ccw_is_frontface
? triangle_cw
: triangle_ccw
;
721 setup
->triangle
= triangle_nop
;