Black Byte

Algoritmos Basicos de Colisiones para Videojuegos

Poligono Convexo: Este test algo mas complicado que los anteriores, pero es mas general. Mediante este algoritmo se puede probar cuando un punto se encuentra dentro de un polígono convexo (polígono convexo es aquel que no tiene ángulos internos mayores a 180 grados).

Punto dentro de poligono convexo

Primero es necesario hallar un punto a sobre cada lado (el intermedio puede ser), para de esta manera encontrar el vector ap que va del punto a al punto p (el punto del que se necesita saber si esta adentro del poligono). Se encuentra tambien el vector N normal "interior" del lado y finalmente se hace el producto punto ap.N. Los casos son:

ap.N es + o 0 para cada lado: El punto esta adentro.
ap.N es - para algun lado: El punto esta afuera.

PLAIN TEXT

C++:

struct Punto2d
{
float x;
float y;
};
struct Poligono
{
list<Punto2d> puntos; //lista de los puntos del poligono
};
bool ladoCorrecto(Punto2d inicial,Punto2d terminal,Punto2d punto)
{
//se calcula el vector "lado" que va de un punto a otro
vector2d lado;
lado.x = inicial.x - terminal.x;
lado.y = inicial.y - terminal.y;
//la perpendicular del vector "lado"
vector2d perp;
perp.x = -lado.y; //las perpendiculares son vectores con componentes intercambiadas
perp.y = lado.x; // y una componente negativa
//se saca un punto "muestra" en la mitad del lado
lado.escalar(0.5f);
vector2d muestra;
muestra.x = inicial.x + lado.x ;
muestra.y = inicial.y + lado.y;
//se busca el vector entre el punto muestra y el punto supuestamente "adentro"
vector2d muestraPunto;
muestraPunto.x = muestra.x - punto.x;
muestraPunto.y = muestra.y - punto.y;
//Finalmente se pregunta si el producto punto perp.muestraPunto es negativo
if(perp.punto(muestraPunto) <0)
{
return false; // si con alguno falla, es que esta afuera
}
return true;
}
bool puntoDentroDePoly(Poligono *poly, Punto2d *punto)
{
list<Punto2d>::iterator iterPuntos = poly->puntos.begin();
bool estaAdentro = true; //En principio se supone que esta adentro
if(poly->puntos.size()> 2) //Bueno, es un poligono, no?
{
//El primer punto que se lee;
Punto2d puntoActual;
Punto2d puntoAnt = *iterPuntos;
iterPuntos++;
while(iterPuntos != poly->puntos.end() && estaAdentro)
{
puntoActual = *iterPuntos;
estaAdentro = ladoCorrecto(puntoAnt,puntoActual,*punto);
puntoAnt = puntoActual;
iterPuntos++;
}
//falta el ultimo con el primero
if(estaAdentro)// hay que comprobar que todavia se considere adentro
{
iterPuntos = poly->puntos.begin();
puntoActual = *iterPuntos;
estaAdentro = ladoCorrecto(puntoAnt,puntoActual ,*punto);
}
return estaAdentro;
}
return false; //eso no es ni siquiera un triangulo
}

PoligonoConvexo.zip( 515 descargas)

Por ahora estos test son útiles por ejemplo para hace seleccion sobre elementos del juego que se puedan encerrar en estas figuras y detectar cuando un cierto elemento del juego entra o sale de una zona demarcada por un circulo, un rectangulo alineado con los ejes o un poligono convexo.

Como nota final es importante ver que estos no son ni los únicos ni los mas eficientes test geométricos (pero con suerte son los mas faciles de entender). Ademas aún no se tiene en cuenta la variable tiempo y las colisiones entre los llamados "bounding", con lo que se puede realmente empezar a trabajar colisiones.

Informacion de Referencia:

Crashing into New Year, articulo de Gamasutra por Jeff Lander.

Paginas: 1 2 3

COMENTARIOS