Collision: Sphere to Face
Author
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
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.
Here's an example.
Author
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
Main.cpp should be smaller and digestable.
ok, I'll break it down for you...
Sphere [P, r]
triangle[V0, V1, V2]
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;}
Author
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
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.
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.
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.
Author
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
