src/gallium/drivers/llvmpipe/lp_setup_tri.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas.
   4  * 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
   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:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  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.
  25  *
  26  **************************************************************************/
  27
  28 /*
  29  * Binning code for triangles
  30  */
  31
  32 #include "util/u_math.h"
  33 #include "util/u_memory.h"
  34 #include "util/u_rect.h"
  35 #include "util/u_sse.h"
  36 #include "lp_perf.h"
  37 #include "lp_setup_context.h"
  38 #include "lp_rast.h"
  39 #include "lp_state_fs.h"
  40 #include "lp_state_setup.h"
  41
  42 #define NUM_CHANNELS 4
  43
  44 #if defined(PIPE_ARCH_SSE)
  45 #include <emmintrin.h>
  46 #endif
  47
  48 static INLINE int
  49 subpixel_snap(float a)
  50 {
  51    return util_iround(FIXED_ONE * a);
  52 }
  53
  54 static INLINE float
  55 fixed_to_float(int a)
  56 {
  57    return a * (1.0 / FIXED_ONE);
  58 }
  59
  60
  61
  62
  63
  64
  65
  66 /**
  67  * Alloc space for a new triangle plus the input.a0/dadx/dady arrays
  68  * immediately after it.
  69  * The memory is allocated from the per-scene pool, not per-tile.
  70  * \param tri_size  returns number of bytes allocated
  71  * \param num_inputs  number of fragment shader inputs
  72  * \return pointer to triangle space
  73  */
  74 struct lp_rast_triangle *
  75 lp_setup_alloc_triangle(struct lp_scene *scene,
  76                         unsigned nr_inputs,
  77                         unsigned nr_planes,
  78                         unsigned *tri_size)
  79 {
  80    unsigned input_array_sz = NUM_CHANNELS * (nr_inputs + 1) * sizeof(float);
  81    unsigned plane_sz = nr_planes * sizeof(struct lp_rast_plane);
  82    struct lp_rast_triangle *tri;
  83
  84    *tri_size = (sizeof(struct lp_rast_triangle) +
  85                 3 * input_array_sz +
  86                 plane_sz);
  87
  88    tri = lp_scene_alloc_aligned( scene, *tri_size, 16 );
  89    if (tri == NULL)
  90       return NULL;
  91
  92    tri->inputs.stride = input_array_sz;
  93
  94    {
  95       char *a = (char *)tri;
  96       char *b = (char *)&GET_PLANES(tri)[nr_planes];
  97       assert(b - a == *tri_size);
  98    }
  99
 100    return tri;
 101 }
 102
 103 void
 104 lp_setup_print_vertex(struct lp_setup_context *setup,
 105                       const char *name,
 106                       const float (*v)[4])
 107 {
 108    const struct lp_setup_variant_key *key = &setup->setup.variant->key;
 109    int i, j;
 110
 111    debug_printf("   wpos (%s[0]) xyzw %f %f %f %f\n",
 112                 name,
 113                 v[0][0], v[0][1], v[0][2], v[0][3]);
 114
 115    for (i = 0; i < key->num_inputs; i++) {
 116       const float *in = v[key->inputs[i].src_index];
 117
 118       debug_printf("  in[%d] (%s[%d]) %s%s%s%s ",
 119                    i,
 120                    name, key->inputs[i].src_index,
 121                    (key->inputs[i].usage_mask & 0x1) ? "x" : " ",
 122                    (key->inputs[i].usage_mask & 0x2) ? "y" : " ",
 123                    (key->inputs[i].usage_mask & 0x4) ? "z" : " ",
 124                    (key->inputs[i].usage_mask & 0x8) ? "w" : " ");
 125
 126       for (j = 0; j < 4; j++)
 127          if (key->inputs[i].usage_mask & (1<<j))
 128             debug_printf("%.5f ", in[j]);
 129
 130       debug_printf("\n");
 131    }
 132 }
 133
 134
 135 /**
 136  * Print triangle vertex attribs (for debug).
 137  */
 138 void
 139 lp_setup_print_triangle(struct lp_setup_context *setup,
 140                         const float (*v0)[4],
 141                         const float (*v1)[4],
 142                         const float (*v2)[4])
 143 {
 144    debug_printf("triangle\n");
 145
 146    {
 147       const float ex = v0[0][0] - v2[0][0];
 148       const float ey = v0[0][1] - v2[0][1];
 149       const float fx = v1[0][0] - v2[0][0];
 150       const float fy = v1[0][1] - v2[0][1];
 151
 152       /* det = cross(e,f).z */
 153       const float det = ex * fy - ey * fx;
 154       if (det < 0.0f)
 155          debug_printf("   - ccw\n");
 156       else if (det > 0.0f)
 157          debug_printf("   - cw\n");
 158       else
 159          debug_printf("   - zero area\n");
 160    }
 161
 162    lp_setup_print_vertex(setup, "v0", v0);
 163    lp_setup_print_vertex(setup, "v1", v1);
 164    lp_setup_print_vertex(setup, "v2", v2);
 165 }
 166
 167
 168 #define MAX_PLANES 8
 169 static unsigned
 170 lp_rast_tri_tab[MAX_PLANES+1] = {
 171    0,               /* should be impossible */
 172    LP_RAST_OP_TRIANGLE_1,
 173    LP_RAST_OP_TRIANGLE_2,
 174    LP_RAST_OP_TRIANGLE_3,
 175    LP_RAST_OP_TRIANGLE_4,
 176    LP_RAST_OP_TRIANGLE_5,
 177    LP_RAST_OP_TRIANGLE_6,
 178    LP_RAST_OP_TRIANGLE_7,
 179    LP_RAST_OP_TRIANGLE_8
 180 };
 181
 182
 183
 184 /**
 185  * The primitive covers the whole tile- shade whole tile.
 186  *
 187  * \param tx, ty  the tile position in tiles, not pixels
 188  */
 189 static boolean
 190 lp_setup_whole_tile(struct lp_setup_context *setup,
 191                     const struct lp_rast_shader_inputs *inputs,
 192                     int tx, int ty)
 193 {
 194    struct lp_scene *scene = setup->scene;
 195
 196    LP_COUNT(nr_fully_covered_64);
 197
 198    /* if variant is opaque and scissor doesn't effect the tile */
 199    if (inputs->opaque) {
 200       if (!scene->fb.zsbuf) {
 201          /*
 202           * All previous rendering will be overwritten so reset the bin.
 203           */
 204          lp_scene_bin_reset( scene, tx, ty );
 205       }
 206
 207       LP_COUNT(nr_shade_opaque_64);
 208       return lp_scene_bin_cmd_with_state( scene, tx, ty,
 209                                           setup->fs.stored,
 210                                           LP_RAST_OP_SHADE_TILE_OPAQUE,
 211                                           lp_rast_arg_inputs(inputs) );
 212    } else {
 213       LP_COUNT(nr_shade_64);
 214       return lp_scene_bin_cmd_with_state( scene, tx, ty,
 215                                           setup->fs.stored,
 216                                           LP_RAST_OP_SHADE_TILE,
 217                                           lp_rast_arg_inputs(inputs) );
 218    }
 219 }
 220
 221
 222 /**
 223  * Do basic setup for triangle rasterization and determine which
 224  * framebuffer tiles are touched.  Put the triangle in the scene's
 225  * bins for the tiles which we overlap.
 226  */
 227 static boolean
 228 do_triangle_ccw(struct lp_setup_context *setup,
 229                 const float (*v0)[4],
 230                 const float (*v1)[4],
 231                 const float (*v2)[4],
 232                 boolean frontfacing )
 233 {
 234    struct lp_scene *scene = setup->scene;
 235    const struct lp_setup_variant_key *key = &setup->setup.variant->key;
 236    struct lp_rast_triangle *tri;
 237    struct lp_rast_plane *plane;
 238    int x[4];
 239    int y[4];
 240    struct u_rect bbox;
 241    unsigned tri_bytes;
 242    int nr_planes = 3;
 243
 244    if (0)
 245       lp_setup_print_triangle(setup, v0, v1, v2);
 246
 247    if (setup->scissor_test) {
 248       nr_planes = 7;
 249    }
 250    else {
 251       nr_planes = 3;
 252    }
 253
 254    /* x/y positions in fixed point */
 255    x[0] = subpixel_snap(v0[0][0] - setup->pixel_offset);
 256    x[1] = subpixel_snap(v1[0][0] - setup->pixel_offset);
 257    x[2] = subpixel_snap(v2[0][0] - setup->pixel_offset);
 258    x[3] = 0;
 259    y[0] = subpixel_snap(v0[0][1] - setup->pixel_offset);
 260    y[1] = subpixel_snap(v1[0][1] - setup->pixel_offset);
 261    y[2] = subpixel_snap(v2[0][1] - setup->pixel_offset);
 262    y[3] = 0;
 263
 264
 265    /* Bounding rectangle (in pixels) */
 266    {
 267       /* Yes this is necessary to accurately calculate bounding boxes
 268        * with the two fill-conventions we support.  GL (normally) ends
 269        * up needing a bottom-left fill convention, which requires
 270        * slightly different rounding.
 271        */
 272       int adj = (setup->pixel_offset != 0) ? 1 : 0;
 273
 274       bbox.x0 = (MIN3(x[0], x[1], x[2]) + (FIXED_ONE-1)) >> FIXED_ORDER;
 275       bbox.x1 = (MAX3(x[0], x[1], x[2]) + (FIXED_ONE-1)) >> FIXED_ORDER;
 276       bbox.y0 = (MIN3(y[0], y[1], y[2]) + (FIXED_ONE-1) + adj) >> FIXED_ORDER;
 277       bbox.y1 = (MAX3(y[0], y[1], y[2]) + (FIXED_ONE-1) + adj) >> FIXED_ORDER;
 278
 279       /* Inclusive coordinates:
 280        */
 281       bbox.x1--;
 282       bbox.y1--;
 283    }
 284
 285    if (bbox.x1 < bbox.x0 ||
 286        bbox.y1 < bbox.y0) {
 287       if (0) debug_printf("empty bounding box\n");
 288       LP_COUNT(nr_culled_tris);
 289       return TRUE;
 290    }
 291
 292    if (!u_rect_test_intersection(&setup->draw_region, &bbox)) {
 293       if (0) debug_printf("offscreen\n");
 294       LP_COUNT(nr_culled_tris);
 295       return TRUE;
 296    }
 297
 298    /* Can safely discard negative regions, but need to keep hold of
 299     * information about when the triangle extends past screen
 300     * boundaries.  See trimmed_box in lp_setup_bin_triangle().
 301     */
 302    bbox.x0 = MAX2(bbox.x0, 0);
 303    bbox.y0 = MAX2(bbox.y0, 0);
 304
 305    tri = lp_setup_alloc_triangle(scene,
 306                                  key->num_inputs,
 307                                  nr_planes,
 308                                  &tri_bytes);
 309    if (!tri)
 310       return FALSE;
 311
 312 #if 0
 313    tri->v[0][0] = v0[0][0];
 314    tri->v[1][0] = v1[0][0];
 315    tri->v[2][0] = v2[0][0];
 316    tri->v[0][1] = v0[0][1];
 317    tri->v[1][1] = v1[0][1];
 318    tri->v[2][1] = v2[0][1];
 319 #endif
 320
 321    LP_COUNT(nr_tris);
 322
 323    /* Setup parameter interpolants:
 324     */
 325    setup->setup.variant->jit_function( v0,
 326                                        v1,
 327                                        v2,
 328                                        frontfacing,
 329                                        GET_A0(&tri->inputs),
 330                                        GET_DADX(&tri->inputs),
 331                                        GET_DADY(&tri->inputs) );
 332
 333    tri->inputs.frontfacing = frontfacing;
 334    tri->inputs.disable = FALSE;
 335    tri->inputs.opaque = setup->fs.current.variant->opaque;
 336
 337    if (0)
 338       lp_dump_setup_coef(&setup->setup.variant->key,
 339                          (const float (*)[4])GET_A0(&tri->inputs),
 340                          (const float (*)[4])GET_DADX(&tri->inputs),
 341                          (const float (*)[4])GET_DADY(&tri->inputs));
 342
 343    plane = GET_PLANES(tri);
 344
 345 #if defined(PIPE_ARCH_SSE)
 346    {
 347       __m128i vertx, verty;
 348       __m128i shufx, shufy;
 349       __m128i dcdx, dcdy, c;
 350       __m128i unused;
 351       __m128i dcdx_neg_mask;
 352       __m128i dcdy_neg_mask;
 353       __m128i dcdx_zero_mask;
 354       __m128i top_left_flag;
 355       __m128i c_inc_mask, c_inc;
 356       __m128i eo, p0, p1, p2;
 357       __m128i zero = _mm_setzero_si128();
 358
 359       vertx = _mm_loadu_si128((__m128i *)x); /* vertex x coords */
 360       verty = _mm_loadu_si128((__m128i *)y); /* vertex y coords */
 361
 362       shufx = _mm_shuffle_epi32(vertx, _MM_SHUFFLE(3,0,2,1));
 363       shufy = _mm_shuffle_epi32(verty, _MM_SHUFFLE(3,0,2,1));
 364
 365       dcdx = _mm_sub_epi32(verty, shufy);
 366       dcdy = _mm_sub_epi32(vertx, shufx);
 367
 368       dcdx_neg_mask = _mm_srai_epi32(dcdx, 31);
 369       dcdx_zero_mask = _mm_cmpeq_epi32(dcdx, zero);
 370       dcdy_neg_mask = _mm_srai_epi32(dcdy, 31);
 371
 372       top_left_flag = _mm_set1_epi32((setup->pixel_offset == 0) ? ~0 : 0);
 373
 374       c_inc_mask = _mm_or_si128(dcdx_neg_mask,
 375                                 _mm_and_si128(dcdx_zero_mask,
 376                                               _mm_xor_si128(dcdy_neg_mask,
 377                                                             top_left_flag)));
 378
 379       c_inc = _mm_srli_epi32(c_inc_mask, 31);
 380
 381       c = _mm_sub_epi32(mm_mullo_epi32(dcdx, vertx),
 382                         mm_mullo_epi32(dcdy, verty));
 383
 384       c = _mm_add_epi32(c, c_inc);
 385
 386       /* Scale up to match c:
 387        */
 388       dcdx = _mm_slli_epi32(dcdx, FIXED_ORDER);
 389       dcdy = _mm_slli_epi32(dcdy, FIXED_ORDER);
 390
 391       /* Calculate trivial reject values:
 392        */
 393       eo = _mm_sub_epi32(_mm_andnot_si128(dcdy_neg_mask, dcdy),
 394                          _mm_and_si128(dcdx_neg_mask, dcdx));
 395
 396       /* ei = _mm_sub_epi32(_mm_sub_epi32(dcdy, dcdx), eo); */
 397
 398       /* Pointless transpose which gets undone immediately in
 399        * rasterization:
 400        */
 401       transpose4_epi32(&c, &dcdx, &dcdy, &eo,
 402                        &p0, &p1, &p2, &unused);
 403
 404       _mm_store_si128((__m128i *)&plane[0], p0);
 405       _mm_store_si128((__m128i *)&plane[1], p1);
 406       _mm_store_si128((__m128i *)&plane[2], p2);
 407    }
 408 #else
 409    {
 410       int i;
 411       plane[0].dcdy = x[0] - x[1];
 412       plane[1].dcdy = x[1] - x[2];
 413       plane[2].dcdy = x[2] - x[0];
 414       plane[0].dcdx = y[0] - y[1];
 415       plane[1].dcdx = y[1] - y[2];
 416       plane[2].dcdx = y[2] - y[0];
 417
 418       for (i = 0; i < 3; i++) {
 419          /* half-edge constants, will be interated over the whole render
 420           * target.
 421           */
 422          plane[i].c = plane[i].dcdx * x[i] - plane[i].dcdy * y[i];
 423
 424          /* correct for top-left vs. bottom-left fill convention.
 425           *
 426           * note that we're overloading gl_rasterization_rules to mean
 427           * both (0.5,0.5) pixel centers *and* bottom-left filling
 428           * convention.
 429           *
 430           * GL actually has a top-left filling convention, but GL's
 431           * notion of "top" differs from gallium's...
 432           *
 433           * Also, sometimes (in FBO cases) GL will render upside down
 434           * to its usual method, in which case it will probably want
 435           * to use the opposite, top-left convention.
 436           */
 437          if (plane[i].dcdx < 0) {
 438             /* both fill conventions want this - adjust for left edges */
 439             plane[i].c++;
 440          }
 441          else if (plane[i].dcdx == 0) {
 442             if (setup->pixel_offset == 0) {
 443                /* correct for top-left fill convention:
 444                 */
 445                if (plane[i].dcdy > 0) plane[i].c++;
 446             }
 447             else {
 448                /* correct for bottom-left fill convention:
 449                 */
 450                if (plane[i].dcdy < 0) plane[i].c++;
 451             }
 452          }
 453
 454          plane[i].dcdx *= FIXED_ONE;
 455          plane[i].dcdy *= FIXED_ONE;
 456
 457          /* find trivial reject offsets for each edge for a single-pixel
 458           * sized block.  These will be scaled up at each recursive level to
 459           * match the active blocksize.  Scaling in this way works best if
 460           * the blocks are square.
 461           */
 462          plane[i].eo = 0;
 463          if (plane[i].dcdx < 0) plane[i].eo -= plane[i].dcdx;
 464          if (plane[i].dcdy > 0) plane[i].eo += plane[i].dcdy;
 465       }
 466    }
 467 #endif
 468
 469    if (0) {
 470       debug_printf("p0: %08x/%08x/%08x/%08x\n",
 471                    plane[0].c,
 472                    plane[0].dcdx,
 473                    plane[0].dcdy,
 474                    plane[0].eo);
 475
 476       debug_printf("p1: %08x/%08x/%08x/%08x\n",
 477                    plane[1].c,
 478                    plane[1].dcdx,
 479                    plane[1].dcdy,
 480                    plane[1].eo);
 481
 482       debug_printf("p0: %08x/%08x/%08x/%08x\n",
 483                    plane[2].c,
 484                    plane[2].dcdx,
 485                    plane[2].dcdy,
 486                    plane[2].eo);
 487    }
 488
 489
 490    /*
 491     * When rasterizing scissored tris, use the intersection of the
 492     * triangle bounding box and the scissor rect to generate the
 493     * scissor planes.
 494     *
 495     * This permits us to cut off the triangle "tails" that are present
 496     * in the intermediate recursive levels caused when two of the
 497     * triangles edges don't diverge quickly enough to trivially reject
 498     * exterior blocks from the triangle.
 499     *
 500     * It's not really clear if it's worth worrying about these tails,
 501     * but since we generate the planes for each scissored tri, it's
 502     * free to trim them in this case.
 503     *
 504     * Note that otherwise, the scissor planes only vary in 'C' value,
 505     * and even then only on state-changes.  Could alternatively store
 506     * these planes elsewhere.
 507     */
 508    if (nr_planes == 7) {
 509       const struct u_rect *scissor = &setup->scissor;
 510
 511       plane[3].dcdx = -1;
 512       plane[3].dcdy = 0;
 513       plane[3].c = 1-scissor->x0;
 514       plane[3].eo = 1;
 515
 516       plane[4].dcdx = 1;
 517       plane[4].dcdy = 0;
 518       plane[4].c = scissor->x1+1;
 519       plane[4].eo = 0;
 520
 521       plane[5].dcdx = 0;
 522       plane[5].dcdy = 1;
 523       plane[5].c = 1-scissor->y0;
 524       plane[5].eo = 1;
 525
 526       plane[6].dcdx = 0;
 527       plane[6].dcdy = -1;
 528       plane[6].c = scissor->y1+1;
 529       plane[6].eo = 0;
 530    }
 531
 532    return lp_setup_bin_triangle( setup, tri, &bbox, nr_planes );
 533 }
 534
 535 /*
 536  * Round to nearest less or equal power of two of the input.
 537  *
 538  * Undefined if no bit set exists, so code should check against 0 first.
 539  */
 540 static INLINE uint32_t
 541 floor_pot(uint32_t n)
 542 {
 543 #if defined(PIPE_CC_GCC) && defined(PIPE_ARCH_X86)
 544    if (n == 0)
 545       return 0;
 546
 547    __asm__("bsr %1,%0"
 548           : "=r" (n)
 549           : "rm" (n));
 550    return 1 << n;
 551 #else
 552    n |= (n >>  1);
 553    n |= (n >>  2);
 554    n |= (n >>  4);
 555    n |= (n >>  8);
 556    n |= (n >> 16);
 557    return n - (n >> 1);
 558 #endif
 559 }
 560
 561
 562 boolean
 563 lp_setup_bin_triangle( struct lp_setup_context *setup,
 564                        struct lp_rast_triangle *tri,
 565                        const struct u_rect *bbox,
 566                        int nr_planes )
 567 {
 568    struct lp_scene *scene = setup->scene;
 569    struct u_rect trimmed_box = *bbox;
 570    int i;
 571
 572    /* What is the largest power-of-two boundary this triangle crosses:
 573     */
 574    int dx = floor_pot((bbox->x0 ^ bbox->x1) |
 575                       (bbox->y0 ^ bbox->y1));
 576
 577    /* The largest dimension of the rasterized area of the triangle
 578     * (aligned to a 4x4 grid), rounded down to the nearest power of two:
 579     */
 580    int sz = floor_pot((bbox->x1 - (bbox->x0 & ~3)) |
 581                       (bbox->y1 - (bbox->y0 & ~3)));
 582
 583    /* Now apply scissor, etc to the bounding box.  Could do this
 584     * earlier, but it confuses the logic for tri-16 and would force
 585     * the rasterizer to also respect scissor, etc, just for the rare
 586     * cases where a small triangle extends beyond the scissor.
 587     */
 588    u_rect_find_intersection(&setup->draw_region, &trimmed_box);
 589
 590    /* Determine which tile(s) intersect the triangle's bounding box
 591     */
 592    if (dx < TILE_SIZE)
 593    {
 594       int ix0 = bbox->x0 / TILE_SIZE;
 595       int iy0 = bbox->y0 / TILE_SIZE;
 596       int px = bbox->x0 & 63 & ~3;
 597       int py = bbox->y0 & 63 & ~3;
 598       int mask = px | (py << 8);
 599
 600       assert(iy0 == bbox->y1 / TILE_SIZE &&
 601              ix0 == bbox->x1 / TILE_SIZE);
 602
 603       if (nr_planes == 3) {
 604          if (sz < 4)
 605          {
 606             /* Triangle is contained in a single 4x4 stamp:
 607              */
 608             return lp_scene_bin_cmd_with_state( scene, ix0, iy0,
 609                                                 setup->fs.stored,
 610                                                 LP_RAST_OP_TRIANGLE_3_4,
 611                                                 lp_rast_arg_triangle(tri, mask) );
 612          }
 613
 614          if (sz < 16)
 615          {
 616             /* Triangle is contained in a single 16x16 block:
 617              */
 618             return lp_scene_bin_cmd_with_state( scene, ix0, iy0,
 619                                                 setup->fs.stored,
 620                                                 LP_RAST_OP_TRIANGLE_3_16,
 621                                                 lp_rast_arg_triangle(tri, mask) );
 622          }
 623       }
 624       else if (nr_planes == 4 && sz < 16)
 625       {
 626          return lp_scene_bin_cmd_with_state(scene, ix0, iy0,
 627                                             setup->fs.stored,
 628                                             LP_RAST_OP_TRIANGLE_4_16,
 629                                             lp_rast_arg_triangle(tri, mask) );
 630       }
 631
 632
 633       /* Triangle is contained in a single tile:
 634        */
 635       return lp_scene_bin_cmd_with_state( scene, ix0, iy0, setup->fs.stored,
 636                                           lp_rast_tri_tab[nr_planes],
 637                                           lp_rast_arg_triangle(tri, (1<<nr_planes)-1) );
 638    }
 639    else
 640    {
 641       struct lp_rast_plane *plane = GET_PLANES(tri);
 642       int c[MAX_PLANES];
 643       int ei[MAX_PLANES];
 644
 645       int eo[MAX_PLANES];
 646       int xstep[MAX_PLANES];
 647       int ystep[MAX_PLANES];
 648       int x, y;
 649
 650       int ix0 = trimmed_box.x0 / TILE_SIZE;
 651       int iy0 = trimmed_box.y0 / TILE_SIZE;
 652       int ix1 = trimmed_box.x1 / TILE_SIZE;
 653       int iy1 = trimmed_box.y1 / TILE_SIZE;
 654
 655       for (i = 0; i < nr_planes; i++) {
 656          c[i] = (plane[i].c +
 657                  plane[i].dcdy * iy0 * TILE_SIZE -
 658                  plane[i].dcdx * ix0 * TILE_SIZE);
 659
 660          ei[i] = (plane[i].dcdy -
 661                   plane[i].dcdx -
 662                   plane[i].eo) << TILE_ORDER;
 663
 664          eo[i] = plane[i].eo << TILE_ORDER;
 665          xstep[i] = -(plane[i].dcdx << TILE_ORDER);
 666          ystep[i] = plane[i].dcdy << TILE_ORDER;
 667       }
 668
 669
 670
 671       /* Test tile-sized blocks against the triangle.
 672        * Discard blocks fully outside the tri.  If the block is fully
 673        * contained inside the tri, bin an lp_rast_shade_tile command.
 674        * Else, bin a lp_rast_triangle command.
 675        */
 676       for (y = iy0; y <= iy1; y++)
 677       {
 678          boolean in = FALSE;  /* are we inside the triangle? */
 679          int cx[MAX_PLANES];
 680
 681          for (i = 0; i < nr_planes; i++)
 682             cx[i] = c[i];
 683
 684          for (x = ix0; x <= ix1; x++)
 685          {
 686             int out = 0;
 687             int partial = 0;
 688
 689             for (i = 0; i < nr_planes; i++) {
 690                int planeout = cx[i] + eo[i];
 691                int planepartial = cx[i] + ei[i] - 1;
 692                out |= (planeout >> 31);
 693                partial |= (planepartial >> 31) & (1<<i);
 694             }
 695
 696             if (out) {
 697                /* do nothing */
 698                if (in)
 699                   break;  /* exiting triangle, all done with this row */
 700                LP_COUNT(nr_empty_64);
 701             }
 702             else if (partial) {
 703                /* Not trivially accepted by at least one plane -
 704                 * rasterize/shade partial tile
 705                 */
 706                int count = util_bitcount(partial);
 707                in = TRUE;
 708
 709                if (!lp_scene_bin_cmd_with_state( scene, x, y,
 710                                                  setup->fs.stored,
 711                                                  lp_rast_tri_tab[count],
 712                                                  lp_rast_arg_triangle(tri, partial) ))
 713                   goto fail;
 714
 715                LP_COUNT(nr_partially_covered_64);
 716             }
 717             else {
 718                /* triangle covers the whole tile- shade whole tile */
 719                LP_COUNT(nr_fully_covered_64);
 720                in = TRUE;
 721                if (!lp_setup_whole_tile(setup, &tri->inputs, x, y))
 722                   goto fail;
 723             }
 724
 725             /* Iterate cx values across the region:
 726              */
 727             for (i = 0; i < nr_planes; i++)
 728                cx[i] += xstep[i];
 729          }
 730
 731          /* Iterate c values down the region:
 732           */
 733          for (i = 0; i < nr_planes; i++)
 734             c[i] += ystep[i];
 735       }
 736    }
 737
 738    return TRUE;
 739
 740 fail:
 741    /* Need to disable any partially binned triangle.  This is easier
 742     * than trying to locate all the triangle, shade-tile, etc,
 743     * commands which may have been binned.
 744     */
 745    tri->inputs.disable = TRUE;
 746    return FALSE;
 747 }
 748
 749
 750 /**
 751  * Try to draw the triangle, restart the scene on failure.
 752  */
 753 static void retry_triangle_ccw( struct lp_setup_context *setup,
 754                                 const float (*v0)[4],
 755                                 const float (*v1)[4],
 756                                 const float (*v2)[4],
 757                                 boolean front)
 758 {
 759    if (!do_triangle_ccw( setup, v0, v1, v2, front ))
 760    {
 761       if (!lp_setup_flush_and_restart(setup))
 762          return;
 763
 764       if (!do_triangle_ccw( setup, v0, v1, v2, front ))
 765          return;
 766    }
 767 }
 768
 769 static INLINE float
 770 calc_area(const float (*v0)[4],
 771           const float (*v1)[4],
 772           const float (*v2)[4])
 773 {
 774    float dx01 = v0[0][0] - v1[0][0];
 775    float dy01 = v0[0][1] - v1[0][1];
 776    float dx20 = v2[0][0] - v0[0][0];
 777    float dy20 = v2[0][1] - v0[0][1];
 778    return dx01 * dy20 - dx20 * dy01;
 779 }
 780
 781
 782 /**
 783  * Draw triangle if it's CW, cull otherwise.
 784  */
 785 static void triangle_cw( struct lp_setup_context *setup,
 786                          const float (*v0)[4],
 787                          const float (*v1)[4],
 788                          const float (*v2)[4] )
 789 {
 790    float area = calc_area(v0, v1, v2);
 791
 792    if (area < 0.0f)
 793       retry_triangle_ccw(setup, v0, v2, v1, !setup->ccw_is_frontface);
 794 }
 795
 796
 797 static void triangle_ccw( struct lp_setup_context *setup,
 798                           const float (*v0)[4],
 799                           const float (*v1)[4],
 800                           const float (*v2)[4])
 801 {
 802    float area = calc_area(v0, v1, v2);
 803
 804    if (area > 0.0f)
 805       retry_triangle_ccw(setup, v0, v1, v2, setup->ccw_is_frontface);
 806 }
 807
 808 /**
 809  * Draw triangle whether it's CW or CCW.
 810  */
 811 static void triangle_both( struct lp_setup_context *setup,
 812                            const float (*v0)[4],
 813                            const float (*v1)[4],
 814                            const float (*v2)[4] )
 815 {
 816    float area = calc_area(v0, v1, v2);
 817
 818    if (0) {
 819       assert(!util_is_inf_or_nan(v0[0][0]));
 820       assert(!util_is_inf_or_nan(v0[0][1]));
 821       assert(!util_is_inf_or_nan(v1[0][0]));
 822       assert(!util_is_inf_or_nan(v1[0][1]));
 823       assert(!util_is_inf_or_nan(v2[0][0]));
 824       assert(!util_is_inf_or_nan(v2[0][1]));
 825       assert(!util_is_inf_or_nan(area));
 826    }
 827
 828    if (area > 0.0f)
 829       retry_triangle_ccw( setup, v0, v1, v2, setup->ccw_is_frontface );
 830    else if (area < 0.0f)
 831       retry_triangle_ccw( setup, v0, v2, v1, !setup->ccw_is_frontface );
 832 }
 833
 834
 835 static void triangle_nop( struct lp_setup_context *setup,
 836                           const float (*v0)[4],
 837                           const float (*v1)[4],
 838                           const float (*v2)[4] )
 839 {
 840 }
 841
 842
 843 void
 844 lp_setup_choose_triangle( struct lp_setup_context *setup )
 845 {
 846    switch (setup->cullmode) {
 847    case PIPE_FACE_NONE:
 848       setup->triangle = triangle_both;
 849       break;
 850    case PIPE_FACE_BACK:
 851       setup->triangle = setup->ccw_is_frontface ? triangle_ccw : triangle_cw;
 852       break;
 853    case PIPE_FACE_FRONT:
 854       setup->triangle = setup->ccw_is_frontface ? triangle_cw : triangle_ccw;
 855       break;
 856    default:
 857       setup->triangle = triangle_nop;
 858       break;
 859    }
 860 }