src/mesa/pipe/draw/draw_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 "draw_context.h"
  37 #include "draw_private.h"
  38
  39
  40 #ifndef IS_NEGATIVE
  41 #define IS_NEGATIVE(X) ((X) < 0.0)
  42 #endif
  43
  44 #ifndef DIFFERENT_SIGNS
  45 #define DIFFERENT_SIGNS(x, y) ((x) * (y) <= 0.0F && (x) - (y) != 0.0F)
  46 #endif
  47
  48 #ifndef MAX_CLIPPED_VERTICES
  49 #define MAX_CLIPPED_VERTICES ((2 * (6 + PIPE_MAX_CLIP_PLANES))+1)
  50 #endif
  51
  52
  53
  54 struct clipper {
  55    struct draw_stage stage;      /**< base class */
  56
  57    float (*plane)[4];
  58 };
  59
  60
  61 /* This is a bit confusing:
  62  */
  63 static INLINE struct clipper *clipper_stage( struct draw_stage *stage )
  64 {
  65    return (struct clipper *)stage;
  66 }
  67
  68
  69 #define LINTERP(T, OUT, IN) ((OUT) + (T) * ((IN) - (OUT)))
  70
  71
  72 /* All attributes are float[4], so this is easy:
  73  */
  74 static void interp_attr( float *fdst,
  75                          float t,
  76                          const float *fin,
  77                          const float *fout )
  78 {
  79    fdst[0] = LINTERP( t, fout[0], fin[0] );
  80    fdst[1] = LINTERP( t, fout[1], fin[1] );
  81    fdst[2] = LINTERP( t, fout[2], fin[2] );
  82    fdst[3] = LINTERP( t, fout[3], fin[3] );
  83 }
  84
  85
  86
  87
  88 /* Interpolate between two vertices to produce a third.
  89  */
  90 static void interp( const struct clipper *clip,
  91                     struct vertex_header *dst,
  92                     float t,
  93                     const struct vertex_header *out,
  94                     const struct vertex_header *in )
  95 {
  96    const unsigned nr_attrs = clip->stage.draw->vertex_info.num_attribs;
  97    unsigned j;
  98
  99    /* Vertex header.
 100     */
 101    {
 102       dst->clipmask = 0;
 103       dst->edgeflag = 0;
 104       dst->pad = 0;
 105       dst->vertex_id = UNDEFINED_VERTEX_ID;
 106    }
 107
 108    /* Clip coordinates:  interpolate normally
 109     */
 110    {
 111       interp_attr(dst->clip, t, in->clip, out->clip);
 112    }
 113
 114    /* Do the projective divide and insert window coordinates:
 115     */
 116    {
 117       const float *pos = dst->clip;
 118       const float *scale = clip->stage.draw->viewport.scale;
 119       const float *trans = clip->stage.draw->viewport.translate;
 120       const float oow = 1.0f / pos[3];
 121
 122       dst->data[0][0] = pos[0] * oow * scale[0] + trans[0];
 123       dst->data[0][1] = pos[1] * oow * scale[1] + trans[1];
 124       dst->data[0][2] = pos[2] * oow * scale[2] + trans[2];
 125       dst->data[0][3] = oow;
 126    }
 127
 128    /* Other attributes
 129     * Note: start at 1 to skip winpos (data[0]) since we just computed
 130     * it above.
 131     * Subtract two from nr_attrs since the first two attribs (always
 132     * VF_ATTRIB_VERTEX_HEADER and VF_ATTRIB_CLIP_POS, see
 133     * draw_set_vertex_attributes()) are in the vertex_header struct,
 134     * not in the data[] array.
 135     */
 136    for (j = 1; j < nr_attrs - 2; j++) {
 137       interp_attr(dst->data[j], t, in->data[j], out->data[j]);
 138    }
 139 }
 140
 141 #if 0
 142 static INLINE void do_tri( struct draw_stage *next,
 143                            struct prim_header *header )
 144 {
 145    unsigned i;
 146    for (i = 0; i < 3; i++) {
 147       float *ndc = header->v[i]->data[0];
 148       _mesa_printf("ndc %f %f %f\n", ndc[0], ndc[1], ndc[2]);
 149       assert(ndc[0] >= -1 && ndc[0] <= 641);
 150       assert(ndc[1] >= 30 && ndc[1] <= 481);
 151    }
 152    _mesa_printf("\n");
 153    next->tri(next, header);
 154 }
 155 #endif
 156
 157
 158 static void emit_poly( struct draw_stage *stage,
 159                        struct vertex_header **inlist,
 160                        unsigned n,
 161                        const struct prim_header *origPrim)
 162 {
 163    struct prim_header header;
 164    unsigned i;
 165
 166    /* later stages may need the determinant, but only the sign matters */
 167    header.det = origPrim->det;
 168
 169    for (i = 2; i < n; i++) {
 170       header.v[0] = inlist[0];
 171       header.v[1] = inlist[i-1];
 172       header.v[2] = inlist[i];
 173
 174       {
 175          unsigned tmp0 = header.v[0]->edgeflag;
 176          unsigned tmp2 = header.v[2]->edgeflag;
 177
 178          if (i != 2)   header.v[0]->edgeflag = 0;
 179          if (i != n-1) header.v[2]->edgeflag = 0;
 180
 181          header.edgeflags = ((header.v[0]->edgeflag << 0) |
 182                              (header.v[1]->edgeflag << 1) |
 183                              (header.v[2]->edgeflag << 2));
 184
 185          stage->next->tri( stage->next, &header );
 186
 187          header.v[0]->edgeflag = tmp0;
 188          header.v[2]->edgeflag = tmp2;
 189       }
 190    }
 191 }
 192
 193
 194 #if 0
 195 static void emit_poly( struct draw_stage *stage )
 196 {
 197    unsigned i;
 198
 199    for (i = 2; i < n; i++) {
 200       header->v[0] = inlist[0];
 201       header->v[1] = inlist[i-1];
 202       header->v[2] = inlist[i];
 203
 204       stage->next->tri( stage->next, header );
 205    }
 206 }
 207 #endif
 208
 209
 210 /* Clip a triangle against the viewport and user clip planes.
 211  */
 212 static void
 213 do_clip_tri( struct draw_stage *stage,
 214              struct prim_header *header,
 215              unsigned clipmask )
 216 {
 217    struct clipper *clipper = clipper_stage( stage );
 218    struct vertex_header *a[MAX_CLIPPED_VERTICES];
 219    struct vertex_header *b[MAX_CLIPPED_VERTICES];
 220    struct vertex_header **inlist = a;
 221    struct vertex_header **outlist = b;
 222    unsigned tmpnr = 0;
 223    unsigned n = 3;
 224    unsigned i;
 225
 226    inlist[0] = header->v[0];
 227    inlist[1] = header->v[1];
 228    inlist[2] = header->v[2];
 229
 230    while (clipmask && n >= 3) {
 231       const unsigned plane_idx = ffs(clipmask)-1;
 232       const float *plane = clipper->plane[plane_idx];
 233       struct vertex_header *vert_prev = inlist[0];
 234       float dp_prev = dot4( vert_prev->clip, plane );
 235       unsigned outcount = 0;
 236
 237       clipmask &= ~(1<<plane_idx);
 238
 239       inlist[n] = inlist[0]; /* prevent rotation of vertices */
 240
 241       for (i = 1; i <= n; i++) {
 242          struct vertex_header *vert = inlist[i];
 243
 244          float dp = dot4( vert->clip, plane );
 245
 246          if (!IS_NEGATIVE(dp_prev)) {
 247             outlist[outcount++] = vert_prev;
 248          }
 249
 250          if (DIFFERENT_SIGNS(dp, dp_prev)) {
 251             struct vertex_header *new_vert = clipper->stage.tmp[tmpnr++];
 252             outlist[outcount++] = new_vert;
 253
 254             if (IS_NEGATIVE(dp)) {
 255                /* Going out of bounds.  Avoid division by zero as we
 256                 * know dp != dp_prev from DIFFERENT_SIGNS, above.
 257                 */
 258                float t = dp / (dp - dp_prev);
 259                interp( clipper, new_vert, t, vert, vert_prev );
 260
 261                /* Force edgeflag true in this case:
 262                 */
 263                new_vert->edgeflag = 1;
 264             } else {
 265                /* Coming back in.
 266                 */
 267                float t = dp_prev / (dp_prev - dp);
 268                interp( clipper, new_vert, t, vert_prev, vert );
 269
 270                /* Copy starting vert's edgeflag:
 271                 */
 272                new_vert->edgeflag = vert_prev->edgeflag;
 273             }
 274          }
 275
 276          vert_prev = vert;
 277          dp_prev = dp;
 278       }
 279
 280       {
 281          struct vertex_header **tmp = inlist;
 282          inlist = outlist;
 283          outlist = tmp;
 284          n = outcount;
 285       }
 286    }
 287
 288    /* Emit the polygon as triangles to the setup stage:
 289     */
 290    if (n >= 3)
 291       emit_poly( stage, inlist, n, header );
 292 }
 293
 294
 295 /* Clip a line against the viewport and user clip planes.
 296  */
 297 static void
 298 do_clip_line( struct draw_stage *stage,
 299               struct prim_header *header,
 300               unsigned clipmask )
 301 {
 302    const struct clipper *clipper = clipper_stage( stage );
 303    struct vertex_header *v0 = header->v[0];
 304    struct vertex_header *v1 = header->v[1];
 305    const float *pos0 = v0->clip;
 306    const float *pos1 = v1->clip;
 307    float t0 = 0.0F;
 308    float t1 = 0.0F;
 309    struct prim_header newprim;
 310
 311    while (clipmask) {
 312       const unsigned plane_idx = ffs(clipmask)-1;
 313       const float *plane = clipper->plane[plane_idx];
 314       const float dp0 = dot4( pos0, plane );
 315       const float dp1 = dot4( pos1, plane );
 316
 317       if (dp1 < 0.0F) {
 318          float t = dp1 / (dp1 - dp0);
 319          t1 = MAX2(t1, t);
 320       }
 321
 322       if (dp0 < 0.0F) {
 323          float t = dp0 / (dp0 - dp1);
 324          t0 = MAX2(t0, t);
 325       }
 326
 327       if (t0 + t1 >= 1.0F)
 328          return; /* discard */
 329
 330       clipmask &= ~(1 << plane_idx);  /* turn off this plane's bit */
 331    }
 332
 333    if (v0->clipmask) {
 334       interp( clipper, stage->tmp[0], t0, v0, v1 );
 335       newprim.v[0] = stage->tmp[0];
 336    }
 337    else {
 338       newprim.v[0] = v0;
 339    }
 340
 341    if (v1->clipmask) {
 342       interp( clipper, stage->tmp[1], t1, v1, v0 );
 343       newprim.v[1] = stage->tmp[1];
 344    }
 345    else {
 346       newprim.v[1] = v1;
 347    }
 348
 349    stage->next->line( stage->next, &newprim );
 350 }
 351
 352
 353 static void clip_begin( struct draw_stage *stage )
 354 {
 355    /* sanity checks.  If these fail, review the clip/interp code! */
 356    assert(stage->draw->vertex_info.num_attribs >= 3);
 357 #if 0
 358    assert(stage->draw->vertex_info.slot_to_attrib[0] == TGSI_ATTRIB_VERTEX_HEADER);
 359    assert(stage->draw->vertex_info.slot_to_attrib[1] == TGSI_ATTRIB_CLIP_POS);
 360 #endif
 361
 362    stage->next->begin( stage->next );
 363 }
 364
 365
 366 static void
 367 clip_point( struct draw_stage *stage,
 368             struct prim_header *header )
 369 {
 370    if (header->v[0]->clipmask == 0)
 371       stage->next->point( stage->next, header );
 372 }
 373
 374
 375 static void
 376 clip_line( struct draw_stage *stage,
 377            struct prim_header *header )
 378 {
 379    unsigned clipmask = (header->v[0]->clipmask |
 380                         header->v[1]->clipmask);
 381
 382    if (clipmask == 0) {
 383       /* no clipping needed */
 384       stage->next->line( stage->next, header );
 385    }
 386    else if ((header->v[0]->clipmask &
 387              header->v[1]->clipmask) == 0) {
 388       do_clip_line(stage, header, clipmask);
 389    }
 390    /* else, totally clipped */
 391 }
 392
 393
 394 static void
 395 clip_tri( struct draw_stage *stage,
 396           struct prim_header *header )
 397 {
 398    unsigned clipmask = (header->v[0]->clipmask |
 399                         header->v[1]->clipmask |
 400                         header->v[2]->clipmask);
 401
 402    if (clipmask == 0) {
 403       /* no clipping needed */
 404       stage->next->tri( stage->next, header );
 405    }
 406    else if ((header->v[0]->clipmask &
 407              header->v[1]->clipmask &
 408              header->v[2]->clipmask) == 0) {
 409       do_clip_tri(stage, header, clipmask);
 410    }
 411 }
 412
 413
 414 static void clip_end( struct draw_stage *stage )
 415 {
 416    stage->next->end( stage->next );
 417 }
 418
 419
 420 static void clip_reset_stipple_counter( struct draw_stage *stage )
 421 {
 422    stage->next->reset_stipple_counter( stage->next );
 423 }
 424
 425
 426 /**
 427  * Allocate a new clipper stage.
 428  * \return pointer to new stage object
 429  */
 430 struct draw_stage *draw_clip_stage( struct draw_context *draw )
 431 {
 432    struct clipper *clipper = CALLOC_STRUCT(clipper);
 433
 434    draw_alloc_tmps( &clipper->stage, MAX_CLIPPED_VERTICES );
 435
 436    clipper->stage.draw = draw;
 437    clipper->stage.begin = clip_begin;
 438    clipper->stage.point = clip_point;
 439    clipper->stage.line = clip_line;
 440    clipper->stage.tri = clip_tri;
 441    clipper->stage.end = clip_end;
 442    clipper->stage.reset_stipple_counter = clip_reset_stipple_counter;
 443
 444    clipper->plane = draw->plane;
 445
 446    return &clipper->stage;
 447 }