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

Search Nedrilad ::

Custom Search