Back to index

radiance  4R0+20100331
o_face.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: o_face.c,v 2.5 2004/03/30 16:13:00 schorsch Exp $";
00003 #endif
00004 /*
00005  *  o_face.c - routines for creating octrees for polygonal faces.
00006  *
00007  *     8/27/85
00008  */
00009 
00010 #include  "standard.h"
00011 
00012 #include  "octree.h"
00013 
00014 #include  "object.h"
00015 
00016 #include  "face.h"
00017 
00018 #include  "plocate.h"
00019 
00020 /*
00021  *     The algorithm for determining a face's intersection
00022  *  with a cube is relatively straightforward:
00023  *
00024  *     1) Check to see if any vertices are inside the cube
00025  *        (intersection).
00026  *
00027  *     2) Check to see if all vertices are to one side of
00028  *        cube (no intersection).
00029  *
00030  *     3) Check to see if any portion of any edge is inside
00031  *        cube (intersection).
00032  *
00033  *     4) Check to see if the cube cuts the plane of the
00034  *        face and one of its edges passes through
00035  *        the face (intersection).
00036  *
00037  *     5) If test 4 fails, we have no intersection.
00038  */
00039 
00040 int
00041 o_face(              /* determine if face intersects cube */
00042        OBJREC  *o,
00043        CUBE  *cu
00044 )
00045 {
00046        FVECT  cumin, cumax;
00047        FVECT  v1, v2;
00048        double  d1, d2;
00049        int  vloc;
00050        register FACE  *f;
00051        register int  i, j;
00052                             /* get face arguments */
00053        f = getface(o);
00054        if (f->area == 0.0)         /* empty face */
00055               return(O_MISS);
00056                                    /* compute cube boundaries */
00057        for (j = 0; j < 3; j++)
00058               cumax[j] = (cumin[j] = cu->cuorg[j]-FTINY)
00059                             + cu->cusize + 2.0*FTINY;
00060 
00061        vloc = ABOVE | BELOW;              /* check vertices */
00062        for (i = 0; i < f->nv; i++)
00063               if ( (j = plocate(VERTEX(f,i), cumin, cumax)) )
00064                      vloc &= j;
00065               else
00066                      return(O_HIT);       /* vertex inside */
00067 
00068        if (vloc)                   /* all to one side */
00069               return(O_MISS);
00070        
00071        for (i = 0; i < f->nv; i++) {      /* check edges */
00072               if ((j = i + 1) >= f->nv)
00073                      j = 0;               /* wrap around */
00074               VCOPY(v1, VERTEX(f,i));            /* clip modifies */
00075               VCOPY(v2, VERTEX(f,j));            /* the vertices! */
00076               if (clip(v1, v2, cumin, cumax))
00077                      return(O_HIT);              /* edge inside */
00078        }
00079                                    /* see if cube cuts plane */
00080        for (j = 0; j < 3; j++)
00081               if (f->norm[j] > 0.0) {
00082                      v1[j] = cumin[j];
00083                      v2[j] = cumax[j];
00084               } else {
00085                      v1[j] = cumax[j];
00086                      v2[j] = cumin[j];
00087               }
00088        if ((d1 = DOT(v1, f->norm) - f->offset) > FTINY)
00089               return(O_MISS);
00090        if ((d2 = DOT(v2, f->norm) - f->offset) < -FTINY)
00091               return(O_MISS);
00092                                    /* intersect face */
00093        for (j = 0; j < 3; j++)
00094               v1[j] = (v1[j]*d2 - v2[j]*d1)/(d2 - d1);
00095        if (inface(v1, f))
00096               return(O_HIT);
00097        
00098        return(O_MISS);             /* no intersection */
00099 }