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 /* This is a bit confusing:
  72  */
  73 static INLINE struct clip_stage *clip_stage( struct draw_stage *stage )
  74 {
  75    return (struct clip_stage *)stage;
  76 }
  77
  78
  79 #define LINTERP(T, OUT, IN) ((OUT) + (T) * ((IN) - (OUT)))
  80
  81
  82 /* All attributes are float[4], so this is easy:
  83  */
  84 static void interp_attr( float *fdst,
  85                          float t,
  86                          const float *fin,
  87                          const float *fout )
  88 {
  89    fdst[0] = LINTERP( t, fout[0], fin[0] );
  90    fdst[1] = LINTERP( t, fout[1], fin[1] );
  91    fdst[2] = LINTERP( t, fout[2], fin[2] );
  92    fdst[3] = LINTERP( t, fout[3], fin[3] );
  93 }
  94
  95
  96 static void copy_colors( struct draw_stage *stage,
  97                          struct vertex_header *dst,
  98                          const struct vertex_header *src )
  99 {
 100    const struct clip_stage *clipper = clip_stage(stage);
 101    uint i;
 102    for (i = 0; i < clipper->num_color_attribs; i++) {
 103       const uint attr = clipper->color_attribs[i];
 104       COPY_4FV(dst->data[attr], src->data[attr]);
 105    }
 106 }
 107
 108
 109
 110 /* Interpolate between two vertices to produce a third.
 111  */
 112 static void interp( const struct clip_stage *clip,
 113                     struct vertex_header *dst,
 114                     float t,
 115                     const struct vertex_header *out,
 116                     const struct vertex_header *in )
 117 {
 118    const unsigned nr_attrs = draw_current_shader_outputs(clip->stage.draw);
 119    const unsigned pos_attr = draw_current_shader_position_output(clip->stage.draw);
 120    unsigned j;
 121
 122    /* Vertex header.
 123     */
 124    {
 125       dst->clipmask = 0;
 126       dst->edgeflag = 0;        /* will get overwritten later */
 127       dst->pad = 0;
 128       dst->vertex_id = UNDEFINED_VERTEX_ID;
 129    }
 130
 131    /* Clip coordinates:  interpolate normally
 132     */
 133    {
 134       interp_attr(dst->clip, t, in->clip, out->clip);
 135    }
 136
 137    /* Do the projective divide and insert 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                        unsigned n,
 167                        const struct prim_header *origPrim)
 168 {
 169    struct prim_header header;
 170    unsigned i;
 171    ushort edge_first, edge_middle, edge_last;
 172
 173    if (stage->draw->rasterizer->flatshade_first) {
 174       edge_first  = DRAW_PIPE_EDGE_FLAG_0;
 175       edge_middle = DRAW_PIPE_EDGE_FLAG_1;
 176       edge_last   = DRAW_PIPE_EDGE_FLAG_2;
 177    }
 178    else {
 179       edge_first  = DRAW_PIPE_EDGE_FLAG_2;
 180       edge_middle = DRAW_PIPE_EDGE_FLAG_0;
 181       edge_last   = DRAW_PIPE_EDGE_FLAG_1;
 182    }
 183
 184    /* later stages may need the determinant, but only the sign matters */
 185    header.det = origPrim->det;
 186    header.flags = DRAW_PIPE_RESET_STIPPLE | edge_first | edge_middle;
 187    header.pad = 0;
 188
 189    for (i = 2; i < n; i++, header.flags = edge_middle) {
 190       /* order the triangle verts to respect the provoking vertex mode */
 191       if (stage->draw->rasterizer->flatshade_first) {
 192          header.v[0] = inlist[0];  /* the provoking vertex */
 193          header.v[1] = inlist[i-1];
 194          header.v[2] = inlist[i];
 195       }
 196       else {
 197          header.v[0] = inlist[i-1];
 198          header.v[1] = inlist[i];
 199          header.v[2] = inlist[0];  /* the provoking vertex */
 200       }
 201
 202       if (i == n-1)
 203          header.flags |= edge_last;
 204
 205       if (0) {
 206          const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader;
 207          uint j, k;
 208          debug_printf("Clipped tri: (flat-shade-first = %d)\n",
 209                       stage->draw->rasterizer->flatshade_first);
 210          for (j = 0; j < 3; j++) {
 211             for (k = 0; k < vs->info.num_outputs; k++) {
 212                debug_printf("  Vert %d: Attr %d:  %f %f %f %f\n", j, k,
 213                             header.v[j]->data[k][0],
 214                             header.v[j]->data[k][1],
 215                             header.v[j]->data[k][2],
 216                             header.v[j]->data[k][3]);
 217             }
 218          }
 219       }
 220
 221       stage->next->tri( stage->next, &header );
 222    }
 223 }
 224
 225
 226 static INLINE float
 227 dot4(const float *a, const float *b)
 228 {
 229    return (a[0] * b[0] +
 230            a[1] * b[1] +
 231            a[2] * b[2] +
 232            a[3] * b[3]);
 233 }
 234
 235
 236 /* Clip a triangle against the viewport and user clip planes.
 237  */
 238 static void
 239 do_clip_tri( struct draw_stage *stage,
 240              struct prim_header *header,
 241              unsigned clipmask )
 242 {
 243    struct clip_stage *clipper = clip_stage( stage );
 244    struct vertex_header *a[MAX_CLIPPED_VERTICES];
 245    struct vertex_header *b[MAX_CLIPPED_VERTICES];
 246    struct vertex_header **inlist = a;
 247    struct vertex_header **outlist = b;
 248    unsigned tmpnr = 0;
 249    unsigned n = 3;
 250    unsigned i;
 251
 252    inlist[0] = header->v[0];
 253    inlist[1] = header->v[1];
 254    inlist[2] = header->v[2];
 255
 256    while (clipmask && n >= 3) {
 257       const unsigned plane_idx = ffs(clipmask)-1;
 258       const float *plane = clipper->plane[plane_idx];
 259       struct vertex_header *vert_prev = inlist[0];
 260       float dp_prev = dot4( vert_prev->clip, plane );
 261       unsigned outcount = 0;
 262
 263       clipmask &= ~(1<<plane_idx);
 264
 265       assert(n < MAX_CLIPPED_VERTICES);
 266       inlist[n] = inlist[0]; /* prevent rotation of vertices */
 267
 268       for (i = 1; i <= n; i++) {
 269          struct vertex_header *vert = inlist[i];
 270
 271          float dp = dot4( vert->clip, plane );
 272
 273          if (!IS_NEGATIVE(dp_prev)) {
 274             assert(outcount < MAX_CLIPPED_VERTICES);
 275             outlist[outcount++] = vert_prev;
 276          }
 277
 278          if (DIFFERENT_SIGNS(dp, dp_prev)) {
 279             struct vertex_header *new_vert;
 280
 281             assert(tmpnr < MAX_CLIPPED_VERTICES+1);
 282             new_vert = clipper->stage.tmp[tmpnr++];
 283
 284             assert(outcount < MAX_CLIPPED_VERTICES);
 285             outlist[outcount++] = new_vert;
 286
 287             if (IS_NEGATIVE(dp)) {
 288                /* Going out of bounds.  Avoid division by zero as we
 289                 * know dp != dp_prev from DIFFERENT_SIGNS, above.
 290                 */
 291                float t = dp / (dp - dp_prev);
 292                interp( clipper, new_vert, t, vert, vert_prev );
 293
 294                /* Force edgeflag true in this case:
 295                 */
 296                new_vert->edgeflag = 1;
 297             } else {
 298                /* Coming back in.
 299                 */
 300                float t = dp_prev / (dp_prev - dp);
 301                interp( clipper, new_vert, t, vert_prev, vert );
 302
 303                /* Copy starting vert's edgeflag:
 304                 */
 305                new_vert->edgeflag = vert_prev->edgeflag;
 306             }
 307          }
 308
 309          vert_prev = vert;
 310          dp_prev = dp;
 311       }
 312
 313       /* swap in/out lists */
 314       {
 315          struct vertex_header **tmp = inlist;
 316          inlist = outlist;
 317          outlist = tmp;
 318          n = outcount;
 319       }
 320    }
 321
 322    /* If flat-shading, copy provoking vertex color to polygon vertex[0]
 323     */
 324    if (clipper->flat) {
 325       if (stage->draw->rasterizer->flatshade_first) {
 326          if (inlist[0] != header->v[0]) {
 327             assert(tmpnr < MAX_CLIPPED_VERTICES + 1);
 328             inlist[0] = dup_vert(stage, inlist[0], tmpnr++);
 329             copy_colors(stage, inlist[0], header->v[0]);
 330          }
 331       }
 332       else {
 333          if (inlist[0] != header->v[2]) {
 334             assert(tmpnr < MAX_CLIPPED_VERTICES + 1);
 335             inlist[0] = dup_vert(stage, inlist[0], tmpnr++);
 336             copy_colors(stage, inlist[0], header->v[2]);
 337          }
 338       }
 339    }
 340
 341    /* Emit the polygon as triangles to the setup stage:
 342     */
 343    if (n >= 3)
 344       emit_poly( stage, inlist, n, header );
 345 }
 346
 347
 348 /* Clip a line against the viewport and user clip planes.
 349  */
 350 static void
 351 do_clip_line( struct draw_stage *stage,
 352               struct prim_header *header,
 353               unsigned clipmask )
 354 {
 355    const struct clip_stage *clipper = clip_stage( stage );
 356    struct vertex_header *v0 = header->v[0];
 357    struct vertex_header *v1 = header->v[1];
 358    const float *pos0 = v0->clip;
 359    const float *pos1 = v1->clip;
 360    float t0 = 0.0F;
 361    float t1 = 0.0F;
 362    struct prim_header newprim;
 363
 364    while (clipmask) {
 365       const unsigned plane_idx = ffs(clipmask)-1;
 366       const float *plane = clipper->plane[plane_idx];
 367       const float dp0 = dot4( pos0, plane );
 368       const float dp1 = dot4( pos1, plane );
 369
 370       if (dp1 < 0.0F) {
 371          float t = dp1 / (dp1 - dp0);
 372          t1 = MAX2(t1, t);
 373       }
 374
 375       if (dp0 < 0.0F) {
 376          float t = dp0 / (dp0 - dp1);
 377          t0 = MAX2(t0, t);
 378       }
 379
 380       if (t0 + t1 >= 1.0F)
 381          return; /* discard */
 382
 383       clipmask &= ~(1 << plane_idx);  /* turn off this plane's bit */
 384    }
 385
 386    if (v0->clipmask) {
 387       interp( clipper, stage->tmp[0], t0, v0, v1 );
 388
 389       if (clipper->flat)
 390          copy_colors(stage, stage->tmp[0], v0);
 391
 392       newprim.v[0] = stage->tmp[0];
 393    }
 394    else {
 395       newprim.v[0] = v0;
 396    }
 397
 398    if (v1->clipmask) {
 399       interp( clipper, stage->tmp[1], t1, v1, v0 );
 400       newprim.v[1] = stage->tmp[1];
 401    }
 402    else {
 403       newprim.v[1] = v1;
 404    }
 405
 406    stage->next->line( stage->next, &newprim );
 407 }
 408
 409
 410 static void
 411 clip_point( struct draw_stage *stage,
 412             struct prim_header *header )
 413 {
 414    if (header->v[0]->clipmask == 0)
 415       stage->next->point( stage->next, header );
 416 }
 417
 418
 419 static void
 420 clip_line( struct draw_stage *stage,
 421            struct prim_header *header )
 422 {
 423    unsigned clipmask = (header->v[0]->clipmask |
 424                         header->v[1]->clipmask);
 425
 426    if (clipmask == 0) {
 427       /* no clipping needed */
 428       stage->next->line( stage->next, header );
 429    }
 430    else if ((header->v[0]->clipmask &
 431              header->v[1]->clipmask) == 0) {
 432       do_clip_line(stage, header, clipmask);
 433    }
 434    /* else, totally clipped */
 435 }
 436
 437
 438 static void
 439 clip_tri( struct draw_stage *stage,
 440           struct prim_header *header )
 441 {
 442    unsigned clipmask = (header->v[0]->clipmask |
 443                         header->v[1]->clipmask |
 444                         header->v[2]->clipmask);
 445
 446    if (clipmask == 0) {
 447       /* no clipping needed */
 448       stage->next->tri( stage->next, header );
 449    }
 450    else if ((header->v[0]->clipmask &
 451              header->v[1]->clipmask &
 452              header->v[2]->clipmask) == 0) {
 453       do_clip_tri(stage, header, clipmask);
 454    }
 455 }
 456
 457
 458 /* Update state.  Could further delay this until we hit the first
 459  * primitive that really requires clipping.
 460  */
 461 static void
 462 clip_init_state( struct draw_stage *stage )
 463 {
 464    struct clip_stage *clipper = clip_stage( stage );
 465
 466    clipper->flat = stage->draw->rasterizer->flatshade ? TRUE : FALSE;
 467
 468    if (clipper->flat) {
 469       const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader;
 470       uint i;
 471
 472       clipper->num_color_attribs = 0;
 473       for (i = 0; i < vs->info.num_outputs; i++) {
 474          if (vs->info.output_semantic_name[i] == TGSI_SEMANTIC_COLOR ||
 475              vs->info.output_semantic_name[i] == TGSI_SEMANTIC_BCOLOR) {
 476             clipper->color_attribs[clipper->num_color_attribs++] = i;
 477          }
 478       }
 479    }
 480
 481    stage->tri = clip_tri;
 482    stage->line = clip_line;
 483 }
 484
 485
 486
 487 static void clip_first_tri( struct draw_stage *stage,
 488                             struct prim_header *header )
 489 {
 490    clip_init_state( stage );
 491    stage->tri( stage, header );
 492 }
 493
 494 static void clip_first_line( struct draw_stage *stage,
 495                              struct prim_header *header )
 496 {
 497    clip_init_state( stage );
 498    stage->line( stage, header );
 499 }
 500
 501
 502 static void clip_flush( struct draw_stage *stage,
 503                              unsigned flags )
 504 {
 505    stage->tri = clip_first_tri;
 506    stage->line = clip_first_line;
 507    stage->next->flush( stage->next, flags );
 508 }
 509
 510
 511 static void clip_reset_stipple_counter( struct draw_stage *stage )
 512 {
 513    stage->next->reset_stipple_counter( stage->next );
 514 }
 515
 516
 517 static void clip_destroy( struct draw_stage *stage )
 518 {
 519    draw_free_temp_verts( stage );
 520    FREE( stage );
 521 }
 522
 523
 524 /**
 525  * Allocate a new clipper stage.
 526  * \return pointer to new stage object
 527  */
 528 struct draw_stage *draw_clip_stage( struct draw_context *draw )
 529 {
 530    struct clip_stage *clipper = CALLOC_STRUCT(clip_stage);
 531    if (clipper == NULL)
 532       goto fail;
 533
 534    clipper->stage.draw = draw;
 535    clipper->stage.name = "clipper";
 536    clipper->stage.point = clip_point;
 537    clipper->stage.line = clip_first_line;
 538    clipper->stage.tri = clip_first_tri;
 539    clipper->stage.flush = clip_flush;
 540    clipper->stage.reset_stipple_counter = clip_reset_stipple_counter;
 541    clipper->stage.destroy = clip_destroy;
 542
 543    clipper->plane = draw->plane;
 544
 545    if (!draw_alloc_temp_verts( &clipper->stage, MAX_CLIPPED_VERTICES+1 ))
 546       goto fail;
 547
 548    return &clipper->stage;
 549
 550  fail:
 551    if (clipper)
 552       clipper->stage.destroy( &clipper->stage );
 553
 554    return NULL;
 555 }