Graphics Reference
In-Depth Information
A
A
O
O
C
B
B
A
D
D
G
O
E
O
F
B
B
Figure 9.11
GJK finding the point on a polygon closest to the origin.
added to
Q
, giving
Q
. The closest point on
CH
(
Q
) to the origin is now
E
.
Because only
B
and
D
are needed to express
E
as a convex combination of vertices
in
Q
,
Q
is updated to
Q
={
A
,
B
,
D
}
E
is
F
, which
is added to
Q
. The point on
CH
(
Q
) closest to the origin is now
G
.
D
and
F
is the
smallest set of vertices in
Q
needed to express
G
as a convex combination, and thus
Q
is updated to
Q
={
B
,
D
}
. The supporting vertex in direction
−
={
D
,
F
}
. At this point, because no vertex is closer to the origin in
direction
−
G
than
G
itself
G
must be the closest point to the origin, and the algorithm
terminates.
Note that the GJK algorithm trivially deals with spherically extended polyhedra
by comparing the computed distance between the inner polyhedron structures with
the sum of the radii of their spherical extension. Note also that if the GJK algorithm
is applied to the vertex sets of nonconvex polyhedra it will compute the smallest
distance between the convex hulls of these nonconvex polyhedra.
Although presented here as a method operating on polyhedra only, the GJK algo-
rithm can in fact be applied to arbitrary convex bodies [Gilbert90]. Because the input
