src/gallium/auxiliary/draw/draw_pipe_clip.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  * \brief  Clipping stage
  30  *
  31  * \author  Keith Whitwell <keith@tungstengraphics.com>
  32  */
  33
  34
  35 #include "util/u_memory.h"
  36 #include "util/u_math.h"
  37
  38 #include "pipe/p_shader_tokens.h"
  39
  40 #include "draw_vs.h"
  41 #include "draw_pipe.h"
  42
  43
  44 #ifndef IS_NEGATIVE
  45 #define IS_NEGATIVE(X) ((X) < 0.0)
  46 #endif
  47
  48 #ifndef DIFFERENT_SIGNS
  49 #define DIFFERENT_SIGNS(x, y) ((x) * (y) <= 0.0F && (x) - (y) != 0.0F)
  50 #endif
  51
  52 #ifndef MAX_CLIPPED_VERTICES
  53 #define MAX_CLIPPED_VERTICES ((2 * (6 + PIPE_MAX_CLIP_PLANES))+1)
  54 #endif
  55
  56
  57
  58 struct clip_stage {
  59    struct draw_stage stage;      /**< base class */
  60
  61    /* Basically duplicate some of the flatshading logic here:
  62     */
  63    boolean flat;
  64    uint num_color_attribs;
  65    uint color_attribs[4];  /* front/back primary/secondary colors */
  66
  67    float (*plane)[4];
  68 };
  69
  70
  71 /** Cast wrapper */
  72 static INLINE struct clip_stage *clip_stage( struct draw_stage *stage )
  73 {
  74    return (struct clip_stage *)stage;
  75 }
  76
  77
  78 #define LINTERP(T, OUT, IN) ((OUT) + (T) * ((IN) - (OUT)))
  79
  80
  81 /* All attributes are float[4], so this is easy:
  82  */
  83 static void interp_attr( float dst[4],
  84                          float t,
  85                          const float in[4],
  86                          const float out[4] )
  87 {
  88    dst[0] = LINTERP( t, out[0], in[0] );
  89    dst[1] = LINTERP( t, out[1], in[1] );
  90    dst[2] = LINTERP( t, out[2], in[2] );
  91    dst[3] = LINTERP( t, out[3], in[3] );
  92 }
  93
  94
  95 /**
  96  * Copy front/back, primary/secondary colors from src vertex to dst vertex.
  97  * Used when flat shading.
  98  */
  99 static void copy_colors( struct draw_stage *stage,
 100                          struct vertex_header *dst,
 101                          const struct vertex_header *src )
 102 {
 103    const struct clip_stage *clipper = clip_stage(stage);
 104    uint i;
 105    for (i = 0; i < clipper->num_color_attribs; i++) {
 106       const uint attr = clipper->color_attribs[i];
 107       COPY_4FV(dst->data[attr], src->data[attr]);
 108    }
 109 }
 110
 111
 112
 113 /* Interpolate between two vertices to produce a third.
 114  */
 115 static void interp( const struct clip_stage *clip,
 116                     struct vertex_header *dst,
 117                     float t,
 118                     const struct vertex_header *out,
 119                     const struct vertex_header *in )
 120 {
 121    const unsigned nr_attrs = draw_current_shader_outputs(clip->stage.draw);
 122    const unsigned pos_attr = draw_current_shader_position_output(clip->stage.draw);
 123    unsigned j;
 124
 125    /* Vertex header.
 126     */
 127    dst->clipmask = 0;
 128    dst->edgeflag = 0;        /* will get overwritten later */
 129    dst->pad = 0;
 130    dst->vertex_id = UNDEFINED_VERTEX_ID;
 131
 132    /* Interpolate the clip-space coords.
 133     */
 134    interp_attr(dst->clip, t, in->clip, out->clip);
 135
 136    /* Do the projective divide and viewport transformation to get
 137     * new window coordinates:
 138     */
 139    {
 140       const float *pos = dst->clip;
 141       const float *scale = clip->stage.draw->viewport.scale;
 142       const float *trans = clip->stage.draw->viewport.translate;
 143       const float oow = 1.0f / pos[3];
 144
 145       dst->data[pos_attr][0] = pos[0] * oow * scale[0] + trans[0];
 146       dst->data[pos_attr][1] = pos[1] * oow * scale[1] + trans[1];
 147       dst->data[pos_attr][2] = pos[2] * oow * scale[2] + trans[2];
 148       dst->data[pos_attr][3] = oow;
 149    }
 150
 151    /* Other attributes
 152     */
 153    for (j = 0; j < nr_attrs; j++) {
 154       if (j != pos_attr)
 155          interp_attr(dst->data[j], t, in->data[j], out->data[j]);
 156    }
 157 }
 158
 159
 160 /**
 161  * Emit a post-clip polygon to the next pipeline stage.  The polygon
 162  * will be convex and the provoking vertex will always be vertex[0].
 163  */
 164 static void emit_poly( struct draw_stage *stage,
 165                        struct vertex_header **inlist,
 166                        const boolean *edgeflags,
 167                        unsigned n,
 168                        const struct prim_header *origPrim)
 169 {
 170    struct prim_header header;
 171    unsigned i;
 172    ushort edge_first, edge_middle, edge_last;
 173
 174    if (stage->draw->rasterizer->flatshade_first) {
 175       edge_first  = DRAW_PIPE_EDGE_FLAG_0;
 176       edge_middle = DRAW_PIPE_EDGE_FLAG_1;
 177       edge_last   = DRAW_PIPE_EDGE_FLAG_2;
 178    }
 179    else {
 180       edge_first  = DRAW_PIPE_EDGE_FLAG_2;
 181       edge_middle = DRAW_PIPE_EDGE_FLAG_0;
 182       edge_last   = DRAW_PIPE_EDGE_FLAG_1;
 183    }
 184
 185    if (!edgeflags[0])
 186       edge_first = 0;
 187
 188    /* later stages may need the determinant, but only the sign matters */
 189    header.det = origPrim->det;
 190    header.flags = DRAW_PIPE_RESET_STIPPLE | edge_first | edge_middle;
 191    header.pad = 0;
 192
 193    for (i = 2; i < n; i++, header.flags = edge_middle) {
 194       /* order the triangle verts to respect the provoking vertex mode */
 195       if (stage->draw->rasterizer->flatshade_first) {
 196          header.v[0] = inlist[0];  /* the provoking vertex */
 197          header.v[1] = inlist[i-1];
 198          header.v[2] = inlist[i];
 199       }
 200       else {
 201          header.v[0] = inlist[i-1];
 202          header.v[1] = inlist[i];
 203          header.v[2] = inlist[0];  /* the provoking vertex */
 204       }
 205
 206       if (!edgeflags[i-1]) {
 207          header.flags &= ~edge_middle;
 208       }
 209
 210       if (i == n - 1 && edgeflags[i])
 211          header.flags |= edge_last;
 212
 213       if (0) {
 214          const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader;
 215          uint j, k;
 216          debug_printf("Clipped tri: (flat-shade-first = %d)\n",
 217                       stage->draw->rasterizer->flatshade_first);
 218          for (j = 0; j < 3; j++) {
 219             for (k = 0; k < vs->info.num_outputs; k++) {
 220                debug_printf("  Vert %d: Attr %d:  %f %f %f %f\n", j, k,
 221                             header.v[j]->data[k][0],
 222                             header.v[j]->data[k][1],
 223                             header.v[j]->data[k][2],
 224                             header.v[j]->data[k][3]);
 225             }
 226          }
 227       }
 228
 229       stage->next->tri( stage->next, &header );
 230    }
 231 }
 232
 233
 234 static INLINE float
 235 dot4(const float *a, const float *b)
 236 {
 237    return (a[0] * b[0] +
 238            a[1] * b[1] +
 239            a[2] * b[2] +
 240            a[3] * b[3]);
 241 }
 242
 243
 244 /* Clip a triangle against the viewport and user clip planes.
 245  */
 246 static void
 247 do_clip_tri( struct draw_stage *stage,
 248              struct prim_header *header,
 249              unsigned clipmask )
 250 {
 251    struct clip_stage *clipper = clip_stage( stage );
 252    struct vertex_header *a[MAX_CLIPPED_VERTICES];
 253    struct vertex_header *b[MAX_CLIPPED_VERTICES];
 254    struct vertex_header **inlist = a;
 255    struct vertex_header **outlist = b;
 256    unsigned tmpnr = 0;
 257    unsigned n = 3;
 258    unsigned i;
 259    boolean aEdges[MAX_CLIPPED_VERTICES];
 260    boolean bEdges[MAX_CLIPPED_VERTICES];
 261    boolean *inEdges = aEdges;
 262    boolean *outEdges = bEdges;
 263
 264    inlist[0] = header->v[0];
 265    inlist[1] = header->v[1];
 266    inlist[2] = header->v[2];
 267
 268    /*
 269     * Note: at this point we can't just use the per-vertex edge flags.
 270     * We have to observe the edge flag bits set in header->flags which
 271     * were set during primitive decomposition.  Put those flags into
 272     * an edge flags array which parallels the vertex array.
 273     * Later, in the 'unfilled' pipeline stage we'll draw the edge if both
 274     * the header.flags bit is set AND the per-vertex edgeflag field is set.
 275     */
 276    inEdges[0] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_0);
 277    inEdges[1] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_1);
 278    inEdges[2] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_2);
 279
 280    while (clipmask && n >= 3) {
 281       const unsigned plane_idx = ffs(clipmask)-1;
 282       const boolean is_user_clip_plane = plane_idx >= 6;
 283       const float *plane = clipper->plane[plane_idx];
 284       struct vertex_header *vert_prev = inlist[0];
 285       boolean *edge_prev = &inEdges[0];
 286       float dp_prev = dot4( vert_prev->clip, plane );
 287       unsigned outcount = 0;
 288
 289       clipmask &= ~(1<<plane_idx);
 290
 291       assert(n < MAX_CLIPPED_VERTICES);
 292       if (n >= MAX_CLIPPED_VERTICES)
 293          return;
 294       inlist[n] = inlist[0]; /* prevent rotation of vertices */
 295       inEdges[n] = inEdges[0];
 296
 297       for (i = 1; i <= n; i++) {
 298          struct vertex_header *vert = inlist[i];
 299          boolean *edge = &inEdges[i];
 300
 301          float dp = dot4( vert->clip, plane );
 302
 303          if (!IS_NEGATIVE(dp_prev)) {
 304             assert(outcount < MAX_CLIPPED_VERTICES);
 305             if (outcount >= MAX_CLIPPED_VERTICES)
 306                return;
 307             outEdges[outcount] = *edge_prev;
 308             outlist[outcount++] = vert_prev;
 309          }
 310
 311          if (DIFFERENT_SIGNS(dp, dp_prev)) {
 312             struct vertex_header *new_vert;
 313             boolean *new_edge;
 314
 315             assert(tmpnr < MAX_CLIPPED_VERTICES + 1);
 316             if (tmpnr >= MAX_CLIPPED_VERTICES + 1)
 317                return;
 318             new_vert = clipper->stage.tmp[tmpnr++];
 319
 320             assert(outcount < MAX_CLIPPED_VERTICES);
 321             if (outcount >= MAX_CLIPPED_VERTICES)
 322                return;
 323
 324             new_edge = &outEdges[outcount];
 325             outlist[outcount++] = new_vert;
 326
 327             if (IS_NEGATIVE(dp)) {
 328                /* Going out of bounds.  Avoid division by zero as we
 329                 * know dp != dp_prev from DIFFERENT_SIGNS, above.
 330                 */
 331                float t = dp / (dp - dp_prev);
 332                interp( clipper, new_vert, t, vert, vert_prev );
 333
 334                /* Whether or not to set edge flag for the new vert depends
 335                 * on whether it's a user-defined clipping plane.  We're
 336                 * copying NVIDIA's behaviour here.
 337                 */
 338                if (is_user_clip_plane) {
 339                   /* we want to see an edge along the clip plane */
 340                   *new_edge = TRUE;
 341                   new_vert->edgeflag = TRUE;
 342                }
 343                else {
 344                   /* we don't want to see an edge along the frustum clip plane */
 345                   *new_edge = *edge_prev;
 346                   new_vert->edgeflag = FALSE;
 347                }
 348             }
 349             else {
 350                /* Coming back in.
 351                 */
 352                float t = dp_prev / (dp_prev - dp);
 353                interp( clipper, new_vert, t, vert_prev, vert );
 354
 355                /* Copy starting vert's edgeflag:
 356                 */
 357                new_vert->edgeflag = vert_prev->edgeflag;
 358                *new_edge = *edge_prev;
 359             }
 360          }
 361
 362          vert_prev = vert;
 363          edge_prev = edge;
 364          dp_prev = dp;
 365       }
 366
 367       /* swap in/out lists */
 368       {
 369          struct vertex_header **tmp = inlist;
 370          inlist = outlist;
 371          outlist = tmp;
 372          n = outcount;
 373       }
 374       {
 375          boolean *tmp = inEdges;
 376          inEdges = outEdges;
 377          outEdges = tmp;
 378       }
 379
 380    }
 381
 382    /* If flat-shading, copy provoking vertex color to polygon vertex[0]
 383     */
 384    if (n >= 3) {
 385       if (clipper->flat) {
 386          if (stage->draw->rasterizer->flatshade_first) {
 387             if (inlist[0] != header->v[0]) {
 388                assert(tmpnr < MAX_CLIPPED_VERTICES + 1);
 389                if (tmpnr >= MAX_CLIPPED_VERTICES + 1)
 390                   return;
 391                inlist[0] = dup_vert(stage, inlist[0], tmpnr++);
 392                copy_colors(stage, inlist[0], header->v[0]);
 393             }
 394          }
 395          else {
 396             if (inlist[0] != header->v[2]) {
 397                assert(tmpnr < MAX_CLIPPED_VERTICES + 1);
 398                if (tmpnr >= MAX_CLIPPED_VERTICES + 1)
 399                   return;
 400                inlist[0] = dup_vert(stage, inlist[0], tmpnr++);
 401                copy_colors(stage, inlist[0], header->v[2]);
 402             }
 403          }
 404       }
 405
 406       /* Emit the polygon as triangles to the setup stage:
 407        */
 408       emit_poly( stage, inlist, inEdges, n, header );
 409    }
 410 }
 411
 412
 413 /* Clip a line against the viewport and user clip planes.
 414  */
 415 static void
 416 do_clip_line( struct draw_stage *stage,
 417               struct prim_header *header,
 418               unsigned clipmask )
 419 {
 420    const struct clip_stage *clipper = clip_stage( stage );
 421    struct vertex_header *v0 = header->v[0];
 422    struct vertex_header *v1 = header->v[1];
 423    const float *pos0 = v0->clip;
 424    const float *pos1 = v1->clip;
 425    float t0 = 0.0F;
 426    float t1 = 0.0F;
 427    struct prim_header newprim;
 428
 429    while (clipmask) {
 430       const unsigned plane_idx = ffs(clipmask)-1;
 431       const float *plane = clipper->plane[plane_idx];
 432       const float dp0 = dot4( pos0, plane );
 433       const float dp1 = dot4( pos1, plane );
 434
 435       if (dp1 < 0.0F) {
 436          float t = dp1 / (dp1 - dp0);
 437          t1 = MAX2(t1, t);
 438       }
 439
 440       if (dp0 < 0.0F) {
 441          float t = dp0 / (dp0 - dp1);
 442          t0 = MAX2(t0, t);
 443       }
 444
 445       if (t0 + t1 >= 1.0F)
 446          return; /* discard */
 447
 448       clipmask &= ~(1 << plane_idx);  /* turn off this plane's bit */
 449    }
 450
 451    if (v0->clipmask) {
 452       interp( clipper, stage->tmp[0], t0, v0, v1 );
 453
 454       if (clipper->flat)
 455          copy_colors(stage, stage->tmp[0], v0);
 456
 457       newprim.v[0] = stage->tmp[0];
 458    }
 459    else {
 460       newprim.v[0] = v0;
 461    }
 462
 463    if (v1->clipmask) {
 464       interp( clipper, stage->tmp[1], t1, v1, v0 );
 465       newprim.v[1] = stage->tmp[1];
 466    }
 467    else {
 468       newprim.v[1] = v1;
 469    }
 470
 471    stage->next->line( stage->next, &newprim );
 472 }
 473
 474
 475 static void
 476 clip_point( struct draw_stage *stage,
 477             struct prim_header *header )
 478 {
 479    if (header->v[0]->clipmask == 0)
 480       stage->next->point( stage->next, header );
 481 }
 482
 483
 484 static void
 485 clip_line( struct draw_stage *stage,
 486            struct prim_header *header )
 487 {
 488    unsigned clipmask = (header->v[0]->clipmask |
 489                         header->v[1]->clipmask);
 490
 491    if (clipmask == 0) {
 492       /* no clipping needed */
 493       stage->next->line( stage->next, header );
 494    }
 495    else if ((header->v[0]->clipmask &
 496              header->v[1]->clipmask) == 0) {
 497       do_clip_line(stage, header, clipmask);
 498    }
 499    /* else, totally clipped */
 500 }
 501
 502
 503 static void
 504 clip_tri( struct draw_stage *stage,
 505           struct prim_header *header )
 506 {
 507    unsigned clipmask = (header->v[0]->clipmask |
 508                         header->v[1]->clipmask |
 509                         header->v[2]->clipmask);
 510
 511    if (clipmask == 0) {
 512       /* no clipping needed */
 513       stage->next->tri( stage->next, header );
 514    }
 515    else if ((header->v[0]->clipmask &
 516              header->v[1]->clipmask &
 517              header->v[2]->clipmask) == 0) {
 518       do_clip_tri(stage, header, clipmask);
 519    }
 520 }
 521
 522
 523 /* Update state.  Could further delay this until we hit the first
 524  * primitive that really requires clipping.
 525  */
 526 static void
 527 clip_init_state( struct draw_stage *stage )
 528 {
 529    struct clip_stage *clipper = clip_stage( stage );
 530
 531    clipper->flat = stage->draw->rasterizer->flatshade ? TRUE : FALSE;
 532
 533    if (clipper->flat) {
 534       const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader;
 535       uint i;
 536
 537       clipper->num_color_attribs = 0;
 538       for (i = 0; i < vs->info.num_outputs; i++) {
 539          if (vs->info.output_semantic_name[i] == TGSI_SEMANTIC_COLOR ||
 540              vs->info.output_semantic_name[i] == TGSI_SEMANTIC_BCOLOR) {
 541             clipper->color_attribs[clipper->num_color_attribs++] = i;
 542          }
 543       }
 544    }
 545
 546    stage->tri = clip_tri;
 547    stage->line = clip_line;
 548 }
 549
 550
 551
 552 static void clip_first_tri( struct draw_stage *stage,
 553                             struct prim_header *header )
 554 {
 555    clip_init_state( stage );
 556    stage->tri( stage, header );
 557 }
 558
 559 static void clip_first_line( struct draw_stage *stage,
 560                              struct prim_header *header )
 561 {
 562    clip_init_state( stage );
 563    stage->line( stage, header );
 564 }
 565
 566
 567 static void clip_flush( struct draw_stage *stage,
 568                              unsigned flags )
 569 {
 570    stage->tri = clip_first_tri;
 571    stage->line = clip_first_line;
 572    stage->next->flush( stage->next, flags );
 573 }
 574
 575
 576 static void clip_reset_stipple_counter( struct draw_stage *stage )
 577 {
 578    stage->next->reset_stipple_counter( stage->next );
 579 }
 580
 581
 582 static void clip_destroy( struct draw_stage *stage )
 583 {
 584    draw_free_temp_verts( stage );
 585    FREE( stage );
 586 }
 587
 588
 589 /**
 590  * Allocate a new clipper stage.
 591  * \return pointer to new stage object
 592  */
 593 struct draw_stage *draw_clip_stage( struct draw_context *draw )
 594 {
 595    struct clip_stage *clipper = CALLOC_STRUCT(clip_stage);
 596    if (clipper == NULL)
 597       goto fail;
 598
 599    clipper->stage.draw = draw;
 600    clipper->stage.name = "clipper";
 601    clipper->stage.point = clip_point;
 602    clipper->stage.line = clip_first_line;
 603    clipper->stage.tri = clip_first_tri;
 604    clipper->stage.flush = clip_flush;
 605    clipper->stage.reset_stipple_counter = clip_reset_stipple_counter;
 606    clipper->stage.destroy = clip_destroy;
 607
 608    clipper->plane = draw->plane;
 609
 610    if (!draw_alloc_temp_verts( &clipper->stage, MAX_CLIPPED_VERTICES+1 ))
 611       goto fail;
 612
 613    return &clipper->stage;
 614
 615  fail:
 616    if (clipper)
 617       clipper->stage.destroy( &clipper->stage );
 618
 619    return NULL;
 620 }