|
Esta semana estoy fuera de casa, de vacaciones con la familia. Me he llevado un portátil preparado para programar un poco, y el acceso que tengo a internet es bastante limitado. La combinación perfecta para que tenga ganas de trabajar un poco en algun algorítmo nuevo. Esta vez le ha tocado a una estructura de memoria llamada Bounding Interval Hierarchy . Hace tiempo que trabajo en un motor de render, donde pruebo cosas nuevas o cosas que se me ocurren. Y he decidido cambiar la jerarquía de objetos para que utilicen este nuevo sistema. Tradicionalmente, un raytracer guarda los triángulos en alguna especie de estructura geométrica que .acelere la búsqueda de objetos. Esto puede ser un grid uniforme, un bsp, un kd-tree,una jeraquía de volúmenes, etc. El grid uniforme es muy sencillo de usar y de calcular. Básicamente se basa en meter todos los polígonos en una cuadrícula 3D. Al ser la cuadricula de un tamaño fijo, lanzar un rayo se convierte en lo mismo que pintar una linea en 3D. La ventaja es su extrema sencillez, pero la desventaja es que si hay mucho espacio vacio, es muy costoso en memoria, y dependiendo de la escena, podemos tardar muchos saltos en encontrar objetos. Ademas, la estructura 3D de un voxel es matadora para la cache. Pero en la mayoría de las escenas reales, es de lo más rápido. Despues tenemos los bsps o los kd-trees . Esto se basa en ordenar la geometría en un "arbol binario" usando criterios geométricos. Basicamente seleccionamos un plano, y marcamos que es lo que está a la izquierda o a la derecha de ese plano. El kd-tree es una variante que en vez de guardar un plano cualquiera, indica si usamos el plano x, y ó z. En principio las búsquedas son más rapidas que el grid uniforme, pero el tiempo de construcción es más lento. Un problema es que muchos polígonos intersecan con el plano que elegimos para el corte. Dependiendo del uso que le demos, tendremos que partir el polígono, y esto suele aumentar considerablemente el tamaño. Además, si el núimero de poligonos es muy grande, necesitamos muchísimo tamaño en la pila para la creación recursiva. Se usa más en videojuegos, porque los mapas son estáticos y podemos hacer herramientas para "compilar" los bsps, y se puede reusar entre frames (donde aprovechamos que son muy rapidos de pintar). Los kd-trees se usan más cuando lo que guardamos son puntos, porque simplifica el buscar puntos cercanos al nuestro, y nos ahorramos el corte de poligonos. Otra gran desventaja es que para calcular el plano de corte ideal, normalmente tenemos que recorrer los hijos para sacar datos útiles que generen árboles bien balanceados, con lo que el tiempo de creación se dispara. Otra técnica son los BVH , ovolúmenes en jerarquía. Esto es tener un bounding box muy grande (o una esfera), y meter volúmenes más pequeños dentro, de tal forma que lo que este dentro, nunca tenga un tamaño más grande que el nodo padre. Asi, si nuestro rayo no colisiona con el nodo padre, tampoco lo hará con el nodo hijo. Son muy usados en física, para detectar colisiones. Nunca los he programado, asi que no puedo decir cual es su principal desventaja :) Yahora aparecen los BIH , una técnica que intenta combinar lo mejor de los BVH y de los kdtrees, Básicamente se basa en guardar no solo un plano de corte, si no un par de intervalos que nos indica cuanto ocupa la parte izq. y la derecha. Estos intervalos pueden solaparse, con lo que tendremos que recorrer los 2 nodos hijo, o puede que tenga un espacio vacío entre elllos, con lo que podemos descartar el rayo sin seguir recorriendo. La ventaja es que es muy rápido de calcular. En cada iteracción, aplicamos un qsort a la lista de candidatos en funcion de si están a la derecha o a la izquierda. Este array se puede reaprovechar en los nodos hijos, ya que realmente estamos acotando el rango de búsqueda (exactamente igual que el algoritmo de quicksort, que no necesita duplicar el array que ordena en cada iteracción, ya que sólo acotamos lospivotes left/right). Al ser muy rápido de calcular, podemos usarlo entre frame y frame aunque nuestra geometría sea dinámica.
El recorrido es igual que el de un kdtree, pero tenemos la ventaja que si el rayo se "cuela" entre los 2 intervalos, podemos terminar la búsqueda antes. En el paper original , podemos ver una comparativa de tiempos donde vemos el tiempo de creación y el de render. No siempre es más rápido en el recorrido, pero suele compensarlo con el tiempo de creación, con lo que el tiempo final suele ser menor, o al menos, no mucho peor.
|
Noticias 
