Algoritmos para colisiones de boundings

Colisión Rectángulo-Rectángulo (Bounding quad)

Este caso sugiere un par de métodos para la detección basados en algoritmos anteriores y algunos nuevos. Para el caso de los rectángulos alineados con los ejes es trivial, mientras que para rectángulos con rotaciones arbitrarias es ligeramente más complejo.

Una idea inicial para detectar las colisiones entre rectángulos es detectar si un punto de alguno de los dos rectángulos se encuentra dentro del otro, probablemente usando el algoritmo de “punto adentro” para rectángulos delineado en el primer tutorial de la serie. Aparentemente este método sería aplicable a rectángulos alineados con los ejes y a rectángulos con rotación arbitraria, pero después de una consideración más clara, existen contraejemplos contra este método.

Claramente ninguno de los puntos de los dos rectángulos está dentro del otro y también es claro que ambos rectángulos se están intersectando. La excepción no hace al algoritmo inútil, pero es mejor no usarlo en condiciones en que los desplazamientos de los rectángulos son comparables con sus lados y cuando la aplicación no evita superponer los rectángulos.

Un método más general y que no posee la falla que muestra la figura es verificar si el rectángulo proyectado sobre los ejes se intersecta. Si los segmentos de recta proyectados del rectángulo se superponen sobre todos los ejes, los rectángulos se intersecan.

Sea P1, P2, P3 y P4 los puntos de un rectángulo R alineado con los ejes, como se muestra en la figura, el algoritmo se resume en:

Eje x
Determinar si P1x de R1 se encuentra entre P1x de R2 y P2x de R2
Determinar si P2x de R1 se encuentra entre P1x de R2 y P2x de R2
Determinar si P1x de R2 se encuentra entre P1x de R1 y P2x de R1
Determinar si P2x de R2 se encuentra entre P1x de R1 y P2x de R1

Eje y
Determinar si P1y de R1 se encuentra entre P1y de R2 y P3y de R2
Determinar si P3y de R1 se encuentra entre P1y de R2 y P3y de R2
Determinar si P1y de R2 se encuentra entre P1y de R1 y P3y de R1
Determinar si P3y de R2 se encuentra entre P1y de R1 y P3y de R1

Si se cumple al menos una condición del eje x y simultáneamente una condición del eje y hay colisión, de lo contrario, un solo eje o ninguno revelan que no hay colisión. El algoritmo como se puede ver realiza 8 comparaciones con 2 preguntas cada una más la comparación final, por lo que se utilizan 17 comparaciones.

Para el caso del método no-optimizado el código se vería así:

struct Punto2d
{
	float x;
	float y;
};

struct Rectangulo2d
{
	Punto2d p1;
	Punto2d p2;
	Punto2d p3;
	Punto2d p4;
	Punto2d mov;
	float rot;
};

//Evalua el contacto entre dos circulos usando la distancia regular
bool evaluarContacto(Rectangulo2d *rect1, Rectangulo2d *rect2)
{
	//Se puede escoger arbitrariamente cualquier rectangulo
	 bool enX = false;
	 bool enY = false;

	 ////////X//////
	//Se comprueba si p1 rel primer rectangulo esta entre p1 y p2 del segundo en x
	if( ( (*rect1).p1.x + (*rect1).mov.x) <= (*rect2).p2.x + (*rect2).mov.x && (*rect1).p1.x + (*rect1).mov.x >= (*rect2).p1.x + (*rect2).mov.x)
	    enX = true;

	//Se comprueba si p2 rel primer rectangulo esta entre p1 y p2 del segundo en x
	if( ( (*rect1).p2.x + (*rect1).mov.x) <= (*rect2).p2.x + (*rect2).mov.x && (*rect1).p2.x + (*rect1).mov.x >= (*rect2).p1.x + (*rect2).mov.x)
	    enX = true;

	//Se comprueba si p1 rel segundo rectangulo esta entre p1 y p2 del primero en x
	if( ( (*rect2).p1.x + (*rect2).mov.x) <= (*rect1).p2.x + (*rect1).mov.x && (*rect2).p1.x + (*rect2).mov.x >= (*rect1).p1.x + (*rect1).mov.x)
	    enX = true;

	//Se comprueba si p2 rel segundo rectangulo esta entre p1 y p2 del primero en x
	if( ( (*rect2).p2.x + (*rect2).mov.x) <= (*rect1).p2.x + (*rect1).mov.x && (*rect2).p2.x + (*rect2).mov.x >= (*rect1).p1.x + (*rect1).mov.x)
	    enX = true;

	/////Y/////
	//Se comprueba si p1 rel primer rectangulo esta entre p1 y p4 del segundo en y
	if( ( (*rect1).p1.y + (*rect1).mov.y) <= (*rect2).p1.y + (*rect2).mov.y && (*rect1).p1.y + (*rect1).mov.y >= (*rect2).p4.y + (*rect2).mov.y)
	    enY = true;

	//Se comprueba si p4 rel primer rectangulo esta entre p1 y p4 del segundo en y
	if( ( (*rect1).p4.y + (*rect1).mov.y) <= (*rect2).p1.y + (*rect2).mov.y && (*rect1).p4.y + (*rect1).mov.y >= (*rect2).p4.y + (*rect2).mov.y)
	    enY = true;

	//Se comprueba si p4 rel segundo rectangulo esta entre p1 y p4 del primero en y
	if( ( (*rect2).p1.y + (*rect2).mov.y) <= (*rect1).p1.y + (*rect1).mov.y && (*rect2).p1.y + (*rect2).mov.y >= (*rect1).p4.y + (*rect1).mov.y)
	    enY = true;

	//Se comprueba si p4 rel segundo rectangulo esta entre p1 y p4 del primero en y
	if( ( (*rect2).p4.y + (*rect2).mov.y) <= (*rect1).p1.y + (*rect1).mov.y && (*rect2).p4.y + (*rect2).mov.y >= (*rect1).p4.y + (*rect1).mov.y)
	    enY = true;

	//Si esta al menos un punto en ambos lados hay colision
	if(enX && enY)
		return true;

	return false;
}

Para este caso los fuentes son:

download


Descargar:	RectanRectan.rar
Version:	0.1
Actualizado:	December 6, 2010
Tamaño:		55.4 KB

1 2 3 4

Compartir esta entrada

DiggReddit
  • Homerocracia

    Hola, interesante mu00e9todo, lo voy a probar. En la primer figura me parece que hay un error en la expresiu00f3n de d(c1-c2), ya que aparecen dos tu00e9rminos que corresponden a variables de X , pero no de Y [ d(c1-c2)=( (c1x-c2x)’1/2 + (c1x-c2x)’1/2) ‘ 1/2]. Saludos

  • http://black-byte.com Jotatsu

    Efectivamente se me habu00eda pasado el error, corregido.nnGracias.

  • Leo

    Hola los links no me funcionan

  • http://black-byte.com Jotatsu

    Click derecho y guardar como, ya los probe.

  • Caris

    es dificil entender esto pero quien me puede explicar ke es esto solo keria buscar diferentes formas de multiplicar

  • http://black-byte.com Jotatsu

    No entendu00ed -.-

  • Locopon

    u00bfcomo descargo los archivos?