Graphics Reference
In-Depth Information
2
3
6
7
1
0
4
5
Figure 7.10
Numbering of the eight child nodes of the root of an octree.
7.3.1
Octrees (and Quadtrees)
The archetypal tree-based spatial partitioning method is the
octree
. It is an axis-aligned
hierarchical partitioning of a volume of 3D world space. As the name suggests, each
parent node in the octree has eight children. Additionally, each node also has a finite
volume associated with it. The root node volume is generally taken to be the smallest
axis-aligned cube fully enclosing the world. This volume is then subdivided into eight
smaller equal-size subcubes (also called cells, octants, or cubelets) by simultaneously
dividing the cube in half along each of the
x
,
y
, and
z
axes (Figure 7.10). These subcubes
form the child nodes of the root node. The child nodes are, in turn, recursively
subdivided in the same fashion. Typical criteria for stopping the recursive creation
of the octree include the tree reaching a maximum depth or the cubes getting smaller
than some preset minimum size. By virtue of construction, the associated volume of
space for each node of the tree fully contains all descendant nodes.
Even though the geometric boundaries of a node can, for instance, be passed
down and refined as the octree is traversed, the node structure is often enhanced to
contain both node position and extent. This simplifies tree operations at the cost of
extra memory. In addition, if the requirement for splitting into eight child volumes of
equal size is relaxed to allow off-center splitting independently on all three axes, this
volume information must be stored in the nodes.
// Octree node data structure
struct Node {
Point center;
// Center point of octree node (not strictly needed)
float halfWidth;
// Half the width of the node volume (not strictly needed)
Node *pChild[8];
// Pointers to the eight children nodes
Object *pObjList;
// Linked list of objects contained at this node
};
