Basic Primitive Tests - Real-Time Collision Detection - page 159

further, the separating-axis test was suggested for the collision detection of oriented
bounding boxes by [Larcombe95].
5.2.1.1 Robustness of the Separating-axis Test
A potential problem with the separating-axis test is robustness in the case of a sep-
arating axis being formed by the cross product of an edge from each object. When
these two edges become parallel, the result is the zero vector and all projections onto
this axis, and sums of these projections, are therefore zero. Thus, if the test is not
carefully crafted, a zero vector may incorrectly be interpreted as a separating axis.
Due to the use of floating-point arithmetic, this problem may occur even in the case
of a near-zero vector for two near-parallel edges. In fact, the robustness problem of
the separating-axis test was encountered in Section 4.4.2 in the context of the OBB-
OBB intersection test, and a solution for the problem in that particular context can
be found there.
When possible, it is best to analyze the robustness problem in the context in which
it will occur. A generic solution to the problem is to test if the resulting cross-product
vector is a (near) zero vector, and if so attempt to deal with the problem either by
producing another axis that is perpendicular to the two vectors or by ignoring the
axis if separation on the axis can be ruled out.
The following code fragment outlines how a more robust separating-axis test for
edges AB and CD could be implemented.
// Compute a tentative separating axis for ab and cd
Vector m = Cross(ab, cd);
if (!IsZeroVector(m)) {
// Edges ab and cd not parallel, continue with m as a potential separating axis
...
} else {
// Edges ab and cd must be (near) parallel, and therefore lie in some plane P.
// Thus, as a separating axis try an axis perpendicular to ab and lying in P
Vector n = Cross(ab,c-a);
m = Cross(ab, n);
if (!IsZeroVector(m)) {
// Continue with m as a potential separating axis
...
}
// ab and ac are parallel too, so edges must be on a line. Ignore testing
// the axis for this combination of edges as it won't be a separating axis.
// (Alternatively, test if edges overlap on this line, in which case the
// objects are overlapping.)
...
}