Una jerarquía de intervalo delimitador ( BIH ) es una estructura de datos de partición similar a la de las jerarquías de volumen delimitador o árboles kd . Las jerarquías de intervalos delimitadores se pueden utilizar en el trazado de rayos de alto rendimiento (o en tiempo real) y pueden ser especialmente útiles para escenas dinámicas.
El BIH se presentó por primera vez con el nombre de SKD-Trees, [1] presentado por Ooi et al., Y BoxTrees, [2] inventado independientemente por Zachmann.
Descripción general
Las jerarquías de intervalo delimitador (BIH) exhiben muchas de las propiedades tanto de las jerarquías de volumen delimitador (BVH) como de los árboles kd . Mientras que la construcción y el almacenamiento de BIH es comparable a la de BVH, el recorrido de BIH se asemeja al de los árboles kd . Además, BIH también son árboles binarios como los árboles kd (y de hecho su superconjunto, árboles BSP ). Finalmente, BIH están alineados con el eje al igual que sus antepasados. Aunque debería ser posible una implementación más general no alineada con el eje del BIH (similar al árbol BSP, que usa planos no alineados), es casi seguro que sería menos deseable debido a la disminución de la estabilidad numérica y un aumento en la complejidad de los rayos. el recorrido.
La característica clave de la BIH es el almacenamiento de 2 planos por nodo (en contraposición a 1 para el árbol kd y 6 para una jerarquía de cuadros delimitadores alineados con el eje ), lo que permite la superposición de hijos (como un BVH), pero al mismo tiempo. tiempo que presenta un orden en los hijos a lo largo de una dimensión / eje (como es el caso de los árboles kd).
También es posible usar la estructura de datos BIH para la fase de construcción, pero atravesar el árbol de la manera en que lo hace una jerarquía tradicional de cuadros delimitadores alineados con el eje. Esto permite algunas optimizaciones de aceleración simples para paquetes de rayos grandes [3] mientras mantiene bajo el uso de memoria / caché .
Algunos atributos generales de las jerarquías de intervalo delimitador (y técnicas relacionadas con BIH) como se describe en [4] son:
- Tiempos de construcción muy rápidos
- Huella de memoria reducida
- Travesía simple y rápida
- Algoritmos de construcción y recorrido muy simples
- Alta precisión numérica durante la construcción y el recorrido.
- Estructura de árbol más plana (menor profundidad del árbol) en comparación con los árboles kd
Operaciones
Construcción
Para construir cualquier estructura de partición de espacio, se suele utilizar alguna forma de heurística . Para esto, la heurística del área de superficie , comúnmente utilizada con muchos esquemas de partición, es un posible candidato. Otra heurística más simplista es la heurística "global" descrita por [4] que solo requiere un cuadro delimitador alineado con el eje , en lugar del conjunto completo de primitivas, lo que la hace mucho más adecuada para una construcción rápida.
El esquema de construcción general para un BIH:
- calcular el cuadro delimitador de la escena
- use una heurística para elegir un eje y un candidato de plano dividido perpendicular a este eje
- ordenar los objetos al hijo izquierdo o derecho (exclusivamente) dependiendo del cuadro delimitador del objeto (tenga en cuenta que los objetos que se cruzan con el plano de división pueden ordenarse por su superposición con los volúmenes secundarios o por cualquier otra heurística)
- calcular el valor límite máximo de todos los objetos de la izquierda y el valor límite mínimo de los de la derecha para ese eje (se puede combinar con el paso anterior para algunas heurísticas)
- almacenar estos 2 valores junto con 2 bits que codifican el eje dividido en un nuevo nodo
- continúe con el paso 2 para los niños
Heurísticas potenciales para la búsqueda de candidatos de plano dividido:
- Clásico: elija el eje más largo y el centro del cuadro delimitador del nodo en ese eje
- Clásico: elija el eje más largo y un plano dividido a través de la mediana de los objetos (da como resultado un árbol de izquierda que a menudo es desafortunado para el trazado de rayos)
- Heurística global: elija el plano de división según un criterio global, en forma de cuadrícula regular (evita divisiones innecesarias y mantiene los volúmenes de los nodos lo más cúbicos posible)
- Heurística del área de superficie: calcule el área de superficie y el número de objetos para ambos niños, sobre el conjunto de todos los posibles candidatos de plano dividido, luego elija el que tenga los costos más bajos (se dice que es óptimo, aunque la función de costo plantea demandas inusuales para probar el fórmula, que no se puede cumplir en la vida real. también una heurística excepcionalmente lenta de evaluar)
Recorrido de rayos
La fase de recorrido se parece mucho a un recorrido de árbol kd: uno tiene que distinguir cuatro casos simples, donde el rayo
- simplemente se cruza con el niño izquierdo
- simplemente se cruza con el niño correcto
- se cruza con ambos niños
- no se cruza con ningún niño (el único caso no es posible en un recorrido kd)
Para el tercer caso, dependiendo de la dirección del rayo (negativa o positiva) del componente (x, yoz) que iguala el eje dividido del nodo actual, el recorrido continúa primero con la izquierda (dirección positiva) o la derecha (negativa dirección) hijo y el otro es empujado a una pila para atravesar el potencial diferido.
El recorrido continúa hasta que se encuentra un nodo hoja. Después de cruzar los objetos en la hoja, el siguiente elemento transversal se extrae de la pila. Si la pila está vacía, se devuelve la intersección más cercana de todas las hojas perforadas. Si el elemento emergente está completamente más allá de la intersección más cercana actual, se omite su recorrido.
También es posible agregar un quinto caso transversal, pero que también requiere una fase de construcción ligeramente complicada. Al intercambiar los significados del plano izquierdo y derecho de un nodo, es posible cortar el espacio vacío en ambos lados de un nodo. Esto requiere un bit adicional que debe almacenarse en el nodo para detectar este caso especial durante el recorrido. Manejar este caso durante la fase transversal es simple, ya que el rayo
- simplemente se cruza con el hijo único del nodo actual o
- no se cruza con nada
Propiedades
Estabilidad numérica
Todas las operaciones durante la construcción / clasificación jerárquica de los triángulos son operaciones mínimas / máximas y comparaciones. Por lo tanto, no se debe hacer ningún recorte de triángulos como es el caso de los árboles kd y que puede convertirse en un problema para los triángulos que se cruzan ligeramente con un nodo. Incluso si la implementación de kd se escribe con cuidado, los errores numéricos pueden dar como resultado una intersección no detectada y, por lo tanto, errores de representación (agujeros en la geometría) debido a la intersección de rayo-objeto perdida.
Extensiones
En lugar de usar dos planos por nodo para separar la geometría, también es posible usar cualquier número de planos para crear una BIH n-aria o usar varios planos en una BIH binaria estándar (ya se propusieron uno y cuatro planos por nodo en [4 ] y luego evaluado adecuadamente en [5] ) para lograr una mejor separación de objetos.
Ver también
Referencias
Documentos
- ^ Nam, Beomseok; Sussman, Alan. Un estudio comparativo de técnicas de indexación espacial para conjuntos de datos científicos multidimensionales
- ^ Zachmann, Gabriel. Detección de colisión mínima jerárquica Archivado el 10 de febrero de 2007 en la Wayback Machine.
- ^ Wald, Ingo; Boulos, Solomon; Shirley, Peter (2007). Trazado de rayos de escenas deformables mediante jerarquías de volumen de límite dinámico
- ^ a b c Wächter, Carsten; Keller, Alexander (2006). Trazado de rayos instantáneo: la jerarquía del intervalo delimitador
- ^ Wächter, Carsten (2008). Simulación de transporte ligero cuasi-Monte Carlo mediante trazado de rayos eficiente
enlaces externos
- Implementaciones BIH: Javascript , C ++ .