All Topics  
Octree

 

 
   Email Print
   Bookmark   Link
 

 

Octree
 
 
  Topics Octree Topic Home

An octree is a tree data structure in which each internal node has up to 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
Quadtree

A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions....
s. The name is formed from oct + tree, and normally written "octree", not "octtree".

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....
s.






Discussion
Ask a question about 'Octree'
Start a new discussion about 'Octree'
Answer questions from other users
Full Discussion Forum



Encyclopedia


An octree is a tree data structure in which each internal node has up to 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
Quadtree

A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions....
s. The name is formed from oct + tree, and normally written "octree", not "octtree".

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....
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 kd-tree is a space partitioning data structure for organizing Point s in a k-dimensional Euclidean space. kd-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
    Spatial index

    Spatial indexes are used by spatial databases to optimize spatial query. Indexes used by non-spatial databases cannot effectively handle features such as how far two points differ and whether points fall within a spatial area of interest....
  • Efficient collision detection
    Collision detection

    In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
     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....


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....
 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.

See also

  • Quadtree
    Quadtree

    A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions....
  • kd-tree
    Kd-tree

    In computer science, a kd-tree is a space partitioning data structure for organizing Point s in a k-dimensional Euclidean space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key ....
  • Loose octrees
  • 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....
  • 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
    Linear octrees

    An octree is said to be complete if every internal node has exactly 8 child nodes. If the maximum permissible depth of an octree is fixed a priori, then it is sufficient to store the complete list of leaf nodes of the octree....
  • Balanced octrees
  • Sauerbraten, a 3D game engine in which geometry is almost entirely based on octrees
  • OGRE
    Ogre

    An ogre is a large, cruel and hideous humanoid monster], featured in mythology, folklore and fiction. Ogres are often depicted in fairy tales and folklore as feeding on human beings, and have appeared in many classic works of literature....
    , has an Octree Scene Manager Implementation


External links


  • [ftp://66.77.27.238/sourcecode/ddj/1996/9601.zip Color Quantization using Octrees in Dr. Dobb's Source Code]