# Collision: Sphere to Face

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

## 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 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 on other sites
thank you very much :) this is great!

##### 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 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.// -----------//  : 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 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 on other sites
Quote:
 Original post by BloodLust666see, 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 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 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

1. 1
Rutin
19
2. 2
3. 3
JoeJ
15
4. 4
5. 5

• 22
• 19
• 11
• 13
• 17
• ### Forum Statistics

• Total Topics
631698
• Total Posts
3001768
×