Graphics Reference
In-Depth Information
faster intersection test that only involves testing four separating axes in addition to a
cheap test in the vertical direction.
In some cases, performing just the first 6 of the 15 axis tests may result in faster
results overall. In empirical tests, [Bergen97] found that the last 9 tests in the OBB
overlap code determine nonintersection about 15% of the time. As perhaps half of
all queries are positive to start with, omitting these 9 tests results in false positives
about 6 to 7% of the time. When the OBB test is performed as a pretest for an exact
test on the bounded geometry, this still leaves the test conservative and no collisions
are missed.
4.4.2
Making the Separating-axis Test Robust
A very important issue overlooked in several popular treatments of the separating-
axis theorem is the robustness of the test. Unfortunately, any code implementing this
test must be very carefully crafted to work as intended. When a separating axis is
formed by taking the cross product of an edge from each bounding box there is a
possibility these edges are parallel. As a result, their cross product is the null vector,
all projections onto this null vector are zero, and the sum of products on each side of
the axis inequality vanishes. Remaining is the comparison 0
0. In the perfect world
of exact arithmetic mathematics, this expression would trivially evaluate to false. In
reality, any computer implementation must deal with inaccuracies introduced by the
use of floating-point arithmetic.
For the optimized inequalities presented earlier, the case of parallel edges cor-
responds to only the zero elements of the rotation matrix
R
being referenced.
Theoretically, this still results in the comparison 0
>
0. In practice, however, due
to accumulation of errors the rotation matrix will not be perfectly orthonormal and
its zero elements will not be exactly zero. Thus, the sum of products on both sides
of the inequality will also not be zero, but some small error quantity. As this accu-
mulation of errors can cause either side of the inequality to change sign or shift in
magnitude, the result will be quite random. Consequently, if the inequality tests are
not very carefully performed these arithmetic errors could lead to the (near) null vec-
tor incorrectly being interpreted as a separating axis. Two overlapping OBBs therefore
could be incorrectly reported as nonintersecting.
As the right-hand side of the inequalities should be larger when two OBBs are
interpenetrating, a simple solution to the problem is to add a small epsilon value to
the absolute values of the matrix elements occurring on the right-hand side of the
inequalities. For near-zero terms, this epsilon term will be dominating and axis tests
corresponding to (near) parallel edges are thus made disproportionately conservative.
For other, nonzero cases, the small epsilon term will simply disappear. Note that as
the absolute values of the components of a rotation matrix are bounded to the range
[
>
using a fixed-magnitude epsilon works fine regardless of the sizes of the boxes
involved. The robustness of the separating-axis test is revisited in Chapter 5.
0, 1
]
