   Moving sphere to triangle collision
  I have been trying to learn a moving sphere to stationary triangle collision. Other threads have suggested http://www.peroxide.dk/papers/collision/collision.pdf , however, even though I understand the algorithm I am still getting no collision when I should be.I have a triangle being built clockwise with the following properties:Vertex One: (4.0f, 0.0f, 4.0f)Vertex Two: (4.0f, 0.0f, 0.0f)Vertex Three: (0.0f, 0.0f, 0.0f)Normal : (0, 1, 0)I then have a sphere moving down onto it with the properties of:Sphere Origin: (1.5, 1.5, 0)Velocity : (0, -1, 0)Radius: 1 (not taken into account here yet)After a timestep of one second their should be collision in two places because the sphere will be at (1.5, 0.5, 0). There should be collision with the sphere going though the sphere and it is also colliding with the edge between Vertex Two and Vertex Three. Here is a picture of itFrontTopThere should clearly be collision, however, I am not getting neither collision or not collision. I have done the math by hand to make sure there is no collision and there is none, I then followed those variables through the bugger and got the same result. It does get to an eventual Vertex Two to Vertex Three edge check, however, it does not report collision.My question is, has anyone ever successfully implemented this algorithm before? If so, do you happen to see what my problem is? At first I tried to just code it using the algorithm, after having the same issue I literally rewrote their code basically line for line, using their same functions. The only issue I had was with their checkPointInTriangle as it seemed to always report collision, but I then implemented a check I read in Real Time Collision Detection and no longer got that issue. This leads me to believe maybe the author of this document made an error in it.Here is my Vertex Two to Vertex Three check, it should report collision but it does not.// p3 -> p1:edge = p1-p3;baseToVertex = p3 - base;edgeSquaredLength = squaredLength(edge);edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);a = edgeSquaredLength*-velocitySquaredLength +edgeDotVelocity*edgeDotVelocity;b = edgeSquaredLength*(2.0*D3DXVec3Dot(&velocity, &baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;c = edgeSquaredLength*(1.0-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;if (getLowestRoot(a,b,c, t, &newT)) {float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength;if (f >= 0.0 && f <= 1.0) {t = newT;foundCollison = true;collisionPoint = p3 + f*edge;}}Here is everything, in case it is interesting. I have checked for typo's countless times.D3DXVECTOR3 triangleNormal = triangle->GetNormal();D3DXVECTOR3 triangleOrigin = triangle->GetVertexOne();D3DXVECTOR3 sphereVelocity = sphere->GetVelocity();D3DXVECTOR3 p1 = triangle->GetVertexOne();D3DXVECTOR3 p2 = triangle->GetVertexTwo();D3DXVECTOR3 p3 = triangle->GetVertexThree();D3DXVECTOR3 vBasePoint = sphere->GetOrigin();// Get interval of plane intersection:double t0, t1;bool embeddedInPlane = false;// Calculate the signed distance from sphere// position to triangle planedouble signedDistToTrianglePlane;{double nDotOrigin = D3DXVec3Dot(&vBasePoint, &triangleNormal);signedDistToTrianglePlane = nDotOrigin + -(triangleNormal.x*triangleOrigin.x + triangleNormal.y*triangleOrigin.y + triangleNormal.z*triangleOrigin.z);}// cache this as we’re going to use it a few times below:float normalDotVelocity = D3DXVec3Dot(&triangleNormal, &sphereVelocity);// if sphere is travelling parrallel to the plane:if (normalDotVelocity == 0.0f) {if (fabs(signedDistToTrianglePlane) >= 1.0f) {// Sphere is not embedded in plane.// No collision possible:crCollisionResult.enCollisionState = RESTING_CONTACT;return crCollisionResult;}else {// sphere is embedded in plane.// It intersects in the whole range [0..1]crCollisionResult.enCollisionState = HAS_COLLISION;return crCollisionResult;embeddedInPlane = true;t0 = 0.0;t1 = 1.0;}}else {// N dot D is not 0. Calculate intersection interval:t0=(-1.0-signedDistToTrianglePlane)/normalDotVelocity;t1=( 1.0-signedDistToTrianglePlane)/normalDotVelocity;// Swap so t0 < t1if (t0 > t1) {double temp = t1;t1 = t0;t0 = temp;}// Check that at least one result is within range:if (t0 > 1.0f || t1 < 0.0f) {// Both t values are outside values [0,1]// No collision possible:crCollisionResult.enCollisionState = NO_COLLISION;return crCollisionResult;}// Clamp to [0,1]if (t0 < 0.0) t0 = 0.0;if (t1 < 0.0) t1 = 0.0;if (t0 > 1.0f) t0 = 1.0f;if (t1 > 1.0f) t1 = 1.0f;}// OK, at this point we have two time values t0 and t1// between which the swept sphere intersects with the// triangle plane. If any collision is to occur it must// happen within this interval.D3DXVECTOR3 collisionPoint;bool foundCollison = false;float t = dElapsedTime;// First we check for the easy case - collision inside// the triangle. If this happens it must be at time t0// as this is when the sphere rests on the front side// of the triangle plane. Note, this can only happen if// the sphere is not embedded in the triangle plane.if (!embeddedInPlane){D3DXVECTOR3 planeIntersectionPoint = (vBasePoint - triangleNormal) + t0 * sphereVelocity;if (checkPointInTriangle(planeIntersectionPoint, p1,p2,p3)){foundCollison = true;t = t0;collisionPoint = planeIntersectionPoint;}}// if we haven’t found a collision already we’ll have to// sweep sphere against points and edges of the triangle.// Note: A collision inside the triangle (the check above)// will always happen before a vertex or edge collision!// This is why we can skip the swept test if the above// gives a collision!if (foundCollison == false) {// some commonly used terms:D3DXVECTOR3 velocity = sphereVelocity;D3DXVECTOR3 base = vBasePoint;float velocitySquaredLength = squaredLength(velocity);float a,b,c; // Params for equationfloat newT;// For each vertex or edge a quadratic equation have to// be solved. We parameterize this equation as// a*t^2 + b*t + c = 0 and below we calculate the// parameters a,b and c for each test.// Check against points:a = velocitySquaredLength;// P1D3DXVECTOR3 vBaseMinusP1 = base - p1;b = 2.0*(D3DXVec3Dot(&velocity, &vBaseMinusP1));c = squaredLength(p1-base) - 1.0;if (getLowestRoot(a,b,c, t, &newT)) {t = newT;foundCollison = true;collisionPoint = p1;}// P2D3DXVECTOR3 vBaseMinusP2 = base - p2;b = 2.0*(D3DXVec3Dot(&velocity, &vBaseMinusP2));c = squaredLength(p2-base) - 1.0;if (getLowestRoot(a,b,c, t, &newT)) {t = newT;foundCollison = true;collisionPoint = p2;}// P3D3DXVECTOR3 vBaseMinusP3 = base - p3;b = 2.0*(D3DXVec3Dot(&velocity, &vBaseMinusP3));c = squaredLength(p3-base) - 1.0;if (getLowestRoot(a,b,c, t, &newT)) {t = newT;foundCollison = true;collisionPoint = p3;}// Check agains edges:// p1 -> p2:D3DXVECTOR3 edge = p2-p1;D3DXVECTOR3 baseToVertex = p1 - base;float edgeSquaredLength = squaredLength(edge);float edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);float edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);// Calculate parameters for equationa = edgeSquaredLength*-velocitySquaredLength + edgeDotVelocity*edgeDotVelocity;b = edgeSquaredLength*(2.0*D3DXVec3Dot(&velocity, &baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;c = edgeSquaredLength*(1.0-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;// Does the swept sphere collide against infinite edge?if (getLowestRoot(a,b,c, t, &newT)) {// Check if intersection is within line segment:float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength;if (f >= 0.0 && f <= 1.0) {// intersection took place within segment.t = newT;foundCollison = true;collisionPoint = p1 + f*edge;}}// p2 -> p3:edge = p3-p2;baseToVertex = p2 - base;edgeSquaredLength = squaredLength(edge);edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);a = edgeSquaredLength*-velocitySquaredLength +edgeDotVelocity*edgeDotVelocity;b = edgeSquaredLength*(2.0f*D3DXVec3Dot(&velocity, &baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;c = edgeSquaredLength*(1.0f-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;if (getLowestRoot(a,b,c, t, &newT)) {float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength;if (f >= 0.0 && f <= 1.0) {t = newT;foundCollison = true;collisionPoint = p2 + f*edge;}}// p3 -> p1:edge = p1-p3;baseToVertex = p3 - base;edgeSquaredLength = squaredLength(edge);edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);a = edgeSquaredLength*-velocitySquaredLength +edgeDotVelocity*edgeDotVelocity;b = edgeSquaredLength*(2.0*D3DXVec3Dot(&velocity, &baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;c = edgeSquaredLength*(1.0-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;if (getLowestRoot(a,b,c, t, &newT)) {float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength;if (f >= 0.0 && f <= 1.0) {t = newT;foundCollison = true;collisionPoint = p3 + f*edge;}}}This question was originally part of another topic, however, I moved it out to make it a more appropriate place. Hopefully someone else can learn something from this topic.[Edited by - simotix on April 27, 2010 11:24:44 AM]
Quote:My question is, has anyone ever successfully implemented this algorithm before?Yes, I have, and I'm pretty sure others here have as well. It's not trivial to implement, but I believe that the algorithm as presented in the paper is correct.I might be able to take a look at your example later, but could you edit your post and break some of the longer lines? At lower resolutions (e.g. 1024x768) the post is wider than the monitor, which makes it hard to read (for me at least).   ;  Sorry about the resolution, I run at 1680 by 1050. The source I provided seems to have been to long horizontally on some times which stretched the rest of the post. If it is still stretched to much please let me know.   ;  What is the value of dElapsedTime when this code is executed? (I don't see it mentioned anywhere...)   ;  dElapsedTime is 1.0f to represent one second passing, however, that is a typo and should be float t = 1.0f; Which would have operated the same was as if dElapsedTime was 1.0   ;  Ok, I worked through the code using the input data you gave. Here is the code for the edge test you mentioned, along with comments showing the intermediate values as worked out by hand:// p2 -> p3:edge = p3-p2;// edge = [-4, 0, 0]baseToVertex = p2 - base;// baseToVertex = [4, 0, 0] - [1.5, 1.5, 0] = [2.5, -1.5, 0]edgeSquaredLength = squaredLength(edge);// edgeSquaredLength = 16edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);// edgeDotVelocity = [-4, 0, 0].[0, -1, 0] = 0edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);// edgeDotBaseToVertex = [-4, 0, 0].[2.5, -1.5, 0] = -10a = edgeSquaredLength*-velocitySquaredLength +edgeDotVelocity*edgeDotVelocity;// a = 16 * -1 = -16b = edgeSquaredLength*(2.0f*D3DXVec3Dot(&velocity,&baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex; // b = 16 * (2 * 1.5) = 16 * 3 = 48c = edgeSquaredLength*(1.0f-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;// c = 16 * (1 - 8.5) + -10 * -10 = 16 * -7.5 + 100 = -20// a = -16// b = 48// c = -20// determinant = b * b - 4 * a * c =//2304 - 4 * -16 * -20 =//2304 - 1280 =//1024// r1 = (-48 - 32) / -32 = -80 / -32 = 2.5// r2 = (-48 + 32) / -32 = -16 / -32 = .5// newT = .5if (getLowestRoot(a,b,c, t, &newT)) {float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength;// f = 10 / 16 = .625// 'f' tells us where along the segment we intersected,// and it's exactly what we would expect.if (f >= 0.0 && f <= 1.0) {t = newT;foundCollison = true;collisionPoint = p2 + f*edge;}}I suggest that you step through this code in the debugger and, at each step, compare the values shown in the debugger to the values shown in my comments. You say that no collision is reported, which means that the last block of code there (starting with t = newT) must not be being reached. This suggests that either getLowestRoot() is erroneously returning false, or f is somehow being computed incorrectly.Working through this by hand, the values I arrived at were exactly as expected, and did indicate a collision between the sphere and the edge in question.I will be interested to hear where (and how) things differ from what's shown above when you step through this in the debugger.   ;  Unfortunately it was due to the fact that my squaredLength function was wrong, it was defined as return (vector.x * vector.x + vector.y * vector.y + vector.z * vector.z)*2;instead ofreturn (vector.x * vector.x + vector.y * vector.y + vector.z * vector.z);The one thing I noticed about this algorithm which I did not think about in motion physics before was that if the velocity is zero, the check will not work properly (basically just saying their is no collision) even if the sphere is colliding with the triangle. Is this because of an optimization where if a spheres velocity is zero then you should just check a stationary sphere to triangle test?There is three things I am looking to upgrade about this technique. The first is to take in elapsed time, so instead of [0, 1] it would be [0, elapsed time] in theory. While reading the algorithm it shows how uses "1-signedDistToTrianglePlane" because t1 is 1. However, to instead use elapsed time I figured it would be the following since t1 would be elapsedTimet0=(-dElapsedTime-signedDistToTrianglePlane)/normalDotVelocity;t1=( dElapsedTime-signedDistToTrianglePlane)/normalDotVelocity;There was other little places such as if (fabs(signedDistToTrianglePlane) >= dElapsedTime) {}else {// sphere is embedded in plane.// It intersects in the whole range [0..1]embeddedInPlane = true;t0 = 0.0;t1 = dElapsedTime;}// Check that at least one result is within range:if (t0 > dElapsedTime || t1 < 0.0f) {// Both t values are outside values [0,1]// No collision possible:crCollisionResult.enCollisionState = NO_COLLISION;return crCollisionResult;}// Clamp to [0,1]if (t0 < 0.0) t0 = 0.0;if (t1 < 0.0) t1 = 0.0;if (t0 > dElapsedTime) t0 = dElapsedTime;if (t1 > dElapsedTime) t1 = dElapsedTime;It also explained that the edge check is done between [0, 1] so I changed it to(f >= 0.0 && f <= dElapsedTime) That was the only places I could tell from the algorithm where [0, 1] should be [0, elapsedTime] when dealing with elapsed time. The problem is that with that there is a lot of collision being found. Did I happen to miss something or misinterpret something?I did also modify the sphere velocity by doing "sphereVelocity = sphere->GetVelocity()  * dElapsedTime;" (I tried without doing this also)   ;  For example, here is a test case.My Sphere Origin is (1.5, 1.5, 0), with a velocity of (0, -1, 0). After you take in the time slice it is really (0, -0.5, 0).Normal dot Velocity = -0.5, which is fine, it is not traveling parallel to the plane.t0 = (-0.5-1.5)/-0.5 = 4t1 = ( 0.5-1.5)/-0.5 = 2Since t0 can not be larger then t1, they are then swapped. This will however make t0 greater than the elapsed time (2 > 0.5) and report no collision. The problem with this is that there will b collision. The sphere will then be at (1.5, 1.0, 0) and just be touching the sphere.Say for example the time step after that, the sphere origin will be (1.5, 1.0, 0) and the velocity is again (0, -0.5, 0).t0 = (-0.5-1.0)/-0.5 = 3t1 = ( 0.5-1.0)/-0.5 = 1t0 and t1 would then again need to be swapped and t0 would be greater then elapsed time.   ;Quote:Unfortunately it was due to the fact that my squaredLength function was wrong, it was defined as return (vector.x * vector.x + vector.y * vector.y + vector.z * vector.z)*2;instead ofreturn (vector.x * vector.x + vector.y * vector.y + vector.z * vector.z);Well, I suspected it was something like that.There are some lessons to be learned here about debugging. If you'd worked through the code in the same way I did (working out the values by hand, so that you could compare them to the values shown in the debugger), you likely would have noticed right away that your 'squared length' function was returning incorrect values.The main reason I went to the trouble of working through your example by hand (which took a little while) was not so much to solve your problem for you, but to show how to go about debugging complex code. Solving this kind of problem via forum posts isn't really a very efficient way of doing things, and I think once your debugging skills have improved a bit, you'll find that these sorts of errors can be isolated and identified in fairly short order.Another thing that will probably help in the future is unit testing. Basic math functions such as 'squared length' and so on should be tested in isolation and confirmed to be correct before being used in complex code such as this. If you can't rely on your basic support functions being correct, then the number of potential causes of error increases dramatically, making debugging that much harder.   ;  I agree, there was a lesson to be learned there in debugging. In fact, that lead me to correct something I believe.While trying to incorporate elapsed time I was doing [0, elapsedTime], however, isn't that unnecessary since I am already doing "sphereVelocity = sphere->GetVelocity()  * dElapsedTime;". I ran the numbers and it everything will turn out grand it seems like if I just affect the velocity right away.   