Game Development Reference
In-Depth Information
Spheres
AABB
P max1
O 1
O 2
P max2
R 1
R 2
Pmin1
P min2
k-DOP
OBB
B
A
b 2 B 2
b 1 B 1
T
a 1 A 1
a 2 A 2
L
Figure 17.12 Test of collision between bounding volumes
17.2.3 Approximate detection (narrow-phase)
Approximate detection uses more andmore detailed approximations of objects done by
simple volumes to locate the zones affected by a collision. Though bounding volumes
are most commonly used, please note that the bound volumes (i.e. contained in the
object) can be useful to indicate a certain collision when they intersect each other. A
rough search of collisions can also benefit frommodern graphic acceleration functions;
several methods were in fact proposed in the last few years.
17.2.3.1 Strategies of detection by bounding volumes
The volumes used to approximate the shape of objects are simple geometrical shapes
like spheres, isothetic boxes (AABB: Axis-Aligned Bounding Boxes), discrete orien-
tation polytopes ( k -DOP) 4 and oriented boxes (OBB: Oriented Bounding Boxes).
However, other more complex volumes such as convex envelops of objects, Quan-
tized Orientation Slabs with Primary Orientations (QuOSPO) (He, 1999), spherical-
Shells (Krishnan et al., 1998) can also be used. Figure 17.12 and table 17.1 provide
the collision detection tests for frequently used volumes.
Detection of non-intersection between bounding volumes is always based on the
same principle: finding an axis separating the two volumes. It turns out that, in reality,
the choice of a volume involves only choosing certain axes to test the separation of
objects (in case of spheres, it is the axis joining the centres of the objects, whereas in case
of AABBs, the reference axes, etc.). The fastest intersections to be tested are between
4 These volumes are polytopes based on the AABB, where we use other axes (fixed) in addition
to those of the reference to define the surfaces. The 6-DOP are the AABB.