Graphics Reference
In-Depth Information
of
C
B
. Specifically, a support mapping is a function
s
A
(
d
) that maps a given
direction
d
into a supporting point for the convex object
A
in that direction. Because
the support mapping function is the maximum over a linear function, the support
mapping for
C
,
s
A
B
(
d
), can be expressed in terms of the support mappings for
A
and
B
as
s
A
B
(
d
)
=
A
d
). Thus, points from the Minkowski difference can be
computed, on demand, from supporting points of the individual polyhedra
A
and
B
.
To search the Minkowski difference
C
for the point closest to the origin, the GJK
algorithm utilizes a result known as
Carathéodory's theorem
[Rockafellar96]. The the-
orem says that for a convex body
H
of
=
s
A
(
d
)
−
s
B
(
−
d
each point of
H
can be expressed as the
R
convex combination of no more than
d
1 points from
H
. This allows the GJK algo-
rithm to search the volume of the Minkowski difference
C
by maintaining a set
Q
of
up to
d
+
1 points from
C
at each iteration. The convex hull of
Q
forms a simplex
inside
C
. If the origin is contained in the current simplex,
A
and
B
are intersecting
and the algorithm stops. Otherwise, the set
Q
is updated to form a new simplex,
guaranteed to contain points closer to the origin than the current simplex. Eventually
this process must terminate with a
Q
containing the closest point to the origin. In
the nonintersecting case, the smallest distance between
A
and
B
is realized by the
point of minimum norm in
CH
(
Q
) (the convex hull of
Q
). The following step-by-step
description of the GJK algorithm specifies in more detail how the set
Q
is updated.
+
+
1. Initialize the simplex set
Q
to one or more points (up to
d
1 points, where
d
is
the dimension) from the Minkowski difference of
A
and
B
.
2. Compute the point
P
of minimum norm in
CH
(
Q
).
3. If
P
is the origin itself, the origin is clearly contained in the Minkowski difference
of
A
and
B
. Stop and return
A
and
B
as intersecting.
4. Reduce
Q
to the smallest subset
Q
CH
(
Q
). That is, remove
any points from
Q
not determining the subsimplex of
Q
in which
P
lies.
of
Q
such that
P
∈
5. Let
V
=
s
A
B
(
−
P
)
=
s
A
(
−
P
)
−
s
B
(
P
) be a supporting point in direction
−
P
.
6. If
V
is no more extremal in direction
P
than
P
itself, stop and return
A
and
B
as
not intersecting. The length of the vector from the origin to
P
is the separation
distance of
A
and
B
.
−
7. Add
V
to
Q
and go to 2.
Figure 9.11 illustrates how GJK iteratively finds the point on a polygon closest
to the origin
O
for a 2D problem. The algorithm arbitrarily starts with the vertex
A
as the initial simplex set
Q
,
Q
. For a single-vertex simplex, the vertex itself is
the closest point to the origin. Searching for the supporting vertex in direction
={
A
}
−
A
results in
B
.
B
is added to the simplex set, giving
Q
. The point on
CH
(
Q
)
closest to the origin is
C
. Because both
A
and
B
are needed to express
C
as a convex
combination, both are kept in
Q
.
D
is the supporting vertex in direction
={
A
,
B
}
−
C
and it is
