sh: src/shclippg.c Source File

00001 
00006 /*
00007  *  PROGRAM NAME:  sh
00008  *
00009  *  (c) COPYRIGHT INTERNATIONAL BUSINESS MACHINES
00010  *  CORPORATION 12/1/2001.  ALL RIGHTS RESERVED.
00011  *
00012  *  Please refer to the LICENSE file in the top directory
00013  *
00014  *      author: Mike Henderson mhender@watson.ibm.com
00015  */
00016 
00017 static char *id="@(#) $Id: shclippg.c,v 1.2 2006/08/17 19:28:17 mhender Exp $";
00018 
00019 #include <shInternal.h>
00020 #include <math.h>
00021 #include <stdio.h>
00022 
00025 #define maxpol 1000
00026 
00045 void shclippg(int *n0,float *x0,float *y0,float *z0,float *nrm0,int *ic0,int *n1,float **x1,float **y1,float **z1,float **nrm1,int **ic1)
00046  {
00047 
00048 /*     clip a polygon */
00049 
00050   float *x2,*y2,*z2;
00051   float *nrm2;
00052   int *ic2;
00053   int in0,in1;
00054   int m1,m2;
00055   int i,j,ip;
00056   float direc;
00057   float t;
00058   int i0;
00059   int verbose;
00060 
00061   verbose=0;
00062 
00063   m2=maxpol;
00064   x2=(float*)malloc(m2*sizeof(float));
00065   y2=(float*)malloc(m2*sizeof(float));
00066   z2=(float*)malloc(m2*sizeof(float));
00067   nrm2=(float*)malloc(3*m2*sizeof(float));
00068   ic2=(int*)malloc(m2*sizeof(int));
00069 
00070   m1=(*n0)+1;
00071   if(*x1==(float*)NULL)*x1=(float*)malloc(m1*sizeof(float));
00072   if(*y1==(float*)NULL)*y1=(float*)malloc(m1*sizeof(float));
00073   if(*z1==(float*)NULL)*z1=(float*)malloc(m1*sizeof(float));
00074   if(*nrm1==(float*)NULL)*nrm1=(float*)malloc(3*m1*sizeof(float));
00075   if(*ic1==(int*)NULL)*ic1=(int*)malloc(m1*sizeof(int));
00076 
00077 /* Clipping Planes */
00078 
00079 /*    NPLNS     Number of clipping planes */
00080 /*    PLNO[2+3*M) point on plane M */
00081 /*    PLNN[2+3*M) normal to plane M */
00082 /*    IPLN(M)   side of plane M to clip (IPLN*PLNN<0 ==> clipped) */
00083 /*    oper(M)   whether clipping is ored or anded. */
00084 
00085 
00086 /* copy polygon 0 into 1, removing near duplicates. */
00087 
00088   *n1=0;
00089   (*x1)[*n1]=x0[0];
00090   (*y1)[*n1]=y0[0];
00091   (*z1)[*n1]=z0[0];
00092   (*nrm1)[0+3*(*n1)]=nrm0[0];
00093   (*nrm1)[1+3*(*n1)]=nrm0[1];
00094   (*nrm1)[2+3*(*n1)]=nrm0[2];
00095   (*ic1)[*n1]=ic0[0];
00096   (*n1)++;
00097   for(i=1;i<*n0;i++)
00098    {
00099     if(fabs(x0[i]-x0[i-1])+fabs(y0[i]-y0[i-1])+fabs(z0[i]-z0[i-1])>1.e-6)
00100      {
00101       (*x1)[*n1]=x0[i];
00102       (*y1)[*n1]=y0[i];
00103       (*z1)[*n1]=z0[i];
00104       (*nrm1)[  3*(*n1)]=nrm0[  3*i];
00105       (*nrm1)[1+3*(*n1)]=nrm0[1+3*i];
00106       (*nrm1)[2+3*(*n1)]=nrm0[2+3*i];
00107       (*ic1)[(*n1)]=ic0[i];
00108       (*n1)++;
00109      }
00110    }
00111 
00112 /* Duplicate first point */
00113 
00114   (*x1)[*n1]=x0[0];
00115   (*y1)[*n1]=y0[0];
00116   (*z1)[*n1]=z0[0];
00117   (*nrm1)[  3*(*n1)]=nrm0[  3*0];
00118   (*nrm1)[1+3*(*n1)]=nrm0[1+3*0];
00119   (*nrm1)[2+3*(*n1)]=nrm0[2+3*0];
00120   (*ic1)[(*n1)]=ic0[0];
00121   (*n1)++;
00122 
00123 /* Loop over the clipping planes */
00124 
00125 /*    in0=this point visible, in1=next point visible */
00126 
00127   if(sh_nplns==0)
00128    {
00129     free(x2);
00130     free(y2);
00131     free(z2);
00132     free(nrm2);
00133     free(ic2);
00134     return;
00135    }
00136 
00137   for(ip=0;ip<sh_nplns;ip++)
00138    {
00139     if(verbose)printf("plane %d is ((x,y,z)-(%f,%f,%f)).(%f,%f,%f)*%d>0\n",ip,sh_plno[  3*ip],sh_plno[1+3*ip],sh_plno[2+3*ip],sh_plnn[  3*ip],sh_plnn[1+3*ip],sh_plnn[2+3*ip],sh_ipln[ip]);
00140     in0=0;
00141     i0=0;
00142     for(i=0;i<*n1;i++)
00143      {
00144       if(verbose){printf("vertex %d(%d) (%f,%f,%f) is ",i,*n1,(*x1)[i],(*y1)[i],(*z1)[i]);fflush(stdout);}
00145       direc=sh_plnn[  3*ip]*((*x1)[i]-sh_plno[  3*ip])+sh_plnn[1+3*ip]*((*y1)[i]-sh_plno[1+3*ip])+sh_plnn[2+3*ip]*((*z1)[i]-sh_plno[2+3*ip]);
00146       in1=sh_ipln[ip]*direc>0;
00147       if(verbose){if(in1)printf("in\n");else printf("out\n");}
00148       if(!in0)i0=i;
00149       in0=in0||in1;
00150      }
00151     if(verbose)fflush(stdout);
00152     if(!in0)
00153      {
00154       if(verbose){printf("Polygon completely outside\n\n");fflush(stdout);}
00155       *n1=0;
00156       free(x2);
00157       free(y2);
00158       free(z2);
00159       free(nrm2);
00160       free(ic2);
00161       return;
00162      }
00163 
00164     if(i0>0)i0--;
00165 
00166     if(verbose){printf("Starting at vertex %d\n",i0);fflush(stdout);}
00167 #define JUNK
00168 #ifdef JUNK
00169     j=0;
00170     direc=sh_plnn[  3*ip]*((*x1)[i0]-sh_plno[  3*ip])+sh_plnn[1+3*ip]*((*y1)[i0]-sh_plno[1+3*ip])+sh_plnn[2+3*ip]*((*z1)[i0]-sh_plno[2+3*ip]);
00171     in0=sh_ipln[ip]*direc>0;
00172     i=i0;
00173     while(i+1<*n1)
00174      {
00175       if(verbose){printf("Vertex %d(%d) (%f,%f,%f) next is %d (%f,%f,%f)\n",i,*n1,(*x1)[i],(*y1)[i],(*z1)[i],i+1,(*x1)[i+1],(*y1)[i+1],(*z1)[i+1]);fflush(stdout);}
00176       direc=sh_plnn[  3*ip]*((*x1)[i+1]-sh_plno[  3*ip])
00177            +sh_plnn[1+3*ip]*((*y1)[i+1]-sh_plno[1+3*ip])
00178            +sh_plnn[2+3*ip]*((*z1)[i+1]-sh_plno[2+3*ip]);
00179       in1=sh_ipln[ip]*direc>0;
00180       if(verbose)
00181        {
00182         if(in0){printf("   %d is in\n",i);fflush(stdout);}
00183         if(!in0){printf("   %d is out\n",i);fflush(stdout);}
00184         if(in1){printf("   %d is in\n",i+1);fflush(stdout);}
00185         if(!in1){printf("   %d is out\n",i+1);fflush(stdout);}
00186        }
00187       if(!in0&&!in1)
00188        {
00189         if(verbose){printf("   !in0&&!in1\n");fflush(stdout);}
00190         in0=in1;
00191         i++;
00192        }else if(in0&&in1)
00193        {
00194         if(verbose){printf("   in0&&in1\n");fflush(stdout);}
00195         in0=in1;
00196         if(j+1>m2)
00197          {
00198           m2+=5;
00199           x2=(float*)realloc((void*)x2,m2*sizeof(float));
00200           y2=(float*)realloc((void*)y2,m2*sizeof(float));
00201           z2=(float*)realloc((void*)z2,m2*sizeof(float));
00202           nrm2=(float*)realloc((void*)nrm2,3*m2*sizeof(float));
00203           ic2=(int*)realloc((void*)ic2,m2*sizeof(int));
00204          }
00205         x2[j]=(*x1)[i];
00206         y2[j]=(*y1)[i];
00207         z2[j]=(*z1)[i];
00208         nrm2[  3*j]=(*nrm1)[  3*i];
00209         nrm2[1+3*j]=(*nrm1)[1+3*i];
00210         nrm2[2+3*j]=(*nrm1)[2+3*i];
00211         ic2[j]=(*ic1)[i];
00212         j++;
00213 
00214         i++;
00215        }else if(!in0&&in1)
00216        {
00217         if(verbose){printf("   !in0&&in1\n");fflush(stdout);}
00218         t=-( sh_plnn[  3*ip]*((*x1)[i]-sh_plno[  3*ip])
00219             +sh_plnn[1+3*ip]*((*y1)[i]-sh_plno[1+3*ip])
00220             +sh_plnn[2+3*ip]*((*z1)[i]-sh_plno[2+3*ip]) )
00221           /( sh_plnn[  3*ip]*((*x1)[i+1]-(*x1)[i])
00222             +sh_plnn[1+3*ip]*((*y1)[i+1]-(*y1)[i])
00223             +sh_plnn[2+3*ip]*((*z1)[i+1]-(*z1)[i]) );
00224         (*x1)[i]=(*x1)[i]+t*((*x1)[i+1]-(*x1)[i]);
00225         (*y1)[i]=(*y1)[i]+t*((*y1)[i+1]-(*y1)[i]);
00226         (*z1)[i]=(*z1)[i]+t*((*z1)[i+1]-(*z1)[i]);
00227         (*nrm1)[  3*i]=(*nrm1)[  3*i]+t*((*nrm1)[  3*(i+1)]-(*nrm1)[  3*i]);
00228         (*nrm1)[1+3*i]=(*nrm1)[1+3*i]+t*((*nrm1)[1+3*(i+1)]-(*nrm1)[1+3*i]);
00229         (*nrm1)[2+3*i]=(*nrm1)[2+3*i]+t*((*nrm1)[2+3*(i+1)]-(*nrm1)[2+3*i]);
00230         (*ic1)[i]=-1;
00231         if(j+1>m2)
00232          {
00233           m2+=5;
00234           x2=(float*)realloc((void*)x2,m2*sizeof(float));
00235           y2=(float*)realloc((void*)y2,m2*sizeof(float));
00236           z2=(float*)realloc((void*)z2,m2*sizeof(float));
00237           nrm2=(float*)realloc((void*)nrm2,3*m2*sizeof(float));
00238           ic2=(int*)realloc((void*)ic2,m2*sizeof(int));
00239          }
00240         x2[j]=(*x1)[i];
00241         y2[j]=(*y1)[i];
00242         z2[j]=(*z1)[i];
00243         nrm2[  3*j]=(*nrm1)[  3*i];
00244         nrm2[1+3*j]=(*nrm1)[1+3*i];
00245         nrm2[2+3*j]=(*nrm1)[2+3*i];
00246         ic2[j]=(*ic1)[i];
00247         j++;
00248         in0=1;
00249         i++;
00250        }else if(in0&&!in1)
00251        {
00252         if(verbose){printf("   in0&&!in1\n");fflush(stdout);}
00253         t=-( sh_plnn[  3*ip]*((*x1)[i]-sh_plno[  3*ip])
00254             +sh_plnn[1+3*ip]*((*y1)[i]-sh_plno[1+3*ip])
00255             +sh_plnn[2+3*ip]*((*z1)[i]-sh_plno[2+3*ip]) )
00256           /( sh_plnn[  3*ip]*((*x1)[i+1]-(*x1)[i])
00257             +sh_plnn[1+3*ip]*((*y1)[i+1]-(*y1)[i])
00258             +sh_plnn[2+3*ip]*((*z1)[i+1]-(*z1)[i]) );
00259         if(j+2>m2)
00260          {
00261           m2+=5;
00262           x2=(float*)realloc((void*)x2,m2*sizeof(float));
00263           y2=(float*)realloc((void*)y2,m2*sizeof(float));
00264           z2=(float*)realloc((void*)z2,m2*sizeof(float));
00265           nrm2=(float*)realloc((void*)nrm2,3*m2*sizeof(float));
00266           ic2=(int*)realloc((void*)ic2,m2*sizeof(int));
00267          }
00268         x2[j]=(*x1)[i];
00269         y2[j]=(*y1)[i];
00270         z2[j]=(*z1)[i];
00271         nrm2[  3*j]=(*nrm1)[  3*i];
00272         nrm2[1+3*j]=(*nrm1)[1+3*i];
00273         nrm2[2+3*j]=(*nrm1)[2+3*i];
00274         ic2[j]=(*ic1)[i];
00275         j++;
00276 
00277         (*x1)[i]=(*x1)[i]+t*((*x1)[i+1]-(*x1)[i]);
00278         (*y1)[i]=(*y1)[i]+t*((*y1)[i+1]-(*y1)[i]);
00279         (*z1)[i]=(*z1)[i]+t*((*z1)[i+1]-(*z1)[i]);
00280         (*nrm1)[  3*i]=(*nrm1)[  3*i]+t*((*nrm1)[  3*(i+1)]-(*nrm1)[  3*i]);
00281         (*nrm1)[1+3*i]=(*nrm1)[1+3*i]+t*((*nrm1)[1+3*(i+1)]-(*nrm1)[1+3*i]);
00282         (*nrm1)[2+3*i]=(*nrm1)[2+3*i]+t*((*nrm1)[2+3*(i+1)]-(*nrm1)[2+3*i]);
00283         (*ic1)[i]=1;
00284 
00285         x2[j]=(*x1)[i];
00286         y2[j]=(*y1)[i];
00287         z2[j]=(*z1)[i];
00288         nrm2[  3*j]=(*nrm1)[  3*i];
00289         nrm2[1+3*j]=(*nrm1)[1+3*i];
00290         nrm2[2+3*j]=(*nrm1)[2+3*i];
00291         ic2[j]=(*ic1)[i];
00292         j++;
00293 
00294         in0=0;
00295        }
00296      }                             /* End of while(i+1<*n1)       */
00297     if(verbose){printf("done plane %d, Caught %d vertices\n",ip,j);fflush(stdout);} 
00298 
00299 /*  Copy back from 2 into 1 */
00300 
00301     if(j+1>m1)
00302      {
00303       m1=j+3;
00304       *x1=(float*)realloc((void*)(*x1),m1*sizeof(float));
00305       *y1=(float*)realloc((void*)(*y1),m1*sizeof(float));
00306       *z1=(float*)realloc((void*)(*z1),m1*sizeof(float));
00307       *nrm1=(float*)realloc((void*)(*nrm1),3*m1*sizeof(float));
00308       *ic1=(int*)realloc((void*)(*ic1),m1*sizeof(int));
00309      }
00310 
00311     for(i=0;i<j;i++)
00312      {
00313       (*x1)[i]=x2[i];
00314       (*y1)[i]=y2[i];
00315       (*z1)[i]=z2[i];
00316       (*nrm1)[  3*i]=nrm2[  3*i];
00317       (*nrm1)[1+3*i]=nrm2[1+3*i];
00318       (*nrm1)[2+3*i]=nrm2[2+3*i];
00319       (*ic1)[i]=ic2[i];
00320      }
00321     (*x1)[j]=x2[0];
00322     (*y1)[j]=y2[0];
00323     (*z1)[j]=z2[0];
00324     (*nrm1)[  3*j]=nrm2[  3*0];
00325     (*nrm1)[1+3*j]=nrm2[1+3*0];
00326     (*nrm1)[2+3*j]=nrm2[2+3*0];
00327     (*ic1)[j]=ic2[0];
00328     (*n1)=j+1;
00329 #endif
00330    }                               /* End of for(ip=0;ip<sh_nplns;ip++) */
00331 
00332   if(verbose){printf("Part of Polygon remains unclipped, %d vertices\n\n",j);fflush(stdout);} 
00333 
00334   free(x2);
00335   free(y2);
00336   free(z2);
00337   free(nrm2);
00338   free(ic2);
00339 
00340   return;
00341  }