Graphics Reference
In-Depth Information
9.5.3
GJK, Closest Points, and Contact Manifolds
In addition to the separation distance, the GJK algorithm can provide a pair of closest
points between the input objects. Upon termination with nonintersection, the set
Q
contains up to three points
Q
i
, forming a simplex from the Minkowski difference
C
B
. Let
k
denote the number of points in
Q
and let
P
be the point of minimum
norm in
CH
(
Q
). Because
Q
contains the smallest number of vertices needed to express
P
as a convex combination,
P
can be expressed as
=
A
P
=
c
i
Q
i
,
c
i
=
1,
c
i
>
0,
1
≤
i
≤
k
1
≤
i
≤
k
where (
c
1
,
c
2
,
...
,
c
k
) are the barycentric coordinates of
P
with respect to points
Q
i
.
Given that each point
Q
i
is the difference of points
A
i
and
B
i
from input objects
A
and
B
, respectively,
P
can be rewritten as
P
=
c
i
(
A
i
−
B
i
)
=
G
−
H
,
where
G
=
c
i
A
i
,
H
=
c
i
B
i
.
1
≤
i
≤
k
1
≤
i
≤
k
1
≤
i
≤
k
Because
P
realizes the shortest distance between
A
and
B
, there must exist (not
necessarily unique) points on the boundaries of
A
and
B
such that their difference is
P
. One such pair of points is
G
and
H
. Thus, by maintaining not just points
Q
i
but
A
i
and
B
i
a pair of closest points between
A
and
B
is directly obtained per the previous.
Note that the calculations needed to determine
P
on the convex hull of
Q
amounts
to computing the barycentric coordinates of
P
with respect to points
Q
i
, and thus the
barycentric coordinates are effectively obtained for free.
In addition to the closest pair of points, it is possible to derive contact manifolds
from the simplices at the termination of the GJK algorithm for two colliding (or
near-colliding) polyhedra. See [Zhang95] and [Nagle02] for details.
9.5.4
Hill Climbing for Extreme Vertices
One of the most expensive steps of the GJK algorithm is finding an extreme vertex in a
given direction. Trivially, extreme vertices can be located in
O
(
n
) time by searching over
all
n
vertices. A better approach relies on having a data structure listing all adjacent
vertex neighbors for each vertex. Then an extreme vertex can be found through a
simple hill-climbing algorithm, greedily visiting more and more extreme vertices
until no vertex more extreme can be found. More specifically, from the current vertex
V
neighboring vertices
V
i
are examined until some vertex
V
j
is found being more
extreme in the search direction than
V
. At this point,
V
j
is made the current vertex and
the process repeats. Due to the convexity of the polyhedron, at the point where no
