Graphics Reference
In-Depth Information
The separating-axis test applies even when an object is not symmetric — as in the
case of an arbitrary convex hull, for instance — but the test would have to be modified
to project the hull vertices onto the axis in order to find the projection intervals.
Separating axes are easy to find by inspection. However, for an implementation
it is important to be able to automatically limit an infinite number of potentially sep-
arating axes to just a few axes tested. For convex polyhedra, it is possible to drastically
reduce the number of axes to test. Ignoring ordering, two polyhedral objects may
come into contact in six different ways with respect to their features. They can meet
face-face, face-edge, face-vertex, edge-edge, edge-vertex, or vertex-vertex. Because
vertices can be considered part of the edges, the combinations involving vertices are
subsumed by the same situations involving edges. This reduces the contact situations
to three essentially different combinations: face-face, face-edge, and edge-edge.
For the face-face and face-edge cases, it is sufficient to test the face normals of both
objects as potential separating axes. For the edge-edge case, the potential separating
axis to be tested corresponds to the cross product of the two edges. The reason the
cross product is used for the separating-axis test in the edge-edge case can be justified
by considering what happens when two objects come into contact edge to edge. The
points on the edges closest to each other form the feet of a perpendicular between
the two edges. Because this perpendicular is the cross product of the edges, it is the
correct candidate to test as a separating axis. In summary, to test the separability of
two polyhedral objects the following axes must be tested.
Axes parallel to face normals of object
A
●
Axes parallel to face normals of object
B
●
Axes parallel to the vectors resulting from the cross products of all edges in
A
with all edges in
B
●
As soon as a separating axis is found, a test can immediately exit with“no intersection.”
If all axes are tested, with no separating axis found, the objects must be intersecting.
For two general polytopes with the same number of faces (
F
) and edges (
E
) there
are 2
F
E
2
potential separating axes. Because the number of separating axes is
quadratic in the number of edges, a separating-axis test may be infeasible for objects
of moderate to high complexity. However, it is possible to speed up a separating-axis
test by caching the last successful separating axis and testing it first on a subsequent
query, in the hope of getting an early nonintersection exit thanks to spatial and
temporal coherency of the objects between queries.
When two polytopes are colliding, the separating-axis test can also assist in com-
puting contact information. Instead of exiting early when an overlap is detected on
an axis, all axes are tested for overlap. After all axes have been tested, the axis with
the least (normalized) overlap can be used as the contact normal, and the overlap can
be used to estimate the penetration depth. With some extra work, contact points can
also be computed with the help of the separating axis. For those interested in reading
+
