Árbol octal

Izquierda: Subdivisión recursiva de un cubo en octantes. Derecha: Octree correspondiente.

Un octree o árbol octal es una estructura en "árbol" de datos en la cual cada nodo interno tiene exactamente 8 "hijos". Las estructuras octree se usan mayormente para partir un espacio tridimensional, dividiéndolo recursivamente en ocho octantes. Las estructuras octree son las análogas tridimensionales de los quadtree bidimensionales. El nombre está formado a partir de oct (octante) + tree (árbol), y normalmente se escribe como "octree" en vez de "octtree".

Estructuras octree para la representación espacial

En una estructura octree, cada nodo subdivide el espacio que representa en ocho octantes. En una región punto (PR) octree, el nodo almacena un punto tridimensional explícito, 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 espacio infinito; el nodo raíz de una octree MX debe representar un espacio con límite finito para que los centros implícitos estén bien definidos. Las estructuras octree nunca se consideran árbol kd, ya que los árboles kd dividen en una dimensión mientras que las estructuras octree dividen alrededor de un punto. Los árboles kd además son siempre binarios, lo cual no se cumple para las estructuras octree.

Usos comunes de estructuras octree

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

Aplicación para la cuantificación del color

El algoritmo de cuantificación del color en una estructura octree, inventado por Gervautz and Purgathofer en 1988, codifica datos de color de imagen como un octree hasta de nueve niveles de profundidad. Las estructuras octree son usadas ya que ${\displaystyle 2^{3}=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 más 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 del 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 el 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

Referencias

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.». Archivado desde el original el 3 de marzo de 2016. Consultado el 23 de septiembre de 2010.