Graphics Reference
In-Depth Information
a few vertices in
P
k
−
1
, all of them neighbors of
V
k
, must be examined to find the
most extreme vertex in
P
k
−
1
. By stepping up the hierarchy in this manner until
P
0
is reached, the most extreme vertex of the original polyhedron is found in
O
(log
n
)
steps. It can be shown that the tests at each step can be performed in constant time
and consequently the extreme vertex is found in
O
(log
n
) time.
An accessible account of the DK hierarchy is given in [O'Rourke98]. Simultane-
ously traversing two hierarchical representations allows the intersection between two
convex polygons to be determined in
O
(log
n
) time and between convex polyhedra
in
O
(log
2
n
) time [Dobkin90].
Specifically for the problem of finding extreme vertices of a polyhedron, the BSP
tree-based acceleration structure presented in [Eberly04] is a worthy alternative to
the DK hierarchy, in that the former is easier to implement and uses less memory.
9.4
Linear and Quadratic Programming
Although it is natural to view the problem of detecting collision between two con-
vex polyhedra as a geometrical problem, it can also be treated as a mathematical
optimization problem. Considering each polyhedron as the intersection volume of a
number of halfspaces, the Boolean intersection test of the polyhedra is equivalent to
what is known as the
feasibility problem
of linear programming. The latter is the prob-
lem of determining if there is a solution to a set of linear inequalities. In terms of the
collision problem, this corresponds to determining if there exists a point interior to all
halfspaces of both polyhedra (each halfspace being a linear inequality). Beyond just
determining if the polyhedra intersect or not, determining the separation distance and
the closest points between them in the case they do not intersect also can be treated
as an optimization problem, specifically as a quadratic programming problem. Both
linear and quadratic programming problems are optimization problems with respect
to linear inequality constraints. In the linear programming problem, the goal is to
optimize a linear function with respect to these constraints. The quadratic program-
ming problem instead optimizes a quadratic function with respect to the constraints.
The following sections describe in more detail how collision detection problems can
be expressed as linear and quadratic programming problems. The following material
also outlines methods for solving these problems.
9.4.1
Linear Programming
Let a
linear function
be a function of the form
f
(
x
1
,
x
2
,
...
,
x
n
)
c
n
x
n
,
where the
c
i
terms are real number constants. Let a
linear constraint
be a linear
equation or a linear inequality, where a
linear equation
is of the form
f
(
x
1
,
x
2
,
...
,
x
n
)
=
c
1
x
1
+
c
2
x
2
+···+
=
c
≤
≥
and
linear inequalities
are of the form
f
(
x
1
,
x
2
,
...
,
x
n
)
c
.
Then, the
linear programming problem
is the problem of optimizing (maximizing or
c
or
f
(
x
1
,
x
2
,
...
,
x
n
)
