home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 5 / MA_Cover_5.iso / ppc / mesa / src / clip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-01-31  |  31.8 KB  |  1,022 lines
  1. /* $Id: clip.c,v 1.14 1997/07/24 01:24:45 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.4
  6.  * Copyright (C) 1995-1997  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: clip.c,v $
  26.  * Revision 1.14  1997/07/24 01:24:45  brianp
  27.  * changed precompiled header symbol from PCH to PC_HEADER
  28.  *
  29.  * Revision 1.13  1997/05/28 03:23:48  brianp
  30.  * added precompiled header (PCH) support
  31.  *
  32.  * Revision 1.12  1997/04/02 03:10:06  brianp
  33.  * call gl_analyze_modelview_matrix instead of gl_compute_modelview_inverse
  34.  *
  35.  * Revision 1.11  1997/02/13 21:16:09  brianp
  36.  * if too many vertices in polygon return VB_SIZE-1, not VB_SIZE
  37.  *
  38.  * Revision 1.10  1997/02/10 21:16:12  brianp
  39.  * added checks in polygon clippers to prevent array overflows
  40.  *
  41.  * Revision 1.9  1997/02/04 19:39:39  brianp
  42.  * changed size of vlist2[] arrays to VB_SIZE per Randy Frank
  43.  *
  44.  * Revision 1.8  1996/12/02 20:10:07  brianp
  45.  * changed the macros in gl_viewclip_polygon() to be like gl_viewclip_line()
  46.  *
  47.  * Revision 1.7  1996/10/29 02:55:02  brianp
  48.  * fixed duplicate vertex bug in gl_viewclip_polygon()
  49.  *
  50.  * Revision 1.6  1996/10/07 23:48:33  brianp
  51.  * changed temporaries to GLdouble in gl_viewclip_polygon()
  52.  *
  53.  * Revision 1.5  1996/10/03 01:43:45  brianp
  54.  * changed INSIDE() macro in gl_viewclip_polygon() to work like other macros
  55.  *
  56.  * Revision 1.4  1996/10/03 01:36:33  brianp
  57.  * changed COMPUTE_INTERSECTION macros in gl_viewclip_polygon to avoid
  58.  * potential roundoff errors
  59.  *
  60.  * Revision 1.3  1996/09/27 01:24:23  brianp
  61.  * removed unused variables
  62.  *
  63.  * Revision 1.2  1996/09/15 01:48:58  brianp
  64.  * removed #define NULL 0
  65.  *
  66.  * Revision 1.1  1996/09/13 01:38:16  brianp
  67.  * Initial revision
  68.  *
  69.  */
  70.  
  71.  
  72. #ifdef PC_HEADER
  73. #include "all.h"
  74. #else
  75. #include <string.h>
  76. #include "clip.h"
  77. #include "context.h"
  78. #include "dlist.h"
  79. #include "macros.h"
  80. #include "matrix.h"
  81. #include "types.h"
  82. #include "vb.h"
  83. #include "xform.h"
  84. #endif
  85.  
  86.  
  87.  
  88.  
  89. /* Linear interpolation between A and B: */
  90. #define LINTERP( T, A, B )   ( (A) + (T) * ( (B) - (A) ) )
  91.  
  92.  
  93. #define EYE_SPACE 1
  94. #define CLIP_SPACE 2
  95.  
  96. static GLuint Space;
  97.  
  98.  
  99.  
  100. /*
  101.  * This function is used to interpolate colors, indexes, and texture
  102.  * coordinates when clipping has to be done.  In general, we compute
  103.  *     aux[dst] = aux[in] + t * (aux[out] - aux[in])
  104.  * where aux is the quantity to be interpolated.
  105.  * Input:  dst - index of array position to store interpolated value
  106.  *         t - a value in [0,1]
  107.  *         in - index of array position corresponding to 'inside' vertex
  108.  *         out - index of array position corresponding to 'outside' vertex
  109.  */
  110. static void interpolate_aux( GLcontext* ctx,
  111.                  GLuint dst, GLfloat t, GLuint in, GLuint out )
  112. {
  113.    struct vertex_buffer* VB = ctx->VB;
  114.  
  115.    if (ctx->ClipMask & CLIP_FCOLOR_BIT) {
  116.       VB->Fcolor[dst][0] = LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
  117.       VB->Fcolor[dst][1] = LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
  118.       VB->Fcolor[dst][2] = LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
  119.       VB->Fcolor[dst][3] = LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
  120.    }
  121.    else if (ctx->ClipMask & CLIP_FINDEX_BIT) {
  122.       VB->Findex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Findex[in],
  123.                          (GLfloat) VB->Findex[out] );
  124.    }
  125.  
  126.    if (ctx->ClipMask & CLIP_BCOLOR_BIT) {
  127.       VB->Bcolor[dst][0] = LINTERP( t, VB->Bcolor[in][0], VB->Bcolor[out][0] );
  128.       VB->Bcolor[dst][1] = LINTERP( t, VB->Bcolor[in][1], VB->Bcolor[out][1] );
  129.       VB->Bcolor[dst][2] = LINTERP( t, VB->Bcolor[in][2], VB->Bcolor[out][2] );
  130.       VB->Bcolor[dst][3] = LINTERP( t, VB->Bcolor[in][3], VB->Bcolor[out][3] );
  131.    }
  132.    else if (ctx->ClipMask & CLIP_BINDEX_BIT) {
  133.       VB->Bindex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Bindex[in],
  134.                          (GLfloat) VB->Bindex[out] );
  135.    }
  136.  
  137.    if (ctx->ClipMask & CLIP_TEXTURE_BIT) {
  138.       /* TODO: is more sophisticated texture coord interpolation needed?? */
  139.       if (Space==CLIP_SPACE) {
  140.      /* also interpolate eye Z component */
  141.      VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
  142.       }
  143.       VB->TexCoord[dst][0] = LINTERP(t,VB->TexCoord[in][0],VB->TexCoord[out][0]);
  144.       VB->TexCoord[dst][1] = LINTERP(t,VB->TexCoord[in][1],VB->TexCoord[out][1]);
  145.       VB->TexCoord[dst][2] = LINTERP(t,VB->TexCoord[in][2],VB->TexCoord[out][2]);
  146.       VB->TexCoord[dst][3] = LINTERP(t,VB->TexCoord[in][3],VB->TexCoord[out][3]);
  147.    }
  148.  
  149. }
  150.  
  151.  
  152.  
  153.  
  154. void gl_ClipPlane( GLcontext* ctx, GLenum plane, const GLfloat *equation )
  155. {
  156.    GLint p;
  157.  
  158.    p = (GLint) plane - (GLint) GL_CLIP_PLANE0;
  159.    if (p<0 || p>=MAX_CLIP_PLANES) {
  160.       gl_error( ctx, GL_INVALID_ENUM, "glClipPlane" );
  161.       return;
  162.    }
  163.  
  164.    /*
  165.     * The equation is transformed by the transpose of the inverse of the
  166.     * current modelview matrix and stored in the resulting eye coordinates.
  167.     */
  168.    if (ctx->NewModelViewMatrix) {
  169.       gl_analyze_modelview_matrix(ctx);
  170.    }
  171.    gl_transform_vector( ctx->Transform.ClipEquation[p], equation,
  172.             ctx->ModelViewInv );
  173. }
  174.  
  175.  
  176.  
  177. void gl_GetClipPlane( GLcontext* ctx, GLenum plane, GLdouble *equation )
  178. {
  179.    GLint p;
  180.  
  181.    if (INSIDE_BEGIN_END(ctx)) {
  182.       gl_error( ctx, GL_INVALID_OPERATION, "glGetClipPlane" );
  183.       return;
  184.    }
  185.  
  186.    p = (GLint) (plane - GL_CLIP_PLANE0);
  187.    if (p<0 || p>=MAX_CLIP_PLANES) {
  188.       gl_error( ctx, GL_INVALID_ENUM, "glGetClipPlane" );
  189.       return;
  190.    }
  191.  
  192.    equation[0] = (GLdouble) ctx->Transform.ClipEquation[p][0];
  193.    equation[1] = (GLdouble) ctx->Transform.ClipEquation[p][1];
  194.    equation[2] = (GLdouble) ctx->Transform.ClipEquation[p][2];
  195.    equation[3] = (GLdouble) ctx->Transform.ClipEquation[p][3];
  196. }
  197.  
  198.  
  199.  
  200.  
  201. /**********************************************************************/
  202. /*                         View volume clipping.                      */
  203. /**********************************************************************/
  204.  
  205.  
  206. /*
  207.  * Clip a point against the view volume.
  208.  * Input:  v - vertex-vector describing the point to clip
  209.  * Return:  0 = outside view volume
  210.  *          1 = inside view volume
  211.  */
  212. GLuint gl_viewclip_point( const GLfloat v[] )
  213. {
  214.    if (   v[0] > v[3] || v[0] < -v[3]
  215.        || v[1] > v[3] || v[1] < -v[3]
  216.        || v[2] > v[3] || v[2] < -v[3] ) {
  217.       return 0;
  218.    }
  219.    else {
  220.       return 1;
  221.    }
  222. }
  223.  
  224.  
  225.  
  226.  
  227. /*
  228.  * Clip a line segment against the view volume defined by -w<=x,y,z<=w.
  229.  * Input:  i, j - indexes into VB->V* of endpoints of the line
  230.  * Return:  0 = line completely outside of view
  231.  *          1 = line is inside view.
  232.  */
  233. GLuint gl_viewclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
  234. {
  235.    struct vertex_buffer* VB = ctx->VB;
  236. #ifndef __STORM__
  237.    GLfloat (*coord)[4] = VB->Clip;
  238. #else
  239.    float (*coord)[4] = VB->Clip;
  240. #endif
  241.    GLfloat t, dx, dy, dz, dw;
  242.    register GLuint ii, jj;
  243.  
  244.    Space = CLIP_SPACE;
  245.    ii = *i;
  246.    jj = *j;
  247.  
  248. /*
  249.  * We use 6 instances of this code to clip agains the 6 planes.
  250.  * For each plane, we define the OUTSIDE and COMPUTE_INTERSECTION
  251.  * macros apprpriately.
  252.  */
  253. #define GENERAL_CLIP                                                    \
  254.    if (OUTSIDE(ii)) {                                                   \
  255.       if (OUTSIDE(jj)) {                                                \
  256.      /* both verts are outside ==> return 0 */                      \
  257.      return 0;                                                      \
  258.       }                                                                 \
  259.       else {                                                            \
  260.      /* ii is outside, jj is inside ==> clip */                     \
  261.      /* new vertex put in position VB->Free */                      \
  262.      COMPUTE_INTERSECTION( VB->Free, jj, ii )                       \
  263.      if (ctx->ClipMask)                                             \
  264.         interpolate_aux( ctx, VB->Free, t, jj, ii );                \
  265.      ii = VB->Free;                                                 \
  266.      VB->Free++;                                                    \
  267.      if (VB->Free==VB_SIZE)  VB->Free = 1;                          \
  268.       }                                                                 \
  269.    }                                                                    \
  270.    else {                                                               \
  271.       if (OUTSIDE(jj)) {                                                \
  272.      /* ii is inside, jj is outside ==> clip */                     \
  273.      /* new vertex put in position VB->Free */                      \
  274.      COMPUTE_INTERSECTION( VB->Free, ii, jj );                      \
  275.      if (ctx->ClipMask)                                             \
  276.         interpolate_aux( ctx, VB->Free, t, ii, jj );                \
  277.      jj = VB->Free;                                                 \
  278.      VB->Free++;                                                    \
  279.      if (VB->Free==VB_SIZE)  VB->Free = 1;                          \
  280.       }                                                                 \
  281.       /* else both verts are inside ==> do nothing */                   \
  282.    }
  283.  
  284.  
  285. #define X(I)    coord[I][0]
  286. #define Y(I)    coord[I][1]
  287. #define Z(I)    coord[I][2]
  288. #define W(I)    coord[I][3]
  289.  
  290. /*
  291.  * Begin clipping
  292.  */
  293.  
  294.    /*** Clip against +X side ***/
  295. #define OUTSIDE(K)      (X(K) > W(K))
  296. #define COMPUTE_INTERSECTION( new, in, out )            \
  297.     dx = X(out) - X(in);                            \
  298.     dw = W(out) - W(in);                            \
  299.     t = (X(in) - W(in)) / (dw-dx);                  \
  300.     X(new) = X(in) + t * dx;                        \
  301.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  302.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  303.     W(new) = W(in) + t * dw;
  304.  
  305.    GENERAL_CLIP
  306.  
  307. #undef OUTSIDE
  308. #undef COMPUTE_INTERSECTION
  309.  
  310.  
  311.    /*** Clip against -X side ***/
  312. #define OUTSIDE(K)      (X(K) < -W(K))
  313. #define COMPUTE_INTERSECTION( new, in, out )            \
  314.     dx = X(out) - X(in);                            \
  315.     dw = W(out) - W(in);                            \
  316.     t = -(X(in) + W(in)) / (dw+dx);                 \
  317.     X(new) = X(in) + t * dx;                        \
  318.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  319.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  320.     W(new) = W(in) + t * dw;
  321.  
  322.    GENERAL_CLIP
  323.  
  324. #undef OUTSIDE
  325. #undef COMPUTE_INTERSECTION
  326.  
  327.  
  328.    /*** Clip against +Y side ***/
  329. #define OUTSIDE(K)      (Y(K) > W(K))
  330. #define COMPUTE_INTERSECTION( new, in, out )            \
  331.     dy = Y(out) - Y(in);                            \
  332.     dw = W(out) - W(in);                            \
  333.     t = (Y(in) - W(in)) / (dw-dy);                  \
  334.     X(new) = X(in) + t * (X(out) - X(in));          \
  335.     Y(new) = Y(in) + t * dy;                        \
  336.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  337.     W(new) = W(in) + t * dw;
  338.  
  339.    GENERAL_CLIP
  340.  
  341. #undef OUTSIDE
  342. #undef COMPUTE_INTERSECTION
  343.  
  344.  
  345.    /*** Clip against -Y side ***/
  346. #define OUTSIDE(K)      (Y(K) < -W(K))
  347. #define COMPUTE_INTERSECTION( new, in, out )            \
  348.     dy = Y(out) - Y(in);                            \
  349.     dw = W(out) - W(in);                            \
  350.     t = -(Y(in) + W(in)) / (dw+dy);                 \
  351.     X(new) = X(in) + t * (X(out) - X(in));          \
  352.     Y(new) = Y(in) + t * dy;                        \
  353.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  354.     W(new) = W(in) + t * dw;
  355.  
  356.    GENERAL_CLIP
  357.  
  358. #undef OUTSIDE
  359. #undef COMPUTE_INTERSECTION
  360.  
  361.  
  362.    /*** Clip against +Z side ***/
  363. #define OUTSIDE(K)      (Z(K) > W(K))
  364. #define COMPUTE_INTERSECTION( new, in, out )            \
  365.     dz = Z(out) - Z(in);                            \
  366.     dw = W(out) - W(in);                            \
  367.     t = (Z(in) - W(in)) / (dw-dz);                  \
  368.     X(new) = X(in) + t * (X(out) - X(in));          \
  369.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  370.     Z(new) = Z(in) + t * dz;                        \
  371.     W(new) = W(in) + t * dw;
  372.  
  373.    GENERAL_CLIP
  374.  
  375. #undef OUTSIDE
  376. #undef COMPUTE_INTERSECTION
  377.  
  378.  
  379.    /*** Clip against -Z side ***/
  380. #define OUTSIDE(K)      (Z(K) < -W(K))
  381. #define COMPUTE_INTERSECTION( new, in, out )            \
  382.     dz = Z(out) - Z(in);                            \
  383.     dw = W(out) - W(in);                            \
  384.     t = -(Z(in) + W(in)) / (dw+dz);                 \
  385.     X(new) = X(in) + t * (X(out) - X(in));          \
  386.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  387.     Z(new) = Z(in) + t * dz;                        \
  388.     W(new) = W(in) + t * dw;
  389.  
  390.    GENERAL_CLIP
  391.  
  392. #undef OUTSIDE
  393. #undef COMPUTE_INTERSECTION
  394.  
  395. #undef GENERAL_CLIP
  396.  
  397.    *i = ii;
  398.    *j = jj;
  399.    return 1;
  400. }
  401.  
  402.  
  403.  
  404.  
  405. /*
  406.  * Clip a polygon against the view volume defined by -w<=x,y,z<=w.
  407.  * Input:  n - number of vertices in input polygon.
  408.  *         vlist - list of indexes into VB->V* of polygon to clip.
  409.  * Output:  vlist - modified list of vertex indexes
  410.  * Return:  number of vertices in resulting polygon
  411.  */
  412. GLuint gl_viewclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
  413.  
  414. {
  415.    struct vertex_buffer* VB = ctx->VB;
  416. #ifndef __STORM__
  417.    GLfloat (*coord)[4] = VB->Clip;
  418. #else
  419.    float (*coord)[4] = VB->Clip;
  420. #endif
  421.  
  422.    GLuint previ, prevj;
  423.    GLuint curri, currj;
  424.    GLuint vlist2[VB_SIZE];
  425.    GLuint n2;
  426.    GLdouble dx, dy, dz, dw, t, neww;
  427.  
  428.    Space = CLIP_SPACE;
  429.  
  430. /*
  431.  * We use 6 instances of this code to implement clipping against the
  432.  * 6 sides of the view volume.  Prior to each we define the macros:
  433.  *    INLIST = array which lists input vertices
  434.  *    OUTLIST = array which lists output vertices
  435.  *    INCOUNT = variable which is the number of vertices in INLIST[]
  436.  *    OUTCOUNT = variable which is the number of vertices in OUTLIST[]
  437.  *    INSIDE(i) = test if vertex v[i] is inside the view volume
  438.  *    COMPUTE_INTERSECTION(in,out,new) = compute intersection of line
  439.  *              from v[in] to v[out] with the clipping plane and store
  440.  *              the result in v[new]
  441.  */
  442.  
  443. #define GENERAL_CLIP                                                    \
  444.    if (INCOUNT<3)  return 0;                                            \
  445.    previ = INCOUNT-1;           /* let previous = last vertex */        \
  446.    prevj = INLIST[previ];                                               \
  447.    OUTCOUNT = 0;                                                        \
  448.    for (curri=0;curri<INCOUNT;curri++) {                                \
  449.       currj = INLIST[curri];                                            \
  450.       if (INSIDE(currj)) {                                              \
  451.      if (INSIDE(prevj)) {                                           \
  452.         /* both verts are inside ==> copy current to outlist */     \
  453.         OUTLIST[OUTCOUNT] = currj;                                  \
  454.         OUTCOUNT++;                                                 \
  455.      }                                                              \
  456.      else {                                                         \
  457.         /* current is inside and previous is outside ==> clip */    \
  458.         COMPUTE_INTERSECTION( currj, prevj, VB->Free )              \
  459.         /* if new point not coincident with previous point... */    \
  460.         if (t>0.0) {                                                \
  461.            /* interpolate aux info using the value of t */          \
  462.            if (ctx->ClipMask)                                       \
  463.           interpolate_aux( ctx, VB->Free, t, currj, prevj );    \
  464.            VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];            \
  465.            /* output new point */                                   \
  466.            OUTLIST[OUTCOUNT] = VB->Free;                            \
  467.            VB->Free++;                                              \
  468.            if (VB->Free==VB_SIZE)   VB->Free = 1;                   \
  469.            OUTCOUNT++;                                              \
  470.         }                                                           \
  471.         /* Output current */                                        \
  472.         OUTLIST[OUTCOUNT] = currj;                                  \
  473.         OUTCOUNT++;                                                 \
  474.      }                                                              \
  475.       }                                                                 \
  476.       else {                                                            \
  477.      if (INSIDE(prevj)) {                                           \
  478.         /* current is outside and previous is inside ==> clip */    \
  479.         COMPUTE_INTERSECTION( prevj, currj, VB->Free )              \
  480.         /* if new point not coincident with previous point... */    \
  481.         if (t>0.0) {                                                \
  482.            /* interpolate aux info using the value of t */          \
  483.            if (ctx->ClipMask)                                       \
  484.           interpolate_aux( ctx, VB->Free, t, prevj, currj );    \
  485.            VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];            \
  486.            /* output new point */                                   \
  487.            OUTLIST[OUTCOUNT] = VB->Free;                            \
  488.            VB->Free++;                                              \
  489.            if (VB->Free==VB_SIZE)   VB->Free = 1;                   \
  490.            OUTCOUNT++;                                              \
  491.         }                                                           \
  492.      }                                                              \
  493.      /* else both verts are outside ==> do nothing */               \
  494.       }                                                                 \
  495.       /* let previous = current */                                      \
  496.       previ = curri;                                                    \
  497.       prevj = currj;                                                    \
  498.       /* check for overflowing vertex buffer */                         \
  499.       if (OUTCOUNT>=VB_SIZE-1) {                                        \
  500.      /* Too many vertices */                                        \
  501.      if (OUTLIST==vlist2) {                                         \
  502.         /* copy OUTLIST[] to vlist[] */                             \
  503.         int i;                                                      \
  504.         for (i=0;i<VB_SIZE;i++) {                                   \
  505.            vlist[i] = OUTLIST[i];                                   \
  506.         }                                                           \
  507.      }                                                              \
  508.      return VB_SIZE-1;                                              \
  509.       }                                                                 \
  510.    }
  511.  
  512.  
  513. #ifndef AMIGAWARP
  514. #define X(I)    coord[I][0]
  515. #define Y(I)    coord[I][1]
  516. #define Z(I)    coord[I][2]
  517. #define W(I)    coord[I][3]
  518. #endif
  519.  
  520. /*
  521.  * Clip against +X
  522.  */
  523. #define INCOUNT n
  524. #define OUTCOUNT n2
  525. #define INLIST vlist
  526. #define OUTLIST vlist2
  527. #define INSIDE(K)      (X(K) <= W(K))
  528.  
  529. #define COMPUTE_INTERSECTION( in, out, new )            \
  530.     dx = X(out) - X(in);                            \
  531.     dw = W(out) - W(in);                            \
  532.     t = (X(in)-W(in)) / (dw-dx);                    \
  533.     neww = W(in) + t * dw;                          \
  534.     X(new) = neww;                                  \
  535.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  536.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  537.     W(new) = neww;
  538.  
  539.    GENERAL_CLIP
  540.  
  541. #undef INCOUNT
  542. #undef OUTCOUNT
  543. #undef INLIST
  544. #undef OUTLIST
  545. #undef INSIDE
  546. #undef COMPUTE_INTERSECTION
  547.  
  548.  
  549. /*
  550.  * Clip against -X
  551.  */
  552. #define INCOUNT n2
  553. #define OUTCOUNT n
  554. #define INLIST vlist2
  555. #define OUTLIST vlist
  556. #define INSIDE(K)       (X(K) >= -W(K))
  557. #define COMPUTE_INTERSECTION( in, out, new )            \
  558.     dx = X(out)-X(in);                              \
  559.     dw = W(out)-W(in);                              \
  560.     t = -(X(in)+W(in)) / (dw+dx);                   \
  561.     neww = W(in) + t * dw;                          \
  562.     X(new) = -neww;                                 \
  563.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  564.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  565.     W(new) = neww;
  566.  
  567.    GENERAL_CLIP
  568.  
  569. #undef INCOUNT
  570. #undef OUTCOUNT
  571. #undef INLIST
  572. #undef OUTLIST
  573. #undef INSIDE
  574. #undef COMPUTE_INTERSECTION
  575.  
  576.  
  577. /*
  578.  * Clip against +Y
  579.  */
  580. #define INCOUNT n
  581. #define OUTCOUNT n2
  582. #define INLIST vlist
  583. #define OUTLIST vlist2
  584. #define INSIDE(K)       (Y(K) <= W(K))
  585. #define COMPUTE_INTERSECTION( in, out, new )            \
  586.     dy = Y(out)-Y(in);                              \
  587.     dw = W(out)-W(in);                              \
  588.     t = (Y(in)-W(in)) / (dw-dy);                    \
  589.     neww = W(in) + t * dw;                          \
  590.     X(new) = X(in) + t * (X(out) - X(in));          \
  591.     Y(new) = neww;                                  \
  592.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  593.     W(new) = neww;
  594.  
  595.    GENERAL_CLIP
  596.  
  597. #undef INCOUNT
  598. #undef OUTCOUNT
  599. #undef INLIST
  600. #undef OUTLIST
  601. #undef INSIDE
  602. #undef COMPUTE_INTERSECTION
  603.  
  604.  
  605. /*
  606.  * Clip against -Y
  607.  */
  608. #define INCOUNT n2
  609. #define OUTCOUNT n
  610. #define INLIST vlist2
  611. #define OUTLIST vlist
  612. #define INSIDE(K)       (Y(K) >= -W(K))
  613. #define COMPUTE_INTERSECTION( in, out, new )            \
  614.     dy = Y(out)-Y(in);                              \
  615.     dw = W(out)-W(in);                              \
  616.     t = -(Y(in)+W(in)) / (dw+dy);                   \
  617.     neww = W(in) + t * dw;                          \
  618.     X(new) = X(in) + t * (X(out) - X(in));          \
  619.     Y(new) = -neww;                                 \
  620.     Z(new) = Z(in) + t * (Z(out) - Z(in));          \
  621.     W(new) = neww;
  622.  
  623.    GENERAL_CLIP
  624.  
  625. #undef INCOUNT
  626. #undef OUTCOUNT
  627. #undef INLIST
  628. #undef OUTLIST
  629. #undef INSIDE
  630. #undef COMPUTE_INTERSECTION
  631.  
  632.  
  633.  
  634. /*
  635.  * Clip against +Z
  636.  */
  637. #define INCOUNT n
  638. #define OUTCOUNT n2
  639. #define INLIST vlist
  640. #define OUTLIST vlist2
  641. #define INSIDE(K)       (Z(K) <= W(K))
  642. #define COMPUTE_INTERSECTION( in, out, new )            \
  643.     dz = Z(out)-Z(in);                              \
  644.     dw = W(out)-W(in);                              \
  645.     t = (Z(in)-W(in)) / (dw-dz);                    \
  646.     neww = W(in) + t * dw;                          \
  647.     X(new) = X(in) + t * (X(out) - X(in));          \
  648.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  649.     Z(new) = neww;                                  \
  650.     W(new) = neww;
  651.  
  652.    GENERAL_CLIP
  653.  
  654. #undef INCOUNT
  655. #undef OUTCOUNT
  656. #undef INLIST
  657. #undef OUTLIST
  658. #undef INSIDE
  659. #undef COMPUTE_INTERSECTION
  660.  
  661.  
  662. /*
  663.  * Clip against -Z
  664.  */
  665. #define INCOUNT n2
  666. #define OUTCOUNT n
  667. #define INLIST vlist2
  668. #define OUTLIST vlist
  669. #define INSIDE(K)       (Z(K) >= -W(K))
  670. #define COMPUTE_INTERSECTION( in, out, new )            \
  671.     dz = Z(out)-Z(in);                              \
  672.     dw = W(out)-W(in);                              \
  673.     t = -(Z(in)+W(in)) / (dw+dz);                   \
  674.     neww = W(in) + t * dw;                          \
  675.     X(new) = X(in) + t * (X(out) - X(in));          \
  676.     Y(new) = Y(in) + t * (Y(out) - Y(in));          \
  677.     Z(new) = -neww;                                 \
  678.     W(new) = neww;
  679.  
  680.    GENERAL_CLIP
  681.  
  682. #undef INCOUNT
  683. #undef INLIST
  684. #undef OUTLIST
  685. #undef INSIDE
  686. #undef COMPUTE_INTERSECTION
  687.  
  688.    /* 'OUTCOUNT' clipped vertices are now back in v[] */
  689.    return OUTCOUNT;
  690.  
  691. #undef GENERAL_CLIP
  692. #undef OUTCOUNT
  693. }
  694.  
  695.  
  696.  
  697.  
  698. /**********************************************************************/
  699. /*         Clipping against user-defined clipping planes.             */
  700. /**********************************************************************/
  701.  
  702.  
  703.  
  704. /*
  705.  * If the dot product of the eye coordinates of a vertex with the
  706.  * stored plane equation components is positive or zero, the vertex
  707.  * is in with respect to that clipping plane, otherwise it is out.
  708.  */
  709.  
  710.  
  711.  
  712. /*
  713.  * Clip a point against the user clipping planes.
  714.  * Input:  v - vertex-vector describing the point to clip.
  715.  * Return:  0 = point was clipped
  716.  *          1 = point not clipped
  717.  */
  718. GLuint gl_userclip_point( GLcontext* ctx, const GLfloat v[] )
  719. {
  720.    GLuint p;
  721.  
  722.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  723.       if (ctx->Transform.ClipEnabled[p]) {
  724.      GLfloat dot = v[0] * ctx->Transform.ClipEquation[p][0]
  725.              + v[1] * ctx->Transform.ClipEquation[p][1]
  726.              + v[2] * ctx->Transform.ClipEquation[p][2]
  727.              + v[3] * ctx->Transform.ClipEquation[p][3];
  728.      if (dot < 0.0F) {
  729.         return 0;
  730.      }
  731.       }
  732.    }
  733.  
  734.    return 1;
  735. }
  736.  
  737.  
  738. #define MAGIC_NUMBER -0.8e-03F
  739.  
  740.  
  741. /* Test if VB->Eye[J] is inside the clipping plane defined by A,B,C,D */
  742. #define INSIDE( J, A, B, C, D )                                 \
  743.    ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B                     \
  744.     + VB->Eye[J][2] * C + VB->Eye[J][3] * D) >= MAGIC_NUMBER )
  745.  
  746.  
  747. /* Test if VB->Eye[J] is outside the clipping plane defined by A,B,C,D */
  748. #define OUTSIDE( J, A, B, C, D )                                \
  749.    ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B                     \
  750.     + VB->Eye[J][2] * C + VB->Eye[J][3] * D) < MAGIC_NUMBER )
  751.  
  752.  
  753. /*
  754.  * Clip a line against the user clipping planes.
  755.  * Input:  i, j - indexes into VB->V*[] of endpoints
  756.  * Output:  i, j - indexes into VB->V*[] of (possibly clipped) endpoints
  757.  * Return:  0 = line completely clipped
  758.  *          1 = line is visible
  759.  */
  760. GLuint gl_userclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
  761. {
  762.    struct vertex_buffer* VB = ctx->VB;
  763.  
  764.    GLuint p, ii, jj;
  765.  
  766.    Space = EYE_SPACE;
  767.  
  768.    ii = *i;
  769.    jj = *j;
  770.  
  771.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  772.       if (ctx->Transform.ClipEnabled[p]) {
  773.      register GLfloat a, b, c, d;
  774.      a = ctx->Transform.ClipEquation[p][0];
  775.      b = ctx->Transform.ClipEquation[p][1];
  776.      c = ctx->Transform.ClipEquation[p][2];
  777.      d = ctx->Transform.ClipEquation[p][3];
  778.  
  779.      if (OUTSIDE( ii, a,b,c,d  )) {
  780.         if (OUTSIDE( jj, a,b,c,d )) {
  781.            /* ii and jj outside ==> quit */
  782.            return 0;
  783.         }
  784.         else {
  785.            /* ii is outside, jj is inside ==> clip */
  786.            GLfloat dx, dy, dz, dw, t, denom;
  787.            dx = VB->Eye[ii][0] - VB->Eye[jj][0];
  788.            dy = VB->Eye[ii][1] - VB->Eye[jj][1];
  789.            dz = VB->Eye[ii][2] - VB->Eye[jj][2];
  790.            dw = VB->Eye[ii][3] - VB->Eye[jj][3];
  791.            denom = dx*a + dy*b + dz*c + dw*d;
  792.            if (denom==0.0) {
  793.           t = 0.0;
  794.            }
  795.            else {
  796.           t = -(VB->Eye[jj][0]*a+VB->Eye[jj][1]*b
  797.                +VB->Eye[jj][2]*c+VB->Eye[jj][3]*d) / denom;
  798.           if (t>1.0F)  t = 1.0F;
  799.            }
  800.            VB->Eye[VB->Free][0] = VB->Eye[jj][0] + t * dx;
  801.            VB->Eye[VB->Free][1] = VB->Eye[jj][1] + t * dy;
  802.            VB->Eye[VB->Free][2] = VB->Eye[jj][2] + t * dz;
  803.            VB->Eye[VB->Free][3] = VB->Eye[jj][3] + t * dw;
  804.  
  805.            /* Interpolate colors, indexes, and/or texture coords */
  806.            if (ctx->ClipMask)
  807.           interpolate_aux( ctx, VB->Free, t, jj, ii );
  808.  
  809.            ii = VB->Free;
  810.            VB->Free++;
  811.            if (VB->Free==VB_SIZE)   VB->Free = 1;
  812.         }
  813.      }
  814.      else {
  815.         if (OUTSIDE( jj, a,b,c,d )) {
  816.            /* ii is inside, jj is outside ==> clip */
  817.            GLfloat dx, dy, dz, dw, t, denom;
  818.            dx = VB->Eye[jj][0] - VB->Eye[ii][0];
  819.            dy = VB->Eye[jj][1] - VB->Eye[ii][1];
  820.            dz = VB->Eye[jj][2] - VB->Eye[ii][2];
  821.            dw = VB->Eye[jj][3] - VB->Eye[ii][3];
  822.            denom = dx*a + dy*b + dz*c + dw*d;
  823.            if (denom==0.0) {
  824.           t = 0.0;
  825.            }
  826.            else {
  827.           t = -(VB->Eye[ii][0]*a+VB->Eye[ii][1]*b
  828.                +VB->Eye[ii][2]*c+VB->Eye[ii][3]*d) / denom;
  829.           if (t>1.0F)  t = 1.0F;
  830.            }
  831.            VB->Eye[VB->Free][0] = VB->Eye[ii][0] + t * dx;
  832.            VB->Eye[VB->Free][1] = VB->Eye[ii][1] + t * dy;
  833.            VB->Eye[VB->Free][2] = VB->Eye[ii][2] + t * dz;
  834.            VB->Eye[VB->Free][3] = VB->Eye[ii][3] + t * dw;
  835.  
  836.            /* Interpolate colors, indexes, and/or texture coords */
  837.            if (ctx->ClipMask)
  838.           interpolate_aux( ctx, VB->Free, t, ii, jj );
  839.  
  840.            jj = VB->Free;
  841.            VB->Free++;
  842.            if (VB->Free==VB_SIZE)   VB->Free = 1;
  843.         }
  844.         else {
  845.            /* ii and jj inside ==> do nothing */
  846.         }
  847.      }
  848.       }
  849.    }
  850.  
  851.    *i = ii;
  852.    *j = jj;
  853.    return 1;
  854. }
  855.  
  856.  
  857.  
  858.  
  859. /*
  860.  * Clip a polygon against the user clipping planes defined in eye coordinates.
  861.  * Input:  n - number of vertices.
  862.  *         vlist - list of vertices in input polygon.
  863.  * Output:  vlist - list of vertices in output polygon.
  864.  * Return:  number of vertices after clipping.
  865.  */
  866. GLuint gl_userclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
  867. {
  868.    struct vertex_buffer* VB = ctx->VB;
  869.  
  870.    GLuint vlist2[VB_SIZE];
  871.    GLuint *inlist, *outlist;
  872.    GLuint incount, outcount;
  873.    GLuint curri, currj;
  874.    GLuint previ, prevj;
  875.    GLuint p;
  876.  
  877.    Space = EYE_SPACE;
  878.  
  879.    /* initialize input vertex list */
  880.    incount = n;
  881.    inlist = vlist;
  882.    outlist = vlist2;
  883.  
  884.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  885.       if (ctx->Transform.ClipEnabled[p]) {
  886.      register float a = ctx->Transform.ClipEquation[p][0];
  887.      register float b = ctx->Transform.ClipEquation[p][1];
  888.      register float c = ctx->Transform.ClipEquation[p][2];
  889.      register float d = ctx->Transform.ClipEquation[p][3];
  890.  
  891.      if (incount<3)  return 0;
  892.  
  893.      /* initialize prev to be last in the input list */
  894.      previ = incount - 1;
  895.      prevj = inlist[previ];
  896.  
  897.      outcount = 0;
  898.  
  899.      for (curri=0;curri<incount;curri++) {
  900.         currj = inlist[curri];
  901.  
  902.         if (INSIDE(currj, a,b,c,d)) {
  903.            if (INSIDE(prevj, a,b,c,d)) {
  904.           /* both verts are inside ==> copy current to outlist */
  905.           outlist[outcount++] = currj;
  906.            }
  907.            else {
  908.           /* current is inside and previous is outside ==> clip */
  909.           GLfloat dx, dy, dz, dw, t, denom;
  910.           /* compute t */
  911.           dx = VB->Eye[prevj][0] - VB->Eye[currj][0];
  912.           dy = VB->Eye[prevj][1] - VB->Eye[currj][1];
  913.           dz = VB->Eye[prevj][2] - VB->Eye[currj][2];
  914.           dw = VB->Eye[prevj][3] - VB->Eye[currj][3];
  915.           denom = dx*a + dy*b + dz*c + dw*d;
  916.           if (denom==0.0) {
  917.              t = 0.0;
  918.           }
  919.           else {
  920.              t = -(VB->Eye[currj][0]*a+VB->Eye[currj][1]*b
  921.                +VB->Eye[currj][2]*c+VB->Eye[currj][3]*d) / denom;
  922.              if (t>1.0F) {
  923.             t = 1.0F;
  924.              }
  925.           }
  926.           /* interpolate new vertex position */
  927.           VB->Eye[VB->Free][0] = VB->Eye[currj][0] + t*dx;
  928.           VB->Eye[VB->Free][1] = VB->Eye[currj][1] + t*dy;
  929.           VB->Eye[VB->Free][2] = VB->Eye[currj][2] + t*dz;
  930.           VB->Eye[VB->Free][3] = VB->Eye[currj][3] + t*dw;
  931.  
  932.           /* interpolate color, index, and/or texture coord */
  933.           if (ctx->ClipMask) {
  934.              interpolate_aux( ctx, VB->Free, t, currj, prevj);
  935.           }
  936.           VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
  937.  
  938.           /* output new vertex */
  939.           outlist[outcount++] = VB->Free;
  940.           VB->Free++;
  941.           if (VB->Free==VB_SIZE)   VB->Free = 1;
  942.           /* output current vertex */
  943.           outlist[outcount++] = currj;
  944.            }
  945.         }
  946.         else {
  947.            if (INSIDE(prevj, a,b,c,d)) {
  948.           /* current is outside and previous is inside ==> clip */
  949.           GLfloat dx, dy, dz, dw, t, denom;
  950.           /* compute t */
  951.           dx = VB->Eye[currj][0]-VB->Eye[prevj][0];
  952.           dy = VB->Eye[currj][1]-VB->Eye[prevj][1];
  953.           dz = VB->Eye[currj][2]-VB->Eye[prevj][2];
  954.           dw = VB->Eye[currj][3]-VB->Eye[prevj][3];
  955.           denom = dx*a + dy*b + dz*c + dw*d;
  956.           if (denom==0.0) {
  957.              t = 0.0;
  958.           }
  959.           else {
  960.              t = -(VB->Eye[prevj][0]*a+VB->Eye[prevj][1]*b
  961.                +VB->Eye[prevj][2]*c+VB->Eye[prevj][3]*d) / denom;
  962.              if (t>1.0F) {
  963.             t = 1.0F;
  964.              }
  965.           }
  966.           /* interpolate new vertex position */
  967.           VB->Eye[VB->Free][0] = VB->Eye[prevj][0] + t*dx;
  968.           VB->Eye[VB->Free][1] = VB->Eye[prevj][1] + t*dy;
  969.           VB->Eye[VB->Free][2] = VB->Eye[prevj][2] + t*dz;
  970.           VB->Eye[VB->Free][3] = VB->Eye[prevj][3] + t*dw;
  971.  
  972.           /* interpolate color, index, and/or texture coord */
  973.           if (ctx->ClipMask) {
  974.              interpolate_aux( ctx, VB->Free, t, prevj, currj);
  975.           }
  976.           VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
  977.  
  978.           /* output new vertex */
  979.           outlist[outcount++] = VB->Free;
  980.           VB->Free++;
  981.           if (VB->Free==VB_SIZE)   VB->Free = 1;
  982.            }
  983.            /* else  both verts are outside ==> do nothing */
  984.         }
  985.  
  986.         previ = curri;
  987.         prevj = currj;
  988.  
  989.         /* check for overflowing vertex buffer */
  990.         if (outcount>=VB_SIZE-1) {
  991.            /* Too many vertices */
  992.            if (outlist!=vlist2) {
  993.           MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
  994.            }
  995.            return VB_SIZE-1;
  996.         }
  997.  
  998.      }  /* for i */
  999.  
  1000.      /* swap inlist and outlist pointers */
  1001.      {
  1002.         GLuint *tmp;
  1003.         tmp = inlist;
  1004.         inlist = outlist;
  1005.         outlist = tmp;
  1006.         incount = outcount;
  1007.      }
  1008.  
  1009.       } /* if */
  1010.    } /* for p */
  1011.  
  1012.    /* outlist points to the list of vertices resulting from the last */
  1013.    /* clipping.  If outlist == vlist2 then we have to copy the vertices */
  1014.    /* back to vlist */
  1015.    if (outlist!=vlist2) {
  1016.       MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
  1017.    }
  1018.  
  1019.    return outcount;
  1020. }
  1021.  
  1022.