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 usan mayormente para particionar un espacio tridimensional, dividiéndolo recursivamente en ocho octantes. Las grillas octree son las análogas tridimensionales de las grillas quadtree. El nombre está formado a partir de oct (octante) + tree (árbol), y normalmente se escribe como "octree" en vez de "octtree".

Grillas octree para la representación espacial

En una grilla octree, cada nodo subdivide el espacio que representa en ocho octantes. En una región punto (PR) octree, el nodo almacena un punto tridimensional explicito, el cual es el "centro" de la subdivisión para ese nodo; el punto que define una de las esquinas para cada uno de los ocho hijos. En una octree MX, el punto de subdivisión es implícitamente el centro del espacio que el nodo representa. El nodo raíz de una PR octree puede representar un espace infinito; el nodo raíz de una octree MX debe representar un espacio con limite finito para que los centros implícitos estén bien definidos. Las grillas octree nunca se consideran árbol kd, ya que los árboles kd dividen en una dimensión mientras que las grillas octree dividen alrededor de un punto. Los árboles kd además son siempre binarios, lo cual no se cumple para las grillas octree.

Usos comunes de grillas octree

• Índice espacial
• Detección de colisiones eficiente en tres dimensiones
• Determinación de cara oculta
• Método multipolo rápido
• Grillas no estructuradas
• Método de los elementos finitos
• Grillas octree de vóxeles escasos
• Teorema de Bayes^[1]

Aplicación para la cuantización del color

El algoritmo de cuantización del color de la grilla octree, inventado por Gervautz and Purgathofer en 1988, codifica datos de color de imagen como una grilla octree hasta de nueve niveles de profundidad. Las grillas octree son usadas ya que 2³ = 8, y hay tres componentes de colores en el sistema modelo de color RGB (del inglés Red, Green, Blue; "rojo, verde, azul"). En índice nodo para ramificar desde en el nivel tope está determinado por una fórmula que usa los bits mas significativos de los componentes de colores rojo, verde, y azul, e.g. 4r + 2g ´b. el siguiente nivel bajo usa el siguiente bit significativo, y etc. los bits menos significativos se ignoran en algunas ocasiones para reducir el tamaño del árbol.

El algoritmo es de una memoria altamente eficiente ya que el tamaño del árbol se puede limitar. El nivel del fondo de la grilla octree consiste de nodos hojas que acumulan datos de color que no están representados en el árbol; estos nodos contienen inicialmente bits simples. Si en ingresan en la grilla octree muchos más números de colores de paletas que los deseados, su tamaño se puede reducir continuamente buscando un nodo de nivel bajo y promediando sus datos de bit hasta en un nodo hoja, podando parte del árbol. Una vez que el muestreo está completo, al explorar todas las rutas en el árbol hasta las hojas nodos, y al tomar nota de los bits a lo largo del camino, se obtendrá aproximadamente los números de colores requeridos.

Véase también

• quadtree
• árbol kd
• Problema de la medida de Klee
• Sauerbraten (videojuego)
• OGRE 3D
• Irrlicht

Enlaces externos

• Octree Quantization in Microsoft Systems Journal
• Octree Overview
• Video: El uso de un octree en estimación de estado

Referencia

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.