Download FUNCIONAMIENTO DE LOS ÁRBOLES BSP (Binary Space

FUNCIONAMIENTO
DE LOS ÁRBOLES BSP
(Binary Space
Partitioning)
Junio 1999
Pedro Pablo Gómez Martín
Marco Antonio Gómez Martín
Enrique Alonso Martín
Explicación árboles BSP
Árboles BSP
Los árboles BSP (Binary Space Partitioning) son unas estructuras recursivas que organizan los
polígonos del modelo de forma jerárquica respecto a su posición en el espacio. Hay muchas variedades de
árboles BSP, y algunas estructuras más complicadas que se basan en ellos. Se utilizan unas u otras en
función de la aplicación concreta que se les quiera dar. Aquí detallaremos la modalidad que hemos
utilizado nosotros.
CONSTRUCCIÓN DE UN ÁRBOL BSP
La construcción de un árbol BSP es un proceso sencillo. Inicialmente se parte del grupo de
polígonos que se quieren almacenar en el árbol. Para ello se dividen en tres grupos en función de la
relación de cada polígono con un plano. Así, tendremos un grupo de polígonos que quedará delante del
plano (en el lado en el que apunta su vector normal), otro grupo con los que queden detrás, y un último
grupo con los polígonos inscritos en el plano. En la raíz del árbol se almacena el plano (su ecuación), y
los polígonos inscritos en él. Recursivamente se obtienen cada uno de los dos hijos con los polígonos de
los otros grupos. La recursión termina cuando no quedan polígonos a ninguno de los dos lados.
Es habitual pensar, en un principio, que según esto, la recursión no terminará nunca, pues dado
un plano y los polígonos del modelo, siempre quedan polígonos a alguno de los lados, salvo que el
modelo sea excesivamente peculiar. Es importante darse cuenta que eso no influye para que la recursión
realmente termine, pues en cada paso recursivo vamos siempre quitando polígonos, por lo que en un nodo
intermedio del árbol no trataremos nunca con todos los polígonos del modelo, si no con los que hayan ido
quedando en el lado correspondiente de los planos almacenados en los nodos superiores.
Se ha dejado pasar por alto la posibilidad de que existan polígonos que corten al plano
seleccionado, con lo que el polígono no podrá ser incluido en ninguno de los tres grupos. En ese caso, el
polígono tendrá que ser "cortado" en dos mitades, de modo que cada una de ellas quede a un lado del
plano.
Nuestros polígonos siempre deben ser triángulos, por lo que dividir un polígono origina tres
nuevos polígonos, quedando dos en un lado, y uno en el otro. Puede darse el caso, no obstante, de que
solo se creen dos nuevos polígonos. Esto ocurre cuando uno de los vértices pertenece al plano.
La división del polígono no es demasiado complicada, aplicando conocimientos de geometría.
No obstante, a la hora de la implementación, hay que tener cuidado con lo que nosotros hemos
denominado "polígonos corruptos". Un polígono corrupto es aquel que posee un área nula, es decir que al
menos dos de sus vértices coinciden, o los tres vértices pertenecen a la misma recta. Éstos polígonos
aparecen por culpa de la discretización de los números reales cuando un polígono queda dividido en otros,
uno de ellos muy pequeño. Los polígonos corruptos estropean el correcto funcionamiento de las consultas
de colisiones sobre el árbol BSP, por lo que deben ser eliminados.
Explicación árboles BSP
La elección del plano en cada nodo del árbol no es una tarea trivial. Algunas modalidades de
árboles BSP eligen planos "al azar". Otra opción es coger planos a los que pertenece al menos un
polígono, que es la que utilizamos nosotros. Por lo tanto, se escoge cualquier polígono, se halla el plano
que lo contiene y se utilizar como plano separador para ese nodo del árbol.
Eligiendo siempre este tipo de planos, y obligándonos a no detener la recursión mientras queden
polígonos en alguno de los lados, nos aseguramos de que todos los polígonos del modelo inicial quedan
en algún nodo, inscritos a algún plano. Otras modalidades de árboles BSP no aseguran esto, pues detienen
la recursión antes para ahorrar espacio.
Elegir un plano u otro va a hacer variar la profundidad del árbol y el número de divisiones de los
polígonos. Interesan árboles poco profundos, para acelerar las búsquedas sobre ellos, y además que hagan
pocas divisiones de los polígonos para ahorrar espacio. Habitualmente una característica empeora cuando
la otra mejora. Nuestras aplicaciones no son críticas en espacio, pues los modelos no es excesivamente
grandes, y sí nos interesan búsquedas rápidas, para acelerar la búsqueda de colisiones. Por lo tanto,
necesitamos árboles de la menor profundidad posible.
Conseguir el árbol de menor profundidad es un problema NP-Completo, por lo que nos
conformamos con construir árboles que no sean demasiado malos. Durante la construcción del árbol, por
lo tanto, en vez de elegir un único polígono cada vez elegimos varios, y construímos el árbol con cada
uno de ellos, quedándonos con el que menor profundidad tenga. Esta técnica aumenta el tiempo de
construcción de los árboles BSP. Para evitar un tiempo excesivo de inicialización del programa pueden
construirse los árboles una única vez con una herramienta auxiliar, y luego almacenarlos en ficheros, de
donde los recogerá la aplicación, es decir “precalcular” el árbol.
BÚSQUEDA DE COLISIONES EN UN ÁRBOL BSP
Los árboles BSP pueden utilizarse para calcular colisiones. Cuando se quiere avanzar por un
mundo virtual de un punto a otro, hay que saber si hay alguna pared que nos lo impida. Para ello, se
utilizan los árboles BSP, que nos detectan si entre el segmento que une dos puntos hay algún polígono.
Ahora que sabemos la estructura de los árboles BSP nos plantearemos cómo averiguarlo.
Todos los polígonos del árbol BSP se encuentran en los nodos del árbol, inscritos en alguno de
sus planos, por lo que para que el segmento (también denominado "rayo") se cruce con algún polígono,
deberá cruzarse con algún plano.
La búsqueda de colisiones de un rayo dentro de un árbol BSP es un procedimiento recursivo, en
el que se van comparando las posiciones de los extremos del rayo respecto a los planos de los nodos. Así,
si los dos extremos están delante o detrás del plano, no habrá corte con él, por lo que se realiza la
búsqueda de colisiones de forma recursiva únicamente con el lado del plano en el que estén los extremos.
El caso interesante es cuando cada extremo está en un lado. Hay varios posibles finales:
• El rayo corta con algún polígono que está en el lado del origen.
• El rayo corta con algún polígono que está inscrito dentro del plano.
• El rayo corta con algún polígono que está en el lado del destino.
Como hay que indicar el primer polígono con el que se colisiona, habrá que empezar primero
mirando, recursivamente, si el rayo colisiona con algún polígono del lado del origen. Si es así, se
devuelve ese polígono sin hacer ninguna otra consulta.
Si no hay colisión, hay que mirar si el rayo atraviesa algún polígono inscrito en el plano. Para
ello, se halla el punto de corte entre el rayo y el plano, y se comprueba si el punto está dentro de alguno
de los polígonos inscritos en el plano. Esta consulta debe ser rápida para acelerar todo el proceso, por lo
que el algoritmo que lo realiza está especialmente optimizado, aunque no nos ocuparemos de él aquí. Sí
es interesante señalar, no obstante, que esa optimización hace que falle con los polígonos corruptos antes
citados, lo que hace especialmente importante su eliminación. Con los polígonos normales, sin embargo,
el algoritmo funciona a la perfección.
Pues bien, si el punto está dentro de alguno de los polígonos, se devuelve dicho polígono como
colisionado y se finaliza la recursión. Si no es así, se consulta las colisiones con el lado del plano donde
está el destino y se devuelve su resultado.
Se entenderá ahora la necesidad de que el árbol tenga la menor profundidad posible. Un árbol
muy profundo ocasionaría muchas llamadas recursivas en los casos en los que no se produjera ninguna
colisión, que es el caso más habitual, ralentizando toda la ejecución.
Explicación árboles BSP
BÚSQUEDA DE COLISIONES CON ESFERAS EN UN ÁRBOL BSP
La búsqueda de colisiones entre un rayo y un árbol BSP explicada es rápida y útil en muchos
casos. Sin embargo, hay veces en las que son ineficaces, si se quiere evitar el acercamiento excesivo a las
paredes por parte del usuario.
Todo lo explicado sobre árboles BSP lo aprendimos de documentos e información obtenida en
Internet, pero no encontramos nada que nos ayudara con nuestro nuevo problema, por lo que tuvimos que
desarrollar completamente la detección de colisiones con esferas. La idea es semejante a la de un rayo,
pero se complica, y ralentiza, en la detección de los cortes.
Ahora no tenemos un punto origen y otro destino que comparar con el plano de cada nodo, sino
una esfera, de la que queremos saber si colisiona con algún polígono. Lo que hacemos es hallar la
posición (y distancia) del centro de la esfera al plano. Si está a una distancia superior al radio de la esfera,
ésta no se cortará con el plano, por lo que no habrá colisión con ninguno de sus polígonos. Continuaremos
la recursión, por lo tanto, únicamente en el lado del plano en el que se encuentre el centro de la esfera.
Si el centro está más cerca, miramos no obstante si hay alguna colisión con algún polígono del
lado donde está el centro de la esfera. Si lo hay, devolvemos ese polígono. Si no, hay que hallar el círculo
de corte entre el plano y la esfera, y mirar si éste corta con alguno de los polígonos inscritos en el plano.
Para hallar dicho círculo, primero hay que calcular su centro. Éste será el punto de corte entre el
plano y un vector perpendicular a éste que pase por el centro de la esfera. Y el radio del círculo se puede
hallar fácilmente por el teorema de pitágoras, a partir del radio de la esfera y de la distancia del centro de
ésta al plano.
radio
esfera
Radio del círculo
distancia
Plano
La figura muestra la situación "de perfil". El plano es perpendicular a la hoja, y se corta con la
esfera representada. El radio del círculo de corte se obtiene usando el triángulo formado por el radio de la
esfera, la distancia del centro al plano, y el propio radio del círculo.
Una vez que hallamos las características del círculo, tenemos que averiguar si éste corta a algún
polígono. Si ocurre así, se devuelve el polígono. Si no, se realiza recursión sobre el lado del plano en el
que no está el centro de la esfera.
Averiguar si un polígono corta con un círculo no es tan sencillo, y también tuvimos que idearlo
nosotros. Hay varias posibles formas de que exista corte:
1
2
3
4
Explicación árboles BSP
En el primer caso, el centro del círculo está dentro del polígono, en el segundo, el polígono tiene
una arista que corta a la circunferencia por dos puntos, en el tercero el polígono tiene una arista (bueno,
son dos, pero es indiferente) que corta a la circunferencia en un único punto, y por último en el cuarto, el
polígono está completamente dentro del círculo. No se considera como colisión que el polígono tenga a
una arista tangente a la circunferencia.
Nuestro algoritmo de detección de colisiones va buscando alguno de esos casos, de modo que si
alguno de ellos se cumple, avisa de que se está produciendo la colisión. Se podría pensar que la
separación entre los casos segundo y tercero no es necesaria si detectamos el corte de una arista con la
circunferencia. Sin embargo, hallar la existencia o no de corte entre un segmento y una circunferencia no
es una tarea especialmente rápida, por lo que hacemos la división para utilizar otras técnicas más eficaces
para saber si se está dando cada uno de los casos.
Saber si se da la primera posible situación es sencillo, una ve z que tenemos el algoritmo para
averiguar si un punto está dentro de un polígono utilizado en la detección de colisión entre un rayo y un
árbol BSP. Bastará mirar si el centro del círculo está en el interior del polígono para comprobar si estamos
o no en este caso.
El segundo es más complicado. Hallar los cortes entre un segmento y una circunferencia es
relativamente complicado matemáticamente. Se nos ocurrió un método alternativo, al darnos cuenta de
que, como la circunferencia es cortada dos veces, la arista será cortada por alguno de sus diametros, en
particular por el diámetro perpendicular a la propia arista. Por lo tanto hallamos el segmento
perpendicular a la arista (que esté dentro del plano, pues todo esto se hace en tres dimensiones), que sea
además diámetro del círculo. Si hay corte entre los dos segmentos, el polígono cortará al circulo. Esta
técnica siempre detecta las colisiones del que hemos llamado tercer caso, de ahí que lo separáramos desde
el principio.
Los otros dos casos ya son más sencillos, y además pueden comprobarse simultáneamente si
buscamos algun vértice del polígono que esté dentro del circulo. Para averiguarlo, se halla la distancia
entre el centro del círculo y el vértice que se está estudiando, y si ésta es menor que el radio del círculo, el
vértice estará dentro.