Llevo todo el día buscado por google una función que realice una detección de colisión entre un triángulo y un círculo en un plano 2d:
// Point es un vector de 2 coordenadas (horizonta, vertical)
bool IsCircleToTriangleCollision (point posCircle, int radius, point v1, point v2, point v3)
Que lo que haga sea devolverme cierto si hay colisión entre un círculo de posición "circle" y radio "radius" y un triángulo de vértices "v1", "v2" y "v3". Y colisión me refiero a que se solapen, vamos, que no me vale que solo intersecten. Es decir, un triángulo dentro de un círculo o viceversa es colisión.
He encontrado muchas cosas, pero casi todas son colisiones entre rectángulos o entre polígonos o de círculo a círculo, colisiones todas ellas que ya tengo implementadas. Y tampoco encuentro código fuente.
Solo necesito "collision", no un vector que describa la "collision response".
Fijo que alguien me resuelve esta duda en un plisplas :)
Hoy estoy vago..
yo de matematicas se muy poco, pero.. ¿no puede reducir tu problema a colision de un segmento y un circulo?
por otra parte, seguramente puedes calcular el punto de un segmento que si trazas una linea de ese punto, al centro del circulo, ese trazo es perpendicular a la linea. Si ese punto ese segmento tiene una longitud infedior a r, entonces el segmento corta al circulo. No se si me he explicado bien.
lo que no se, es como calcular ese punto. Pero ese punto, otro punto cualquiera del segmento, y el centro del circulo, forman un triangulo rectangulo. Lo cual seguramente es una pista. Dadme una folio, un lapiz, una toballa, media bañera llena de agua caliente, una toballa, y dentro de media hora estare gritando EUREKA!
oops: no habia visto lo de que decias que no te vale como colision que solo intersecten. Joder.. si solo quieres saber si un trinagulo esta dentro de un criculo, solo compruebna si los vertices del triangulo estan dentro del circulo. el calculo de distancia es una eso de sqrt(abs(xi-xc)+abs(yi-yc)) que no me acuerdo como se llama.
Cita de: "Loover"Y colisión me refiero a que se solapen, vamos, que no me vale que solo intersecten. Es decir, un triángulo dentro de un círculo o viceversa es colisión.
Pues si lo que quieres saber si se solapa el triangulo dentro del circulo yo creo que con calcular las distancias de los vertices del triangulo respecto al centro de la circunferencia y comprobar que sean iguales o menores al radio bastaria. Si los 3 vertices son iguales o menores en distancia al centro es que el triangulo esta dentro del circulo.
Salu2...
Bueno, ideas, he visto varias por internet, lo que me serviría de veras es el código fuente en c++ de la función que os he puesto. Pero bueno, como os habeis tomado la molestia de escribir (gracias de veras), os respondo a ambos.
1) Sobre lo que comenta [EX3]:
CitarPues si lo que quieres saber si se solapa el triangulo dentro del circulo yo creo que con calcular las distancias de los vertices del triangulo respecto al centro de la circunferencia y comprobar que sean iguales o menores al radio bastaria. Si los 3 vertices son iguales o menores en distancia al centro es que el triangulo esta dentro del circulo.
Eso, no sé porque, es lo primero que se me ocurrió a mi también, pero es erroneo.. Con eso solo sabrás si los vértices están o no dentro del círculo. Mira la figura y verás por qué rápidamente:
(http://www.pixelartgames.com/temporal/ejemplo.PNG)
2) En cuanto a lo que comenta Tei:
Citar¿no puede reducir tu problema a colision de un segmento y un circulo?
No, así no sabría si el círculo está totalmente dentro del triángulo o al revés. Ya lo comenté en el post anterior.
Lo segundo que propones también lo había pensado yo, pero nuevamente no vale, porque si está dentro no hay intersección. Lo que se podría hacer es calcular el punto de ese segmento (que va del centro del círculo en dirección al centro del triángulo y de longitud la del radio) está dentro del triángulo: así sí funcionaria. Y la función para saber si un punto está dentro de un triángulo ya la tengo, fácil. Esa es la forma que yo había pensado... pero estoy seguro que todas estas chapuzas que se me ocurren a mi sobre el papel, se podrían hacer mil veces más rápido de otra forma.
(http://www.pixelartgames.com/temporal/ejemplo2.PNG)
Vamos, que no quiero reinventar la rueda, quiero un código fuente en c++ que lo haga de manera rápida y eficiente, sin preocuparme mucho cómo funciona. Si nadie da otra propuesta mejor o un link a función que ya lo haga pues lo implementaré de la menera que he puesto en el segundo dibujo. Pero me cuesta creer que no pueda encontrarlo en google... y eso que busco en inglés :P
que tal un triangle-sphere collision (http://www.gamedev.net/community/forums/topic.asp?topic_id=320071) ?
Yo suelo usar esta tabla (http://www.realtimerendering.com/int/) pero por desgracia cada dia los enlaces estan mas muertos.
Hmmm... Tres puntos que definen rectas dos a dos; tres inecuaciones que resuelven el lado "bueno" a partir del punto que no define su recta. Calculas si el centro del círculo está en el lado "bueno" de las tres inecuaciones y luego compruebas si intersectan o no.
Si están en el lado bueno y no intersectan, uno está dentro del otro, o viceversa.
¡Buena tabla Tamat! Hay algo de circle to triangle aquí: http://www.andrewaye.com/TgS%20MLE@COLLISION/TgS%20Collision%20-%20Circle-Triangle.cpp.html
Bastante lioso sin explicaciones, le echaré un vistazo con calma luego.
CitarHmmm... Tres puntos que definen rectas dos a dos; tres inecuaciones que resuelven el lado "bueno" a partir del punto que no define su recta. Calculas si el centro del círculo está en el lado "bueno" de las tres inecuaciones y luego compruebas si intersectan o no.
Si están en el lado bueno y no intersectan, uno está dentro del otro, o viceversa.
Inecuacinamelo en una función escrita en c++ :D, o funciones matemáticas, o un dibujito. Que el lenguaje castellano pa estas cosas es algo chungo.
Si la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.
Se asume que el lado positivo es el interior del triángulo, por ejemplo, tomando el orden de los vértices en el sentido de las agujas del reloj.
Es el mismo concepto que has programado mil veces en octrees, bsps y cualquier otro sistema de particionamiento convexo: lo que está a un lado (ej: el positivo) del separador puede estar dentro o no (hay que probar todos los separadores), pero lo que está al otro lado, está fuera seguro.
CitarSi la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.
Define "distancia". Supongo que te refieres al segmento con dirección de la normal de la cara del triángulo al centro del círculo. ¿Y cómo va a ser negativa?
¿Código fuente?
Cita de: "Loover"CitarSi la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.
Define "distancia". Supongo que te refieres al segmento con dirección de la normal de la cara del triángulo al centro del círculo. ¿Y cómo va a ser negativa?
¿Código fuente?
No me seas vago que poniendo "line circle intersection" te salen mil links en google :P
Si tu sustituyes un punto en la ecuación de una recta el valor resultante es positivo o negativo según a que lado estés. La distancia, es el valor absoluto de esa magnitud.
Ax + By - D = 0 (te suena a la ecuación del plano pero con Z=0?)
A,B es el vector que va del vértice de origen al vértice destino y D es el valor de Y en la recta cuando la prolongas hasta x=0.
Hay otras formas de representar las ecuaciones de una recta, aunque en este caso no te sirven, es para que entiendas:
x´= x1 + t * (x2-x1)
y´= y1 + t * (y2-y1)Llamamos "distancia" al valor de t (cuantas veces hay que multiplicar el vector de dirección para llegar al destino). Si ésta formula la aplicamos a la normal de la recta para llegar al centro del circulo, te sale la "distancia".
La fórmula a usar es la primera, que si te das cuenta A*x + B*Y es el Dot product que aparece en el código que has puesto, considerando A,B y X,Y como dos vectores (que lo son).
La distancia D de la fórmula la conviertes en cero si consideras que el vertice de inicio del lado del triángulo es el origen de coordenadas. Por tanto, si tanto al segundo vértice como al centro del círculo les restas el vértice de origen, te queda:
Cx * X2 + Cy * Y2 = 0
donde a todos esos términos le ha restado previamente x1,y1.
Supongo que ahora podrás entender mejor el código, si no, pregunta lo que sea.
Por cierto, me he saltado el tema de normalzaciones y demás para no complicarlo o termino escribiéndote de nuevo el código que has puesto o que encuentres por ahí :P
Cita de: "Loover"
Define "distancia". Supongo que te refieres al segmento con dirección de la normal de la cara del triángulo al centro del círculo. ¿Y cómo va a ser negativa?
Respondiéndote en una frase: si la normal apunta adentro del triángulo, la distancia te sale con signo contrario a si la normal apunta hacia fuera del triángulo.
Añado (ale 3 post seguidos) para que entiendas el signo mejor:
Si coges la normal de una arista del triángulo y la lanzas desde el centro del círculo, tarde o temprano chocará con la recta o se alejará en dirección contraria, dependiendo de a que lado hayas cogido la normal.
Cita de: "Loover"1) Sobre lo que comenta [EX3]:
CitarPues si lo que quieres saber si se solapa el triangulo dentro del circulo yo creo que con calcular las distancias de los vertices del triangulo respecto al centro de la circunferencia y comprobar que sean iguales o menores al radio bastaria. Si los 3 vertices son iguales o menores en distancia al centro es que el triangulo esta dentro del circulo.
Eso, no sé porque, es lo primero que se me ocurrió a mi también, pero es erroneo.. Con eso solo sabrás si los vértices están o no dentro del círculo. Mira la figura y verás por qué rápidamente:
(http://www.pixelartgames.com/temporal/ejemplo.PNG)
Quizas no me explique bien:
(http://img239.imageshack.us/img239/4690/solapadoob2.jpg)
Si mal no entendi tu buscas lo primero:
Colision = (Dist(A, O) =< R) && (Dist(B, O) =< R) && (Dist(C, O) =< R)En cuanto uno de los vectores este fuera de la circunferencia su distancia al centro de esta sera superior a su radio. Que no sea el metodo mas optimo no te lo discuto :P
Salu2...
EDITO, disculpar pero hoy voy un poco lento de neuronas, no duermo mucho estos ultimos dias y ya me esta pasando factura :P Mi codigo oviamente solo vale para triangulos mas pequeños que el circulo, pero no para el caso inverso que es el que muestras arriba.
enum {
CLOCKWISE = -1,
COLINEAR = 0,
COUNTERCLOCKWISE = 1
};
const float Epsilon = 0.0001f;
struct Vector2 {
const static Vector2 Zero;
Vector2() { }
Vector2(float _x,float _y) : x(_x), y(_y) { }
Vector2(const Vector2 &v) : x(v.x), y(v.y) { }
int operator==(const Vector2 &V) const { return (fabs(x-V.x)<Epsilon && fabs(y-V.y)<Epsilon); }
int operator!=(const Vector2 &V) const { return (fabs(x-V.x)>Epsilon || fabs(y-V.y)>Epsilon); }
float Dot(const Vector2 &t) const { return x * t.x + y * t.y; }
Vector2 operator*(float f) const { return Vector2(x * f,y * f); }
Vector2 operator/(float f) const { f=1.0f/f; return Vector2(x * f,y * f); }
Vector2 operator+(const Vector2 &t) const { return Vector2(x + t.x, y + t.y); }
Vector2 operator-() const { return Vector2(-x,-y); }
Vector2 operator-(const Vector2 &t) const { return Vector2(x - t.x , y - t.y); }
Vector2 &operator*=(float f) { return *this = *this * f; }
Vector2 &operator/=(float f) { return *this = *this / f; }
Vector2 &operator+=(const Vector2 &t) { return *this = *this + t; }
Vector2 &operator-=(const Vector2 &t) { return *this = *this - t; }
operator float*() { return w; }
operator const float*() const { return w; }
float &operator[](int i) { return w[i]; }
const float operator[](int i) const { return w[i]; }
Vector2 Tangent(void) const { return Vector2(y, -x); }
float Length() const { return float(sqrt(x*x + y*y)); }
float Angle() const {
float d=Length();
if(d<Epsilon) return 0.0f;
float a=Rad2Deg(acos(x/d));
return (y<0.0f) ? 360.0f-a : a;
}
float Square_Length() const { return x*x + y*y; }
float Normalize() {
float inv, l = Length();
if(l>Epsilon) inv = 1.0f / l;
u *= inv;
v *= inv;
return l;
}
//***************************************************************
// To determine a triangle side
//***************************************************************
static inline int Triangle_Side(const Vector2 a, const Vector2 b, const Vector2 c)
{
const float d = (b-a).Dot( (c-a).Tangent() );
if( d > Epsilon ) return CLOCKWISE;
if( d < -Epsilon ) return COUNTERCLOCKWISE;
return COLINEAR;
}
static bool Are_Segments_Crossing(const Vector2& a1, const Vector2& a2, const Vector2& b1, const Vector2& b2)
{
Vector2 t;
t = (a2-a1).Tangent();
if( t.Dot(b1-a1) * t.Dot(b2-a1) > Epsilon*Epsilon) return false;
t = (b2-b1).Tangent();
if( t.Dot(a1-b1) * t.Dot(a2-b1) > Epsilon*Epsilon) return false;
return true;
}
union {
struct {
float x,y;
};
struct {
float u,v;
};
float w[2];
};
};
struct Circle
{
Vector2 Center;
float Radius;
Circle() { }
Circle(const Vector2 &c, float r) : Center(c), Radius(r) { }
bool Intersection(const Vector2 &v) const
{
Vector2 c=v-Center;
return c.Dot(c) <= Square(Radius);
}
// segment, not tested
bool Intersection(const Vector2 &a, const Vector2 &b) const
{
Vector2 ba = b-a;
Vector2 ca = Center-a;
float d = ba.Tangent().Dot(ca);
if( d > Radius ) return false;
if( d < Radius ) return false;
if( (ca).Square_Length() < Radius*Radius) return true;
if( (Center-b).Square_Length() < Radius*Radius) return true;
float l = ba.Square_Length();
d = ba.Dot(ca);
if( d <= l && d >= 0.0f) return true;
}
// triangle, not tested
bool Intersection(const Vector2 &a, const Vector2 &b, const Vector2 &c) const
{
const Vector2 v[3] = { a, b, c };
Vector2 dv[3];
Vector2 dc[3];
int j = 2;
for(int i=0; i<3; ++i)
{
dv[i] = v[i] - v[j];
dc[i] = Center - v[i];
if(dv[i].Tangent().Dot(dc[i]) > Radius) return false;
j = i;
}
for(int i=0; i<3; ++i)
if(dc[i].Square_Length() > Radius*Radius) return true;
j = 2;
for(int i=0; i<3; ++i)
{
float d = dv[i].Dot(dc[j]);
if(d >= 0.0f)
{
float l = dv[i].Square_Length();
if(d <= l) return true;
}
j = i;
}
return false;
}
bool Intersection(const Box2 &c) const
{
if(c.Intersection(Center)) return true;
float r;
r = fmin( Square(c.Min.x - Center.x) , Square(c.Max.x - Center.x));
r += fmin( Square(c.Min.x - Center.x) , Square(c.Max.x - Center.x));
return r <= Square(Radius);
}
bool Intersection(const Circle &c) const
{
Vector2 d=c.Center - Center;
return d.Square_Length() <= Square(Radius + c.Radius);
}
};
No esta probado ojo.
El algoritmo es:
Descartar si el producto punto de la tangente a un segmento por el origen del circulo mas el dezplazamiento al origen del segmento es mayor al radio.
Si la distancia del origen del circulo a un vertice es menor que el radio entonces esta dentro.
Determinar la proyeccion del origen del circulo a la recta donde posa un segmento, si el proyectado esta dentro del segmento incorporar (hay intersepcion)
Saludos
Cita de: "senior wapo"Si la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.
Se asume que el lado positivo es el interior del triángulo, por ejemplo, tomando el orden de los vértices en el sentido de las agujas del reloj.
.
Esto es correcto pero incompleto. Por ejemplo que pasa si la distancia es negativa y en valor absoluto menor que el radio. ¿Hay invasion? Puede que si y puede que no.
El problema no es trivial, hay que tener en cuenta los diferentes casos.
Mi solucion(por casos):
- COLISION SI el triangulo esta dentro del circulo. (Implementación: Test facil con los vertices y el radio)
- COLISION SI el circulo esta completamente dentro del triangulo
PARA TODOS los segmentos del triangulo la distancia(por el lado hacia dentro del triangulo) al centro del circulo es mayor o igual a su radio.
(Implementación: Test utilizando el pseudocodigo de senior wapo, distancia punto a recta)
- COLISION SI existen 2 o más puntos de intersección de la circunferencia con los
segmentos del triangulo, contando las intersecciones con todos los segmentos. (Implementación: Test de intersección de segmento con circunferencia para todos los segmentos)
Saludos
Nostromo
[editando]
Cita de: "nostromo"
Esto es correcto pero incompleto. Por ejemplo que pasa si la distancia es negativa y en valor absoluto menor que el radio. ¿Hay invasion? Puede que si y puede que no.
Si se cumple para las 3 rectas necesariamente hay invasión. Hay que comprobar siempre y en todo caso las 3 rectas a menos que en una ya esté lo bastante alejado.
Loover pide que la respuesta sea un booleano indicando si hay invasión de algún tipo o no, luego no es necesario calcular donde ni como.
@Loover: Viendo el código de Pogacha me he dado cuenta que en mi explicación he usado directamente el vector del segmento y no su normal, aunque luego en el texto me refiera a la normal.
La normal la calculas girando 90 grados el vector a un lado u a otro, lo que se traduce en ajustar signos (X o Y según sentido de giro) e intercambiar X e Y. Es en la parte en donde pone tangente (técnicamente el nombre correcto).
@Pogacha: Bonito código, está bastante limpio y estructurado. Deberías ver el spaguetti que yo hago a veces.
Sobre la idea del triangulo ampliado:
(http://img204.imageshack.us/img204/3478/trianguloyp9.jpg)
El circulo de abajo a la derecha tiene el centro dentro pero esta fuera del triangulo original. (Según he estado dándole vueltas siempre cerca de los vértices están los casos especiales no triviales)
Cita de: "senior wapo"
Si se cumple para las 3 rectas necesariamente hay invasión. Hay que comprobar siempre y en todo caso las 3 rectas a menos que en una ya esté lo bastante alejado.
Si. Pero si se cumple(distancia negativa y absoluta menor que el radio) solo en dos rectas ¿hay invasión siempre? no siempre
No tengo tiempo ahora de pintar un ejemplo... más tarde a ver si puedo...
Lo de decir donde esta el circulo en mi solución solo es para aclarar los casos de prueba que es necesario hacer.
Un saludo
Nostromo
Jo que rápidos sois:
CitarEl circulo de abajo a la derecha tiene el centro dentro pero esta fuera del triangulo original. (Según he estado dándole vueltas siempre cerca de los vértices están los casos especiales no triviales)
Me dí cuenta también justo después de postear. Le estoy dando vueltas aquí sobre papel y en los casos de las esquinas la envolvente mayor no sería un triángulo... sino una curva (hecha con el radio). Pero en estos casos se podría ver si el vértice está dentro del círculo y ya se sabría así si hay colisión...
Ok, mi algoritmo falla.
Me olvide el segundo de los casos y que cuando se proyecta se debe verificar la distancia:
Citar- COLISION SI el triangulo esta dentro del circulo. (Implementación: Test facil con los vertices y el radio)
- COLISION SI el circulo esta completamente dentro del triangulo
PARA TODOS los segmentos del triangulo la distancia(por el lado hacia dentro del triangulo) al centro del circulo es mayor o igual a su radio.
(Implementación: Test utilizando el pseudocodigo de senior wapo, distancia punto a recta)
- COLISION SI existen 2 o más puntos de intersección de la circunferencia con los segmentos del triangulo, contando las intersecciones con todos los segmentos. (Implementación: Test de intersección de segmento con circunferencia para todos los segmentos)
Yo lo escribiria así:
Citar- NO COLISION si para algun segmento el producto punto de la tangente al segmento por el circulo menos el dezplazamiento al origen del segmento es mayor al radio.
- COLISION si el centro del circulo esta dentro del triangulo
- COLISION si la proyeccion del centro del circulo contra un segmento esta dentro del segmento y la distancia del centro del circulo a ese segmento es menor o igual al radio.
- COLISION si la distancia a un vertice del centro del circulo, es menor o igual al radio.
- NO COLISION si llego hasta aqui.
Sobre el caso especial que le comentaba a senior wapo : 2 rectas con distancia negativa(hacia afuera) y absoluta menor que el radio.
(http://img132.imageshack.us/img132/8001/triangulowb5.jpg)
Como vemos el circulo puede estar solapado o fuera... por eso decía que no es trivial... hay que verlo por casos
Saludos
Nostromo
¿Funcionaría esto?
(http://www.pixelartgames.com/temporal/ejemplo4.PNG)
Creamos un triángulo más grande que el original, desde cada cara ampliamos la cara la distancia del radio.
Algoritmo:
- Vemos si el centro del círculo está dentro del triángulo pequeño. Si es así, devolver cierto (hay colisión).
- Vemos si el centro del círculo está dentro del triángulo creado (más grande)
- Si es así, ahora verificamos que algún vértice está dentro del círculo, porque pude ser que sea un caso especial (el de las esquinas) y que realmente no haya colisión. Si un vértice está dentro del círculo, devolver cierto (hay colisión). En el dibujo que he puesto si la hay.
¿Correcto?
Funcionaría correctamente para los casos especiales:
(http://img132.imageshack.us/img132/8001/triangulowb5.jpg)
¿No?
Si, es cierto, lo olvidé. De hecho lo expliqué en este hilo de hace 3 años en referencia a un cuadrado (hay gráfico).
http://www.stratos-ad.com/forums3/viewtopic.php?t=4123&view=previous&sid=c78682150407c64c0a08e93f47bb9947
Para evitar comparar con los 3 vértices en el caso de ese hilo (contra cuadrado) recomendaba elegir el vértice a comparar usando signos (centro del círculo - centro del cuadrado)
En el caso del triéngulo con orientación arbitraria se me ocurre que el vértice a comparar es aquél que no forma parte del segmento cuya distancia al circulo es mayor (en valor absoluto). Al fin y al cabo las distancias las tenemos que calcular primero.
Cita de: "Loover"Jo que rápidos sois:
CitarEl circulo de abajo a la derecha tiene el centro dentro pero esta fuera del triangulo original. (Según he estado dándole vueltas siempre cerca de los vértices están los casos especiales no triviales)
Me dí cuenta también justo después de postear. Le estoy dando vueltas aquí sobre papel y en los casos de las esquinas la envolvente mayor no sería un triángulo... sino una curva (hecha con el radio). Pero en estos casos se podría ver si el vértice está dentro del círculo y ya se sabría así si hay colisión...
Por eso tenes que comprobar la proyeccion sobre el segmento.
Aca se ven todos los casos.
(http://img510.imageshack.us/img510/7286/tricirwy0.jpg)
Si el centro esta en la zona verde esta fuera, esto se cumple cuando la distancia con signo a algun segmento es mayor al radio(*).
Si esta en la violeta esta dentro, esto es cuando todas las distancias con signos a todos los segmentos son negativos(*).
Si esta en alguna de las amarillas esta dentro, esto es si la distancia del centro del circulo a algun vertice es menor al radio.
Si esta en la marron rosasea es que esta dentro, esto es cuando la proyeccion a un segmento donde la distancia con signo sea positiva este dentro del segmento.
Con esto hemos descartado todo el espacio exepto las esquinas rojas, el centro estará en ellas y por ende esta descartado.
Saludos
* Tomar en cuenta el signo que tu tengas definido.[/img]
Pogacha:
Bueno, es lo mismo que digo yo (no en ese post que comentas, sino en uno posterior), solo que yo no hago proyecciones ¿no?. ¿Qué sería más rápido? O igual me estoy liando y estás diciendo exactamente lo mismo. Por cierto, ¿cómo se crearía ese triángulo más grande que comento yo? El triángulo cuyos lados se "amplian" la distancia del radio...
No, tu algoritmo fracasa, tienes que si o si buscar un metodo donde tomes un angulo recto con respecto al segmento, la proyeccion hace exactamente eso.
Ese triangulo mas grande lo logras al sumar el radio al desplazamiento al origen del segmento.
No veo donde está el error, estoy algo denso hoy. ¿Puedes ponerme un ejemplo donde fracase, por favor?
Algoritmo:
1) Vemos si el centro del círculo está dentro del triángulo. Si es así, devolver cierto (hay colisión).
2) Creamos el triángulo más grande. (Sus lados se amplián la distancia del radio, usando la normal de cada lado, en las esquinas quedará más separado, ahí están los casos especiales).
3.a) Vemos si el centro del círculo está dentro del triángulo creado (más grande). Si está fuera, devolver falso (no hay colisión)
3.b) Si está dentro, ahora verificamos que algún vértice del triángulo está dentro del círculo, porque puede ser que sea un caso especial (el de las esquinas) y que realmente no haya colisión. Si un vértice está dentro del círculo, devolver cierto (hay colisión) sino, devolver falso (no hay colisión).
(http://www.pixelartgames.com/temporal/ejemplo4.PNG)
No, perdon, es exactamente lo mismo o incluso mejor.
Me confundio tu dibujo, las normales al segmento te dan un angulo recto e incluso es mas "tranqui" de implementar que proyectando.
Guay, por una vez una "idea féliz" funciona. Aunque fijo que habrá por ahí métodos mas rápidos. Pero bueno, casi mejor algo que pueda hacer y entender yo mismo mientras no vaya lentísimo.
Estoy muy verde en álgebra, a ver si logro crear el triángulo este más grande... las otras dos funciones (dentro del círculo, dentro del triángulo), ya las tengo.
En cuanto tenga resultados, los postearé.
Es que no debes crear el triangulo.
Tienes Vector o Point con componentes X e Y
El segmento A-B = S y el circulo de centro C y radio R
La normal a S es igual a:
N = | (B.y-A.y, A.x-B.x) |
El desplazamiento al origen del segmento es
D = N . D = N.x * D.x + N.y * D.y
. es el producto punto
Si N . C - D > R entonces esta lejos del segmento.
Si N.x * C.x + N.y * C.y - D > R esta fuera del segmento.
Si N.x * C.x + N.y * C.y - D > 0 entonces es que esta a un lado del segmento pero lo suficientemente cerca como para poder aun estar en contacto.
Aqui pruebas de esta misma manera con las normales en las puntas y determinas si el centro esta o no sobre el rectangulo proyeccion caso que no pruebas las distancias a los verices del segmento.
Saludos
¿Mande? :shock:
Más o menos lo entiendo, ¿podrías echarme un cable con el código fuente? ¿Lo que comentas hay que hacerlo para cada uno de los segmentos? ¿Importa si los vértices están desordenados o hay que hacerlo según las agujas del reloj? ¿Cómo se calcula la normal en los vértices, sumando las normales de las caras adyacentes?
OK, yo lo escribo y tu lo pruebas, eh?
CitarOK, yo lo escribo y tu lo pruebas, eh?
Jajaja, ¿y quién te paga? Qué morro tengo. Hazlo solo si tienes tiempo, sino ya me buscaré yo las castañas como buenamente pueda.
De momento estoy implementando el sistema general. Para cada "entidad" del juego se podrán definir una serie de bounding areas a base de círculos, rectángulos y triángulos, por supuesto los rectángulos los trato internamente como dos triángulos. Además, esas bounding areas se podrán agrupar mediante un identificador, de forma que por ejemplo puedas definir en un sprite la cabeza mediante 3 círculos (cabeza y dos orejas) y darle id="head" y luego a otra zona del sprite, por ejemplo 3 rectángulos, dalre id="zapato".
Y las entidades deben poder escalarse y rotar.
<?xml version="1.0" encoding="utf-8"?>
<collision>
<circle id="player_head" x="0" y="0" radius="40" />
<rectangle id="player_head" x="30" y="30" width="50" height="50" />
<triangle id="rocket_tip" ax="10" ay="10" bx="30" by="10" cx="15" cy="40" />
</collision>De momento estoy con las colisiones triángulo a triángulo, parece que va bien el asunto.
// triangle, not tested
bool Intersection(const Vector2 &a, const Vector2 &b, const Vector2 &c) const
{
const Vector2 v[3] = { a, b, c };
Vector2 sd[3]; // segment v[i] - v[(i-1)%3] direction
Vector2 dc[3]; // center minus vector[i]
float lc[3]; // center signed distance to segment i
// All the signs depends on the triangle vertex order
// Check if the center is far away from any segment
int i, j = 2;
for(i=0; i<3; ++i)
{
sd[i] = v[i] - v[j];
dc[i] = Center - v[i];
lc[i] = sd[i].Tangent().Dot(dc[i]);
if(lc[i] > Radius) return false;
j = i;
}
// Check if the center is inside the triangle
j=2;
for(i=0; i<3; ++i)
{
if(lc[i] > 0.0f)
{
// The circle is over a side.
// check if it's projected over the segment
// if it is outside some bound check the distance
// of the correspondent vertex
// maybe this couple of > < signs are inverted !?
// Edit: yes they were inverted, I have corrected them
if(sd[i].Dot(v[i]) < sd[i].Dot(Center))
return dc[i].Square_Length() < Radius;
if(sd[i].Dot(v[j]) > sd[i].Dot(Center))
return dc[j].Square_Length() < Radius;
// it's projected over the segment
return true;
}
j=i;
}
// The circle center is inside the triangle
return true;
}
OK, ahora te toca probarlo a ti.
Saludos
Edit: corregi los signos de la deteccion de los bounds de proyeccion del centro sobre el segmento
Para que luego digan que a la gente no le gustan las matematicas :D
Te lo agradezco un montón Pogacha, estoy deseando llegar a esa parte para probarlo. De momento estoy aún intentando mostrar colisiones triángulo a triángulo y agrupándolas por id después de parsearlas con el xml. Mañana vuelvo a españa (toy en Rep. Checa), el domingo o el lunes lo probaré.
Según te había entendido yo al principio, quieres poder saber si tienes un triángulo completamente dentro de un círculo o un círculo completamente dentro del triángulo, ¿es así?
Lo de las inecuaciones es fácil. Por ahí atrás ya habían puesto cómo queda el sistema de ecuaciones de una recta, que no es más que ecuaciones lineales igualadas a cero (es la que define los puntos que pasan por la recta). Si haces que sean o bien mayores o bien menores que cero, defines un semiespacio. Decides si quieres que ese símbolo es mayor o menor simplemente sustituyendo en la ecuación el punto del tercer vértice que no forma parte de la recta y viendo cuál se cumple.
Haciendo esto para las tres rectas, obtendrás tres semiecuaciones. Entonces sólo tienes que sustituir el punto del centro del círculo en las tres y ver si se cumple para las tres. Si lo hace, o el círculo está dentro del triángulo o viceversa; sólo te queda saber si interseccionan para saber si está completamente dentro o no, y ese cálculo me suena que ya sabías cómo hacerlo, ¿no?
El codigo que arme ahi es para determinar si hay intersección alguna entre un circulo y un triangulo, que creo que era lo que se pedia.
Bueno, hoy por fin he tenido tiempo para ponerme con esto de nuevo. Entre los códigos que he visto por internet, el código de pogacha y las ideas que saqué en claro aquí está finalmente el resultado (funciona estupendamente). En breve pondré una prueba en la que vereis un par de sprites rotando, con varias áreas asignadas mediante un archivo xml (áreas triangulares, círculos y rectángulos) y en las que se pueden chequear colisiones por grupo).
[edit] Mirando el código fuente veo que me he dejado una función D3DXVec2Dot que es de direct3d, no es más que el dot product de toda la vida.
Gracias de nuevo a todos.
/*
==================
Check collision between a circle and a triangle
==================
*/
inline bool IND_Render::IsCircleToTriangleCollision (D3DXVECTOR2 pPCenter, int pRadius, D3DXVECTOR2 pA2, D3DXVECTOR2 pB2, D3DXVECTOR2 pC2)
{
// Circle center inside the triangle
if (IsPointInsideTriangle (pPCenter, pA2, pB2, pC2)) return 1;
// Check the distancy of the circle center to the 3 triangle segments
if (PointToLineDistance (pA2, pB2, pPCenter, 1) < pRadius) return 1;
if (PointToLineDistance (pB2, pC2, pPCenter, 1) < pRadius) return 1;
if (PointToLineDistance (pC2, pA2, pPCenter, 1) < pRadius) return 1;
return 0;
}
Que utiliza estos métodos:
/*
==================
Compute the dot product AB . BC
==================
*/
int IND_Render::Dot3 (D3DXVECTOR2 pA, D3DXVECTOR2 pB, D3DXVECTOR2 pC)
{
D3DXVECTOR2 mAB;
D3DXVECTOR2 mBC;
mAB.x = pB.x - pA.x;
mAB.y = pB.y - pA.y;
mBC.x = pC.x - pB.x;
mBC.y = pC.y - pB.y;
return (int) ( (mAB.x * mBC.x) + (mAB.y * mBC.y) );
}
/*
==================
Compute the cross product AB x AC
==================
*/
int IND_Render::Cross3 (D3DXVECTOR2 pA, D3DXVECTOR2 pB, D3DXVECTOR2 pC)
{
D3DXVECTOR2 mAB;
D3DXVECTOR2 mAC;
mAB.x = pB.x - pA.x;
mAB.y = pB.y - pA.y;
mAC.x = pC.x - pA.x;
mAC.y = pC.y - pA.y;
return (int) ( (mAB.x * mAC.y) - (mAB.y * mAC.x) );
}
/*
==================
Compute the distance from A to B
==================
*/
inline double IND_Render::Distance (D3DXVECTOR2 pA, D3DXVECTOR2 pB)
{
float mD1 = (pA.x - pB.x);
float mD2 = (pA.y - pB.y);
return sqrt ( (mD1 * mD1) + (mD2 * mD2) );
}
/*
==================
Compute the distance from AB to C
if isSegment is true, AB is a segment, not a line.
==================
*/
inline double IND_Render::PointToLineDistance (D3DXVECTOR2 pA, D3DXVECTOR2 pB, D3DXVECTOR2 pC, bool pIsSegment)
{
double mDist = Cross3 (pA, pB, pC) / Distance (pA, pB);
if (pIsSegment)
{
int mDot1 = Dot3 (pA, pB, pC);
if (mDot1 > 0) return Distance (pB, pC);
int mDot2 = Dot3 (pB, pA, pC);
if (mDot2 > 0) return Distance (pA, pC);
}
return abs (mDist);
}
/*
==================
Check if point p is inside the triangle with vertex a, b, c
Technique from: http://www.blackpawn.com/texts/pointinpoly/default.html
==================
*/
inline bool IND_Render::IsPointInsideTriangle (D3DXVECTOR2 p,
D3DXVECTOR2 a,
D3DXVECTOR2 b,
D3DXVECTOR2 c)
{
// Compute vectors
D3DXVECTOR2 v0 = c - a;
D3DXVECTOR2 v1 = b - a;
D3DXVECTOR2 v2 = p - a;
// Compute dot products
float dot00 = D3DXVec2Dot (&v0, &v0);
float dot01 = D3DXVec2Dot (&v0, &v1);
float dot02 = D3DXVec2Dot (&v0, &v2);
float dot11 = D3DXVec2Dot (&v1, &v1);
float dot12 = D3DXVec2Dot (&v1, &v2);
// Compute barycentric coordinates
float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
// Check if point is in triangle
return (u > 0) && (v > 0) && (u + v < 1);
}