Graphics Reference
In-Depth Information
B
T
A
L
r
A
r
B
T
•
L
Figure 4.9
Two OBBs are separated if for some axis
L
the sum of their projected radii is less
than the distance between their projected centers.
this test could be performed by checking if the vertices of box
A
are all on the outside
of the planes defined by the faces of box
B
, and vice versa. However, although this
test works in 2D it does not work correctly in 3D. It fails to deal with, for example, the
case in which
A
and
B
are almost meeting edge to edge, the edges perpendicular to
each other. Here, neither box is fully outside any one face of the other. Consequently,
the simple test reports them as intersecting even though they are not. Even so, the
simple test may still be useful. Although it is not always correct, it is conservative in
that it never fails to detect a collision. Only in some cases does it incorrectly report
separated boxes as overlapping. As such, it can serve as a pretest for a more expensive
exact test.
An exact test for OBB-OBB intersection can be implemented in terms of what is
known as the separating axis test. This test is discussed in detail in Chapter 5, but
here it is sufficient to note that two OBBs are separated if, with respect to some axis
L
, the sum of their projected radii is less than the distance between the projection of
their center points (as illustrated in Figure 4.9). That is, if
|
T
·
L
|
>
r
A
+
r
B
.
For OBBs it is possible to show that at most 15 of these separating axes must be tested
to correctly determine the OBB overlap status. These axes correspond to the three
coordinate axes of
A
, the three coordinate axes of
B
, and the nine axes perpendicular
to an axis from each. If the boxes fail to overlap on any of the 15 axes, they are
not intersecting. If no axis provides this early out, it follows that the boxes must be
overlapping.
The number of operations in the test can be reduced by expressing
B
in the coor-
dinate frame of
A
.If
t
is the translation vector from
A
to
B
and
R
=
r
ij
(the rotation
