Graphics Reference
In-Depth Information
3. Intersect each edge of
Q
against polyhedron
P
(for example, using the method
described in Section 5.3.8). If an edge intersects
P
, stop and report the polyhedra
as intersecting.
4. To deal with the degenerate case of identical objects (such as cubes) passing
through each other with their faces aligned, test the centroid of each face of
Q
against all faces of
P
. If a centroid is found contained in
P
, stop and return
intersection as a result.
5. Return nonintersection.
Both algorithm formulations are
O
(
n
2
) in the number of vertices or edges tested.
In practice, even though the tests remain
O
(
n
2
) worst case they can be improved
by providing a bounding box for each polyhedron and restricting the testing to the
vertices, edges, and faces intersecting the overlap volume of the two boxes. If the
polyhedra are not intersecting, the bounding boxes typically overlap only a little (if at
all) and most vertices, edges, and faces are culled from the expensive test. When the
polyhedra are intersecting, the chance of detecting an intersection early — for exam-
ple, by determining a vertex lying inside the other polyhedron — increases greatly. As
a result, near linear behavior can be expected in most cases. However, linear behavior
is still not as efficient as possible. By better exploiting the convexity of the objects,
faster collision algorithms can be obtained. Such algorithms are explored ahead.
9.2
Closest-features Algorithms
In real-time simulations objects tend to move or rotate by small amounts from one
frame to the next. For convex objects, this frame-to-frame coherence suggests that
in general the closest points between two nonintersecting objects are located in the
near vicinity of the closest points between the objects of the previous frame. However,
although an accurate observation for strictly convex sets (informally, that curve every-
where) this it is not always true for polyhedra. For a polyhedron, even a minute change
in orientation can cause the closest point to move from one side to the opposite side
of one of its faces, which (depending on the size of the face) may be arbitrarily far
away. Thus, for polyhedra, rather than tracking the closest points and using the clos-
est points of the previous frame as a starting point a better approach is to track the
closest features
(vertices, edges, or faces) from frame to frame. A pair of features, one
from each of two disjoint polyhedra, are said to be the closest features if they contain
a pair of closest points for the polyhedra.
Perhaps the earliest and most well known collision detection algorithm based
on the tracking of closest features is the
Lin-Canny algorithm
[Lin91]. A later, sim-
ilar algorithm, addressing some serious flaws in the Lin-Canny algorithm, is the
Voronoi-Clip
,or
V-Clip algorithm
[Mirtich98]. The V-Clip algorithm is summarized in
the next section.
