Game Development Reference
In-Depth Information
Support point in
direction V
v
Support point in
direction - V
Figure 17.1 Trace of a polyhedron on an axis by calculation of support points
try to find a plane of space that separates A and B ; this plane, marked as P , is called the
separator plane . Every perpendicular D orthogonal to the separator plane is called the
separator axis . In fact, orthogonal projection of polytopes A and B on D gives disjoint
segments. Whereas, a support point of a polyhedron A with respect to a direction or
vector
v is the point (not necessarily unique) P such as
v
·
P
=
max
{
v
·
X ; X
A
}
.To
find the trace of a polyhedron on an axis of direction vector
v , it is enough to project
the support points of the polyhedron with respect to
v on this axis (see fig-
ure 17.1). By comparing the traces of two polyhedrons on the axis, we can determine
whether the axis is separator or not. Chung and Wang (1996) suggest a method of
iterative construction for such axis.
If D i is not a separating direction, we call P i and Q i the support points of A as per
D i and B as per
v and
D i . We then have:
D i + 1
= D i
· D i )
2(
r i
r i
. We take D 0 as any axis, the series D i converges on
a separator axis, if it exists. It was established that during a movement, it is often
quicker to test the separator axis of the previous moment before trying to construct a
new one (Baraff, 1990). The main difficulty of this algorithm is in finding the support
points. The graph traversal methods make it possible to accelerate this search: In
case of a vertex, we check whether one of its neighbours has a higher scalar product
and reiterate till we find a maximal scalar product (method known as Hill climbing ).
Convexity guarantees that this maximum is unique. However, this does not mean that
a single point provides this maximum: Several contiguous vertices can provide the same
result, in certain border-line cases (for example, two surfaces of a cube opposite each
other). Unfortunately, this property tends to significantly degrade the convergence of
algorithms. We would like tomention that some radically different approaches consider
that two objects are disjoint if we find a strictly positive minimal limit at the distance
separating them. This limit can be determined by calculating the distance between the
simple volumes (spheres) covering the objects or by using the first steps of an algorithm
that calculates the distance between polytopes by iteration (Bergen, 1999).
where
r i
=
( P i
Q i ) /
P i
Q i