Sign in to follow this  
BloodLust666 (dupe)

Collision: Sphere to Face

Recommended Posts

Can someone show me the most efficient way to test a sphere to face collision and find the specific point on the face. Things that I have is the position of the sphere with the radius and each of the verticies on the face and the normal

Share this post


Link to post
Share on other sites
I would use Dave Eberly's code to find the closest point in a triangle from a point in space. If that point is inside the sphere (square radius check), then you have an intersection.

Here's an example.

Share this post


Link to post
Share on other sites
actually, there's a lot of stuff in the code that i don't really understand... a lot of variables that don't really explain what they're for. Is there a more documented example or even an article about this kind of collision? thanks

Share this post


Link to post
Share on other sites
Main.cpp should be smaller and digestable.

ok, I'll break it down for you...

Sphere [P, r]
triangle[V0, V1, V2]




//-------------------------------------------------------------------
// Calculate the squared distance of a point to the triangle
//
// Nicked code from David Eberly's most excelent physics site
// Don't ask me how it works. It just does :)
// (http://www.magic-software.com)
//
// Parameters.
// -----------
// [P] : Point in question.
// [V0, V1, V2] : triangle vertices.
//
// return values.
// --------------
// [s, t] : closest point, in Parametric form (for tex coord reconstruction).
// [ClosestPoint] : The point on the triangle the closest, as a vector.
// Returns : The squared distance of the point to the triangle.
//-------------------------------------------------------------------
float PointTriangleDistanceSquared(const Vector& P, const Vector& V0, const Vector& V1, const Vector& V2, float* s, float* t, Vector* pClosestPoint)
{
//-------------------------------------------------------------------
// 2 edges of the triangle
//-------------------------------------------------------------------
Vector E0 = (V1 - V0);
Vector E1 = (V2 - V0);
Vector kDiff = (V0 - P);

float fA00 = E0.DotProduct(E0);
float fA01 = E0.DotProduct(E1);
float fA11 = E1.DotProduct(E1);
float fB0 = kDiff.DotProduct(E0);
float fB1 = kDiff.DotProduct(E1);
float fC = kDiff.DotProduct(kDiff);

float fDet = (float) fabs(fA00*fA11-fA01*fA01);
float fS = fA01*fB1-fA11*fB0;
float fT = fA01*fB0-fA00*fB1;
float fSqrDist;


//-------------------------------------------------------------------
// degenerate triangle
//-------------------------------------------------------------------
if (fabs(fDet) < 0.000000001f)
return 100000000.0f;

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

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

if ( s )
*s = fS;

if ( t )
*t = fT;

if ( pClosestPoint )
*pClosestPoint = V0 + (fS * E0) + (fT * E1);

return (float) fabs(fSqrDist);
}

bool CollideSphereWithTriangle(Vector& P, float r, const Vector& V0, const Vector& V1, const Vector& V2)
{
Vector ClosestPoint;
float distance_squared = PointTriangleDistanceSquared(P, V0, V1, V2, NULL, NULL, &ClosestPoint);

// sphere centre too far away from triangle
if (distance_squared > r*r)
return false;

// now push the sphere centre away from the triangle
float distance = sqrt(distance_squared); // distance to triangle
Vector Dir = (P - ClosestPoint) / distance; // direction of push (normalised)
float dist = r - d; // distance of push
P += Dir * dist; // push point

// we intersected
return true;
}

Share this post


Link to post
Share on other sites
see, what i don't get is all those regions. I dont' really get why you take the dot product of itself, couldn't you just say .Length()? i guess what I'm saying is could you put a little more documentation in it? no rush :) thanks again

Share this post


Link to post
Share on other sites
Quote:
Original post by BloodLust666
see, what i don't get is all those regions. I dont' really get why you take the dot product of itself, couldn't you just say .Length()? i guess what I'm saying is could you put a little more documentation in it? no rush :) thanks again


Dot product of itself isn't the length. It's length*length.

Share this post


Link to post
Share on other sites
This code is Dave Eberly's code. It's explained in his docs, and is rather maths heavy (related to plucker coordinates iirc). I do not 100% understand what is happening there, I guess I could with spending more time with the algo, but all I care about is the result. Can't be simpler really, pass in a point, three vertices, and it gives you the distance squared, the point on the triangle and barycentric coordinates is you need them.

Really, it's not very hard to write a 'closest point' algo. I guess if I had to write one, It would be based on the same 'region' concept. Trying to find which feature (face, vertex, edge) of the triangle is the closest, then find the point on that feature. For that, you need to partition space into regions (called a voronoi diagram) and find which region the point belongs to, then find the corresponding feature to that region, and find the closest point on that feature. Sounds complicated but it's quite straight forward.

I just found his algo really elegant, so I didn't write my own.

Share this post


Link to post
Share on other sites
ah, alright, i guess i'll have to deal for now then. Also, is that free source? meaning could I use his function to find the point of collision and that in my engine? I'd have to rename pretty much everything to go with the code standard in my engine but yea; i'll have to break it apart sometime but for now, i guess i'll just use it as is thanks

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this