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