Graphics Reference
In-Depth Information
[Chung96] show that three iterations were sufficient to identify noncolliding objects
in over 95% of cases when utilizing temporal coherence for the starting vector.
9.7
Summary
Collision systems work almost exclusively with convex objects because they have
certain properties that make them highly suitable for intersection testing. One of
these properties is the existence of a separating plane (or, equivalently, a separating
axis) for two nonintersecting convex objects. Another property of convex objects is
that when the distance between two points from two different convex objects are at
a minimum they are at a global minimum. This allows closest pairs of points to be
located using simple hill-climbing techniques.
One algorithm that utilizes hill climbing is the V-Clip algorithm. It tracks a pair of
features, one from each input polytope, updating the features by walking across the
surface of the polytopes so as to decrease the distance until the closest pair of fea-
tures has been obtained. Closest-point queries on polytopes can also be accelerated
using hierarchical representations, one example of which is the Dobkin-Kirkpatrick
hierarchy.
Intersection queries on polytopes can also be answered using mathematical opti-
mization methods. If a Boolean result is sufficient, linear programming can be used
to determine the intersection status of two (or more) polytopes. However, linear
programming cannot determine the closest points between two polytopes. For this
problem, quadratic programming must be used instead.
Effectively a specialized quadratic programming method, the GJK algorithm is one
of the most efficient methods for determining intersection between two polytopes,
or in its generalized form between two arbitrary convex objects (as long as they can
be described by a support mapping function). As was shown, the GJK algorithm
also extends to handle objects moving under linear translational motion. Last, the
CW separating-vector algorithm was presented as an efficient approach to finding a
separating axis for two nonintersecting objects.
