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.