Graphics Reference
In-Depth Information
polyhedra [Gilbert90]. Whereas the examples presented here are in terms of poly-
topes, the described algorithm is the generalized version that applies to nonpolygonal
convex sets in a straightforward way.
Although the original presentation of the GJK algorithm is quite technical, neither
the algorithm itself nor its implementation are very complicated in practice. However,
understanding of the algorithm does require familiarity with some concepts from
convex analysis and the theory of convex sets on which the algorithm relies.
An important point is that the GJK algorithm does not actually operate on the
two input objects per se but on the Minkowski difference between the objects. This
transformation of the problem reduces the problem from finding the distance between
two convex sets to that of finding the distance between the origin and a single convex
set. The GJK algorithm searches the Minkowski difference object iteratively a sub-
volume at a time, each such volume being a simplex. The Minkowski difference is not
explicitly computed but sampled through a support mapping function on demand.
These concepts (Minkowski difference, simplices, and support mapping functions)
were described in Chapter 3, and in the following it is assumed the reader is familiar
with them.
9.5.1
The Gilbert-Johnson-Keerthi Algorithm
As mentioned earlier, the GJK algorithm effectively determines intersection between
polyhedra by computing the Euclidean distance between them. The algorithm is
based on the fact that the separation distance between two polyhedra
A
and
B
is
equivalent to the distance between their Minkowski difference
C
,
C
B
, and the
origin (Figure 9.10). Thus, the problem is reduced to that of finding the point on
C
closest to the origin. At the outset, this does not seem like much of an improvement,
as the Minkowski difference is nontrivial to compute explicitly. However, a key point
of the GJK algorithm is that it does not explicitly compute the Minkowski differ-
ence
C
. It only samples the Minkowski difference point set using a
support mapping
=
A
A
(-
B
)
A
B
Figure 9.10
The distance between
A
and
B
is equivalent to the distance between their
Minkowski difference and the origin.
