home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / radsrc22 / src / ot / o_face.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-12  |  2.4 KB  |  102 lines
  1. /* Copyright (c) 1986 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)o_face.c 2.1 11/12/91 LBL";
  5. #endif
  6.  
  7. /*
  8.  *  o_face.c - routines for creating octrees for polygonal faces.
  9.  *
  10.  *     8/27/85
  11.  */
  12.  
  13. #include  "standard.h"
  14.  
  15. #include  "octree.h"
  16.  
  17. #include  "object.h"
  18.  
  19. #include  "face.h"
  20.  
  21. #include  "plocate.h"
  22.  
  23. /*
  24.  *    The algorithm for determining a face's intersection
  25.  *  with a cube is relatively straightforward:
  26.  *
  27.  *    1) Check to see if any vertices are inside the cube
  28.  *       (intersection).
  29.  *
  30.  *    2) Check to see if all vertices are to one side of
  31.  *       cube (no intersection).
  32.  *
  33.  *    3) Check to see if any portion of any edge is inside
  34.  *       cube (intersection).
  35.  *
  36.  *    4) Check to see if the cube cuts the plane of the
  37.  *       face and one of its edges passes through
  38.  *       the face (intersection).
  39.  *
  40.  *    5) If test 4 fails, we have no intersection.
  41.  */
  42.  
  43.  
  44. o_face(o, cu)            /* determine if face intersects cube */
  45. OBJREC  *o;
  46. CUBE  *cu;
  47. {
  48.     FVECT  cumin, cumax;
  49.     FVECT  v1, v2;
  50.     double  d1, d2;
  51.     int  vloc;
  52.     register FACE  *f;
  53.     register int  i, j;
  54.                 /* get face arguments */
  55.     f = getface(o);
  56.     if (f->area == 0.0)        /* empty face */
  57.         return(O_MISS);
  58.                     /* compute cube boundaries */
  59.     for (j = 0; j < 3; j++)
  60.         cumax[j] = (cumin[j] = cu->cuorg[j]-FTINY)
  61.                 + cu->cusize + 2.0*FTINY;
  62.  
  63.     vloc = ABOVE | BELOW;        /* check vertices */
  64.     for (i = 0; i < f->nv; i++)
  65.         if (j = plocate(VERTEX(f,i), cumin, cumax))
  66.             vloc &= j;
  67.         else
  68.             return(O_HIT);    /* vertex inside */
  69.  
  70.     if (vloc)            /* all to one side */
  71.         return(O_MISS);
  72.     
  73.     for (i = 0; i < f->nv; i++) {    /* check edges */
  74.         if ((j = i + 1) >= f->nv)
  75.             j = 0;            /* wrap around */
  76.         VCOPY(v1, VERTEX(f,i));        /* clip modifies */
  77.         VCOPY(v2, VERTEX(f,j));        /* the vertices! */
  78.         if (clip(v1, v2, cumin, cumax))
  79.             return(O_HIT);        /* edge inside */
  80.     }
  81.                     /* see if cube cuts plane */
  82.     for (j = 0; j < 3; j++)
  83.         if (f->norm[j] > 0.0) {
  84.             v1[j] = cumin[j];
  85.             v2[j] = cumax[j];
  86.         } else {
  87.             v1[j] = cumax[j];
  88.             v2[j] = cumin[j];
  89.         }
  90.     if ((d1 = DOT(v1, f->norm) - f->offset) > FTINY)
  91.         return(O_MISS);
  92.     if ((d2 = DOT(v2, f->norm) - f->offset) < -FTINY)
  93.         return(O_MISS);
  94.                     /* intersect face */
  95.     for (j = 0; j < 3; j++)
  96.         v1[j] = (v1[j]*d2 - v2[j]*d1)/(d2 - d1);
  97.     if (inface(v1, f))
  98.         return(O_HIT);
  99.     
  100.     return(O_MISS);        /* no intersection */
  101. }
  102.