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 alineada 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:
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:
Posibles heurísticas para la búsqueda de candidatos en el plano dividido:
La fase de recorrido se parece mucho a un recorrido de árbol kd: hay que distinguir cuatro casos simples, donde el rayo
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
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, 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.