src/mesa/tnl/t_vb_cliptmp.h

   1 /* $Id: t_vb_cliptmp.h,v 1.2 2000/12/27 19:57:37 keithw Exp $ */
   2
   3 /*
   4  * Mesa 3-D graphics library
   5  * Version:  3.5
   6  *
   7  * Copyright (C) 1999  Brian Paul   All Rights Reserved.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining a
  10  * copy of this software and associated documentation files (the "Software"),
  11  * to deal in the Software without restriction, including without limitation
  12  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13  * and/or sell copies of the Software, and to permit persons to whom the
  14  * Software is furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included
  17  * in all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  * Author:
  27  *    Keith Whitwell <keithw@valinux.com>
  28  */
  29
  30
  31 #define INSIDE( J ) !NEGATIVE(J)
  32 #define OUTSIDE( J ) NEGATIVE(J)
  33
  34
  35
  36
  37 static GLuint TAG(userclip_line)( GLcontext *ctx,
  38                                   GLuint *i, GLuint *j,
  39                                   interp_func interp )
  40 {
  41    struct vertex_buffer *VB = &TNL_CONTEXT(ctx)->vb;
  42    GLfloat (*coord)[4] = VB->ClipPtr->data;
  43    GLuint ii = *i;
  44    GLuint jj = *j;
  45    GLuint p;
  46
  47    for (p=0;p<MAX_CLIP_PLANES;p++) {
  48       if (ctx->Transform.ClipEnabled[p]) {
  49          GLfloat a = ctx->Transform._ClipUserPlane[p][0];
  50          GLfloat b = ctx->Transform._ClipUserPlane[p][1];
  51          GLfloat c = ctx->Transform._ClipUserPlane[p][2];
  52          GLfloat d = ctx->Transform._ClipUserPlane[p][3];
  53
  54          GLfloat dpI = d*W(ii) + c*Z(ii) + b*Y(ii) + a*X(ii);
  55          GLfloat dpJ = d*W(jj) + c*Z(jj) + b*Y(jj) + a*X(jj);
  56
  57          GLuint flagI = OUTSIDE( dpI );
  58          GLuint flagJ = OUTSIDE( dpJ );
  59
  60          if (flagI ^ flagJ) {
  61             if (flagJ) {
  62                GLfloat t = dpI / (dpI - dpJ);
  63                VB->ClipMask[jj] |= CLIP_USER_BIT;
  64                jj = interp( ctx, t, ii, jj, GL_FALSE );
  65                VB->ClipMask[jj] = 0;
  66             } else {
  67                GLfloat t = dpJ / (dpJ - dpI);
  68                VB->ClipMask[ii] |= CLIP_USER_BIT;
  69                ii = interp( ctx, t, jj, ii, GL_FALSE );
  70                VB->ClipMask[ii] = 0;
  71             }
  72          }
  73          else if (flagI)
  74             return 0;
  75       }
  76    }
  77
  78    *i = ii;
  79    *j = jj;
  80    return 1;
  81 }
  82
  83
  84 static GLuint TAG(userclip_polygon)( GLcontext *ctx,
  85                                      GLuint n,
  86                                      GLuint vlist[],
  87                                      interp_func interp )
  88 {
  89    struct vertex_buffer *VB = &TNL_CONTEXT(ctx)->vb;
  90    GLfloat (*coord)[4] = VB->ClipPtr->data;
  91    GLuint vlist2[MAX_CLIPPED_VERTICES];
  92    GLuint *inlist = vlist, *outlist = vlist2;
  93    GLubyte *clipmask = VB->ClipMask;
  94    GLuint p;
  95
  96 #define CLIP_DOTPROD(xx) d*W(xx) + c*Z(xx) + b*Y(xx) + a*X(xx)
  97
  98    /* Can be speeded up to if vertex_stage actually saves the
  99     * UserClipMask, and if it is used in this loop (after computing a
 100     * UserClipOrMask).
 101     */
 102    for (p=0;p<MAX_CLIP_PLANES;p++) {
 103       if (ctx->Transform.ClipEnabled[p]) {
 104          register float a = ctx->Transform._ClipUserPlane[p][0];
 105          register float b = ctx->Transform._ClipUserPlane[p][1];
 106          register float c = ctx->Transform._ClipUserPlane[p][2];
 107          register float d = ctx->Transform._ClipUserPlane[p][3];
 108
 109          /* initialize prev to be last in the input list */
 110          GLuint idxPrev = inlist[n-1];
 111          GLfloat dpPrev = CLIP_DOTPROD(idxPrev);
 112          GLuint outcount = 0;
 113          GLuint i;
 114
 115          for (i = 0 ; i < n ; i++) {
 116             GLuint idx = inlist[i];
 117             GLfloat dp = CLIP_DOTPROD(idx);
 118
 119             if (!NEGATIVE(dpPrev)) {
 120                outlist[outcount++] = idxPrev;
 121                clipmask[idxPrev] &= ~CLIP_USER_BIT;
 122             } else {
 123                clipmask[idxPrev] |= CLIP_USER_BIT;
 124             }
 125
 126
 127             if (DIFFERENT_SIGNS(dp, dpPrev)) {
 128                GLuint newvert;
 129                if (NEGATIVE(dp)) {
 130                   /* Going out of bounds.  Avoid division by zero as we
 131                    * know dp != dpPrev from DIFFERENT_SIGNS, above.
 132                    */
 133                   GLfloat t = dp / (dp - dpPrev);
 134                   newvert = interp( ctx, t, idx, idxPrev, GL_TRUE );
 135 /*                fprintf(stderr,"Goint out: in: %d/%d out: %d/%d new: %d/%d\n", */
 136 /*                        idxPrev, VB->EdgeFlagPtr->data[idxPrev], */
 137 /*                        idx, VB->EdgeFlagPtr->data[idx], */
 138 /*                        newvert, VB->EdgeFlagPtr->data[newvert]); */
 139                } else {
 140                   /* Coming back in.
 141                    */
 142                   GLfloat t = dpPrev / (dpPrev - dp);
 143                   newvert = interp( ctx, t, idxPrev, idx, GL_FALSE );
 144 /*                fprintf(stderr,"coming in: in: %d/%d out: %d/%d new: %d/%d\n", */
 145 /*                        idx, VB->EdgeFlagPtr->data[idx], */
 146 /*                        idxPrev, VB->EdgeFlagPtr->data[idxPrev], */
 147 /*                        newvert, VB->EdgeFlagPtr->data[newvert]); */
 148                }
 149                clipmask[newvert] = 0;
 150                outlist[outcount++] = newvert;
 151             }
 152
 153             idxPrev = idx;
 154             dpPrev = dp;
 155          }
 156
 157          if (outcount < 3)
 158             return 0;
 159
 160          {
 161             GLuint *tmp;
 162             tmp = inlist;
 163             inlist = outlist;
 164             outlist = tmp;
 165             n = outcount;
 166          }
 167       } /* if */
 168    } /* for p */
 169
 170    if (inlist!=vlist) {
 171       GLuint i;
 172       for (i = 0 ; i < n ; i++)
 173          vlist[i] = inlist[i];
 174    }
 175
 176 /*     fprintf(stderr, "%s: finally:\n", __FUNCTION__); */
 177 /*     for (i = 0 ; i < n ; i++)  */
 178 /*        fprintf(stderr, "%d: %d\n", vlist[i], VB->EdgeFlagPtr->data[vlist[i]]); */
 179
 180    return n;
 181 }
 182
 183
 184 /* This now calls the user clip functions if required.
 185  */
 186 static void TAG(viewclip_line)( GLcontext *ctx,
 187                                 GLuint i, GLuint j,
 188                                 GLubyte mask )
 189 {
 190    struct vertex_buffer *VB = &TNL_CONTEXT(ctx)->vb;
 191    interp_func interp = (interp_func) VB->interpfunc;
 192    GLfloat (*coord)[4] = VB->ClipPtr->data;
 193    GLuint ii = i, jj = j;
 194    GLuint vlist[2];
 195    GLuint n;
 196
 197    VB->LastClipped = VB->FirstClipped;
 198
 199 /*
 200  * We use 6 instances of this code to clip against the 6 planes.
 201  */
 202 #define GENERAL_CLIP                                    \
 203    if (mask & PLANE) {                                  \
 204       GLfloat dpI = CLIP_DOTPROD( ii );                 \
 205       GLfloat dpJ = CLIP_DOTPROD( jj );                 \
 206                                                         \
 207       if (DIFFERENT_SIGNS(dpI, dpJ)) {                  \
 208          if (NEGATIVE(dpJ)) {                           \
 209             GLfloat t = dpI / (dpI - dpJ);              \
 210             VB->ClipMask[jj] |= PLANE;                  \
 211             jj = interp( ctx, t, ii, jj, GL_FALSE );    \
 212             VB->ClipMask[jj] = 0;                       \
 213          } else {                                       \
 214             GLfloat t = dpJ / (dpJ - dpI);              \
 215             VB->ClipMask[ii] |= PLANE;                  \
 216             ii = interp( ctx, t, jj, ii, GL_FALSE );    \
 217             VB->ClipMask[ii] = 0;                       \
 218          }                                              \
 219       }                                                 \
 220       else if (NEGATIVE(dpI))                           \
 221          return;                                        \
 222   }
 223
 224 #undef CLIP_DOTPROD
 225 #define PLANE CLIP_RIGHT_BIT
 226 #define CLIP_DOTPROD(K) (- X(K) + W(K))
 227
 228    GENERAL_CLIP
 229
 230 #undef CLIP_DOTPROD
 231 #undef PLANE
 232 #define PLANE CLIP_LEFT_BIT
 233 #define CLIP_DOTPROD(K) (X(K) + W(K))
 234
 235    GENERAL_CLIP
 236
 237 #undef CLIP_DOTPROD
 238 #undef PLANE
 239 #define PLANE CLIP_TOP_BIT
 240 #define CLIP_DOTPROD(K) (- Y(K) + W(K))
 241
 242    GENERAL_CLIP
 243
 244 #undef CLIP_DOTPROD
 245 #undef PLANE
 246 #define PLANE CLIP_BOTTOM_BIT
 247 #define CLIP_DOTPROD(K) (Y(K) + W(K))
 248
 249    GENERAL_CLIP
 250
 251 #undef CLIP_DOTPROD
 252 #undef PLANE
 253 #define PLANE CLIP_FAR_BIT
 254 #define CLIP_DOTPROD(K) (- Z(K) + W(K))
 255
 256    if (SIZE >= 3) {
 257       GENERAL_CLIP
 258    }
 259
 260 #undef CLIP_DOTPROD
 261 #undef PLANE
 262 #define PLANE CLIP_NEAR_BIT
 263 #define CLIP_DOTPROD(K) (Z(K) + W(K))
 264
 265    if (SIZE >=3 ) {
 266       GENERAL_CLIP
 267    }
 268
 269 #undef CLIP_DOTPROD
 270 #undef PLANE
 271 #undef GENERAL_CLIP
 272
 273
 274    if (mask & CLIP_USER_BIT) {
 275       if ( TAG(userclip_line)( ctx, &ii, &jj, interp ) == 0 )
 276          return;
 277    }
 278
 279    vlist[0] = ii;
 280    vlist[1] = jj;
 281    n = 2;
 282
 283    /* If necessary, project new vertices.
 284     */
 285    {
 286       GLuint i, j;
 287       GLfloat (*proj)[4] = VB->ProjectedClipPtr->data;
 288       GLuint start = VB->FirstClipped;
 289
 290       for (i = 0; i < n; i++) {
 291          j = vlist[i];
 292          if (j >= start) {
 293             if (SIZE == 4 && W(j) != 0.0F) {
 294                GLfloat wInv = 1.0F / W(j);
 295                proj[j][0] = X(j) * wInv;
 296                proj[j][1] = Y(j) * wInv;
 297                proj[j][2] = Z(j) * wInv;
 298                proj[j][3] = wInv;
 299             } else {
 300                proj[j][0] = X(j);
 301                proj[j][1] = Y(j);
 302                proj[j][2] = Z(j);
 303                proj[j][3] = W(j);
 304             }
 305          }
 306       }
 307    }
 308
 309    if (ctx->Driver.BuildProjectedVertices)
 310       ctx->Driver.BuildProjectedVertices(ctx,
 311                                          VB->FirstClipped,
 312                                          VB->LastClipped,
 313                                          ~0);
 314
 315
 316    /* Render the new line.
 317     */
 318    ctx->Driver.LineFunc( ctx, ii, jj, j );
 319 }
 320
 321 /* We now clip polygon triangles individually.  This is necessary to
 322  * avoid artifacts dependent on where the boundary of the VB falls
 323  * within the polygon.  As a result, there is an upper bound on the
 324  * number of vertices which may be created, and the test against VB_SIZE
 325  * is redundant.
 326  */
 327 static void TAG(viewclip_polygon)( GLcontext *ctx,
 328                                    GLuint n, GLuint vlist[], GLuint pv,
 329                                    GLubyte mask )
 330 {
 331    struct vertex_buffer *VB = &TNL_CONTEXT(ctx)->vb;
 332    interp_func interp = (interp_func) VB->interpfunc;
 333    GLfloat (*coord)[4] = VB->ClipPtr->data;
 334    GLuint vlist2[MAX_CLIPPED_VERTICES];
 335    GLuint *inlist = vlist, *outlist = vlist2;
 336    GLuint i;
 337    GLubyte *clipmask = VB->ClipMask;
 338
 339    VB->LastClipped = VB->FirstClipped;
 340
 341    if (mask & CLIP_ALL_BITS) {
 342
 343 #define GENERAL_CLIP                                                    \
 344    if (mask & PLANE) {                                                  \
 345       GLuint idxPrev = inlist[n-1];                                     \
 346       GLfloat dpPrev = CLIP_DOTPROD(idxPrev);                           \
 347       GLuint outcount = 0;                                              \
 348       GLuint i;                                                         \
 349                                                                         \
 350       mask &= ~PLANE;                                                   \
 351                                                                         \
 352       for (i = 0; i < n; i++) {                                         \
 353          GLuint idx = inlist[i];                                        \
 354          GLfloat dp = CLIP_DOTPROD(idx);                                \
 355                                                                         \
 356          if (!NEGATIVE(dpPrev)) {                                       \
 357             outlist[outcount++] = idxPrev;                              \
 358             clipmask[idxPrev] &= ~PLANE;                                \
 359          }                                                              \
 360                                                                         \
 361          if (DIFFERENT_SIGNS(dp, dpPrev)) {                             \
 362             GLuint newvert;                                             \
 363             if (NEGATIVE(dp)) {                                         \
 364                /* Going out of bounds.  Avoid division by zero as we    \
 365                 * know dp != dpPrev from DIFFERENT_SIGNS, above.        \
 366                 */                                                      \
 367                GLfloat t = dp / (dp - dpPrev);                          \
 368                newvert = interp( ctx, t, idx, idxPrev, GL_TRUE );       \
 369             } else {                                                    \
 370                /* Coming back in.                                       \
 371                 */                                                      \
 372                GLfloat t = dpPrev / (dpPrev - dp);                      \
 373                newvert = interp( ctx, t, idxPrev, idx, GL_FALSE );      \
 374             }                                                           \
 375             clipmask[newvert] = mask;                                   \
 376             outlist[outcount++] = newvert;                              \
 377          }                                                              \
 378                                                                         \
 379          idxPrev = idx;                                                 \
 380          dpPrev = dp;                                                   \
 381       }                                                                 \
 382                                                                         \
 383       if (outcount < 3)                                                 \
 384          return;                                                        \
 385                                                                         \
 386       {                                                                 \
 387          GLuint *tmp = inlist;                                          \
 388          inlist = outlist;                                              \
 389          outlist = tmp;                                                 \
 390          n = outcount;                                                  \
 391       }                                                                 \
 392    }
 393
 394
 395 #define PLANE CLIP_RIGHT_BIT
 396 #define CLIP_DOTPROD(K) (- X(K) + W(K))
 397
 398    GENERAL_CLIP
 399
 400 #undef CLIP_DOTPROD
 401 #undef PLANE
 402
 403
 404 #define PLANE CLIP_LEFT_BIT
 405 #define CLIP_DOTPROD(K) (X(K) + W(K))
 406
 407    GENERAL_CLIP
 408
 409 #undef CLIP_DOTPROD
 410 #undef PLANE
 411
 412 #define PLANE CLIP_TOP_BIT
 413 #define CLIP_DOTPROD(K) (- Y(K) + W(K))
 414
 415    GENERAL_CLIP
 416
 417 #undef CLIP_DOTPROD
 418 #undef PLANE
 419
 420 #define PLANE CLIP_BOTTOM_BIT
 421 #define CLIP_DOTPROD(K) (Y(K) + W(K))
 422
 423    GENERAL_CLIP
 424
 425 #undef CLIP_DOTPROD
 426 #undef PLANE
 427
 428 #define PLANE CLIP_FAR_BIT
 429 #define CLIP_DOTPROD(K) (- Z(K) + W(K))
 430
 431    if (SIZE >= 3) {
 432       GENERAL_CLIP
 433    }
 434
 435 #undef CLIP_DOTPROD
 436 #undef PLANE
 437
 438 #define PLANE CLIP_NEAR_BIT
 439 #define CLIP_DOTPROD(K) (Z(K) + W(K))
 440
 441    if (SIZE >=3 ) {
 442       GENERAL_CLIP
 443    }
 444
 445 #undef CLIP_DOTPROD
 446 #undef PLANE
 447 #undef GENERAL_CLIP
 448
 449       if (inlist != vlist)
 450          for (i = 0 ; i < n ; i++)
 451             vlist[i] = inlist[i];
 452    }
 453
 454    /* Clip against user clipping planes in clip space.
 455     */
 456    if (mask & CLIP_USER_BIT) {
 457       n = TAG(userclip_polygon)( ctx, n, vlist, interp );
 458       if (n < 3) return;
 459    }
 460
 461    /* Project if necessary.
 462     */
 463    {
 464       GLuint i;
 465       GLfloat (*proj)[4] = VB->ProjectedClipPtr->data;
 466       GLuint first = VB->FirstClipped;
 467
 468       for (i = 0; i < n; i++) {
 469          GLuint j = vlist[i];
 470          if (j >= first) {
 471             if (SIZE == 4 && W(j) != 0.0F) {
 472                GLfloat wInv = 1.0F / W(j);
 473                proj[j][0] = X(j) * wInv;
 474                proj[j][1] = Y(j) * wInv;
 475                proj[j][2] = Z(j) * wInv;
 476                proj[j][3] = wInv;
 477             } else {
 478                proj[j][0] = X(j);
 479                proj[j][1] = Y(j);
 480                proj[j][2] = Z(j);
 481                proj[j][3] = W(j);
 482             }
 483          }
 484       }
 485    }
 486
 487    if (ctx->Driver.BuildProjectedVertices)
 488       ctx->Driver.BuildProjectedVertices(ctx,
 489                                          VB->FirstClipped,
 490                                          VB->LastClipped,
 491                                          ~0);
 492
 493    /* Render the new vertices as an unclipped polygon.
 494     * Argh - need to pass in pv...
 495     */
 496    {
 497       GLuint *tmp = VB->Elts;
 498       VB->Elts = vlist;
 499       render_poly_pv_raw_elts( ctx, 0, n, PRIM_BEGIN|PRIM_END, pv );
 500       VB->Elts = tmp;
 501    }
 502 }
 503
 504
 505
 506 #undef W
 507 #undef Z
 508 #undef Y
 509 #undef X
 510 #undef SIZE
 511 #undef TAG
 512 #undef INSIDE
 513 #undef OUTSIDE