Graphics Reference
In-Depth Information
point to the other object as found on the previous frame. An alternative is to keep
the simplex from the previous frame. In both cases, an array or a hash table can
effectively hold this information for each pair of objects from one frame to the next.
When there is little frame-to-frame coherency, a better option might be to obtain
the vector between the object centroids, compute supporting vertices on both objects
with respect to the vector, and use these vertices as the starting points. This method
can also be useful as a first-time initialization.
9.5.6
Rotated Objects Optimization
To be able to collide two objects, they must be in the same reference frame, such
as both objects expressed in the coordinate system of the world space or one object
given in the coordinate system of the other (the latter being a cheaper option because
only one object must be transformed). However, for GJK rather than up-front trans-
forming all vertices of one object into the space of the other a better approach is
to simply transform the direction passed into the support mapping into the other
reference frame. In the former case, all
n
vertices of one object (preferably the one
with fewer vertices) must be transformed once. In the latter case, only a single vector
must be transformed but a vector must be transformed
k
times, once per iteration of
the algorithm. Generally
k
is much smaller than
n
, and thus the latter approach is
therefore much more effective. In addition, the first approach requires extra storage
to hold the transformed vertices, whereas the second alternative needs no additional
vertex storage. In both cases, after the closest points have been found two more
transformations may be needed to express these points in world space.
One scenario in which the latter approach may not be preferable is when a binary
search over time is performed to find the time
t
at which an object moving under
a linear translation intersects another object. The first approach still only requires
n
transformations (in that a translation does not change the object's rotation), whereas
the latter now requires
km
transformations, where
m
is the number of steps of the
binary search.
9.5.7
GJK for Moving Objects
Although the GJK algorithm is usually presented and thought of as operating on two
convex polyhedra, it is more general than this. Given two point sets, it computes
the minimum distance vector between the convex hulls of the point sets (an easy
way of seeing this is to note that the support mapping function never returns a point
interior to the hull). This is an important distinction, as it allows GJK to be used to
determine collisions between convex objects under linear translational motion in a
straightforward manner.
One approach to dealing with moving polyhedra is presented in [Xavier97]. Con-
sider two polyhedra
P
and
Q
, with movements given by the vectors
t
1
and
t
2
,
