Algoritmos para colisiones de boundings

Existen varias formas de optimizar el algoritmo para realizar menos comparaciones, por ejemplo:

Si R1x > R2x

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

Si no

Eje x
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

Si R1y > R2y

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

Si no

Eje y
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 (algún Eje Y && algún Eje X): Colisión.

Para este caso se realizan en el peor de los casos 3 preguntas por eje y la comparación final, con un total de 7. En el mejor de los casos se realizan 2 preguntas por eje y la final, para un total de 5. Adicionalmente las preguntas de si el rectángulo tiene un lado X mas largo que el otro (R1y>R2y) o un lado Y (R1y>R2y) son pre calculables para rectángulos que no cambian de tamaño.

El código optimizado se vería así:

struct Punto2d
{
	float x;
	float y;
};

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

Rectangulo2d rectan1;
Rectangulo2d rectan2;

bool r1xBigger;
bool r1yBigger

….

	r1xBigger = abs(rectan2.p2.x - rectan2.p1.x)  > abs(rectan1.p2.x - rectan1.p1.x);
	r1yBigger = (abs(rectan2.p1.y - rectan2.p3.y)  > abs(rectan1.p1.y - rectan1.p3.y));

…
//Evalua el contacto entre dos circulos usando la distancia regular
bool evaluarContacto(Rectangulo2d *rect1, Rectangulo2d *rect2)
{
	 bool enX = false;
	 bool enY = false;

	enX = evaluarContactoX(rect1,rect2);
	enY = evaluarContactoY(rect1,rect2);

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

	return false;
}

bool evaluarContactoX(Rectangulo2d *rect1, Rectangulo2d *rect2)
{
	if( r1xBigger )
	{
		//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)
			return 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)
			return true;
		}
	else
	{
		//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)
			return 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)
			return true;
	}
	return false;

}

bool evaluarContactoY(Rectangulo2d *rect1, Rectangulo2d *rect2)
{
	if( r1yBigger )
	{
		//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)
			return 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)
			return true;
	}
	else
	{
		//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)
		   return 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)
			return true;
	}
	return false;
}

El código del ejemplo está en c++ para Visual Studio 2010, aunque no debería ser problema compilarlo en Visual Studio 2008. El código se ejecutó en Windows 7 y Xp.

download


Descargar:	RectanRectanOpt.rar
Version:	0.1
Actualizado:	December 6, 2010
Tamaño:		55.6 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?