Jerarquía de Volúmenes Contenedores

Definición

Una jerarquía de volúmenes contenedores es una estructura de árboles sobre un conjunto de objetos geométricos. Todos los objetos geométricos están envueltos en un volumen que forma los nodos hoja del árbol. Estos nodos luego son agrupados en pequeños conjuntos y envueltos en volúmenes más grandes. Éstos, a su vez, son también agrupados y envueltos en volúmenes contenedores más grandes de forma recursiva, resultando en una estructura de árbol con un único volumen contenedor en el tope del árbol.


Razón de Uso de una Jerarquía


Envolver a los objetos en volúmenes contenedores y realizar pruebas de colisiones en los volúmenes contenedores antes de probar las geometría contenidas en ellos simplifica las pruebas y puede resultar en mejoras significativas del desempeño, es útil crear una jerarquía organizada en forma de árbol para no tener que recorrer todos los volúmenes contenedores en busca de un objeto particular y evitar la búsqueda O(n)  de un arreglo o una lista enlazada.

Arreglando los volúmenes contenedores en una jerarquía en forma de árbol, la complejidad en tiempo de la búsqueda puede ser reducida a un orden logarítmico. Usando esta jerarquía, durante la detección de colisiones, los hijos no tienen que ser examinados si sus volúmenes padre no son intersectados (por un rayo o una detección de colisión, por ejemplo).

Consideraciones de Diseño para una Jerarquía de Volúmenes Contenedores 


Para lograr una implementación eficiente se tienen dos objetivos posiblemente contrarios a considerar. Por una parte, es deseable usar volúmenes contenedores con una forma geométrica simple y por otra es también deseable usar volúmenes contenedores cuya forma geométrica corresponda cercanamente a los objetos que contienen .

Usando volúmenes de formas geométricas simples se tiene la ventaja que se necesita poca memoria para almacenarlos y los cálculos de distancia e intersección son simples e inmediatos. Uno de los volúmenes contenedores más comúnmente usados es el volumen contenedor mínimo alineado a un eje. El volumen contenedor mínimo alineado a un eje.

El volumen contenedor mínimo alineado a un eje es su volumen contenedor mínimo (el volumen de menor área, perímetro o unidades de volumen posible que contenga todos los puntos de la geometría) sujeto además a la limitación que las aristas del volumen sean paralelas a los ejes de coordenadas cartesianas. Hallar un volumen contenedor mínimo alineado a un eje (en dos o tres dimensiones) es computacionalmente más económico que hallar un volumen contenedor mínimo de alineación arbitraria.

El volumen mínimo contenedor alineado a un eje es fácil de calcular, necesita poca memoria y los tests de intersección con él fáciles de implementar y extremadamente rápidos.

Hay varias propiedades deseables para una jerarquía de volúmenes contenedores que deben ser tomadas en consideración cuando se implementa uno para una aplicación particular:

* A medida que el nivel de los nodos contenedores aumente en el árbol la geometría que contienen debe estar más próxima espacialmente.

* Cada nodo en la jerarquía de volumen contenedor debe ser de volumen mínimo (no de perímetro mínimo).

* La suma de todos los volúmenes contenedores debe ser mínima.

* La poda de objetos cerca de la raíz del árbol de volúmenes contenedores elimina más objetos de los tests de evaluación de colisión.

* El volumen solapado por nodos hermanos debe ser mínimo.

* La jerarquía de voúmenes contenedores debe ser balanceada con respecto a su estructura de nodos y su contenido. El balanceo permite la mayor poda posible de la jerarquía de volúmenes contenedores.

Un árbol binario es jerarquía de volúmenes contenedores más comúmente usada.

Inserción de Nodos en una Jerarquía de Volúmenes Contenedores

Hay 3 métodos de construccción de jerarquías de volúmenes contenedores, los métodos bottom-up y top-down, que son usados para la construcción de jerarquías off-line (no en tiempo real) y el método de inserción (que es usado en tiempo real).

Método top-down

Se particiona el conjunto de entrada en dos o más subconjuntos usando el volumen contenedor deseado y se continua recursivamente hasta que se llega a contener una única primitiva en cada volumen. El método de construcción top-down es el más fácil de implementar y popular, pero no resulta en los mejores árboles de contención.

Método bottom-up

Se empieza con el conjunto de entrada como hojas en el árbol y se agrupan dos o más para formar un nuevo nodo interno y procede recursivamente hasta que toda la escena queda contenida en un mismo nodo, que corresponde a la raíz del árbol. Los métodos bottom-up son más difíciles de implementar pero resultan en mejores árboles de contención.

Método de Inserción

Se inserta un nodo a la vez, empezando de un árbol vacío. La locación de inserción se elije buscando aquello que cause al árbol crecer lo mínimo posible en base a un métrica de costo. Los métodos de inserción son considerados métodos online, ya que no requieren que todas las primitivas estén disponibles antes que la construcción del árbol empiece y permiten así que las actualizaciones sean realizadas en tiempo de ejecución.