Jerarquía de intervalos delimitadores

Una jerarquía de intervalos delimitadores ( BIH ) es una estructura de datos de partición similar a la de las jerarquías de volúmenes delimitadores 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 resultar especialmente útiles para escenas dinámicas.

El BIH se presentó por primera vez bajo el nombre de SKD-Trees, ^[1] presentado por Ooi et al., y BoxTrees, ^[2] inventado independientemente por Zachmann.

Las jerarquías de intervalos delimitadores (BIH) presentan muchas de las propiedades de las jerarquías de volúmenes delimitadores (BVH) y de los árboles kd . Mientras que la construcción y el almacenamiento de BIH son comparables a los de BVH, el recorrido de BIH se asemeja al de los árboles kd . Además, las BIH también son árboles binarios al igual que los árboles kd (y de hecho su superconjunto, los árboles BSP ). Finalmente, las BIH están alineadas con los ejes, al igual que sus antecesores. Aunque debería ser posible una implementación más general no alineada con los ejes de la BIH (similar al árbol BSP, que utiliza planos no alineados), casi con certeza sería menos deseable debido a la disminución de la estabilidad numérica y al aumento de la complejidad del recorrido de rayos.

La característica clave del BIH es el almacenamiento de 2 planos por nodo (a diferencia de 1 para el árbol kd y 6 para una jerarquía de cuadros delimitadores alineados con el eje ), lo que permite superponer hijos (como un BVH), pero al mismo tiempo 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 utilizar únicamente la estructura de datos BIH para la fase de construcción, pero recorrer el árbol de la misma forma que lo hace una jerarquía de cuadros delimitadores alineados con ejes tradicional. Esto permite realizar algunas optimizaciones de velocidad simples para grandes haces de rayos ^[3] mientras se mantiene bajo el uso de memoria / caché .

Algunos atributos generales de las jerarquías de intervalos delimitadores (y técnicas relacionadas con BIH) como se describe en ^[4] son:

• Tiempos de construcción muy rápidos
• Bajo consumo de memoria
• Travesía sencilla y rápida
• Algoritmos de construcción y recorrido muy sencillos
• Alta precisión numérica durante la construcción y el recorrido.
• Estructura de árbol más plana (profundidad de árbol reducida) en comparación con los árboles kd

Para construir cualquier estructura de partición espacial se suele utilizar algún tipo de heurística . Para ello, la heurística del área de superficie, que se utiliza habitualmente en muchos esquemas de partición, es un posible candidato. Otra heurística más simple es la heurística "global" ^[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 general de construcción para un BIH:

• Calcular el cuadro delimitador de la escena
• Utilice una heurística para elegir un eje y un candidato a plano dividido perpendicular a este eje
• Ordena los objetos del hijo izquierdo o derecho (exclusivamente) según el cuadro delimitador del objeto (ten en cuenta que los objetos que intersecan el plano dividido pueden ordenarse por su superposición con los volúmenes del hijo o 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)
• Almacene 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.

Posibles heurísticas para la búsqueda de candidatos en el plano dividido:

• Clásico: seleccione 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 izquierdista que, a menudo, es desafortunado para el trazado de rayos)
• Heurística global: elige el plano de división según un criterio global, en forma de una 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 al plano dividido, luego elija el que tenga los costos más bajos (se afirma que es óptimo, aunque la función de costo plantea demandas inusuales para probar la fórmula, que no se pueden cumplir en la vida real. También es una heurística excepcionalmente lenta para evaluar)

La fase de recorrido se parece mucho a un recorrido de árbol kd: hay que distinguir cuatro casos simples, donde el rayo

• simplemente intersecta al niño izquierdo
• simplemente se cruza con el niño correcto
• intersecta a ambos niños
• no interseca a ninguno de los hijos (el único caso no posible en un recorrido kd)

Para el tercer caso, dependiendo de la dirección del rayo (negativa o positiva) del componente (x, y o z) que es igual al eje dividido del nodo actual, el recorrido continúa primero con el hijo izquierdo (dirección positiva) o derecho (dirección negativa) y el otro se empuja hacia una pila para un recorrido potencial diferido.

El recorrido continúa hasta que se encuentra un nodo de hoja. Después de intersecar los objetos en la hoja, se extrae de la pila el siguiente elemento del recorrido. Si la pila está vacía, se devuelve la intersección más cercana de todas las hojas perforadas. Si el elemento extraído está completamente más allá de la intersección más cercana actual, se omite su recorrido.

También es posible añadir un quinto caso de recorrido, 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. El manejo de este caso durante la fase de recorrido es simple, ya que el rayo

• simplemente interseca al único hijo del nodo actual o
• no intersecta nada

Todas las operaciones durante la construcción/ordenación de la jerarquía de los triángulos son operaciones de mínimo/máximo y comparaciones. Por lo tanto, no es necesario realizar ningún recorte de triángulos como sucede con los árboles kd, lo que puede convertirse en un problema para los triángulos que apenas intersecan un nodo. Incluso si la implementación de kd está escrita 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 del rayo con el objeto que no se detecta.

En lugar de utilizar dos planos por nodo para separar la geometría, también es posible utilizar cualquier número de planos para crear un BIH n-ario o utilizar múltiples planos en un BIH binario estándar (uno y cuatro planos por nodo ya se propusieron en ^[4] y luego se evaluaron adecuadamente en ^[5] ) para lograr una mejor separación de objetos.

• Implementaciones BIH: Javascript, C++.