Una jerarquía de volumen delimitador ( BVH ) es una estructura de árbol sobre un conjunto de objetos geométricos . Todos los objetos geométricos, que forman los nodos de hoja del árbol, están envueltos en volúmenes delimitadores . Estos nodos se agrupan luego como conjuntos pequeños y se encierran dentro de volúmenes delimitadores más grandes. Estos, a su vez, también se agrupan y encierran dentro de otros volúmenes delimitadores más grandes de manera recursiva, lo que finalmente da como resultado una estructura de árbol con un solo volumen delimitador en la parte superior del árbol. Las jerarquías de volumen delimitador se utilizan para admitir varias operaciones en conjuntos de objetos geométricos de manera eficiente, como en la detección de colisiones y el trazado de rayos .
Aunque envolver objetos en volúmenes delimitadores y realizar pruebas de colisión sobre ellos antes de probar la geometría del objeto en sí simplifica las pruebas y puede dar como resultado mejoras significativas en el rendimiento, se sigue realizando la misma cantidad de pruebas por pares entre volúmenes delimitadores. Al organizar los volúmenes delimitadores en una jerarquía de volúmenes delimitadores, la complejidad temporal (la cantidad de pruebas realizadas) se puede reducir a logarítmica en la cantidad de objetos. Con una jerarquía de este tipo en su lugar, durante las pruebas de colisión, no es necesario examinar los volúmenes secundarios si sus volúmenes primarios no se intersecan (por ejemplo, si los volúmenes delimitadores de dos autos chocadores no se intersecan, no sería necesario verificar la colisión de los volúmenes delimitadores de los propios autos chocadores).
La elección del volumen delimitador está determinada por un equilibrio entre dos objetivos. Por un lado, nos gustaría utilizar volúmenes delimitadores que tengan una forma muy simple. Por lo tanto, solo necesitamos unos pocos bytes para almacenarlos, y las pruebas de intersección y los cálculos de distancia son simples y rápidos. Por otro lado, nos gustaría tener volúmenes delimitadores que se ajusten muy bien a los objetos de datos correspondientes. Uno de los volúmenes delimitadores más utilizados es un cuadro delimitador mínimo alineado con el eje . El cuadro delimitador mínimo alineado con el eje para un conjunto dado de objetos de datos es fácil de calcular, solo necesita unos pocos bytes de almacenamiento y las pruebas de intersección robustas son fáciles de implementar y extremadamente rápidas.
Hay varias propiedades deseadas para un BVH que deben tenerse en cuenta al diseñar uno para una aplicación específica: [1]
En términos de la estructura del árbol binario, se debe decidir qué grado (número de hijos) y altura se utilizarán en el árbol que representa el árbol binario. Un árbol de grado bajo tendrá una altura mayor, lo que aumenta el tiempo de recorrido de raíz a hoja. Por otro lado, se debe dedicar menos trabajo en cada nodo visitado para verificar si sus hijos se superponen. Lo opuesto se aplica a un árbol de grado alto: aunque el árbol tendrá una altura menor, se dedica más trabajo en cada nodo. En la práctica, los árboles binarios (grado = 2) son, con diferencia, los más comunes. Una de las principales razones es que los árboles binarios son más fáciles de construir. [2]
Hay tres categorías principales de métodos de construcción de árboles: de arriba hacia abajo, de abajo hacia arriba y métodos de inserción.
Los métodos descendentes proceden a dividir el conjunto de entrada en dos (o más) subconjuntos, acotándolos en el volumen delimitador elegido y luego continúan dividiendo (y delimitando) recursivamente hasta que cada subconjunto consista en un solo primitivo (se alcanzan los nodos de hoja). Los métodos descendentes son fáciles de implementar, rápidos de construir y, por lejos, los más populares, pero no dan como resultado los mejores árboles posibles en general.
Los métodos ascendentes comienzan con el conjunto de entrada como las hojas del árbol y luego agrupan dos (o más) de ellas para formar un nuevo nodo (interno), y proceden de la misma manera hasta que todo se haya agrupado bajo un solo nodo (la raíz del árbol). Los métodos ascendentes son más difíciles de implementar, pero es probable que produzcan mejores árboles en general. Algunos estudios recientes [3] indican que en el espacio de baja dimensión, la velocidad de construcción se puede mejorar en gran medida (lo que coincide o supera a los enfoques descendentes) al ordenar los objetos utilizando una curva que llena el espacio y aplicar una agrupación aproximada basada en este orden secuencial.
Tanto los métodos de arriba hacia abajo como los de abajo hacia arriba se consideran métodos fuera de línea , ya que ambos requieren que todos los primitivos estén disponibles antes de que comience la construcción. Los métodos de inserción construyen el árbol insertando un objeto a la vez, comenzando desde un árbol vacío. La ubicación de inserción debe elegirse de manera que haga que el árbol crezca lo menos posible de acuerdo con una métrica de costo. Los métodos de inserción se consideran métodos en línea, ya que no requieren que todos los primitivos estén disponibles antes de que comience la construcción y, por lo tanto, permiten que se realicen actualizaciones en tiempo de ejecución.
Los BVH se utilizan a menudo en el trazado de rayos para eliminar candidatos potenciales de intersección dentro de una escena omitiendo objetos geométricos ubicados en volúmenes delimitadores que no son intersectados por el rayo actual. [4] Además, como optimización de rendimiento común, cuando solo la intersección más cercana del rayo es de interés, como el algoritmo de recorrido de trazado de rayos está descendiendo nodos y varios nodos secundarios están intersectando el rayo, el algoritmo de recorrido considerará primero el volumen más cercano y, si encuentra una intersección allí, que es definitivamente más cercana que cualquier intersección posible en el segundo (u otro) volumen (es decir, los volúmenes no se superponen), puede ignorar de manera segura el segundo volumen. Se pueden emplear optimizaciones similares durante el recorrido BVH al descender a volúmenes secundarios del segundo volumen, para restringir aún más el espacio de búsqueda y, por lo tanto, reducir el tiempo de recorrido.
Además, se desarrollaron muchos métodos especializados para BVH, especialmente aquellos basados en AABB (cuadros delimitadores alineados con el eje), como construcción paralela, recorrido acelerado SIMD , buena heurística de división (SAH: la heurística de área de superficie se usa a menudo en el trazado de rayos), árboles anchos (los árboles 4-arios y 16-arios brindan algunos beneficios de rendimiento, tanto en el rendimiento de construcción como de consulta para escenas prácticas) y actualización rápida de la estructura (en aplicaciones en tiempo real, los objetos pueden moverse o deformarse espacialmente de manera relativamente lenta o estar quietos, y el mismo BVH se puede actualizar para que siga siendo válido sin hacer una reconstrucción completa desde cero).
Naturalmente, los BVH también admiten la inserción y eliminación de objetos sin una reconstrucción completa, pero el BVH resultante suele tener un peor rendimiento de consulta en comparación con la reconstrucción completa. Para resolver estos problemas (así como el hecho de que la actualización rápida de la estructura no es óptima), el nuevo BVH se podría construir de forma asincrónica en paralelo o sincrónica, después de detectar un cambio suficiente (la superposición de hojas es grande, la cantidad de inserciones y eliminaciones superó el umbral y otras heurísticas más refinadas).
Los BVH también se pueden combinar con métodos de gráficos de escena e instancias de geometría para reducir el uso de memoria, mejorar la actualización de la estructura y el rendimiento de reconstrucción completa, así como para guiar mejor la división de objetos o primitivas.