Physically Based Animation - Computer Animation: Algorithms and Techniques - page 223

sphere or bounding slabs (pairs of parallel planes at various orientations that bound the object) can be
used. A hierarchy of bounding shapes can be used on object groups, individual objects, and individual
faces. If these bounding tests fail to conclusively establish that a nonoverlap situation exists, then more
elaborate tests must be conducted.
Most collisions can be detected by testing each of the vertices of one object to see if any are inside
another polyhedron and then testing each of the vertices of the other object to see if any are inside the
first. To test whether a point is inside a convex polyhedron, each of the planar equations for the faces of
the object is evaluated using the point's coordinates. If the planes are oriented so that a point to the
outside of the object evaluates to a positive value and a point to the inside of the object evaluates
to a negative value, then the point under consideration has to evaluate to a negative value in all of
the planar equations in order to be declared inside the polyhedron.
Testing a point to determine if it is inside a concave polyhedron is more difficult. One way to do it is
to construct a semi-infinite ray emanating from the point under consideration in any particular direc-
tion. For example, y ¼ P y , z ¼ P z , x > P x defines a line parallel to the x -axis going in the positive
direction from the point P . This semi-infinite ray is used to test for intersection with all of the faces
of the object, and the intersections are counted; an odd number of intersections means that the point
is inside the object, and an even number means that the point is outside. To intersect a ray with a face,
the ray is intersected with the planar equation of the face and then the point of intersection is tested to
see if it is inside the polygonal face.
Care must be taken in correctly counting intersections if this semi-infinite ray intersects the object
exactly at an edge or vertex or if the ray is colinear with an edge of the object. (These cases are similar to
the situations that occur when scan converting concave polygons.) While this does not occur very often,
it should be dealt with robustly. Because the number of intersections can be difficult to resolve in such
situations, it can be computationally more efficient to simply choose a semi-infinite ray in a different
direction and start over with the test.
One can miss some intersection situations if performing only these tests. The edges of each object
must be tested for intersection with the faces of the other object and vice versa to capture other overlap
situations. The edge-face intersection test consists of two steps. In the first step, the edge is tested for
intersection with the plane of the face (i.e., the edge vertices are on opposite sides of the plane of the
face) and the point of intersection is computed if it exists. In the second step, the point of intersection is
tested for two-dimensional containment inside the face. The edge-face intersection tests capture almost
all of the penetration situations, 2 but because it is the more expensive of the two tests, it is usually better
to perform the vertex tests first (see Figure 7.19 ) .
In any of these tests, vertices of one object that lie exactly in the plane of a face from the other object
are a special case that must be handled carefully. Usually it is sufficient to logically and consistently
push such a vertex to one side of the plane.
Often, a normal that defines the plane of intersection is used in the collision response calculations.
For collisions that are detected by the penetration tests, one of two collision situations can usually be
established by looking at the relative motion of the objects. Either a vertex has just penetrated a face, or
an edge from one object has just intersected an edge from the other object. In either case, the plane of
2 The edge-face intersection test will miss the case when one object is entirely inside of the other; this case is handled by
testing a single vertex from each object to see if it is inside the other object.