readme

[Game.Programming].Academic - Graphics Gems (6 books source code)

		EFFICIENT INTERSECTION TESTING OF
		GENERAL  POLYGONS  AND  POLYHEDRA
		AGAINST AN  AXIALLY-ALIGNED  CUBE

                Authors:
                        Don Hatch - [e-mail]
                        Daniel Green - [e-mail]
                January 1994


Published routines:

        polygon_intersects_cube
        fast_polygon_intersects_cube
        trivial_vertex_tests
        segment_intersects_cube
        polygon_contains_point_3d


BACKGROUND

In Graphics Gems III, Douglas Voorhies gives  an algorithm  that  tests
whether  a  given  triangle intersects the axially-aligned cube of edge
length 1 centered at the origin.  The algorithm presented here  extends
that work in several ways.  The most important difference is that it is
generalized to handle arbitrary polygons which may be  convex,  concave
or  self-intersecting.   The  implementation  is also more efficient in
several places and fixes bugs in the original implementation which  can
generate  both  false  positive  and  false  negative results.  The new
efficiency and robustness come mostly from  completely  rewritten  core
routines.

In Graphics  Gems IV, Ned  Greene describes an efficient  algorithm for
testing convex polyhedra against axially aligned boxes.  That algorithm
works by attempting to find a plane separating the two figures.  Greene
mentions  that the  intuitive approach  is inefficient  because of  the
number of possible intersection  calculations.  (The intuitive approach
contains an intersection test of each polygon edge with each cube face,
followed by intersecting each cube diagonal with the polygon body). Our
approach  is  something  of  a  hybrid.   It  contains  only  a  single
intersection  calculation  which is  rarely  performed  because of  the
trivial tests that precede it.  The rest of the calculations are of the
same sort of fast inequality tests that Greene uses.


DESCRIPTION

Voorhies's original approach  is elegant and sound, and  we've kept the
general approach  which proceeds from  cheap trivial accept  and reject
tests through more  expensive edge and face  intersection tests.  We've
also broken these individual tests  out into separate routines in order
to allow  higher level routines to  be built on  top of them -  such as
general polyhedra  and polygon  mesh tests -  without having  to suffer
redundant tests on shared vertices or edges.

The composite fast_polygon_intersects_cube routine  presented  here  is
meant  to  replace  Voorhies'  triangle-cube  intersection routine.  It
begins by calling the trivial_vertex_tests routine which is  almost  an
exact  copy  of  the  trivial  point-plane  tests from the beginning of
Voorhies'   implementation    and    only    calls    the    definitive
polygon_intersects_cube routine when that fails.

The main algorithmic  difference in our point-plane tests is  that in a
number of places we avoid  testing against planes which cannot possibly
give useful information.   For example, when a point is  found to be to
the left of the left face plane of the cube, we don't need to also test
whether it might be to the right of the right face plane.

The trivial_vertex_tests routine can be  used to quickly test an entire
set of vertices  for trivial reject or accept.  This  can be useful for
testing polyhedra  or entire  polygon meshes.  Useful  applications for
polyhedra  testing  include more  than  just  the faster  rendering  of
polyhedra; another important use is in testing for trivial rejection of
polyhedral bounding volumes (described more fully in the last section).

Note that  when trivial_vertex_tests is  used to simultaneously  test a
large set of  vertices against a set of bounding  planes it's sometimes
possible for the function to stop testing vertices early when it can be
determined that there are no planes left that all of the vertices might
be outside of. For example, if at least one vertex has been found to be
to the right  of the left face plane,  and at least one is  found to be
below the top  face plane and likewise for the  other four face planes,
then  there is  no  point  in classifying  all  the remaining  vertices
because it's  impossible that as a  set they could all  lie outside any
one of those planes.  We do  this by keeping a running "cumulative AND"
mask  representing the  set  of cube  face planes  which  still have  a
possibility  of trivially  rejecting  the entire  figure while  looping
through all the vertices.  We do the same when testing against the sets
of bevel  and corner planes (i.e.   the 12 planes adjacent  to the cube
edges and the 8 planes adjacent to the corners).

[NB: A  graphic here showing these  three sets of planes  would be very
useful  here  especially because  one  was  not included  in  Voorhies'
paper.]

As  stated previously,  when trivial_vertex_tests  fails to  classify a
given polygon,  fast_polygon_intersects_cube then calls  the definitive
polygon_intersects_cube routine.   Just like  in Voorhies'  version the
general algorithm is:

    1. If any edge intersects the cube, return true.
    2. If the polygon interior intersects the cube, return true.
    3. Return false.

Our implementation,  however, is  very different.   In the  first step,
testing whether  a line  segment intersects the  cube is  equivalent to
testing  whether the  origin  is  contained in  the  solid obtained  by
dragging a unit cube from (being  centered at)  one segment endpoint to
the other.  This  solid is a warped rhombic dodecahedron.   The code to
implement this consists of 12  sidedness tests, which is more efficient
and  less error-prone  than the  original six  line-plane intersections
plus six point-within-polygon tests.

[NB: a graphic might be useful here but it may be difficult to generate
one that's any clearer than the above textual description.]

In the second step, since we know no  vertex  or  edge  intersects  the
cube,  this  amounts  to testing whether any of the four cube diagonals
intersects  the  interior  of  the  polygon.   (This  is  the  same  as
Voorhies'  test).   The  difference  in  our  implementation is that we
recognize that we really only need to test against  the  diagonal  that
comes  closest  to  being perpendicular to the plane of the polygon; if
the polygon intersects any of the cube  diagonals,  it  will  intersect
that  one.   Finding  that  diagonal  is  trivial,  so this part of our
implementation is roughly four times as fast as the original.

The last part of the second step is a test to see whether  the  polygon
contains  the  point  which  is the intersection of the polygon's plane
with the chosen diagonal.  We provide the polygon_contains_point_3d for
that  purpose, and are publishing it because it may be useful for other
purposes.


VECTOR MATH MACRO LIBRARY

Another way we squeeze performance out of our implementation is through
the  use  of the  linear  algebra  library  "vec.h".  This  library  is
implemented purely  as a set of  C macros, thereby avoiding  a function
call  for every  operation.  Another  big  advantage of  using a  macro
implementation is that  it is completely type  independent.  The source
and destination types of vectors and matrices may be any types that can
be indexed into and are assignment compatible. All integer and floating
point types  may be  freely mixed;  in addition,  any C++  classes that
support arithmetic operations may be used.

The  vec.h  header  file  is automatically  generated  by  the  program
vec_h.c.  This  program takes a  single integer argument and  outputs a
vec.h file containing macros that handle vectors and matrices up to the
dimension specified.   The library includes  N-dimensional determinants
and cross products in addition to the simpler operations.


POLYHEDRON-CUBE INTERSECTION TESTING

When used to test polyhedra, remember that the routines included in our
module only test for intersections with points, edges and surfaces, not
volumes.  If  no such  intersection is reported,  the caller  should be
aware that the  volume of the polyhedra could still  contain the entire
unit box.   That condition would  then need to  be checked for  with an
additional point-within-polyhedron test.  The origin would be a natural
point to check  in such a test.  Below is  C-like pseudo-code that puts
all  the   pieces  together   for  a  fast,   complete  polyhedron-cube
intersection test.

    switch(trivial_vertex_tests(verts))
    {
        case  1: return true  /* trivial accept */
        case  0: return false /* trivial reject */
        case -1: for each edge
                     if(segment_intersects_cube(edge))
                         return true
                 for each face
		     if(fast_polygon_intersects_cube(..., true, true))
                         return true
                 return polyhedra_contains_point(polyhedra, origin)
    }

It's  useful to  notice that  when a  box is  used as  a modeling-space
bounding polyhedron, testing its intersection against a view volume can
often be performed  in either direction.  In other words,  not only can
the box  be transformed  by the viewing  transformation that  takes the
view volume to  the unit cube and  then tested there, but  the the view
volume can  also be  transformed by the  transformation that  takes the
bounding box to be the unit cube  and the test performed there.  In the
latter case it is the world-space  truncated pyramid of the view volume
that becomes the polyhedron being tested.

[Note that our implementation contains "const" arguments which may need
to be removed for those old compilers that do not understand const.]