Graphics Reference
In-Depth Information
the triangles is trivially zero, but the closest points are not likely to be well defined
because there may be infinitely many (for example, if the triangles are parallel and
overlapping).
5.2
Testing Primitives
The
testing
of primitives is less general than the computation of distance between
them. Generally, a test will indicate only that the primitives are intersecting, not
determine where or how they are intersecting. Therefore, these intersection tests are
often much faster than tests returning additional information.
5.2.1
Separating-axis Test
An extremely useful tool for implementing various intersection tests is the
separating
-
axis test
. It follows from the
separating hyperplane theorem
, a fundamental result of
convex analysis. This theorem states that given two convex sets
A
and
B
, either the
two sets are intersecting or there exists a separating hyperplane
P
such that
A
is on
one side of
P
and
B
is on the other.
The separating-axis test follows intuitively from the theorem, because two con-
vex objects cannot “curve” around each other. Thus, when they are not intersecting
there will be a gap between them into which a plane can be inserted to separate the
two objects. When either or both objects are concave, a plane would in general no
longer be sufficient to separate the nonintersecting objects. Instead, a curved sur-
face would be required to separate the objects. When the objects are intersecting, no
surface — curved or not — can be inserted between the objects to separate them.
Given a hyperplane
P
separating
A
and
B
,a
separating axis
is a line
L
perpendicular
to
P
. It is called a separating axis because the orthogonal projections of
A
and
B
onto
L
result in two nonoverlapping intervals (Figure 5.13). Because the two intervals
do not overlap, the conclusion is that the geometries must be disjoint. Because a
separating axis exists if and only if a separating hyperplane exists, either can be tested
for. However, in practice it turns out to be better to test for separation on an axis, in
that it results in a less expensive test.
For performing a separating-axis test, it is worth noting that many collision
primitives — such as segments, AABBs, OBBs,
k
-DOPs, and spheres — are sym-
metrical in the sense that they have a center point
C
, which always projects into the
middle of the projection interval of their projection onto an axis. Given a potentially
separating axis
L
, an efficient separation test of two symmetrical objects
A
and
B
is
therefore to compute the halfwidth, or radii, of their projection intervals and compare
the sum of them against the distance between their center projections. If the sum is
less than the distance between the center projections, the objects must be disjoint.
An example is given in Figure 5.14, in which
A
and
B
correspond to a circle and an
