/* $Id: clip_funcs.h,v 1.4 1999/09/30 11:18:21 keithw Exp $ */

/*
 * Mesa 3-D graphics library
 * Version:  3.1
 * 
 * Copyright (C) 1999  Brian Paul   All Rights Reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

/*
 * New (3.1) transformation code written by Keith Whitwell.
 */

static GLuint TAG(userclip_line)( struct vertex_buffer *VB, 
				  GLuint *i, GLuint *j );
static GLuint TAG(userclip_polygon)( struct vertex_buffer *VB, 
				     GLuint n, GLuint vlist[] );



/* This now calls the user clip functions if required.
 */
static GLuint TAG(viewclip_line)( struct vertex_buffer *VB, 
				  GLuint *i, GLuint *j,
				  GLubyte mask )
{
   GLfloat (*coord)[4] = VB->ClipPtr->data;
   GLfloat t, dx, dy, dz, dw, neww;
   GLuint ii = *i, jj = *j;
   GLuint vlist[2];
   GLuint n;
   clip_interp_func interp = VB->ctx->ClipInterpFunc;
   GLuint vb_free = VB->FirstFree;

/*
 * We use 6 instances of this code to clip agains the 6 planes.
 * For each plane, we define the OUTSIDE and COMPUTE_INTERSECTION
 * macros apprpriately.
 */
#define GENERAL_CLIP					\
   if (mask & PLANE) {					\
      GLuint flagI = INSIDE( ii );			\
      GLuint flagJ = INSIDE( jj );			\
							\
      if (!(flagI|flagJ))				\
	 return 0;					\
							\
      if (flagI ^ flagJ) {				\
	 COMPUTE_INTERSECTION( jj, ii, vb_free );	\
	 interp( VB, vb_free, t, jj, ii);		\
							\
	 if (flagI) {					\
            VB->ClipMask[jj] |= PLANE;			\
	    jj = vb_free;				\
	 } else {					\
            VB->ClipMask[ii] |= PLANE;			\
	    ii = vb_free;				\
	 }						\
							\
         VB->ClipMask[vb_free++] = 0;			\
      }							\
   }

#include "general_clip.h"

   VB->Free = vb_free;

   if (mask & CLIP_USER_BIT) {
      if ( TAG(userclip_line)( VB, &ii, &jj ) == 0 )
	 return 0;
   }

   vlist[0] = ii;
   vlist[1] = jj;
   n = 2;

   /* Should always be at least one new vertex.
    */
   {
      const GLfloat *m = VB->ctx->Viewport.WindowMap.m;
      GLfloat sx = m[MAT_SX];
      GLfloat tx = m[MAT_TX];
      GLfloat sy = m[MAT_SY];
      GLfloat ty = m[MAT_TY];
      GLfloat sz = m[MAT_SZ];
      GLfloat tz = m[MAT_TZ];
      GLuint i, j;
      GLfloat (*win)[4] = VB->Win.data;
      GLuint start = VB->FirstFree;

      for (i = 0; i < n; i++) {
	 j = vlist[i];
	 if (j >= start) {
	    if (W(j) != 0.0F) {
	       GLfloat wInv = 1.0F / W(j);
	       win[j][0] = X(j) * wInv * sx + tx;
	       win[j][1] = Y(j) * wInv * sy + ty;
	       win[j][2] = Z(j) * wInv * sz + tz;
	       win[j][3] = wInv;
	    } else {
	       win[j][0] = win[j][1] = win[j][2] = 0.0F;
	       win[j][3] = 1.0F;
	    }
	 }
      }
   }

   if (VB->ctx->Driver.RasterSetup)
      VB->ctx->Driver.RasterSetup(VB, VB->FirstFree, VB->Free);

   *i = ii;
   *j = jj;
   return 1;
}

/* We now clip polygon triangles individually.  This is necessary to
 * avoid artifacts dependent on where the boundary of the VB falls
 * within the polygon.  As a result, there is an upper bound on the
 * number of vertices which may be created, and the test against VB_SIZE
 * is redundant.  
 */
static GLuint TAG(viewclip_polygon)( struct vertex_buffer *VB, 
				     GLuint n, GLuint vlist[],
				     GLubyte mask )
{
   GLfloat (*coord)[4] = VB->ClipPtr->data;
   GLuint vlist2[VB_SIZE-VB_MAX];
   GLuint *inlist = vlist, *outlist = vlist2;
   GLdouble dx, dy, dz, dw, t = 0, neww;
   GLuint i;
   GLuint vb_free = VB->FirstFree;
   clip_interp_func interp = VB->ctx->ClipInterpFunc;

   if (mask & CLIP_ALL_BITS) {

#define GENERAL_CLIP							\
   if (mask & PLANE) {							\
      GLuint prevj = inlist[n-1];					\
      GLuint prevflag = INSIDE(prevj);					\
      GLuint outcount = 0;						\
      GLuint ef_state = 3;						\
      GLuint i;								\
									\
									\
      for (i = 0; i < n; i++) {						\
	 GLuint j = inlist[i];						\
	 GLuint flag = INSIDE(j);					\
									\
	 if (flag ^ prevflag) {						\
	    if (flag) {							\
	       /* Coming back in					\
		*/							\
	       COMPUTE_INTERSECTION( j, prevj, vb_free );		\
	       interp( VB, vb_free, t, j, prevj );			\
									\
	       if (IND&CLIP_TAB_EDGEFLAG)				\
		  VB->EdgeFlagPtr->data[vb_free] =			\
		     VB->EdgeFlagPtr->data[prevj] & ef_state;		\
									\
									\
	    } else {							\
	       /* Going out of bounds					\
		*/							\
	       COMPUTE_INTERSECTION( prevj, j, vb_free );		\
	       interp( VB, vb_free, t, prevj, j );			\
									\
	       if (IND&CLIP_TAB_EDGEFLAG)				\
		  VB->EdgeFlagPtr->data[vb_free] = 1;			\
	    }								\
									\
	    outlist[outcount++] = vb_free;				\
            VB->ClipMask[vb_free++] = 0;				\
	 }								\
									\
	 if (flag) {							\
	    outlist[outcount++] = j;					\
	 } else {							\
            VB->ClipMask[j] |= (PLANE&CLIP_ALL_BITS); /* don't setup */	\
         }								\
	 prevj = j;							\
	 prevflag = flag;						\
	 ef_state = 1;							\
      }									\
									\
      if (outcount < 3)							\
	 return 0;							\
      else {								\
	 GLuint *tmp = inlist;						\
	 inlist = outlist;						\
	 outlist = tmp;							\
	 n = outcount;							\
      }									\
   }


#include "general_clip.h"

      if (inlist != vlist) 
	 for (i = 0 ; i < n ; i++)
	    vlist[i] = inlist[i];
   }

   VB->Free = vb_free;
 
   /* Clip against user clipping planes in clip space. 
    */
   if (mask & CLIP_USER_BIT) {
      n = TAG(userclip_polygon)( VB, n, vlist );
      if (n < 3) return 0;
   }


   {
      const GLfloat *m = VB->ctx->Viewport.WindowMap.m;
      GLfloat sx = m[MAT_SX];
      GLfloat tx = m[MAT_TX];
      GLfloat sy = m[MAT_SY];
      GLfloat ty = m[MAT_TY];
      GLfloat sz = m[MAT_SZ];
      GLfloat tz = m[MAT_TZ];
      GLuint i;
      GLfloat (*win)[4] = VB->Win.data;
      GLuint first = VB->FirstFree;

      for (i = 0; i < n; i++) {
	 GLuint j = vlist[i];
	 if (j >= first) {
	    if (W(j) != 0.0F) {
	       GLfloat wInv = 1.0F / W(j);
	       win[j][0] = X(j) * wInv * sx + tx;
	       win[j][1] = Y(j) * wInv * sy + ty;
	       win[j][2] = Z(j) * wInv * sz + tz;
	       win[j][3] = wInv;
	    } else {
	       win[j][0] = win[j][1] = win[j][2] = 0.0;
	       win[j][3] = 1.0F;
	    }
	 }
      }
   }

   if (VB->ctx->Driver.RasterSetup)
      VB->ctx->Driver.RasterSetup(VB, VB->FirstFree, VB->Free);

   return n;
}


#define INSIDE( J ) !NEGATIVE(J)
#define OUTSIDE( J ) NEGATIVE(J)




static GLuint TAG(userclip_line)( struct vertex_buffer *VB, 
				  GLuint *i, GLuint *j )
{
   GLcontext *ctx = VB->ctx;
   GLfloat (*coord)[4] = VB->ClipPtr->data;
   clip_interp_func interp = ctx->ClipInterpFunc;
   GLuint ii = *i;
   GLuint jj = *j;
   GLuint p;
   GLuint vb_free = VB->Free;

   for (p=0;p<MAX_CLIP_PLANES;p++) {
      if (ctx->Transform.ClipEnabled[p]) {
	 GLfloat a = ctx->Transform.ClipUserPlane[p][0];
	 GLfloat b = ctx->Transform.ClipUserPlane[p][1];
	 GLfloat c = ctx->Transform.ClipUserPlane[p][2];
	 GLfloat d = ctx->Transform.ClipUserPlane[p][3];

	 GLfloat dpI = d*W(ii) + c*Z(ii) + b*Y(ii) + a*X(ii);
	 GLfloat dpJ = d*W(jj) + c*Z(jj) + b*Y(jj) + a*X(jj);

         GLuint flagI = OUTSIDE( dpI );
         GLuint flagJ = OUTSIDE( dpJ );

	 if (flagI & flagJ) 
	    return 0;

	 if (flagI ^ flagJ) {
	    GLfloat t = -dpI/(dpJ-dpI);

	    INTERP_SZ( t, coord, vb_free, ii, jj, SIZE );
	    interp( VB, vb_free, t, ii, jj );

	    if (flagI) {
	       VB->ClipMask[ii] |= CLIP_USER_BIT;
	       ii = vb_free;
	    } else {
	       VB->ClipMask[jj] |= CLIP_USER_BIT;
	       jj = vb_free;
	    }
	    
	    VB->ClipMask[vb_free++] = 0;
         }
      }
   }

   VB->Free = vb_free;
   *i = ii;
   *j = jj;
   return 1;
}


static GLuint TAG(userclip_polygon)( struct vertex_buffer *VB, 
				     GLuint n, GLuint vlist[] )
{
   GLcontext *ctx = VB->ctx;
   GLfloat (*coord)[4] = VB->ClipPtr->data;
   clip_interp_func interp = ctx->ClipInterpFunc;
   GLuint vlist2[VB_SIZE];
   GLuint *inlist = vlist, *outlist = vlist2;
   GLuint vb_free = VB->Free;
   GLuint p;

   for (p=0;p<MAX_CLIP_PLANES;p++) {
      if (ctx->Transform.ClipEnabled[p]) {
	 register float a = ctx->Transform.ClipUserPlane[p][0];
	 register float b = ctx->Transform.ClipUserPlane[p][1];
	 register float c = ctx->Transform.ClipUserPlane[p][2];
	 register float d = ctx->Transform.ClipUserPlane[p][3];

	 /* initialize prev to be last in the input list */
	 GLuint prevj = inlist[n - 1];
	 GLfloat dpJ = d*W(prevj) + c*Z(prevj) + b*Y(prevj) + a*X(prevj);
	 GLuint flagJ = INSIDE(dpJ);
	 GLuint outcount = 0;
	 GLuint curri;

         for (curri=0;curri<n;curri++) {
	    GLuint currj = inlist[curri];
	    GLfloat dpI = d*W(currj) + c*Z(currj) + b*Y(currj) + a*X(currj);
            GLuint flagI = INSIDE(dpI);

	    if (flagI ^ flagJ) {
	       GLfloat t;
	       GLuint in;
	       GLuint out;

	       if (flagI) {
		  out = prevj;
                  in = currj;
                  t = dpI/(dpI-dpJ);

		  if (IND&CLIP_TAB_EDGEFLAG)
		     VB->EdgeFlagPtr->data[vb_free] =
			VB->EdgeFlagPtr->data[prevj];
	       } else {
		  in = prevj;
                  out = currj;
                  t = dpJ/(dpJ-dpI);

		  if (IND&CLIP_TAB_EDGEFLAG)
		     VB->EdgeFlagPtr->data[vb_free] = 1;
	       }		  
	       
	       INTERP_SZ( t, coord, vb_free, in, out, SIZE );
	       interp( VB, vb_free, t, in, out);
	       outlist[outcount++] = vb_free;
	       VB->ClipMask[vb_free++] = 0;
            }

	    if (flagI) {
	       outlist[outcount++] = currj;
	    } else {
	       VB->ClipMask[currj] |= CLIP_USER_BIT;
	    }

	    prevj = currj;
	    flagJ = flagI;
	    dpJ = dpI;
         } 

	 if (outcount < 3)
	    return 0;
	 else {
            GLuint *tmp;
            tmp = inlist;
            inlist = outlist;
            outlist = tmp;
            n = outcount;
         }

      } /* if */
   } /* for p */

   if (inlist!=vlist) {
      GLuint i;
      for (i = 0 ; i < n ; i++) 
	 vlist[i] = inlist[i];
   }

   VB->Free = vb_free;
   return n;
}


static void TAG(init_clip_funcs)(void)
{
   gl_poly_clip_tab[IND][SIZE] = TAG(viewclip_polygon);
   gl_line_clip_tab[IND][SIZE] = TAG(viewclip_line);
}

#undef W
#undef Z
#undef Y
#undef X
#undef SIZE
#undef TAG
#undef INSIDE
#undef OUTSIDE
#undef IND
