Detección de Colisiones entre objetos  deformables

En los dos anteriores artículos hemos visto como poner en marcha una simulación e incluso como optimizarla en cuanto al error y a la velocidad utilizando el paso adaptativo. Ahora vamos a centrarnos en como detectar colisiones entre los objetos de nuestra escena. Queremos evitar interpenetración entre los objetos a toda costa pues es un fenómeno que se detectará visualmente por parte del usuario, que quedará probablemente muy decepcionado con las expectativas que tenía del juego. ¿Dónde se ha visto agua que traspase las paredes o dos pedazos de tela que se rebasan entre ellos?, hay que evitar efectos de este tipo....y sobretodo nunca subestimar al usuario que lo pilla todo !

Centrándonos en los objetos deformables tenemos que recordar que trabajamos con sistemas de partículas, es decir, cientos de particulillas con su masa y demás atributos interconectadas entre ellas mediante resortes (muelles). Parece fácil imaginar como modelar un pedazo de tela o un océano...bastará con crear una malla de resortes y partículas, pintarla adecuadamente en base a triángulos o colocarle texturas encima...y a simular!!!...¿pero y las colisiones?

Trabajando con deformables no tenemos como entidad mínima al objeto (Sistema de Partículas) sinó a la partícula en sí. Por lo tanto está claro que las colisiones se producirán entre partículas o entre una partícula y la cara de un objeto. Pueden darse casos críticos (singularidades) como por ejemplo dos caras triangulares formadas por 3 muelles y 3 partículas cada una, que chocan con sus centros y sin ninguna partícula implicada en la colisión....de momento vamos a lo "normal" y ya analizaremos los casos raros más adelante.

Vamos a lo ideal pués...

Vamos a suponer que nuestro objeto está formado a partir de caras triangulares formadas por 3 muelles / 3 partículas cada una. Es lo más recomendable dada la flexibilidad de los triángulos. Recordad que:

• Los triángulos siempre residen en un único plano, sin pliegues. Sus 3 vértices son coplanares.
• Los triángulos se procesan a velocidad de vértigo por los pipeline's gráficos, más si los aceleramos vía Hardware (aceleradoras 3D).

Ahí tenemos a una partícula (bolita negra) que va a chocar con un plano (línea recta negra). Veamos que ocurre en cada una de las 3 situaciones numeradas:

1. Estamos en un estadio intermedio de la animación. Hemos llegado a un tiempo de simulación de valor T0 y nos disponemos a iterar de nuevo. Aún no sabemos que la colisión es inminente.
2. Hemos iterado el sistema usando un paso de valor IncT y ooopsss!!!!...resulta que observamos que estamos literalmente metidos dentro de otro objeto!!!...ha habido interpenetración y eso tiene que evitarse a toda costa.
3. La solución. Volvemos al estado 1, del que habiamos hecho cópia, e iteramos de nuevo pero usando la mitad del paso, es decir IncT / 2. Entonces observamos de nuevo si hay o no interpenetración. Si es así, volveremos a 1 de nuevo y usaremos IncT / 4 y así sucesivamente; sinó verificaremos que la distancia entre la partícula y el plano sea o no inferior o igual a una determinada Epsilon (la figura la muestra). Si la distancia hasta el plano cumple ese requisito entonces podemos afirmar que SI, acabamos de detectar una colisión!

Obviamente si se trabaja en "tiempo real" no se dibuja hasta que se ha detectado la colisión....sinó el usario verá el sistema oscilando hacia adelante y hacia detrás hasta estabilizarse.

¿Queda claro el Backtracking?

Cálculo de distancias

Sólo queda saber como calcular la distancia de nuestra partícula al plano o cara. Aqui veremos que la cosa es bastante sencilla aparentemente aunque se plantea un pequeño problema.

La distancia de un punto a un plano (recordad que nuestra partícula tiene una posición 3D en el espacio y por tanto puede considerarse como un punto) es muy fácil de evaluar:

Considerando el plano de la primera línea de la figura (es el plano en el que reside la cara-triángulo), podemos encontrar la distancia d de un punto ( X1, Y1, Z1) al plano tal y cómo se indica. Esta distancia d será la que contrastaremos con nuestra Epsilon.

El problema es distinguir entre distancias positivas y negativas, es decir, mientras estamos fuera y nos vamos acercando no hay problema pero ¿como discernimos que ha habido interpenetración a partir de la distancia del punto al plano?, ¿cómo sabemos si es negativa o positiva?

Os puedo decir que hay varios artículos publicados por prestigiosos doctores en relación a la posible manera de solventar este problema. Nosotros seremos algo más humildes y dejaremos de lado las complejas eculubraciones para ir a lo práctico. No reinventaremos la rueda sinó que reutilizaremos material y a eso voy ahora!

R.A.P.I.D. de Stefan Gottschalk

RAPID es una librería "freeware" de Stefan Gottschalk para la detección de colisiones entre triángulos. Funciona asombrosamente rápido y es una opción perfecta para los no iniciados en el tema. Sabed que la detección de colisiones es un tema de investigación abierto y no resuelto completamente.

Lo que os sugiero es que implementeis el Backtracking en vuestro sistema utilizando una libreria como RAPID o similar para la detección entre triángulos. Es una buena opción de despegue y para cualquiera que haya programado algunas líneas de código es muy sencilla de aplicar. Incluye un TXT de documentación sobre el úso de la librería que tendreis que leer en un rato para no liaros después....no nos pasemos de autodidactas!!!....8)

Podeis encontrar la libreria aqui.

Optimización: "Bounding Boxes"

Ya para acabar mencionar un preproceso que podemos aplicar a la detección para aligerar los cálculos y, como siempre, acelerar el sistema global. Se trata de utilizar las "archiconocidas Bounding Boxes" o cajas envolventes para cada uno de nuestros sistemas de partículas (objetos de la animación).

Podemos definir un cubo o una esfera que englobe completamente a cada uno de nuestros objetos. Para detectar colisiones lo primero que haremos será verificar colisiones entre estos cubos o esferas. Si no las hay nos olvidamos pero en caso contrario pasaremos a un nivel de detalle más profundo con el Backtracking.

Podemos evaluar cual es la caja envolvente de cada objeto observando cuales son sus valors máximos y mínimos de XYZ. En el caso de ser rígidos, el envolvente no variará nunca pero si son deformables, que es nuestro caso en principio, puede ser que al irse produciendo deformaciones tengamos que ir recalculando la caja. En la figura podéis ver en que consiste el proceso general:

En la figura se ilustra un posible caso. Detectamos colisión entre las cajas y como no sabemos si también la hay entre objetos tendremos que aplicar Backtracking aunque realmente no es necesario. De todas formas habrá muchas iteraciones en las que ni tan sólo las cajas intersectarán y no será necesaria la aplicación de librerias como RAPID.

Las condiciones a evaluar entre las cajas de dos objetos cualesquiera para la detección son obvias:

...dónde los valores que véis en las condiciones se corresponden a las fronteras que definen a las cajas. Si sólo una de estas condiciones se cumple entre dos cajas podéis asegurar que no colisionan entre ellas. A este test se le conoce como el de MinMax. En el caso de envolventes esféricos tan sólo hay que verificar que la distancia entre los centros de las dos esferas sea mayor que la suma de los dos radios....¿lo véis no?

Creo que de momento ya teneis bastante información como para iros divirtiendo un poco...en el siguiente número os comentaré el módulo de respuesta a las colisiones (una vez detectadas que hacer con el sistema) así como algunas singularidades que se pueden producir en la detección.
 
 

ÚLTIMA REVISIÓN EN JULIO DE 1999