Graphics Reference
In-Depth Information
out that the polyhedron distance problem can be stated as a
quadratic programming
problem
. Similar to LP problems, quadratic programming (QP) problems have linear
constraints. However, the objective function is no longer linear but quadratic. One
possible QP formulation of the polyhedron distance problem is to let the two disjoint
polyhedra
A
and
B
each be defined as the convex hull of a finite set of points in
d
:
R
A
=
CH
(
S
A
),
S
A
={
A
1
,
A
2
,
...
,
A
m
}
B
=
CH
(
S
B
),
S
B
={
B
1
,
B
2
,
...
,
B
n
}
The goal is now to find points
P
in
A
and
Q
in
B
such that the distance between
P
and
Q
, or equivalently that the length of the (column) vector
v
=
P
−
Q
, is minimized.
Let
G
be the
d
n
matrix containing (as columns) the points of
S
B
. The polyhedron distance problem
is now to solve the following QP problem in the variables
x
×
m
matrix containing (as columns) the points of
S
A
. Let
H
be the
d
×
(
x
1
,
x
2
,
...
,
x
m
)
T
and
=
(
y
1
,
y
2
,
...
,
y
n
)
T
.
y
=
Minimize
v
T
v
subject to:
Gx
−
Hy
=
v
x
1
+
x
2
+
...
+
x
m
=
1
y
1
+
y
2
+
...
+
y
n
=
1
x
1
,
x
2
,
...
,
x
m
≥
0
y
1
,
y
2
,
...
,
y
n
≥
0
Solving QP problems is, in general, more difficult than solving LP problems. Many
algorithms have been suggested for solving QP problems. For the size of a problem
typical of collision detection, two practical algorithms are given by Botkin [Botkin],
[Botkin95] and Gärtner [Gärtner00]. Both algorithms share similarities with Seidel's
algorithm for linear programming. Botkin's algorithm has an expected running time
of
O
(
dd
!
n
). No time complexity is given for Gärtner's algorithm.
9.5
The Gilbert-Johnson-Keerthi Algorithm
One of the most effective methods for determining intersection between two polyhe-
dra is an iterative algorithm due to Gilbert, Johnson, and Keerthi, commonly referred
to as the
GJK algorithm
[Gilbert88]. As originally described, GJK is a simplex-based
descent algorithm that given two sets of vertices as inputs finds the Euclidean dis-
tance (and closest points) between the convex hulls of these sets. In a generalized
form, the GJK algorithm can also be applied to arbitrary convex point sets, not just
