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 successor or no successor.

Octrees are mainly used in computer graphics to subdivide three-dimensional data hierarchically. The root in this case represents all data every other node represents an octant of data from its immediate predecessor. They are therefore suitable for implementing the strategy of divide and rule.

Octree can be viewed as an extension of binary trees and Quad Trees: Binary trees subdivide one-dimensional data, two-dimensional quadtree and octree three-dimensional; occasionally a generalization to arbitrary N -dimensional data tree is called. A more generalized version, in which the dimensions are not specified, is the B-tree.

• 2.1 Non- Empty - Empty - octree
• 2.2 Min-Max octree

Application

The following example illustrates the most common use of an octree, namely for the uniform outline of a cube-shaped data space: the root represents the whole cube. The cube is in eight smaller cubes - the octant - parts and any successor of the root is one of them. Each of these small cubes in turn divided into eight or smaller cubes, and so on. The subdivision of a part of the cube ends when no further division is possible or not necessary.

The source volume do not have to be cube-shaped, but may be generally cuboidal. A division of the volume in non- large parts is possible. Usually in the node additional information about the child nodes are stored. Thus, for example, contains every node of the special development min-max octree the minimum and the maximum of the following sub- tree, which enables efficient searching.

Other areas of application

General applications for octrees are:

• Image representation
• Space indexing (eg in geographic information systems )
• Grouping of particles in molecular dynamics / DEM simulations
• HiddenSurfaceRemoval of terrain data.
• Collision detection in 3D computer games
• Hierarchical splatting
• Adaptive solving differential equations, eg of deformable bodies
• State estimation

Special forms

Empty Non- Empty - octree

In a Non- Empty - Empty - octree either the value is stored empty or non- empty in each node. Blank indicates that the amount of data represented by the node does not contain process data worth, non- empty indicates accordingly that the associated amount of data must be processed. Space is usually at the same time the termination criterion for the subdivision; because the associated data set contains no interesting information more, it also is not worth it to be broken down further.

Min-Max octree

In a min-max octree the minimum and the maximum of the subtree of the node are stored in each node. Min-max octree are thus suitable for efficient searching along the lines of binary trees. The subtree of a node is searched only if the search value between minimum and maximum of the node. Thus, any parts of the tree cut out and the search can be accelerated by it.

For the special case, that minimum and maximum values ​​in a node are equal, the search in the subtree can also be omitted, because the entire subtree of the node containing this value. Normally, the minimum case is equal to the maximum and the termination criterion for the subdivision, ie the corresponding dataset is not further subdivided.

Min-max octree for example be used in volume rendering to speed up the marching cubes algorithm. Here all sub-cubes of the octree are searched, in which a predetermined threshold is included. This threshold is a material density for which the voxel data from an iso-surface to be extracted.

Tensor fields

Mathematically be Octrees are particularly suitable for structure of tensor fields. A voxel with gray values ​​, for example, is a scalar field, a zero-order tensor field, voxel three color values ​​on the RGB scheme and an alpha component are as a vector field tensor of the first order.