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;

};