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