Octree

Un octree (del latín octo 'ocho' y del inglés árbol 'árbol' ) es una estructura de datos en informática . Un octárbol es un árbol enraizado cuyos nodos tienen cada uno ocho descendientes directos o ningún descendiente.

Los octárboles se utilizan principalmente en gráficos por computadora para subdividir jerárquicamente conjuntos de datos tridimensionales. La raíz representa todos los datos, cada otro nodo representa un octante de los datos de su predecesor directo. Esto los hace adecuados para implementar la estrategia divide y vencerás .

Los octárboles pueden verse como extensiones de árboles binarios y cuadrúpedos : los árboles binarios subdividen datos unidimensionales, los cuadrboles bidimensionales y los octárboles tridimensionales; Ocasionalmente, una generalización a datos de cualquier dimensión se llama N-Tree . Otra versión más generalizada, donde las dimensiones no son fijas, es el B-tree .

usar

Esquema de un octárbol. A la izquierda la subdivisión del volumen en forma de cubo, a la derecha el octárbol resultante.

El siguiente ejemplo ilustra el uso más común de un octárbol, es decir, para la estructura uniforme de un espacio de datos en forma de cubo: La raíz representa el cubo completo. El cubo se divide en ocho cubos más pequeños, los octantes, y cada sucesor de la raíz representa uno de ellos. Cada uno de estos cubos más pequeños se corta a su vez en ocho cubos aún más pequeños, y así sucesivamente. La subdivisión de un cubo parcial finaliza cuando no es posible o no es necesaria ninguna otra división.

El volumen original no tiene que tener forma de cubo, sino que también puede ser generalmente cuboide. También es posible dividir los volúmenes en partes desiguales. Como regla general, la información adicional sobre los nodos subordinados se almacena en los nodos. Entonces contiene z. Por ejemplo, cada nodo de la forma especial min-max-octree tiene el mínimo y el máximo del siguiente subárbol, lo que permite búsquedas eficientes.

Otras áreas de aplicación

Las áreas generales de aplicación de los octárboles son:

• Representación de imágenes
• Indexación espacial (por ejemplo, en sistemas de información geográfica )
• Agrupación de partículas en dinámica molecular / simulaciones DEM
• Eliminación de datos del terreno en superficies ocultas
• Detección de colisiones en juegos de computadora 3D
• Salpicaduras jerárquicas
• Resolución adaptativa de ecuaciones diferenciales, p. Ej. B. cuerpos deformables
• Estimación del estado

Formas especiales

Vacío-no-vacío-octree

El valor vacío o no vacío se almacena en cada nodo en un octárbol vacío no vacío . Vacío indica que el volumen de datos representado por el nodo no contiene ningún dato que valga la pena procesar; en consecuencia , no vacío indica que el volumen de datos asociado debe procesarse. Por lo general, vacío también es el criterio de terminación para la subdivisión; Dado que el volumen de datos asociado ya no contiene información interesante, tampoco vale la pena subdividirlo más.

Min-Max-Octree

Esquema de un octárbol min-max. Cada nodo contiene el mínimo (superior) y el máximo (inferior) de su subárbol. Al buscar el valor 3, solo es necesario buscar los volúmenes de datos de los nodos marcados en amarillo.

El mínimo y el máximo del subárbol del nodo se almacenan en un mínimo-máximo-octárbol en cada nodo. Los min-max-octrees son, por tanto, adecuados para búsquedas eficientes basadas en el ejemplo de árboles binarios. El subárbol de un nodo solo se busca si el valor buscado se encuentra entre el mínimo y el máximo del nodo. De esta forma, se pueden dejar fuera partes del árbol y se puede acelerar la búsqueda.

Para el caso especial en el que el mínimo y el máximo son iguales en un nodo, la búsqueda en el subárbol también se puede omitir, porque todo el subárbol del nodo contiene el valor que está buscando. Normalmente, el caso de mínimo igual a máximo es también el criterio de terminación para la subdivisión, es decir, el volumen de datos asociado no se subdivide más.

Por ejemplo, los octrees mínimo-máximo se utilizan en gráficos de volumen para acelerar el algoritmo del cubo de marcha . Aquí se buscan todos los subcubos del octárbol que contienen un valor umbral determinado. Este valor umbral es una densidad de material para la que se debe extraer una isosuperficie de los datos de vóxel.

Campos tensores

Desde un punto de vista matemático, los octrees son particularmente adecuados para estructurar campos tensoriales . Una cuadrícula de vóxeles con valores grises, por ejemplo, es un campo tensorial de orden cero como campo escalar , y una cuadrícula de vóxeles con tres valores de color según el esquema RGB y un componente alfa como campo vectorial es un campo de primer orden. campo tensorial.

enlaces web

Evidencia individual

1. ↑ Martin Seiler et al., Una representación triple para la simulación adaptativa de objetos deformables incrustados en contacto , Journal of WSCG, Pilsen, República Checa, febrero de 2010.
2. ↑ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Actas de la XIII Conferencia Internacional sobre Fusión de Información, Edimburgo, Reino Unido, julio de 2010. (PDF; 3,2 MB)