An octree is a rooted tree that represents a three-dimensional region by recursively subdividing it into eight congruent, axis-aligned cuboids, usually cubes (Meagher 1982, Samet 1990). Each internal node represents a spatial cell and has eight children, one for each octant of the cell. A tree leaf represents a cell that is not subdivided further.
If the root cell is a cube of side length 
, then a cell
at depth 
has side length 
and volume 
. Uniform subdivision through depth 
produces 
leaf cells. In an adaptive octree, only selected cells
are subdivided, giving a nonuniform mesh with fine resolution
in selected regions and coarse resolution elsewhere.
Octrees support efficient spatial queries and locally refined meshes because large uniform regions can be stored at shallow depth while detailed regions
are represented by deeper branches. The two-dimensional analogue is a quadtree;
more generally, recursive subdivision of a 
-dimensional rectangular region into 
congruent children gives a 
-ary spatial tree.
