pcube.h

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

#ifndef _PCUBE_
#define _PCUBE_

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
 *                                                                           *
 *                       POLYGON-CUBE INTERSECTION                           *
 *                       by Don Hatch & Daniel Green                         *
 *                       January 1994                                        *
 *                                                                           *
 *    CONTENTS:                                                              *
 *        polygon_intersects_cube()                                          *
 *        fast_polygon_intersects_cube()                                     *
 *        trivial_vertex_tests()                                             *
 *        segment_intersects_cube()                                          *
 *        polygon_contains_point_3d()                                        *
 *                                                                           *
 *                                                                           *
 *  This module contains  routines that test points,  segments and polygons  *
 *  for intersections  with the  unit cube defined  as the  axially aligned  *
 *  cube of edge length 1 centered  at the origin.  Polygons may be convex,  *
 *  concave or  self-intersecting.  Also contained is a routine  that tests  *
 *  whether a point  is within a polygon.  All routines  are intended to be  *
 *  fast and robust. Note that the cube and polygons are defined to include  *
 *  their boundaries.                                                        *
 *                                                                           *
 *  The  fast_polygon_intersects_cube  routine  is  meant  to  replace  the  *
 *  triangle-cube  intersection routine  in  Graphics Gems  III by  Douglas  *
 *  Voorhies.   While  that  original  algorithm  is  still sound,   it  is  *
 *  specialized  for triangles  and  the  implementation contained  several  *
 *  bugs and inefficiencies.  The trivial_vertex_tests routine defined here  *
 *  is  almost an  exact copy  of the  trivial point-plane  tests from  the  *
 *  beginning of Voorhies' algorithm but broken out into a separate routine  *
 *  which is called by  fast_polygon_intersects_cube.  The segment-cube and  *
 *  polygon-cube intersection algorithms have been completely rewritten.     *
 *                                                                           *
 *  Notice that trivial_vertex_tests 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.   When  used  to  test  *
 *  polyhedra, remember  that these  routines only  test 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 which  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.                                           *
 *                                                                           *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
								    

#ifndef real
#define real double
#endif

/*
 *                   POLYGON INTERSECTS CUBE
 *
 * Tells how the given polygon intersects the cube of edge length 1 centered
 * at the origin.
 * If any vertex or edge of the polygon intersects the cube,
 * a value of 1 will be returned.
 * Otherwise the value returned will be the multiplicity of containment
 * of the cross-section of the cube in the polygon; this may
 * be interpreted as a boolean value in any of the standard
 * ways; e.g. the even-odd rule (it's inside the polygon iff the
 * result is odd) or the winding rule (it's inside the polygon iff
 * the result is nonzero).
 *
 * The "polynormal" argument is a vector perpendicular to the polygon.  It
 * need not be of unit length.  It is suggested that Newell's method be used
 * to calculate polygon normals (See Graphics Gems III).  Zero-lengthed normals
 * are quite acceptable for degenerate polygons but are not acceptable
 * otherwise.  In particular, beware of zero-length normals which Newell's
 * method can return for certain self-intersecting polygons (for example
 * a bow-tie quadrilateral).
 *
 * The already_know_verts_are_outside_cube flag is unused by this routine
 * but may be useful for alternate implementations.
 *
 * The already_know_edges_are_outside_cube flag is useful when testing polygon
 * meshes with shared edges in order to not test the same edge more than once.
 *
 * Note: usually users of this module would not want to call this routine
 * directly unless they have previously tested the vertices with the trivial
 * vertex test below.  Normally one would call the fast_polygon_intersects_cube
 * utility instead which combines both of these tests.
 */
extern int
polygon_intersects_cube(int nverts, const real verts[/* nverts */][3],
			const real polynormal[3],
			int already_know_verts_are_outside_cube,
			int already_know_edges_are_outside_cube);


/*
 *                   FAST POLYGON INTERSECTS CUBE
 *
 * This is a version of the same polygon-cube intersection that first calls
 * trivial_vertex_tests() to hopefully skip the more expensive definitive test.
 * It simply calls polygon_intersects_cube() when that fails.
 * Note that unlike polygon_intersects_cube(), this routine does use the
 * already_know_verts_are_outside_cube argument.
 */
extern int
fast_polygon_intersects_cube(int nverts, const real verts[/* nverts */][3],
			const real polynormal[3],
			int already_know_verts_are_outside_cube,
			int already_know_edges_are_outside_cube);


/*
 *                   TRIVIAL VERTEX TESTS
 *
 * Returns 1 if any of the vertices are inside the cube of edge length 1
 * centered at the origin (trivial accept), 0 if all vertices are outside
 * of any testing plane (trivial reject), -1 otherwise (couldn't help).
 */
extern int
trivial_vertex_tests(int nverts, const real verts[/* nverts */][3],
			int already_know_verts_are_outside_cube);


/*
 *                   SEGMENT INTERSECTS CUBE
 *
 * Returns 1 if the given line segment intersects the cube of edge length 1
 * centered at the origin, 0 otherwise.
 */
extern int
segment_intersects_cube(const real v0[3], const real v1[3]);


/*
 *                   POLYGON CONTAINS POINT 3D
 *
 * Tells whether a given polygon with nonzero area contains a point which is
 * assumed to lie in the plane of the polygon.
 * Actually returns the multiplicity of containment.  This will always be 1
 * or 0 for non-self-intersecting planar polygons with the normal in the
 * standard direction (towards the eye when looking at the polygon so that
 * it's CCW).
 */
extern int
polygon_contains_point_3d(int nverts, const real verts[/* nverts */][3],
			const real polynormal[3],
			real point[3]);

#endif