Colisión entre círculo y triángulo 2d

[Pogacha]

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

[Loover]

¿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?

[Pogacha]

OK, yo lo escribo y tu lo pruebas, eh?

[Loover]

OK, 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.

Código [Seleccionar] Expand

<?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.

[Pogacha]

Código [Seleccionar] Expand

 // 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

[Tei]

Para que luego digan que a la gente no le gustan las matematicas :D

[Loover]

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é.

[Mars Attacks]

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?

[Pogacha]

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.

[Loover]

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.

Código [Seleccionar] Expand


/*
==================
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:

Código [Seleccionar] Expand


/*
==================
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);
}