Octree

An octree (from Latin octo 'eight' and English tree 'tree' ) is a data structure in computer science . An octree is a rooted tree whose nodes each have either eight direct descendants or no descendants at all.

Octrees are mainly used in computer graphics to subdivide three-dimensional data sets hierarchically. The root represents all data, each other node represents an octant of the data of its direct predecessor. This makes them suitable for implementing the divide and conquer strategy .

Octrees can be seen as extensions of binary trees and quadtrees : binary trees subdivide one-dimensional data, quadtrees two-dimensional and octrees three-dimensional; occasionally, a generalization to any-dimensional data is called an N-tree . A more generalized version where the dimensions are not fixed is the B-tree .

application

Scheme of an octree. On the left the subdivision of the cube-shaped volume, on the right the resulting octree.

The following example illustrates the most common use of an octree, namely for the even structure of a cube-shaped data space: The root stands for the entire cube. The cube is divided into eight smaller cubes - the octants - and each successor to the root stands for one of them. Each of these smaller cubes is in turn cut into eight even smaller cubes, and so on. The subdivision of a partial cube ends when no further division is possible or not necessary.

The original volume does not have to be cube-shaped, but can also be generally cuboid. It is also possible to divide the volume into unequal parts. As a rule, additional information about the subordinate nodes is stored in the nodes. So contains z. For example, every node of the special min-max-octree form has the minimum and maximum of the following subtree, which enables efficient searches.

Further areas of application

General areas of application for octrees are:

• Image representation
• Spatial indexing (e.g. in geographic information systems )
• Grouping of particles in molecular dynamics / DEM simulations
• Hidden surface removal of terrain data.
• Collision detection in 3D computer games
• Hierarchical splatting
• Adaptive solving of differential equations, e.g. B. deformable bodies
• State estimation

Special forms

Empty-Non-Empty-Octree

In an Empty-Non-Empty-Octree, either the value empty or non-empty is stored in each node . Empty indicates that the data volume represented by the node does not contain any data worth processing; non-empty accordingly indicates that the associated data volume must be processed. Normally, empty is also the termination criterion for the subdivision; Since the associated data volume no longer contains any interesting information, it is also not worthwhile to subdivide it further.

Min-Max-Octree

Scheme of a min-max octree. Each node contains the minimum (top) and maximum (bottom) of its subtree. When searching for the value 3, only the data volumes of the nodes marked in yellow need to be searched.

The minimum and maximum of the sub-tree of the node are stored in a min-max-octree in each node. Min-Max-Octrees are therefore suitable for efficient searches based on the example of binary trees. The subtree of a node is only searched if the searched value lies between the minimum and maximum of the node. In this way, parts of the tree can be left out and the search can be accelerated.

For the special case that the minimum and maximum are the same in a node, the search in the subtree can also be left out, because the entire subtree of the node contains the value sought. Normally, the case of minimum equals maximum is also the termination criterion for the subdivision, i.e. the associated data volume is not subdivided further.

Min-Max-Octrees are used, for example, in volume graphics to accelerate the marching cube algorithm. Here all sub-cubes of the octree are searched that contain a given threshold value. This threshold value is a material density for which an isosurface is to be extracted from the voxel data.

Tensor fields

From a mathematical point of view, octrees are particularly suitable for structuring tensor fields . A voxel grid with gray values, for example, is a zero-order tensor field as a scalar field, and a voxel grid with three color values ​​according to the RGB scheme and an alpha component as a vector field is a first-order tensor field.

Web links

Commons : Octree  - collection of images, videos and audio files

Individual evidence

1. ↑ Martin Seiler et al., A Threefold Representation for the Adaptive Simulation of Embedded Deformable Objects in Contact , Journal of WSCG, Pilsen, Czech Republic, February, 2010.
2. ↑ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010. (PDF; 3.2 MB)