Una jerarquía de volumen delimitador ( BVH ) es una estructura de árbol en un conjunto de objetos geométricos . Todos los objetos geométricos están envueltos en volúmenes delimitadores que forman los nodos de hojas del árbol. 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 forma 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 en ellos antes de probar la geometría del objeto en sí simplifica las pruebas y puede dar como resultado mejoras significativas en el rendimiento, todavía se realiza 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 del tiempo (el número de pruebas realizadas) se puede reducir a logarítmico en el número de objetos. Con tal jerarquía en su lugar, durante las pruebas de colisión, los volúmenes secundarios no tienen que ser examinados si sus volúmenes principales no se cruzan (por ejemplo, si los volúmenes delimitadores de dos autos chocadores no se cruzan, los volúmenes límite de los parachoques mismos no se cruzan). no es necesario comprobar si hay colisión).
Problemas de diseño de BVH
La elección del volumen delimitador está determinada por una compensación 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, necesita solo unos pocos bytes de almacenamiento y las pruebas de intersección sólidas 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]
- Los nodos contenidos en cualquier subárbol deben estar cerca unos de otros. Cuanto más abajo del árbol, más cerca deben estar los nodos entre sí.
- Cada nodo del BVH debe tener un volumen mínimo.
- La suma de todos los volúmenes delimitadores debe ser mínima.
- Se debe prestar mayor atención a los nodos cercanos a la raíz del BVH. La poda de un nodo cerca de la raíz del árbol elimina más objetos de una mayor consideración.
- El volumen de superposición de los nodos hermanos debe ser mínimo.
- El BVH debe estar equilibrado con respecto tanto a su estructura de nodo como a su contenido. El equilibrio permite podar la mayor cantidad posible de BVH siempre que no se atraviese una rama.
En términos de la estructura de BVH, se debe decidir qué grado (el número de niños) y altura usar en el árbol que representa a BVH. Un árbol de bajo grado será de mayor altura. Eso aumenta el tiempo de recorrido de raíz a hoja. Por otro lado, se debe gastar menos trabajo en cada nodo visitado para verificar si sus hijos se superponen. Lo contrario es válido para un árbol de alto grado: aunque el árbol será de menor altura, se gasta más trabajo en cada nodo. En la práctica, los árboles binarios (grado = 2) son, con mucho, los más comunes. Una de las principales razones es que los árboles binarios son más fáciles de construir. [2]
Construcción
Hay tres categorías principales de métodos de construcción de árboles: métodos de arriba hacia abajo, de abajo hacia arriba y de inserción.
Los métodos descendentes proceden dividiendo el conjunto de entrada en dos (o más) subconjuntos, delimitándolos en el volumen delimitador elegido, luego continúan particionando (y delimitando) de forma recursiva hasta que cada subconjunto consista en una sola primitiva (se alcanzan los nodos hoja). Los métodos descendentes son fáciles de implementar, rápidos de construir y, con mucho, los más populares, pero no dan como resultado los mejores árboles posibles en general.
Los métodos ascendentes comienzan con la entrada establecida como las hojas del árbol y luego agrupan dos (o más) de ellos para formar un nuevo nodo (interno), proceden de la misma manera hasta que todo se haya agrupado bajo un solo nodo (el raíz del árbol). Los métodos de abajo hacia arriba son más difíciles de implementar, pero es probable que produzcan mejores árboles en general. Algunos estudios recientes (por ejemplo, [3] ) indican que en un espacio de baja dimensión, la velocidad de construcción se puede mejorar en gran medida (lo que iguala o supera los enfoques de arriba hacia abajo) clasificando los objetos usando la curva de llenado de espacio y aplicando agrupaciones aproximadas basadas en esto. 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 todas las primitivas 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. Se debe elegir la ubicación de inserción 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 todas las primitivas estén disponibles antes de que comience la construcción y, por lo tanto, permiten que las actualizaciones se realicen en tiempo de ejecución.
Uso
Los BVH se utilizan a menudo en el trazado de rayos para eliminar posibles candidatos de intersección dentro de una escena al omitir los 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, ya que el algoritmo de recorrido de trazado de rayos son nodos descendentes y varios nodos secundarios se cruzan con el rayo, el algoritmo de recorrido considerará primero el volumen más cercano y si encuentra una intersección allí, que está definitivamente más cerca que cualquier posible intersección en el segundo (u otro) volumen (es decir, los volúmenes no se superponen), puede ignorar con seguridad el segundo volumen. Se pueden emplear optimizaciones similares durante el recorrido de BVH al descender a volúmenes secundarios del segundo volumen, para restringir más el espacio de búsqueda y así reducir el tiempo de recorrido.
Además, se desarrollaron muchos métodos especializados para BVH, especialmente los basados en AABB (cuadros delimitadores alineados con ejes), como construcción paralela, recorrido acelerado SIMD , buena heurística dividida (SAH: la heurística del área de superficie se usa a menudo en el trazado de rayos), árboles anchos (los árboles 4-ary y 16-ary proporcionan algunos beneficios de rendimiento, tanto en 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 con relativa lentitud o estar quietos, y mismo BVH se puede actualizar para que siga siendo válido sin hacer una reconstrucción completa desde cero).
Los BVH también admiten naturalmente la inserción y eliminación de objetos sin una reconstrucción completa, pero el BVH resultante suele tener un rendimiento de consulta peor en comparación con la reconstrucción completa. Para resolver estos problemas (además de que la actualización rápida de la estructura es subóptima), el nuevo BVH podría construirse de forma asíncrona en paralelo o sincrónicamente, después de que se detecte un cambio suficiente (la superposición de hojas es grande, el número de inserciones y extracciones cruzó el umbral, y otras heurísticas más refinadas).
Los BVH también se pueden combinar con métodos de gráficos de escena y creación de 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 guiar mejor la división de objetos o primitivos.
Ver también
Referencias
- ^ Christer Ericson, Detección de colisiones en tiempo real, páginas 236-237
- ^ Ericson, Christer. Detección de colisiones en tiempo real . pag. 238. ISBN 1-55860-732-3.
- ^ Y. Gu, Y. He, K. Fatahalian y G Blelloch. Construcción BVH eficiente a través de agrupaciones aglomerativas aproximadas . HPG 2013.
- ^ Johannes Günther, Stefan Popov, Hans-Peter Seidel y Philipp Slusallek, Realtime Ray Tracing en GPU con Packet Traversal basado en BVH