Graphics Reference
In-Depth Information
Chapter 9. In many situations, however, fully accurate polytope collision detection
might be neither necessary nor desired. By relaxing the test to allow approximate
solutions, it is possible to obtain both simpler and faster methods.
One such approach maintains both the defining planes and vertices of each convex
hull. To test two hulls against each other, the vertices of each hull are tested against
the planes of the other to see if they lie fully outside any one plane. If they do, the
hulls are not intersecting. If neither set of vertices is outside any face of the other hull,
the hulls are conservatively considered overlapping. In terms of the separating-axis
test, this corresponds to testing separation on the face normals of both hulls, but not
the edge-edge combinations of both.
Another approach is simply to replace the vertex set with a set of spheres. The
spheres are chosen so that their union approximates the convex hull. Now the test
proceeds by testing spheres (instead of vertices) against the planes. The idea is that
compared to vertex tests fewer sphere tests must be performed. Although this test is
faster, it is also less accurate. To improve accuracy while keeping the set size down,
the set of spheres is often hand optimized.
As with
k
-DOPs, testing can be sped up by ordering the stored planes to make
successive planes as perpendicular to each other as possible. Similarly, to avoid degen-
erate behavior due to clustering the vertices (or spheres) can be randomly ordered.
Bounding the vertex set with a sphere and testing the sphere against the plane before
testing all vertices often allow for early outs.
Compared to other bounding volume tests, these tests are still relatively expensive
and are typically preceded by a cheaper bounding volume test (such as a sphere-
sphere test) to avoid hull-testing objects that are sufficiently far apart to not be
intersecting. The coherency methods presented in Chapter 9 are also useful for
minimizing the number of hull tests that have to be performed.
4.7
Other Bounding Volumes
In addition to the bounding volumes covered here, many other types of volumes
have been suggested as bounding volumes. These include cones [Held97], [Eberly02],
cylinders [Held97], [Eberly00], [Schömer00], spherical shells [Krishnan98], ellipsoids
[Rimon92], [Wang01], [Choi02], [Wang02], [Chien03], and zonotopes [Guibas03].
Cones, cylinders, and ellipsoids are self-explanatory. Spherical shells are the inter-
section of the volume between two concentric spheres and a cone with its apex at
the sphere center. Zonotopes are centrally symmetric polytopes of certain properties.
These shapes have not found widespread use as bounding volumes, in part due to
having expensive intersection tests. For this reason, they are not covered here further.
It should be noted that whereas ellipsoid-ellipsoid is an expensive intersection test,
tests of ellipsoids against triangles and other polygons can be transformed into testing
a sphere against a skewed triangle by applying a nonuniform scaling to the coordinate
space. Thus, ellipsoids are feasible bounding volumes for certain sets of tests.
