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