Sign in to follow this  

Collision: Sphere to Face

This topic is 3868 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

This topic is 3868 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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