Octrees are the 3D version of quadtrees. The octree is a tree-based data representation to store and index location information about a 3D image or area. The root of the tree has eight branches corresponding to the eight octants of the image/area. For example, if the area is a unit square, then the first branch is for the area with coprdinates (0–0.5,0–0.5,0–0.5), and the next one (0–0.5,0–0.5,0.5–1). If there are no data points in any of these octants, then they are marked as empty. Otherwise the points are allocated to the relevant octant and then the same process is used to build an octree of those.
Used on page 259