Octree

Octree Definition

Octrees are a hierarchical tree structure used for spatial partitioning of three-dimensional space - they divide space into a system of smaller and smaller cubes. The octree starts with a single cube (the “root” of the tree) that bounds a region of interest, for example a point cloud or a mesh. This cube is then equally divided into eight smaller cubes (“branches” on the tree), and this process is continued until a termination criteria is reached. Each “node” in the tree is linked to its parent and children, enabling the tree to be traversed.

This partitioning of space allows for efficient searching of the data encoded by the octree. For example, an octree representation of a surface mesh can be used when performing Ray-Triangle Intersection tests; rather than testing the ray against every triangle in the mesh, the ray can be tested for intersection with an octree node (using a Ray-Box Intersection test) - if the ray doesn’t intersect with the cube, surely it can’t intersect any of the triangles contained within the cube, so a single ray-box intersection test can eliminate the need for thousands of ray-triangle intersection tests.

Generating Octrees

Octrees can be used to represent various types of data, including point clouds, voxel meshes, surface meshes, and implicit functions.

Point Cloud Octrees

See Points2Octree()

Perhaps the most straight forward data to represent with an octree is a set of points. First, the root node is created to bound the full set of points. It is then subdivided into 8 children and the points are checked against the bounds of each child to determine which points are contained by which node of the octree. This process is repeated, with points being passed from parents to the children containing the points until each octree node contains only one point (or until a specified maximum depth is reached). Those nodes are marked as “leaf” nodes, while nodes that contain no points are marked as “empty” and no longer continue to be subdivided.

Voxel Octrees

See Voxel2Octree()

Since octrees are based on cubes, it’s natural to associate them with voxel meshes - voxel meshes can be used to create octrees and vice versa. The creation of an octree from a voxel mesh is essentially the same as creating an octree from a point cloud, but the points are the centroids of the voxels. When care is taken to properly specify the size of the root node, the octree can be subdivided until leaf nodes exactly correspond to voxel elements.

Surface Mesh Octrees

See Surface2Octree()

Implicit Function Octrees

See Function2Octree()

An octree can be constructed to efficiently sample an implicit function, allowing for higher resolution in complex regions of the surface and lower resolution in regions with larger features. Several strategies exist for creating such an octree, most of which rely on using both the function and its gradient to assess the error associated with representing the function at the current octree level to determine whether or not to subdivide further.

Two popular choices are the Euclidean Distance Error (EDError) [ZBS03] and Quadratic Error Functions (QEF) [SW05].

Euclidean Distance Error

The Euclidean distance error function measures the error between linear interpolation of the vertices of the current octree node and exact evaluation of the function at the vertices of the next level of refinement.