BOOLEAN.H

Go to the documentation of this file.

/* --
OpenFX version 2.3 - Modelling, Animation and Rendering Package
-- */

/* boolean.h  */

typedef struct Boolean_WORKEDGE {
  long e;
  long ea[2]; 
  short  t;   
  short  b;   
} workedge;

typedef struct Boolean_WORKFACE {
  long f;
  long ea[3]; 
  long fa[3]; 
  int  id;    
  vector n;
} workface;

typedef struct Boolean_TOOLEDGE {
  long e;
  vector p0,p1;
} tooledge;

typedef struct Boolean_TOOLFACE {
  long f;
  point  p0,p1,p2;
  vector n;
} toolface;

typedef struct Boolean_VTXADJ {
  long nf,ne;
  long *flist;
  long *elist;
} vtxadj;

#ifndef min
#define min(a,b)  ( ((a) < (b)) ? (a) : (b) )
#endif
#ifndef max
#define max(a,b)  ( ((a) > (b)) ? (a) : (b) )
#endif
#define VECCOPY(a,b)    { b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; }
#define VECSUB(a,b,c)   { c[0]=a[0]-b[0]; c[1]=a[1]-b[1]; c[2]=a[2]-b[2];}
#define VECSUM(a,b,c)   { c[0]=a[0]+b[0]; c[1]=a[1]+b[1]; c[2]=a[2]+b[2];}
#define VECSCALE(a,b,c) { c[0]=(a)*b[0]; c[1]=(a)*b[1]; c[2]=(a)*b[2];}
#define DOT(a,b)        ( (a[0]*b[0]) + (a[1]*b[1]) + (a[2]*b[2]) )
#define CROSS(v1,v2,r)  { \
                          r[0] = (v1[1]*v2[2]) - (v2[1]*v1[2]);  \
                          r[1] = (v1[2]*v2[0]) - (v1[0]*v2[2]);  \
                          r[2] = (v1[0]*v2[1]) - (v2[0]*v1[1]);  \
                         }
#define POINT2VECTOR(p,v) v[0]=(double)p[0]; v[1]=(double)p[1]; \
                          v[2]=(double)p[2];
#define VECTOR2POINT(v,p) p[0]=(long)v[0]; p[1]=(long)v[1]; \
                          p[2]=(long)v[2];

#define NO               0
#define YES              1
#define FAIL            -1
#define OK               1

static workface *add_small_face(long a, long b, long c,
                                long f, long i, workface *w,
                                long *nface);
static long BoolAddVertex(vector v, short status);
static short EdgePierceFace(vector vi,
                            vector p0, vector p1, vector p2,
                            short *code, short *id);
static short EdgeThroughFace(vector pa, vector pb, vector pc, vector n,
                             vector p0, vector p1, vector p2, short full);
static workface *AddDelaunayTriangulation(vector p2, workface *bf1, long id,
                                     long nns,long *nf, workface *w,
                                     long *nwe,workedge **we);
static short Del_Swap(vector p, long v1l, long v2l, long v3l);
static long Del_Edgeid(long v1, long v2, workface *w, long k,
                       long *fa1, long *fa2, long *e1, long *e2);
static workface *split_edge(vector p2, long  edgeID,
                            workface *w, workedge **e,
                            long *nface, long *nedge, long *LastVtxID);
static void switch_adjacent_faces(long edgeID, workface *w, long n,
                                   workedge *we, long ne);
static int FindAdjFaces(workface *wf, long nf, workedge *we, long ne);
static void SetConnectingID(long);
static void FindBitsAndPieces(workface *, long, workedge *, long, long);
static int can_switch_faces(long , workface *, workedge *);
static void IntersectObject(int, int);

#define TOL  200000.0  // very important DO not TAMPER
#define TOL1    0.0005 //0.001 // 0.01 changed 4/6/95 for problem with missed point
#define TOL2    0.9995 //0.999 // 0.99 in phase one too near an edge and disregarded
#define TOL3   -1.00000
#define TOL8    1.00000
#define TOL5   -0.001
#define TOL6    1.001
#define TOL9  100.0
#define TOLA  100.0
#define TOLB  10.0
#define TOLC  100.0

static short EdgePierceFace(vector vi,
                            vector p0, vector p1, vector p2,
                            short *code, short *id){
/* code  = 0 point vi is in plane and inside face                */
/*       = 1   "      "      "        on edge id id's the edge   */
/*       = 2   "      "      "        at vertex id id's the edge */
 double ve1,ve2,ve3,vp1,vp2,vp3,q1,q2,q3,det,a,b,ab,
        det1,det2,det3,detmax,dm;
 short k;
  q1=vi[0]-p0[0];  q2=vi[1]-p0[1];  q3=vi[2]-p0[2];
 ve1=p2[0]-p0[0]; ve2=p2[1]-p0[1]; ve3=p2[2]-p0[2];
 vp1=p1[0]-p0[0]; vp2=p1[1]-p0[1]; vp3=p1[2]-p0[2];
 det1=ve1*vp2-vp1*ve2;    /* new way to ensure optimum numerics */
 det2=ve2*vp3-vp2*ve3;
 det3=ve1*vp3-vp1*ve3;
 k=0; detmax=TOL;
 if((dm=fabs(det1)) > detmax){k=1; detmax=dm;}
 if((dm=fabs(det2)) > detmax){k=2; detmax=dm;}
 if((dm=fabs(det3)) > detmax){k=3; detmax=dm;}
 if(k == 0)return 0;
 else if(k == 1){
   a=( vp2*q1-vp1*q2)/det1;
   b=(-ve2*q1+ve1*q2)/det1;
 }
 else if(k == 2){
   a=( vp3*q2-vp2*q3)/det2;
   b=(-ve3*q2+ve2*q3)/det2;
 }
 else if(k == 3){
   a=( vp3*q1-vp1*q3)/det3;
   b=(-ve3*q1+ve1*q3)/det3;
 }
 else return 0;
/* a=1 at p2      b=1 at p1  */
 ab=a+b;
 if(a < TOL5 || a > TOL6 || b < TOL5 || b > TOL6 || ab > TOL6)return 0;
 if(a >= TOL1 && a <= TOL2 && b >= TOL1 && b <= TOL2 && ab <= TOL2){
   *code=0;  /* inside face */
   return 1;
 }
 else if(a < TOL1){ /* along edge 0-1 */
   if(b < TOL1){ /* p0 */
     *code=2; *id=0;
     return 1;
   }
   else if(b > TOL2){ /* p1 */
     *code=2; *id=1;
     return 1;
   }
   else{  /* on edge 0-1 */
     *code=1; *id=0;
     return 1;
   }
 }
 else if(b < TOL1){ /* along edge 0-2 */
   if(a < TOL1){ /* p0 */
     *code=2; *id=0;
     return 1;
   }
   else if(a > TOL2){ /* p2 */
     *code=2; *id=2;
     return 1;
   }
   else{ /* on edge 0-2 */
     *code=1; *id=2;
     return 1;
   }
 }
 else if(ab > TOL2){/* on edge 1-2 */
   *code=1; *id=1;
   return 1;
 }
 return 0;
}

static short EdgeThroughFace(vector pa, vector pb, vector pc,vector n,
                             vector p0, vector p1, vector p2, short full){
/* full = 0 implies that the edge intersects the tool face internally.
            At least one vertex of the edge does not lie in the plane
            of the tool face face.
   full = 1 implies that the edge crosses the tool face but it may cross
            the face at one of it's edges, however neither of the vertices
            of the edge lie in/near the plane of the tool face.
   full = 2 implies that if both points lie in plane of tool face then
            it is checked to see if it is a bounding edge.
   pa, pb and pc are the vertices of the face
   p0 and p1 are points at end of edge
   returns p2 point of intersection
   tool edge 0-1 intersects work face
*/
 short code,id;
 vector da,db,dba;
 double d,d0,d1,d01,mu,mu1;
 VECSUB(pa,p0,da)
 VECSUB(pa,p1,db)
 d0=DOT(da,n); d1=DOT(db,n);
 d01 =d0*d1;
 if(fabs(d0) > TOLA || fabs(d1) > TOLA){         /* TOLA => not in plane */
   /* at least one vertex lies out of the tool plane */
   if(d01 <= TOL8){          /* TOL8 => edge crosses the tool face cross */
     VECSUB(p1,p0,dba)
     mu1=DOT(dba,n);
     if(fabs(mu1) > TOL9){
       mu=d0/mu1;
       if(full > 0){   /* not near either end of edge */
         if(fabs(d0) < TOLA || fabs(d1) < TOLA)return 0;
       }
       VECSCALE(mu,dba,dba)
       VECSUM(p0,dba,p2)   /* p2 is the intersection point */
       if(EdgePierceFace(p2,pa,pb,pc,&code,&id)){
         if(code == 0 || full > 0)return 1; /* allow Xn even on face edges */
       }
     }
   }
 }
 else if(full == 2){ /* both points lie in plane of tool face */
   /* check to see if this edge is a boundary edge   */
   VECSUM(p0,p1,dba)
   VECSCALE(0.5,dba,dba)        /* midpoint of edge  */
   VECSUB(pa,dba,da)
   if(fabs(DOT(da,n)) < TOLC){  /*    "  is in plane */
     if(EdgePierceFace(dba,pa,pb,pc,&code,&id))return 2; /* inside toolface */
   }
 }
 return 0;
}

static int O_normalize(vector v){
 double n,nn;
 n= (double)((v[0]*v[0]) + (v[1]*v[1]) + (v[2]*v[2]));
 if(n < 1.e-10)return FAIL;
 nn=sqrt(n);
 n = 1.0 / nn;
 VECSCALE(n,v,v)
 return OK;
}

#if 0
static int PrintAdjFaces(workface *wf, long nf, workedge *we, long ne){
 face *f;
 edge *e;
 vertex *vp;
 long i,nvl=0;
 fprintf(debug,"nwf=%ld nwe=%ld\nVertices\n",nf,ne);
 vp=MainVp; for(i=0;i<Nvert;i++){
   if(vp->status == DESELECTED){ /* work vertex */
     fprintf(debug,"%4ld  [%4ld  %4ld  %4ld]\n",nvl,
     vp->xyz[0]/1024,vp->xyz[1]/1024,vp->xyz[2]/1024);
     nvl++;
   }
   vp++;
 }
 fprintf(debug,"Faces\n");
 for(i=0;i<nf;i++){
  f=(MainFp+wf[i].f);
  fprintf(debug,"f[%4ld] =[%4ld %4ld %4ld]  af=[%4ld  %4ld  %4ld]  ae=[%4ld  %4ld  %4ld]\n",i,
       (MainVp+f->V[0])->id,(MainVp+f->V[1])->id,(MainVp+f->V[2])->id,
       wf[i].fa[0],wf[i].fa[1],wf[i].fa[2],
       wf[i].ea[0],wf[i].ea[1],wf[i].ea[2]);
 }
 fprintf(debug,"Edges\n");
 for(i=0;i<ne;i++){
   e=(MainEp+we[i].e);
   fprintf(debug,"e[%4ld] = [%4ld  %4ld]  af=[%4ld  %4ld]  boundary=[%1ld]\n",i,
      (MainVp+e->V[0])->id,(MainVp+e->V[1])->id,
      we[i].ea[0],we[i].ea[1],we[i].b);
 }
}
#endif