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