Octree

Octree
Left: Recursive subdivision of a cube into octants. Right: The corresponding octree.

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 quadtrees. The name is formed from oct + tree, and normally written "octree", not "octtree". Octrees are often used in 3D graphics and 3D game engines.

Contents

Octrees for spatial representation

Each node in an octree subdivides the space it represents into eight octants. 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, 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

Application to color quantization

The octree color quantization algorithm, invented by Gervautz and Purgathofer in 1988, encodes image color data as an octree up to nine levels deep. Octrees are used because 23 = 8 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

References

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

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Octree — Izquierda: Subdivisión recursiva de un cubo en octantes. Derecha: La grilla octree correspondiente. Una grilla octree es una estructura árbol (informática) de datos en la cual cada nodo interno tiene exactamente 8 hijos . Las grillas octree se… …   Wikipedia Español

  • Octree — Des nœuds d octree dépeints en tant que division d un espace de couleur. Un octree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu à huit enfants. Les octrees sont le plus souvent utilisés pour partitionner …   Wikipédia en Français

  • Octree — Ein Octree (von lat. octo „acht“, und engl. tree „Baum“) ist eine Datenstruktur der Informatik. Ein Octree ist ein gewurzelter Baum, dessen Knoten jeweils entweder acht direkte Nachfolger oder gar keine Nachfolger haben. Octrees werden… …   Deutsch Wikipedia

  • octree — noun A treelike data structure each of whose nodes has up to eight children, most often used to partition a three dimensional space by recursively subdividing it …   Wiktionary

  • Sparse Voxel Octree — Построение воксельного октодерева Sparse Voxel Octree (SVO, рус. Разреженное воксельное октоде …   Википедия

  • OLI — octree level index …   Medical dictionary

  • OLI — • octree level index …   Dictionary of medical acronyms & abbreviations

  • Oktalbaum — Ein Octree (von lat. oct „acht“, und engl. tree „Baum“) ist eine Datenstruktur der Informatik. Ein Octree ist ein gewurzelter Baum, dessen Knoten jeweils entweder acht direkte Nachfolger oder gar keine Nachfolger haben. Octrees werden… …   Deutsch Wikipedia

  • Октодерево — Слева: Рекурсивное разделение куба на октанты. Справа: Соответствующее октодерево …   Википедия

  • Level set (data structures) — In computer science a level set data structure is designed to represent discretely sampled dynamic level sets functions.A common use of this form of data structure is in efficient image rendering.Chronological developmentsThe powerful level set… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”