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

Search Nedrilad ::

Custom Search