Octree

Definition

An octree is a data structure to represent objects in the three-dimensional space, automatically grouping them hierarchically and avoiding the representation of empty portions of the space.

The first octree node is the root cell, see Fig. above, which is an array of eight contiguous elements. Each of these elements can point to another block of eight contiguos elements, where each one can point to another block of eight contiguous elements and so forth, until a certain maximum number of levels is reached. The last level is the leaf level where the leaf elements or voxels are stored.

Voxel Search Principle

The figure above shows the correspondence between the data structure in the memory (left) and its representation in three-dimensional space (right). The tree contains eight voxels and five levels. Each level is represented in a different color. The eight voxels stored in the last level of the octree are represented in pink. The table in the figure show the coordinates of the fifth voxel (index 4) of the last cell. Its coordinates: 31, 30 and 30 are then shown on the right side in binary. Finally, each column corresponding to each coordinate bit also corresponds to an octree level. Concatenating the bits of each column, one obtains the indexes (appearing in the last line of the table) of each element in a cell for the corresponding level, used to traverse the tree and to find the searched voxel. This is the principle to search a given voxel in an octree.

The main advantage of this scheme is that the voxel coordinates are not stored but are implicit to the position of the elements to be traversed. This is particularly interesting in high resolution voxel spaces, where coordinates are long and cumbersome to store. 3D grids too have coordinates implicit to the voxel position, but also have the serious disadvantage of representing every voxel in the volume even if most of the volume is empty.

Memory Occupation

If every element of every cell above the leaf level points to a cell, the octree is called a "full octree". A full octree with n levels contains the same number of voxels as a regular 3D grid of resolution 2ⁿ x 2ⁿ x 2ⁿ (e.g., a full octree of 5 levels is equivalent to a 3D grid with resolution 32 x 32 x 32). In this extreme case the octree takes roughly 14% more room than a correspondent 3D grid. However, when the voxels represent surfaces instead of volumes, most of the space is empty and it is not represented in the octree. In these cases, the octree is very economic, allowing high resolution voxel spaces with low memory consumption.