Hello I am coding some physics stuff but currently I am only handling collisions between sphere and planes and now I want to expand this to test sphere with the "Real Level Polygons", but unfortunatly I cant find info about it. The trouble is that my physics lib need the contact point , the penetration distance and the normal of the point of collision. so I really appreciate so much if someone could share with me some resources about sphere-triangle intersection?? Some source code would be a Plus, I really appreciate any help about this. Thanks in advance! Oscar PS: Happy new year!!!!

Hi,

One way to go is:
Check whether the plane, which the triangle spans, intersects the sphere (you have this part). If it does intersect, project the sphere to the plane and check whether the triangle and the circle intersects.

Hmm, this was just a quick thought. Might be overkill though.
Check for other algorithms also...

Regards

/Mankind gave birth to God.

Hello

Thanks for your answer, it a good metho the one you suggest.

By other hand thinking about my trouble (sphere - triangle collision), I was wondering if this is the only method used to detect collision in games, I mean all games go with collisions between Bounding Volumes and Polys or use some aproximation for this?

PS: exist some FREE collision detection lib like I-Collide, OPCODE, V-Collide, etc... which handle collision detection with Physics in mind (penetration depth, contact point and contact normal) ???

Thanks for your help.
Oscar

Hello

Finally got a solution to this trouble!!!. Thanks to the SphereTriangleOverlap test by David Eberly in Magic.

I just need to modify this routine a little to get the distance from my sphere to the triangle and use it to compute the penetration distance to feed my physics lib.

Here I post the full source code (hoping it may help some other people : )


#define MAX_FLOAT FLT_MAX
bool SphereTriangleIntersect(const COLLISION_TRIANGLE *pT, const D3DXVECTOR3 & pos, float radius, float & sqrDist)
{
D3DXVECTOR3 TriEdge0 = pT->vertices[1] - pT->vertices[0];
D3DXVECTOR3 TriEdge1 = pT->vertices[2] - pT->vertices[0];

D3DXVECTOR3 kDiff = pT->vertices[0] - pos;
float fA00 = D3DXVec3LengthSq(&TriEdge0); // TriEdge0.SquareMagnitude();
float fA01 = D3DXVec3Dot(&TriEdge0, &TriEdge1); // TriEdge0 | TriEdge1;
float fA11 = D3DXVec3LengthSq(&TriEdge1); // TriEdge1.SquareMagnitude();
float fB0 = D3DXVec3Dot(&kDiff, &TriEdge0); // kDiff | TriEdge0;
float fB1 = D3DXVec3Dot(&kDiff, &TriEdge1); // kDiff | TriEdge1;
float fC = D3DXVec3LengthSq(&kDiff); // kDiff.SquareMagnitude();
float fDet = fabsf(fA00 * fA11 - fA01 * fA01);
float u = fA01 * fB1 - fA11 * fB0;
float v = fA01 * fB0 - fA00 * fB1;
float SqrDist;

if(u + v <= fDet)
{
if(u < 0.0f)
{
if(v < 0.0f) // region 4
{
if(fB0 < 0.0f)
{
v = 0.0f;
if(-fB0>=fA00) { u = 1.0f; SqrDist = fA00+2.0f*fB0+fC; }
else { u = -fB0/fA00; SqrDist = fB0*u+fC; }
}
else
{
u = 0.0f;
if(fB1>=0.0f) { v = 0.0f; SqrDist = fC; }
else if(-fB1>=fA11) { v = 1.0f; SqrDist = fA11+2.0f*fB1+fC; }
else { v = -fB1/fA11; SqrDist = fB1*v+fC; }
}
}
else // region 3
{
u = 0.0f;
if(fB1>=0.0f) { v = 0.0f; SqrDist = fC; }
else if(-fB1>=fA11) { v = 1.0f; SqrDist = fA11+2.0f*fB1+fC; }
else { v = -fB1/fA11; SqrDist = fB1*v+fC; }
}
}
else if(v < 0.0f) // region 5
{
v = 0.0f;
if(fB0>=0.0f) { u = 0.0f; SqrDist = fC; }
else if(-fB0>=fA00) { u = 1.0f; SqrDist = fA00+2.0f*fB0+fC; }
else { u = -fB0/fA00; SqrDist = fB0*u+fC; }
}
else // region 0
{
// minimum at interior point
if(fDet==0.0f)
{
u = 0.0f;
v = 0.0f;
SqrDist = MAX_FLOAT;
}
else
{
float fInvDet = 1.0f/fDet;
u *= fInvDet;
v *= fInvDet;
SqrDist = u*(fA00*u+fA01*v+2.0f*fB0) + v*(fA01*u+fA11*v+2.0f*fB1)+fC;
}
}
}
else
{
float fTmp0, fTmp1, fNumer, fDenom;

if(u < 0.0f) // region 2
{
fTmp0 = fA01 + fB0;
fTmp1 = fA11 + fB1;
if(fTmp1 > fTmp0)
{
fNumer = fTmp1 - fTmp0;
fDenom = fA00-2.0f*fA01+fA11;
if(fNumer >= fDenom)
{
u = 1.0f;
v = 0.0f;
SqrDist = fA00+2.0f*fB0+fC;
}
else
{
u = fNumer/fDenom;
v = 1.0f - u;
SqrDist = u*(fA00*u+fA01*v+2.0f*fB0) + v*(fA01*u+fA11*v+2.0f*fB1)+fC;
}
}
else
{
u = 0.0f;
if(fTmp1 <= 0.0f) { v = 1.0f; SqrDist = fA11+2.0f*fB1+fC; }
else if(fB1 >= 0.0f) { v = 0.0f; SqrDist = fC; }
else { v = -fB1/fA11; SqrDist = fB1*v+fC; }
}
}
else if(v < 0.0f) // region 6
{
fTmp0 = fA01 + fB1;
fTmp1 = fA00 + fB0;
if(fTmp1 > fTmp0)
{
fNumer = fTmp1 - fTmp0;
fDenom = fA00-2.0f*fA01+fA11;
if(fNumer >= fDenom)
{
v = 1.0f;
u = 0.0f;
SqrDist = fA11+2.0f*fB1+fC;
}
else
{
v = fNumer/fDenom;
u = 1.0f - v;
SqrDist = u*(fA00*u+fA01*v+2.0f*fB0) + v*(fA01*u+fA11*v+2.0f*fB1)+fC;
}
}
else
{
v = 0.0f;
if(fTmp1 <= 0.0f) { u = 1.0f; SqrDist = fA00+2.0f*fB0+fC; }
else if(fB0 >= 0.0f) { u = 0.0f; SqrDist = fC; }
else { u = -fB0/fA00; SqrDist = fB0*u+fC; }
}
}
else // region 1
{
fNumer = fA11 + fB1 - fA01 - fB0;
if(fNumer <= 0.0f)
{
u = 0.0f;
v = 1.0f;
SqrDist = fA11+2.0f*fB1+fC;
}
else
{
fDenom = fA00-2.0f*fA01+fA11;
if(fNumer >= fDenom)
{
u = 1.0f;
v = 0.0f;
SqrDist = fA00+2.0f*fB0+fC;
}
else
{
u = fNumer/fDenom;
v = 1.0f - u;
SqrDist = u*(fA00*u+fA01*v+2.0f*fB0) + v*(fA01*u+fA11*v+2.0f*fB1)+fC;
}
}
}
}

//
// llena la distancia cuadrada
sqrDist = SqrDist;

return fabsf(SqrDist) < (radius * radius);
}


So to use it I do as follows:
for each triangle to test collision do
{
float sqrDist; // returned square dist from sphere to triangle
if (SphereTriangleIntersect(&collidable_polys, Sphere.center, Sphere.radius, sqrDist))
{
// get real dist from sphere to poly (not squared)
float dist = (float)fsqrt(distSqr);
// compute penetration depth
float depth = - (dist - Sphere.radius);

// for last compute the contact point on poly
cp = Sphere.center - collidable_polys.normal * dist;<br><br>} // end if sphereTriangleIntersec<br><br>PS: This routine dose not use the sphere velocity to avoid collision troubles if the sphere is moving REALLY FAST.<br><br>Regards,<br>Oscar<br> <br> <br><br><br> </i>