Game Development Reference
In-Depth Information
5.4 Overview of GJK
GJK is an iterative method for approximating the distance between two convex
objects. The original paper on this topic discussed the use of GJK for polytopes
only [Gilbert et al. 88], however, with some minor adaptations of the termination
condition, GJK is applicable to convex objects in general [Gilbert and Foo 90].
In this section, we will briefly discuss GJK in order to get us going for the next
section. For an in-depth discussion of GJK, the reader is referred to [van den
Bergen 03].
GJK essentially approximates the point of the CSO that is closest to the origin.
GJK may be used to solve other queries as well, but at its core it remains a method
for finding the closest point. GJK approximates the closest point of A
B in
the following way. In each iteration, a simplex is constructed that is contained
in A
B and that lies closer to the origin than the simplex constructed in the
previous iteration. A simplex is the convex hull of an affinely independent set of
vertices. The simplices can have one to four vertices, so a simplex can be a single
point, a line segment, a triangle, or a tetrahedron. We define W k as the set of
vertices of the simplex constructed in the k th iteration and v k as the point closest
to the origin of the simplex. Initially, we take W 0 =
,and v 0 , an arbitrary point
B . Since the simplex 1 W k is contained in A
in A
B ,
and thus, the length of v k is an upper bound for the distance between A and B .
In each iteration, a new support point w k = s A−B (
B , we see that v k
A
v k ) is added as a vertex
to the current simplex W k .Let Y k = W k ∪{
be the new simplex. The closest
point v k +1 of the new simplex is taken to be the current best approximation of the
point closest to the origin of A
w k }
B . As we keep adding vertices, older vertices
that no longer contribute to the closest point are removed. Thus, each new simplex
W k +1 is taken to be the smallest set X
Y k , such that v k +1 is contained in the
convex hull of X . It can be seen that exactly one such X exists and that it must
be affinely independent.
GJK terminates as soon as v k is close enough to the closest point of A
B .
In order to determine the error in the current approximation, we need also a lower
bound for the distance. As a lower bound we can use the signed distance of the
origin to the supporting plane at w k ,whichis
v k
·
w k
.
v k
Note that the upper and lower bounds depend on
. Computing the length of a
vector involves evaluating a square root, which may hurt performance. A cheaper
v k
1 Formally, we should refer to the simplex as conv( W k ) , the convex hull of W k , but we often
identify a simplex by its vertices.