Game Development Reference

In-Depth Information

return index;

}

}

where the indices for each area match those shown in figure 12.10.

An oct-tree works in exactly the same way, but has eight child nodes and performs

a comparison on each of the three vector components to determine where an object

is located:

struct OctTreeNode

{

Vector3 position;

OctTreeNode child[8];

unsigned int getChildIndex(const Vector3 &object)

{

unsigned int index;

if (object.x > position.x) index += 1;

if (object.y > position.y) index += 2;

if (object.z > position.z) index += 4;

return index;

}

}

Although in theory the position vector for each node can be set anywhere, it is

common to see quad- and oct-trees with each node dividing its parents in half. Start-

ing with an axis-aligned bounding box that covers all the objects in the game, the

top-level node is positioned at the center point of this box. This effectively creates

four boxes of the same size (for a quad-tree; eight for an oct-tree). Each of these boxes

is represented by a node, whose position is at the center point of that box, creating

four (or eight) more boxes of the same size. And so on down the hierarchy.

There are two advantages to using this halving. First, it is possible to get rid of

the
position
vector from the node data structure and calculate the point on the fly

during recursion down the tree. This saves memory.

Second, it means we don't need to perform any calculations to find the best lo-

cation to place each node's split point. This makes it much faster to build the initial

hierarchy.

Other than their method of recursion and the number of children at each node,

the quad- and oct-trees work in exactly the same way as the BSP tree. The algorithms

that work with a BSP tree for determining collisions are the same as for a quad- or

oct-tree, but the test is simpler and there are more possible children to recurse into.

Also as with the BSP tree, we have to decide where to put objects that overlap the

dividing lines. In the previous code examples I have assumed the object goes into the