home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch7_2 / fpcube.c next >
Encoding:
C/C++ Source or Header  |  1995-03-07  |  6.9 KB  |  209 lines
  1.  
  2. /*
  3.  *                  FAST POLYGON-CUBE INTERSECTION TESTS
  4.  *                  by Daniel Green
  5.  *                  January 1994
  6.  *
  7.  *
  8.  * The original inspiration for this routine comes from the triangle-cube
  9.  * intersection algorithm in Graphics Gems III by Douglas Voorhies.
  10.  * Aside from the fact that the original code was special-cased for triangles
  11.  * only, it suffered from some bugs.  Don Hatch re-wrote the non-trivial tests
  12.  * using the same basic ideas, fixed the bugs and also made it more
  13.  * general and efficient.  Don's implementation performs just the
  14.  * intersection calculations without any trivial accept or reject tests,
  15.  * and is embodied in the routine polygon_intersects_cube().
  16.  *
  17.  * The function implemented here is simply a wrapper that begins with a
  18.  * slightly more efficient version of Voorhies' original trivial reject tests
  19.  * and only calls polygon_intersects_cube() when those tests fail.
  20.  * The result is a fast and robust polygon-cube tester.
  21.  *
  22.  * Also included here is trivial_vertex_tests() which is used by
  23.  * fast_polygon_intersects_cube().  It can be used to quickly test an entire
  24.  * set of vertices for trivial reject or accept.  This is useful for testing
  25.  * polyhedra or polygon meshes.
  26.  *
  27.  * WARNING: When used to test intersection of a polyhedron with the unit cube,
  28.  * remember that these routines only test *surfaces* and not volumes.
  29.  * If polygon_intersects_cube() reports no intersection with any of the faces
  30.  * of the polyhedron, the caller should be aware that the polyhedron
  31.  * could still contain the whole unit cube which would then need to be checked
  32.  * with a point-within-polyhedron test.  The origin would be a natural point
  33.  * to check in such a test.
  34.  */
  35.  
  36.  
  37. #include "pcube.h"
  38.  
  39. #ifndef __cplusplus
  40. #define inline
  41. #endif
  42.  
  43.  
  44. #define TEST_AGAINST_PARALLEL_PLANES(posbit, negbit, value, limit)    \
  45.     if (mask & (posbit|negbit)) {                    \
  46.         register real temp = value;                \
  47.         if ((mask & posbit) && temp > limit)            \
  48.             outcode |= posbit;                \
  49.         else if ((mask & negbit) && temp < -limit)        \
  50.             outcode |= negbit;                \
  51.     }                                \
  52.  
  53.  
  54. /*
  55.  * Tells which of the six face-planes the given point is outside of.
  56.  * Only tests faces not represented in "mask".
  57.  */
  58.  
  59. static inline unsigned long
  60. face_plane(const real p[3], unsigned long mask)
  61. {
  62.     register unsigned long outcode = 0L;
  63.  
  64.     TEST_AGAINST_PARALLEL_PLANES(0x001, 0x002, p[0], 0.5)
  65.     TEST_AGAINST_PARALLEL_PLANES(0x004, 0x008, p[1], 0.5)
  66.     TEST_AGAINST_PARALLEL_PLANES(0x010, 0x020, p[2], 0.5)
  67.  
  68.     return(outcode);
  69. }
  70.  
  71.  
  72.  
  73. /*
  74.  * Tells which of the twelve edge planes the given point is outside of.
  75.  * Only tests faces not represented in "mask".
  76.  */
  77.  
  78. static inline unsigned long
  79. bevel_2d(const real p[3], unsigned long mask)
  80. {
  81.     register unsigned long outcode = 0L;
  82.  
  83.     TEST_AGAINST_PARALLEL_PLANES(0x001, 0x002, p[0] + p[1], 1.0)
  84.     TEST_AGAINST_PARALLEL_PLANES(0x004, 0x008, p[0] - p[1], 1.0)
  85.     TEST_AGAINST_PARALLEL_PLANES(0x010, 0x020, p[0] + p[2], 1.0)
  86.     TEST_AGAINST_PARALLEL_PLANES(0x040, 0x080, p[0] - p[2], 1.0)
  87.     TEST_AGAINST_PARALLEL_PLANES(0x100, 0x200, p[1] + p[2], 1.0)
  88.     TEST_AGAINST_PARALLEL_PLANES(0x400, 0x800, p[1] - p[2], 1.0)
  89.  
  90.     return(outcode);
  91. }
  92.  
  93.  
  94.  
  95. /*
  96.  * Tells which of the eight corner planes the given point is outside of.
  97.  * Only tests faces not represented in "mask".
  98.  */
  99.  
  100. static inline unsigned long
  101. bevel_3d(const real p[3], unsigned long mask)
  102. {
  103.     register unsigned long outcode = 0L;
  104.  
  105.     TEST_AGAINST_PARALLEL_PLANES(0x001, 0x002, p[0] + p[1] + p[2], 1.5)
  106.     TEST_AGAINST_PARALLEL_PLANES(0x004, 0x008, p[0] + p[1] - p[2], 1.5)
  107.     TEST_AGAINST_PARALLEL_PLANES(0x010, 0x020, p[0] - p[1] + p[2], 1.5)
  108.     TEST_AGAINST_PARALLEL_PLANES(0x040, 0x080, p[0] - p[1] - p[2], 1.5)
  109.  
  110.     return(outcode);
  111. }
  112.  
  113.  
  114.  
  115. /*
  116.  * Returns 1 if any of the vertices are inside the cube of edge length 1
  117.  * centered at the origin (trivial accept), 0 if all vertices are outside
  118.  * of any testing plane (trivial reject), -1 otherwise (couldn't help).
  119.  */
  120.  
  121. extern int
  122. trivial_vertex_tests(int nverts, const real verts[][3],
  123.             int already_know_verts_are_outside_cube)
  124. {
  125.     register unsigned long cum_and;  /* cumulative logical ANDs */
  126.     register int i;
  127.  
  128.     /*
  129.      * Compare the vertices with all six face-planes.
  130.      * If it's known that no vertices are inside the unit cube
  131.      * we can exit the loop early if we run out of bounding
  132.      * planes that all vertices might be outside of.  That simply means
  133.      * that this test failed and we can go on to the next one.
  134.      * If we must test for vertices within the cube, the loop is slightly
  135.      * different in that we can trivially accept if we ever do find a
  136.      * vertex within the cube, but we can't break the loop early if we run
  137.      * out of planes to reject against because subsequent vertices might
  138.      * still be within the cube.
  139.      */
  140.     cum_and = ~0L;  /* Set to all "1" bits */
  141.     if(already_know_verts_are_outside_cube) {
  142.         for(i=0; i<nverts; i++)
  143.             if(0L == (cum_and = face_plane(verts[i], cum_and)))
  144.                 break; /* No planes left to trivially reject */
  145.     }
  146.     else {
  147.         for(i=0; i<nverts; i++) {
  148.             /* Note the ~0L mask below to always test all planes */
  149.             unsigned long face_bits = face_plane(verts[i], ~0L);
  150.             if(0L == face_bits)  /* vertex is inside the cube */
  151.                 return 1; /* trivial accept */
  152.             cum_and &= face_bits;
  153.         }
  154.     }
  155.     if(cum_and != 0L)  /* All vertices outside some face plane. */
  156.         return 0;  /* Trivial reject */
  157.  
  158.     /*
  159.      * Now do the just the trivial reject test against the 12 edge planes.
  160.      */
  161.     cum_and = ~0L;  /* Set to all "1" bits */
  162.     for(i=0; i<nverts; i++)
  163.         if(0L == (cum_and = bevel_2d(verts[i], cum_and)))
  164.             break; /* No planes left that might trivially reject */
  165.     if(cum_and != 0L)  /* All vertices outside some edge plane. */
  166.         return 0;  /* Trivial reject */
  167.  
  168.     /*
  169.      * Now do the trivial reject test against the 8 corner planes.
  170.      */
  171.     cum_and = ~0L;  /* Set to all "1" bits */
  172.     for(i=0; i<nverts; i++)
  173.         if(0L == (cum_and = bevel_3d(verts[i], cum_and)))
  174.             break; /* No planes left that might trivially reject */
  175.     if(cum_and != 0L)  /* All vertices outside some corner plane. */
  176.         return 0;  /* Trivial reject */
  177.  
  178.     /*
  179.      * By now we know that the polygon is not to the outside of any of the
  180.      * test planes and can't be trivially accepted *or* rejected.
  181.      */
  182.     return -1;
  183. }
  184.  
  185.  
  186.  
  187. /*
  188.  * This is a version of the same polygon-cube intersection that first calls
  189.  * trivial_vertex_tests() to hopefully skip the more expensive definitive test.
  190.  * It simply calls polygon_intersects_cube() when that fails.
  191.  * Note that after the trivial tests we at least know that all vertices are
  192.  * outside the cube and can therefore pass a true flag to
  193.  * polygon_intersects_cube().
  194.  */
  195. extern int
  196. fast_polygon_intersects_cube(int nverts, const real verts[][3],
  197.                         const real polynormal[3],
  198.             int already_know_verts_are_outside_cube,
  199.             int already_know_edges_are_outside_cube)
  200. {
  201.     int quick_test = trivial_vertex_tests(nverts, verts,
  202.                 already_know_verts_are_outside_cube);
  203.     if(-1 == quick_test)
  204.         return polygon_intersects_cube(nverts, verts, polynormal, 1,
  205.                 already_know_edges_are_outside_cube);
  206.     else
  207.         return quick_test;
  208. }
  209.