Game Development Reference
F IGURE 12.9
A binary space partition tree.
They are also commonly used to detect collisions between the level geometry and the
game level. Figure 12.9 shows a small BSP for part of a game level.
The BSP doesn't hold objects at its leaves, but rather is a boolean indication of
whether the object is colliding or not. An object is tested against each plane, re-
cursively. If it intersects the plane, both children are checked; otherwise, only one
is checked, as before. If the object reaches a leaf marked as a collision we know a
collision has occurred.
Because most collisions will occur between moving objects and the level geometry
(which typically cannot change or move in any way), the BSP approach is very useful.
Unfortunately a complex preprocessing stage is required to build the BSP from the
O CT -T REES AND Q UAD -T REES
Oct-trees and quad-trees are spatial tree data structures with many similarities to
both BSPs and BVHs. Quad-trees are used for two dimensions (or three dimensions
where most objects will be stuck on the ground), and oct-trees for three dimensions.
I'll focus on that first.
A quad-tree is made up of a set of nodes, each with four descendents. The node
splits space into four areas that intersect at a single point. It can be thought of as
three nodes of a BSP tree, although the directions that are split are always aligned
with the world axes. A node can be represented as a vector position and four chil-