Game Development Reference
In-Depth Information
12.4
S PATIAL D ATA S TRUCTURES
Several different approaches to coarse collision detection fall under the banner of
“spatial data structures.” The distinction between spatial data structures and bound-
ingvolumesissomewhatblurry.
A bounding volume hierarchy groups objects together based on their relative po-
sitions and sizes. If the objects move, then the hierarchy will move too. For different
sets of objects the hierarchy will have a very different structure.
A spatial data structure is locked to the world. If an object is found at some loca-
tion in the world, it will be mapped to one position in the data structure. A spatial data
structure doesn't change its structure depending on what objects are placed within it.
This makes it much easier to build the data structure.
In reality the line between the two is blurred, and a combination of techniques
is sometimes used (hierarchies embedded in a spatial data structure, for example, or,
less commonly, a spatial data structure at one node in a hierarchy). It is also worth
noting that even when no bounding volume hierarchies are used, it is very common
to use bounding volumes around each object. In the remainder of this chapter, I will
assume objects are wrapped in a bounding volume: it makes many of the algorithms
far simpler.
This section looks at three common spatial data structures: binary space partition
(BSP) trees, quad- and oct-trees, and grids. In most games only one will be used.
12.4.1
B INARY S PACE P ARTITIONING
A binary space partition tree behaves in a similar way to a bounding volume hierarchy.
It is a binary tree data structure, and a recursive algorithm starts at the top of the tree
and descends into child nodes only if they are capable of taking part in a collision.
Rather than use bounding volumes, however, each node in the BSP uses a plane
that divides all space into two. It has two child nodes, one for each side of the plane.
Objects lying on one side of the plane or the other will be found as a descendent of
the corresponding child. Objects that cross the plane are handled differently: they can
be directly attached to that node; placed in the child node that they are nearest to; or,
more commonly, placed in both child nodes.
The dividing planes at each level are different, allowing all space to be divided up
in any way. The figure later in this section shows a 2D version, but the same structure
works for three dimensions.
Each plane in the BSP is represented as a vector position and a vector direction:
struct Plane
{
Vector3 position;
Vector3 direction;
};