Graphics Reference
In-Depth Information
bodies are always sampled through their support mappings, all that is required to
allow the GJK algorithm to work with general convex objects is to supply appropriate
support mappings (see Section 3.8).
The GJK algorithm terminates with the separation distance in a finite number
of steps for polyhedra. However, it only asymptotically converges to the separation
distance for arbitrary convex bodies. Therefore, a suitable tolerance should be added
to the termination condition to allow the algorithm to terminate correctly when
operating on nonpolyhedral objects.
Upon termination with nonintersection, in addition to returning the separation
distance it is possible to have GJK compute the closest points between the input
objects, computed from the points of objects
A
and
B
that formed the points in the
last copy of simplex set
Q
. The steps of this computation are outlined in Section
9.5.3.
For an excellent in-depth description of the GJK algorithm, see [Bergen03]. A
good presentation is also given in [Coutinho01]. A conversion to C of the origi-
nal FORTRAN implementation of the GJK algorithm is available on the Internet
[Ruspini].
9.5.2
Finding the Point of Minimum Norm in a Simplex
It remains to describe how to determine the point
P
of minimum norm in
CH
(
Q
)
for a simplex set
Q
4. In the original presentation
of GJK, this is done through a single procedure called the
distance subalgorithm
(or
Johnson's algorithm
). The distance subalgorithm reduces the problem to considering
all subsets of
Q
separately. For example, for
k
= {
Q
1
,
Q
2
,
...
,
Q
k
}
,1
≤
k
≤
=
4 there are 15 subsets corresponding
to 4 vertices
(
Q
1
,
Q
2
,
Q
3
,
Q
4
)
, 6 edges
(
Q
1
Q
2
,
Q
1
Q
3
,
Q
1
Q
4
,
Q
2
Q
3
,
Q
2
Q
4
,
Q
3
Q
4
)
, 4 faces
(
.
The subsets are searched one by one, in order of increasing size. The search stops
when the origin is contained in the Voronoi region of the feature (vertex, edge, or
face) specified by the examined subset (or, for the subset corresponding to the interior
of the simplex when the origin is inside the simplex). Once a feature has been located,
the point of minimum norm on this feature is given by the orthogonal projection of
the origin onto the feature.
Consider again the case of
Q
Q
1
Q
2
Q
3
,
Q
1
Q
2
Q
4
,
Q
1
Q
3
Q
4
,
Q
2
Q
3
Q
4
)
, and the interior of the simplex
(
Q
1
Q
2
Q
3
Q
4
)
= {
Q
1
,
Q
2
,
Q
3
,
Q
4
}
. An arbitrary point
P
(specifically
the origin) lies in the Voronoi region for, say, vertex
Q
1
if and only if the following
inequalities are satisfied:
(
P
−
Q
1
)
·
(
Q
2
−
Q
1
)
≤
0
(
P
−
Q
1
)
·
(
Q
3
−
Q
1
)
≤
0
(
P
−
Q
1
)
·
(
Q
4
−
Q
1
)
≤
0.
