Octree

# Octree

Overview
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...

s. The name is formed from oct + tree, and normally written "octree", not "octtree". Octrees are often used in 3D graphics and 3D game engine
Game engine
A game engine is a system designed for the creation and development of video games. There are many game engines that are designed to work on video game consoles and personal computers...

s.

Each node in an octree subdivides the space it represents into eight octant
Octant
An octant is one of eight divisions.-Octant in the plane :Traditionally wind direction is given as one of the 8 octants because that is more accurate than merely giving one of the 4 quadrants, and the wind vane typically does not have enough accuracy to bother with more precise indication.-Octant...

s.
Discussion

Encyclopedia
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...

s. The name is formed from oct + tree, and normally written "octree", not "octtree". Octrees are often used in 3D graphics and 3D game engine
Game engine
A game engine is a system designed for the creation and development of video games. There are many game engines that are designed to work on video game consoles and personal computers...

s.

## Octrees for spatial representation

Each node in an octree subdivides the space it represents into eight octant
Octant
An octant is one of eight divisions.-Octant in the plane :Traditionally wind direction is given as one of the 8 octants because that is more accurate than merely giving one of the 4 quadrants, and the wind vane typically does not have enough accuracy to bother with more precise indication.-Octant...

s. In a point region (PR) octree, the node stores an explicit 3-dimensional point, which is the "center" of the subdivision for that node; the point defines one of the corners for each of the eight children. In an MX octree, the subdivision point is implicitly the center of the space the node represents. The root node of a PR octree can represent infinite space; the root node of an MX octree must represent a finite bounded space so that the implicit centers are well-defined. Octrees are never considered kD-trees
Kd-tree
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...

, as kD-trees split along a dimension and octrees split around a point. kD-trees are also always binary, which is not true of octrees.

## Common uses of octrees

• Spatial indexing
• Efficient collision detection
Collision detection
Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...

in three dimensions
• View frustum culling
• Fast Multipole Method
Fast Multipole Method
The fast multipole method is a mathematical technique that was developed to speed up the calculation of long-ranged forces in the n-body problem...

• Unstructured grid
Unstructured grid
An unstructured grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern...

• Finite element analysis
• Sparse voxel octree
Sparse voxel octree
A sparse voxel octree is a 3D computer graphics rendering technique using a raycasting or sometimes a ray tracing approach into an octree data representation....

• State estimation

## Application to color quantization

The octree color quantization
Color quantization
In computer graphics, color quantization or color image quantization is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as visually similar as possible to the original image. Computer algorithms to perform color...

algorithm, invented by Gervautz and Purgathofer in 1988, encodes image color data as an octree up to nine levels deep. Octrees are used because and there are three color components in the RGB system. The node index to branch out from at the top level is determined by a formula that uses the most significant bits of the red, green, and blue color components, e.g. 4r + 2g + b. The next lower level uses the next bit significance, and so on. Less significant bits are sometimes ignored to reduce the tree size.

The algorithm is highly memory efficient because the tree's size can be limited. The bottom level of the octree consists of leaf nodes that accrue color data not represented in the tree; these nodes initially contain single bits. If much more than the desired number of palette colors are entered into the octree, its size can be continually reduced by seeking out a bottom-level node and averaging its bit data up into a leaf node, pruning part of the tree. Once sampling is complete, exploring all routes in the tree down to the leaf nodes, taking note of the bits along the way, will yield approximately the required number of colors.

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...

• Bounding Interval Hierarchy
Bounding interval hierarchy
A bounding interval hierarchy is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance ray tracing and may be especially useful for dynamic scenes.The BIH itself is, however, not new...

• Klee's measure problem
Klee's measure problem
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of rectangular ranges can be computed...

• Linear octrees
• Cube 2, a 3D game engine in which geometry is almost entirely based on octrees
• OGRE
OGRE
OGRE is a scene-oriented, flexible 3D rendering engine written in C++ designed to make it easier and intuitive for developers to produce applications utilizing hardware-accelerated 3D graphics...

, has an Octree Scene Manager Implementation
• Irrlicht Engine
Irrlicht Engine
Irrlicht is an open source 3D engine written in C++. It is cross-platform, officially running on Windows, Mac OS X, Linux and Windows CE and due to its open nature ports to other systems are available, including Xbox, PlayStation Portable, SymbianOS and iPhone.Irrlicht is known for its small size...

, supports octree scene nodes
• Dendro, a parallel multigrid library for finite element computations using octrees
• id Tech 6
Id Tech 6
id Tech 6 is an upcoming OpenGL based game engine under preliminary development by id Software, which will tentatively follow id Tech 5 for id Software games following Rage, and Doom 4....

an in development 3D game engine that utilizes voxels stored in octrees