/** 3DGPL *************************************************\
 *  ()                                                    *
 *  3-D volume and Z clipping.                            *
 *                                                        *
 *  Defines:                                              *
 *   C_volume_clipping       Out-of view volume elements; *
 *                                                        *
 *   C_line_z_clipping       Clipping a line;             *
 *   C_polygon_z_clipping    View plane cliping.          *
 *                                                        *
 *  (6/1995) By Sergei Savchenko. (savs@cs.mcgill.ca).    *
 *  Copyright (c) 1995 Sergei Savchenko.                  *
 *  THIS SOURCE CODE CAN'T BE USED FOR COMERCIAL PURPOSES *
 *  WITHOUT AUTHORISATION                                 *
\**********************************************************/

#include <limits.h>                         /* INT_MAX & INT_MIN */

#include "../hardware/hardware.h"           /* HW_copy_int stuff */
#include "../clipper/clipper.h"             /* clipping constants */

int C_3D_clipping;                          /* type of performed clipping */

/**********************************************************\
 *  Hole element volume clipping,                         *
 *                                                        *
 *  RETURNS:  0 when array of passed vertices is for sure *
 *  --------    outside the view volume;                  *
 *           -1 when further clipping is required;        *
 *            1 when element has a fair chanse to be      *
 *              inside the view volume, and should be     *
 *              clipped by 2-D clipping when rendering    *
 *              onto the screen.                          *
 *                                                        *
 *               | z                                      *
 *          \    |    /        View volume is a piramid   *
 *           \   |   /         with 90 degree angle.      *
 *            \  |  /                                     *
 *        -x>z \ | /  x>z                                 *
 *              \|/                                       *
 *       --------+--------- x                             *
 *       z<C_Z_CLIPPING_MIN                               *
 *                                                        *
 *  ADDITIONAL FUNCTIONS: 1) extraction of tuples &       *
 *  ---------------------    FORMAT change                *
 *  source:       n,a1,...,aN      where N=dimension-3    *
 *  destanation:  x,y,z,a1,...,aN  (x,y,z extracted from  *
 *  int *vertex array starting from index n)              *
\**********************************************************/

int C_volume_clipping(register int *from,register int *to,
                      int *vertex,int dimension,int length
                     )
{
 register int i;
 int xmin,ymin,zmin,xmax,ymax,zmax;

 dimension-=3;                              /* but X,Y,Z */

 ymin=xmin=zmin=INT_MAX;
 ymax=xmax=zmax=INT_MIN;                    /* initializing searching */

 for(i=0;i<length;i++)
 {
  HW_copy_int(&vertex[*from++],to,3);       /* copying actual tuples */

  if(*to>xmax) xmax=*to;                    /* determining polygon extend */
  if(*to<xmin) xmin=*to;
  to++;
  if(*to>ymax) ymax=*to;
  if(*to<ymin) ymin=*to;
  to++;
  if(*to>zmax) zmax=*to;
  if(*to<zmin) zmin=*to;                    /* by searching max/min */
  to++;

  HW_copy_int(from,to,dimension);           /* rest (for shading etc)*/
  to+=dimension;
  from+=dimension;
 }

 if((zmax<xmin)||(zmax<ymin)||(zmax<-xmax)||
   (zmax<-ymax)||(zmax<=C_Z_CLIPPING_MIN))
  return(0);                                /* outside */
 else
  if(zmin<C_Z_CLIPPING_MIN) return(-1);     /* partly behind clipping plane */
  else return(1);
}

/**********************************************************\
 *  Line clipping using binary search technique.          *
 *                                                        *
 *  RETURNS: 0 element is outside the view volume;        *
 *  -------  1 element is clipped to the view volume.     *
 *                                                        *
 *  SETS: C_3D_clipping to 1 if first vertex was clipped; *
 *  -----               0 otherwise.                      *
\**********************************************************/

int C_line_z_clipping(int **vertex1,int **vertex2,int dimension)
{
 register int i;
 register int whereto;
 register int *l,*r,*m,*t;                  /* left right and midle and tmp */
 static int c_store0[C_MAX_DIMENSIONS];     /* static stores for clipped vxes */
 static int c_store1[C_MAX_DIMENSIONS];
 static int c_store2[C_MAX_DIMENSIONS];
 int **vmn,**vmx;                           /* so that *vmn[3] < *vmx[3] */
 int swap;                                  /* were coordinates swaped? */

 C_3D_clipping=0;                           /* default no clipping yet */

 if((*vertex1)[2]<(*vertex2)[2])            /* only Z counts 0=X,1=Y,2=Z,... */
 { swap=0; vmn=vertex1; vmx=vertex2; }      /* so that *vmn[2] < *vmx[2] */
 else
 { swap=1; vmn=vertex2; vmx=vertex1; }

 if((*vmx)[2]<C_Z_CLIPPING_MIN) return(0);
 else
 {
  if((*vmn)[2]<=C_Z_CLIPPING_MIN)           /* clipping */
  {
   HW_copy_int(*vmn,l=c_store0,dimension);  /* copying old vertices */
   HW_copy_int(*vmx,m=c_store1,dimension);
   r=c_store2;

   whereto=0;
   while(m[2]!=C_Z_CLIPPING_MIN)
   {
    if(whereto==1) { t=l; l=m; m=t; }
    else           { t=r; r=m; m=t; }
    for(i=0;i<dimension;i++) m[i]=(l[i]+r[i])>>1;
    whereto=m[2]<C_Z_CLIPPING_MIN;
   }
   *vmn=m;                                  /* that is why m[] is static */
   C_3D_clipping=swap^1;
  }
  return(1);                                /* partialy or not clipped */
 }
}

/***********************************************************\
 *  Creating a z-clipped polygon.                          *
 *                                                         *
 *  RETURNS: number of elements in the clipped polygon.    *
 *  -------  (0 when compleately behind view plane)        *
 *                                                         *
 *          |            1-2-3-4-5-6-1  -> 2-2'-5'-6-1-2   *
 *          |5'                                            *
 *       5*-*-----*6     If first dot in the line is being *
 *       /  |      \     clipped both points are copyed,   *
 *     4*   |       *1   If no clipping or second point is *
 *       \  |      /     clipped then only second point is *
 *       3*-*-----*2     copyed. If both points are        *
 *          |2'          clipped well, neither is copyed.  *
\***********************************************************/

int C_polygon_z_clipping(register int *from,register int *to,
                         int dimension,int length
                        )
{
 register int i;
 int *v1,*v2,new_lng=0;
 int *first_vrtx=to;                        /* begining of the source */

 for(i=0;i<length;i++)                      /* for all edges */
 {
  v1=from; from+=dimension; v2=from;        /* taking two vertices */

  if(C_line_z_clipping(&v1,&v2,dimension))  /* clipping */
  {
   if(C_3D_clipping)                        /* depends which one was clipped */
   {
    HW_copy_int(v1,to,dimension); to+=dimension;
    HW_copy_int(v2,to,dimension); to+=dimension;
    new_lng+=2;                             /* first point clipped */
   }
   else
   {
    HW_copy_int(v2,to,dimension); to+=dimension;
    new_lng++;                              /* second point clipped */
   }
  }
 }
 HW_copy_int(first_vrtx,to,dimension);      /* looping the polygon vertices */

 return(new_lng);
}

/**********************************************************/