Game Development Reference
In-Depth Information
Certain applications do not make do with a Boolean response and require finding
the accurate minimum distance between a pair of polyhedrons. This value is also the
distance between the origin and the Minkowski difference of two polytopes, defined
as: A
.If A and B are convex, even this polyhedron is shown
as convex. The GJK method (Gilbert et al., 1988) aims at determining the distance
between A
B
={
x
y ;
x
A ,
y
B
}
B . This
simplex is a point, a segment, a triangle or a tetrahedron formed by the vertices of
A
B and the origin by iteration, without explicitly calculating A
B .
In practice, as the Minkowski difference is not constructed, every vertex of A
B
is not known explicitly, but is systematically defined as the difference between a vertex
of A and a vertex of B . The shortest distance between simplex S i and the origin is
calculated at step i. Let V i be the point of this simplex, closest to the origin. The
simplex is then reduced by selecting the surface, edge or vertex of the simplex on
which the V i is located. Or S i , the minimum simplex found. We then find the support
point w i of A
B (in fact, the difference of the current supporting points of A and B as
per the direction and its opposite respectively). Point w i is then added to the simplex,
and we reiterate the algorithm on the convex envelop of the union of simplex S i and
point w i . Point V i and simplex S i are found in a single step: It is enough to take the
smallest sub-set { w j } of vertices of S i such as:
λ j ×
V i =
w j
and λ j > 0,
j
where V i is the closest point between the origin and the convex envelop of this set
{ w j }. This set is determined by doing an exhaustive search, starting with the set of one,
then two and then three vertices of S i . It is sufficient to choose one vertex of A
Bas
a simplex at the beginning of the algorithm. The algorithm ends when no new vertex
close to the origin can be added to the simplex. The minimum distance is then the
distance between this simplex and the origin. Figure 17.2 illustrates some calculation
steps of the GJK algorithm. This algorithm has had several upgrades, mainly the ISA-
GJK, making it better for numerical calculations (Bergen, 1999). There are some other
approaches to calculate the distance between polytopes, but we will not describe them
here as these algorithms require pre-processing the objects before they can be applied:
The DK method (Dobkin & Kirkpatrick, 1990) consists of constructing a series of
increasingly rough approximations of the polytopes in advance.
Then the distance between the rough approximations is calculated and then ascer-
tained more and more accurately by refining the approximation of polytopes. The LC
method (Lin & Canny, 1991), which was later called Voronoi marching, is based on
a section of the space surrounding each polytope in Voronoi regions. i.e. two points
selected respectively on the two polytopes; these two points are on a support element
(vertex, edge or face) of the polytope. These two points are separated by a minimum
distance, if they are included respectively in the Voronoi region of the support of the
other point. This criterion makes it possible to find the solution points and determine
the distance between the polytopes, only by searching the minimum distance.
The advantage of being able to determine the distance between two polytopes is
being able to anticipate their approach and ensure that this proximity is not converted
sooner or later into interpenetration. A method avoiding distance calculation involves
“enlarging'' all the objects, i.e. creating a safety zone around them and using this zone