Separating Axis Theorem

[Loover]

 Hi, hace un par de días implementé una algoritmo de colisión 2d por areas. Cuando digo areas me refiero a un polígono de 4 lados. Por ejemplo, si cojo una imagen, la roto en los 3 ejes me quedará proyectada en 2d un polígonos de 4 lados de forma arbitraria. Pues el algoritmo en cuestión verifica la colisión entre dos areas de ese tipo.
El algoritmo que hice hace lo siguiente:

1. Primero, y para optimizar, mira si hay colisión entre los dos rectángulos que engloban totalmente al polígono de 4 lados. Sino no hay colisión salimos devolviendo 0.

2. Comparamos, mirando si hay intersección, cada una de los lados del polígonos A con los 4 lados del polígono B (16 comparaciones en el peor caso). Si hay, salimos devolviendo 1.

3. Salimos devolviendo 0.

Lo malo de este algoritmo es que si una de las areas está completamente dentro de la otra, al no tocarse los lados, no hay colisión...  (nooo)

Ahora bien, he visto por ahí que existe un teorema llamado Separating Axis pero no encuentro información detallada como para entenderlo. Lo he visto en gamasutra y en otro sitios y nada. ¿Alguién puede explicarme como funciona? Seguramente será menos costoso que lo que yo hago. Aunque lo que no me queda claro es si es solo para rectángulos rotados en el eje z o si funciona para rectángulos rotados en cualquiera de los ejes (polígono de 4 lados arbitrario una vez proyectado).

Un saludo!

[Loover]

 Creo que ya entiendo como funciona... creo que es proyectando cada uno de los segmentos de A con el que le corresponda en B sobre el eje x y sobre el eje y. Si no estan solapados en ni sobre las x ni sobre las y los dos rectángulos no pueden estar solapados y ya podemos devolver 0... sino seguir comprobando y si se cumple en todos devolver 1. ¿Es así?

[tewe76]

 Tú te lo guisas, tú te lo comes. Me encanta  :D

Yo no tengo ni idea del tema, loover, pero te puedo cantar el cumpleaños feliz si quieres, jeje

(perdón por el offtopic, toi muy ocioso hoy)

[Loover]

 Jajajajaja, gracias  :D

PD: De todas formas creo que no es como decía... falla sobre papel

[jelorol]

 Buenas,

para ese caso "rebelde" de un polígono dentro de otro, ¿por qué no compruebas si el centro del rectángulo que contiene a uno de ellos se encuentra contenido en el rectángulo que engloba al otro (y viceversa)?
 

[Loover]

 Vale ya entiendo el separating axis, pero solo funciona cuando los rectángulos estan rotados en el eje z. No si estan rotados en todos los ejes. Así que para el otro caso tendré que verificar si cada vértice de A esta dentro de B. El típico algoritmo de trazar el rayo para saber si un punto está dentro de un polígono...

jelorol: porque al rotarlos tb en el eje "x" e "y" los rectangulos ya no son... rectángulos. Imagina que estas mirando una página de frente y que ahora progresivamente la vas torciendo... en la pantalla ves como se va tumbando y el problema ahora ya no es sobre rectángulos, sino sobre un polígono de 4 lados de forma arbitraria.

El separating axis viene muy bien cuando los rectangulos solo rotan en el eje Z, es muy rápida la verificación: http://www.gamasutra.com/features/19991018/Gomez_5.htm (Gracias Noti!)

[Thenend]

 No se si te entiendo bien porque no me aclaro si estas con colisiones en 2D o 3D, igual te digo alguna tontería pero a ver si te digo algo que te sirva.  :)

Si tenemos dos rectángulos que no se superponen (interseccionan o como quieras decirlo), tiene que haber una cara de uno de los dos que divida el espacio de forma que a cada lado quede un rectángulo (esto es así porque son polígonos convexos).

Calcular esto con polígonos rotados es un poco costoso. Pero si primero rotamos un rectángulo hasta dejarlo alineado con los ejes (y si lo trasladamos al origen (0,0) aún mejor), es facil comprobar si alguno de sus lados es un eje de separación para los dos rectángulos.

Después se hace lo mismo con el otro rectángulo, y si no se ha encontrado ningún eje de separación, quiere decir que se superponen.

Rotar los puntos de manera que uno de los rectángulos esté alineado con los ejes es sencillo. Hallas el ángulo que tienes que rotar por medio de un poco de trigonometría y luego aplicas a todos los puntos estas ecuaciones que igual ya conoces:

x' = x * cos A - y * sen A
y' = x * sen A + y * cos A

"A" es el ángulo, claro.

No se si me he explicado bien, a ver si te vale para algo.

[Loover]

 Son colisiones 2d (aunque el teorema este se puede extender a 3d) y tu método es totalmente válido, gracias! Solo que muy lento por lo de los senos y cosenos. Para rectángulos rotados en el eje z mirate el link que he puesto sobre el teorema del hilo. Lo digo por si tienes implementado lo otro y quieres que vaya más rápido.
El Separating Axis Theorem viene a ser algo así como:

1. Proyectar el punto más a la derecha de A (o el de más a la izquierda, da igual porque son rectángulos) y su centro sobre el eje x. Hacer lo mismo con B. A estos dos valores les llamamos "radios".
2. Halla la distancia entre el centro de A y el centro de B
3. Si  la distancia entre centros es menor que la suma de los radios => colisión en el eje x
4. Hacer lo mismo, pero esta vez proyectoando sobre el eje y
5. Si tanto en uno como en otro ha habido colisión => están solapapos los dos rectánguos

Pero solo funciona con rectángulos, no con polígonos de 4 lados cualesquiera.

Creo que es así, de todos modos lo tienes aquí:
http://www.gamasutra.com/features/19991018/Gomez_5.htm

Un saludo!

[Thenend]

 De nada.  :D

Bueno, desde que existen las tablas, los senos y cosenos no cuestan de generar mas que una multiplicación y un acceso a memoria. ¿no?

Con el de gamasutra me estoy liando un poco con esos nombres de variables tan lacónicos  :P  Igual mas tarde le hecho un ojo y lo descifro. Por lo que veo hace algo bastante parecido a lo que te he dicho, solo que desde un punto de vista mas "algebraico" y siendo un poco mas estricto con lo que es un cambio de base y esas cosas, el mio es bastante mas chavacano  :rolleyes: . Lo que está claro es que es bastante mas genérico que el que te comento. Lo de si irá mas rápido o no... pues no se. Ahora mismo tengo que hacer unas prácticas pero este finde intentaré comparar los dós métodos, que me ha entrado curiosidad... xD

[Grugnorr]

 Con el tema de las tablas precalculadas... investiga un poco el asunto por Google, algo he leido yo reciente de que en estos tiempos en que vivimos.... por temas de caché... no son mejores que usar directamente senos y cosenos... uno de los temas que me gustaría tener claro, si sacas algo en claro postéalo  :P  

[Thenend]

 Pues si te fias de Valve, en el Half Life 2 usan tablas.

No es que tenga el código fuente  :ph34r: , que es ilegal, me lo ha dicho un amigo que trabaja ahí  :P  

[Grugnorr]

  ;)  

[Thenend]

 He hecho una implementación del método ese que dije y lo he colgado aqui por si a alguno le interesa. He intentado optimizar lo mínimo para que quede mas claro qué es lo que hace, pero he puesto en los comentarios los atajos mas obvios.

Loover, si implementas el de gamasutra y no te importa compartirlo, te agradecería mucho que me lo pasaras. :-)

[Loover]

 Oye gracias! Me ha sido de mucha ayuda tu código. Al final he comprendido el separating axis theorem, pero no he sabido implementarlo. Hace lo mismo que tú, solo que sin necesidad de rotarlo, con proyecciones. No tengo muy fresca el álgebra así que creo que lo voy a dejar para más adelante. De momento he implementado esto fijándome en tu código:

http://galeon.com/loover/Collision.cpp

He intentado mejorarlo un poco, lo mismo te sirve alguna de las mejoras (aunque sé que algunas de ellas no las has puesto para que el código fuera mas legible):
- Para la rotación uso funciones y matrices de D3D (no creo que haya problemas en portarlo a OGL) así se podrá aprovechar el transform and lighting de las tarjetas y nos ahorramos los senos y cosenos (que lo haga D3D).
- En cuanto una comparación no se cumple, devuelvo false (tu devolvías el valor al final)
- Para calcular rápidamente los máximos y mínimos he usado una función que ya utilizaba para la colisión por segmentos, que calcula algo más rápido los valores max y min.

De todos modos, el código lo he hecho ahora mismo en una hora y se podrá mejorar un montón. A ver si logramos pulirlo un poco más.

Lo malo es que no podrás compilarlo directamente, pq estoy usando mi libreria 2d para las pruebas y si te paso todo el código va a ser un follonazo, así que solo he subido la parte de colisión por rectángulos orientados y he intentado comentarla lo mejor posible.

Gracias de nuevo tio, un saludo!

[Thenend]

 De nada, hombre.

Le he hechado un ojo a tu código y está muy bien, más elegante que el mio.  :D

Me alegro de haberte ayudado. Si hago algo con el "axis theorem" ya te avisaré.

Hasta pronto...