Game Development Reference
In-Depth Information
Table 17.1 Bounding volumes and collision tests.
Volumes
Non-collision tests
Spheres
dist( O 1 , O 2 ) 2 > ( R 1 + R 2 ) 2
AABB
k ∈{ x , y , z } , P max [ k ]< P min [ k ]
k -DOP
k ∈{ 1 ··· l } , P max [ k ]< P min [ k ]
L ∈{ A i , B i , A i B j } ,
OBB
| T · L | > i = 1 | a i A i · L |+ i = 1 | b i B i · L |
Envelop or other convex volume
GJK, DK or LC- Voronoi Marching
spheres, between AABBs and between the k -DOP. On the other hand, the test between
OBBs is the slowest, but these volumes nonetheless offer a better approximation of
objects and hence an abundant choice of separator axes. Same is the case with convex
envelops. Due to this compromise between speed and accuracy, the choice of volume
depends largely on the context and mainly on the shape and the movement of the
objects being considered.
We generally use a collection of volumes capable of approximating the object at
various scales - entirely, in parts or its constitutive primitives. Certain structures are
based on piled or imbricate volumes and do not depend on the objects. For example,
R-Tree (Held et al., 1995), Box-Trees (Zachmann, 1997) and subdivision of the object
space into voxels (Garcia-Alonso et al., 1994), octrees (Ponamgi et al., 1995), Bucket-
Tree (Ganovelli et al., 2000) or spherical octrees (Tzafestas &Coiffet, 1996). However,
a tree structure of approximation volumes ( BVH ) if often used to quickly find the
zones of contact or proximity. Such hierarchy can be implemented by two different
approaches (Barequet et al., 1996):
Top-down approach: Construction of the hierarchy in this approach is from the
global volume to the basic primitives of the object. In other words, the entire object
is covered by the selected volume, the volume or the object is then subdivided into
sub-volumes, the same procedure is applied to the sub-volumes obtained till the
lowest level primitives are reached;
Bottom-up approach: This approach constructs the bounding volumes by starting
from the basic primitives and then covering the entire volume. Firstly, the small
volumes are spread over the surface of the entire object, then a number of these
small objects are grouped together in a bounding volume of a higher level and so
on till the object is completely covered.
We start by inspecting the root volumes to detect the collisions between two BVHs.
If there is an intersection, we go down recursively in the hierarchy either of both the
objects or of the object that has a larger inspected bounding volume, depending on
the method used. The algorithm then provides a set of facets in probable collision.
We find the hierarchies of OBB (OBBTrees) in Gottschalk et al. (1996), AABB in a
global reference (Hahn, 1988; Larsson & Möller, 2001) or in the local reference of
the object (Bergen, 1998), spheres (Palmer et al., 1995; Hubbard, 1996; O'Sullivan &
Dingliana, 1999; Redon et al., 2001), k -DOP (Klosowski et al., 1998; Zachmann,
1998), Spherical-Shells (Krishnan et al., 1998) or QuOSPOs (He, 1999). As per the
case, each node of the hierarchy is subdivided into two, four, or even eight sub-volumes