   accurate sphere triangle collide detection
    i want to calcuate the accurate time when a sphere collide with a triangle, with the input ( sphere position, sphere radius, triangle''s 3 points, sphere''s speed vector).  i''ve searched for some time but all i got are things like "are they intersected(collided)" , not "when will they intersected(collided)". so i hope to get help here.  thanks in advance! 
  This will take some time to explain. So, I will only explain colliding a sphere with a plane. Finding whether the collision is in the triangle will be easy anyway.First take the plane normal (pointing towards the sphere) and subtract that from the center of the sphere. Now before you do this, you should have the length of the normal vector set to equal the radius of the sphere. Subtracting gives you the point on the sphere that will collide with the plane. You follow the velocity of the sphere from this point until it collides with the plane.Ray-plane intersections are easy to do. Here is my Ray-Plane intersection code:double RayPlaneIntersect(const Vector3D &PlaneOrgin, const Vector3D &PlaneNormal, const Vector3D &RayOrgin, const Vector3D &RayVector){double Dist=Dot(PlaneNormal,RayOrgin)-Dot(PlaneNormal,PlaneOrgin);// Perpendicular distance from RayOrgin to the planedouble Cosine=Dot(PlaneNormal,RayVector.unit());// Cosine of angle between normal vector and intersecting vectorif(Cosine==0)// If the intersecting vector is parallel to the planereturn -1.0;// There is no collision, so return a negative numberreturn (-Dist/Cosine);// Otherwise return the distance along RayVector to plane}  This is the distance from the point on the sphere to the point on the plane. Now just figure out how long it took to reach that point (time=distance/velocity).   --------------------------------------I am the master of stories.....If only I could just write them down...   [edited by - Nathaniel Hammen on February 11, 2004 2:50:24 PM];  it's quite complicated, but in general, here it goes. doing a swept sphere / triangle intersection test cam be decomposed into 3 parts.find the intersection of a ray (from sphere centre, in direction of the sphere velocity) with the triangle plane, pushed up by the sphere radius. once you have the intersection point and time, you check if the intersection point is in the triangle. if it is, then you have the time of collision.if not, then you calculate the time of collision of the sphere against each edges, and against each vertices. take the minimum time, and you have the time of collision.first, sphere collision with triangle plane.if you don't have the plane normal, then N = ((V1 - V0) x (V2 - V1)).Normalise();also, P = V0, or V1 or V2, it doesn't matter. //-----------------------------------------// sphere [C, V, r]// plane [O, N]// equation of ray : P = C + V.t, 0 <= t <= 1// equation of plane : (P - O) . N = r//// replace P from [eq1] in [eq2]// => t = (r - (C - O) . N) / (V . N)//-----------------------------------------float SpherePlaneCollide(const Vector& C, const Vector& V, float r, const Vector& N, const Vector O, float tmax){//-----------------------------------------// setup the equation//-----------------------------------------Vector D = C - O;float denom = V * N;float numer = r - D * N;//-----------------------------------------// sphere moving away from plane, don't check// also, sphere is under the triangle, don;t check//-----------------------------------------if (denom > -0.0000000001f || numer < -r)return -1.0f;//-----------------------------------------// sphere intersecting the plane already//-----------------------------------------if (numer < 0.0f)return 0.0f;float t = numer / denom;if (t < 0.0f || t > tmax)return -1.0f;return t;} [edited by - oliii on February 12, 2004 4:47:35 AM];  here is the general routine, you need the PointInTriangle() test, and the and SphereEdge() tests. This is relatively easy, there are loads of references in the forums.  bool PointInTriangle(const Vector& P, const Vector& N, const Vector* V){int i = 2;int j;for(j = 0; j < 3; i = j, j ++){Vector E = V[j] - V[i];Vector En; En.Cross(N, E);Vector D = P - V[i];if (D * En < 0.0f)return false;}return true;}//-------------------------------------// test if a triangle and sphere collide, and at what time// tmax is the maximum time of collision, // tcoll is the time of collision, Ncoll is normal of collision//-------------------------------------bool SphereTriangleCollision(const Vector& C, const Vector& V, float r, const Vector* W, float &tcoll, Vector& Ncoll, Vector& Ccoll){//-------------------------------------// calculate triangle normal//-------------------------------------Vector E = W[1] - W[0];Vector F = W[2] - W[1];Vector N; N.Cross(E, F);N.Normalise();//-------------------------------------// find time of collision of sphere with triangle plane//-------------------------------------float t = SpherePlaneCollide(C, V, r, N, W[0], tcoll);//-------------------------------------// time not in valid range, return no collision//-------------------------------------if (t < 0.0f)return false;//-------------------------------------// calculate the point of collision of sphere with plane//-------------------------------------Vector P = C + V * t;//-------------------------------------// if point in triangle, then we found the time of collision//-------------------------------------if (PointInTriangle(P, N, W)){tcoll = t;Ncoll = N;Ccoll = P;return true;}//-------------------------------------// else, test each edges, and their vertices as well//-------------------------------------bool bCollided = false;bCollided |= SphereEdgeCollide(C, V, r, W[0], W[1], true, tcoll, Ncoll, Ccoll);bCollided |= SphereEdgeCollide(C, V, r, W[1], W[2], true, tcoll, Ncoll, Ccoll);bCollided |= SphereEdgeCollide(C, V, r, W[2], W[0], true, tcoll, Ncoll, Ccoll);return bCollided;}  [edited by - oliii on February 12, 2004 4:46:29 AM];  for edge collisiosn, edges can be split in 3 parts. the start vertex, the edge itself, and the end vertex. doing a sphere vs vertex collision is like doing a ray versus a vertex with radius equal to the shere radius. Equally, doing a ray versus an edge is equivalent to doing a ray versus a cylinder (an edge with a radius equal to the sphere radius).  //-------------------------------------------------------------// vertex [O] vs swept sphere [C, V, r]// ray equation : P = C + V.t, 0 <= t <= tmax// sphere equation : (P - O)^2 = r^2// substitute P in [eq2]// => ((C - O) + V.t)^2 = r^2//// second order equation in the form a.t^2 + b.t + c = 0, where :// a = V.V// b = 2 * V.(C - O)// c = (C - O) . (C - O) - r*r//// solve for t using root solver :// => d = b*b - 4*a*c// t0 = (-b - sqrt(d)) / (2 * a)// t1 = (-b + sqrt(d)) / (2 * a)//-------------------------------------------------------------float Solve2ndOrderForCollision(float a, float b, float c, float tmax){//---------------------------------------------// basic equation solving//---------------------------------------------float d = b*b - 4*a*c;//---------------------------------------------// no root//---------------------------------------------if (d < 0.0f)return -1.0f;//---------------------------------------------// calculate two possible roots//---------------------------------------------d = sqrt(d);float one_over_two_a = 1.0f / (2.0f * a);float t0 = (-b - d) * one_over_two_a;float t1 = (-b + d) * one_over_two_a;//---------------------------------------------// return the first positive root//---------------------------------------------if (t0 < t1){float temp = t0; t0 = t1; t1 = temp;}if (t1 < 0.0f || t0 > tmax)return -1.0f;if (t0 > 0.0f)return t0;return t1;}//-------------------------------------------------------------// vertex [O] vs swept sphere [C, V, r]// ray equation : P = C + V.t, 0 <= t <= tmax// sphere equation : (P - O)^2 = r^2// substitute P in [eq2]// => ((C - O) + V.t)^2 = r^2//// second order equation in the form a.t^2 + b.t + c = 0// a = V.V// b = 2 * V.(C - O)// c = (C - O) . (C - O) - r*r//-------------------------------------------------------------bool SphereVertexCollide(const Vector& C, const Vector& V, float r, const Vector& O, float& tcoll, Vector& Ncoll, Vector& Ccoll){//---------------------------------------------// setup the equation//---------------------------------------------Vector D = C - O;float a = V * V;float b = 2.0f * (D * V);float c = D * D - r*r;//---------------------------------------------// if b > 0, the objects are separating, so don't collide//---------------------------------------------if (b > 0.0f)return false;//---------------------------------------------// if c < 0, we have an overlap at t = 0.//---------------------------------------------if (c < 0.0f){tcoll = 0.0f;Ncoll = D;Ncoll.Normalise();return true;}//---------------------------------------------// find the intersection//---------------------------------------------float t = Solve2ndOrderForCollision(a, b, c, tcoll);//---------------------------------------------// no intersection//---------------------------------------------if (t < 0.0f)return false;//---------------------------------------------// calculate normal at time of collision//---------------------------------------------Vector Pcoll;tcoll = t;Ccoll = C + V * t;Ncoll = (Ccoll - O);Ncoll.Normalise();return true;}//-------------------------------------------------------------// Edge [E, F] vs swept sphere [C, V, r]// ray equation : P = C + V.t, 0 <= t <= tmax// Cylinder equation : ((P - O) x L)^2 = r^2// where L = (F - E) / |F - E|, O = E// substitute P in [eq2]// => ((C - O) x L + (V x L).t)^2 = r^2//// second order equation in the form a.t^2 + b.t + c = 0// a = (V x L) . (V x L)// b = 2 * (V x L).((C - O) x L)// c = ((C - O) x L) . ((C - O) x L) - r*r//-------------------------------------------------------------bool SphereEdgeCollide(const Vector& C, const Vector& V, float r, const Vector& E, const Vector& F, bool bTestVertices, float& tcoll, Vector& Ncoll, Vector& Ccoll){//---------------------------------------------// setup the equation//---------------------------------------------Vector D = C - E;Vector L = F - E;float l2 = L * L;Vector VxL; VxL.Cross(V, L);Vector DxL; DxL.Cross(D, L);float a = (VxL * VxL);float b = (DxL * VxL) * 2.0f;float c = (DxL * DxL) - (r*r * l2);//---------------------------------------------// if b > 0, the objects are separating, so don't collide//---------------------------------------------if (b > 0.0f)return false;//---------------------------------------------// if c < 0, we have an overlap at t = 0 with infinite// line pasing through segment. check if we need// to test for end points collision, else// return a collision at time t = 0 with edge//---------------------------------------------float t = 0.0f;if (c > 0.0f){//---------------------------------------------// find the intersection//---------------------------------------------t = Solve2ndOrderForCollision(a, b, c, tcoll);}//---------------------------------------------// no intersection//---------------------------------------------if (t < 0.0f)return false;//---------------------------------------------// calculate normal at time of collision//---------------------------------------------Vector Pcoll = C + V * t;//---------------------------------------------// how far are we on the edge at time of collision//---------------------------------------------D = (Pcoll - E);float l = (D * L) / l2;//---------------------------------------------// we are before the start vertex, so need to // test with start vertex//---------------------------------------------if (l < 0.0f){if (bTestVertices)return SphereVertexCollide(C, V, r, E, tcoll, Ncoll, Ccoll);elsereturn false;}//---------------------------------------------// we are after the end vertex, so need to // test with end vertex//---------------------------------------------if (l > 1.0f){if (bTestVertices)return SphereVertexCollide(C, V, r, F, tcoll, Ncoll, Ccoll);elsereturn false;}//---------------------------------------------// we collided with edge. setup the collision//---------------------------------------------tcoll = t;Ncoll = D - L * l;Ncoll.Normalise();Ccoll = Pcoll;return true;} [edited by - oliii on February 12, 2004 4:46:01 AM];  thanks a lot! that''s exactly what i need. :-) ;  I need to test the code. It''s not tested, but compiles. I''ll post an update once I got it up to scratch ;  Incidently, you only need to do the vertex check if your edge checks fail i.e. that collision detection with ellipsoids paper that''s around is slightly wrong. This will make things slightly faster and slightly simpler.The whole method is explained very clearly and completely in the "Real Time Rendering" book. However, when you implement it be very careful about numerical accuracy (speaking from experience!). ;  Actually, if you do your edge check with a capsule instead of a cylinder, you don''t even need to do a vertex check at all.   --------------------------------------I am the master of stories.....If only I could just write them down... ;  I've been trying to implement the swept sphere intersection with edge for sometimes now, for my implementation based on the cylinder ray idea described above, the sphere alway register a hit when it is still some distance away.I had look at the code above, I think V for the sphere is meant to be the velocity per second for the sphere and tmax would be the timestep. please tell me if I am wrong. This is slightly different than the way mine function is called. I call it with the displacement of the sphere and ask it to  return the point of collision on the line and collision normal on the sphere surface.It could also be that I normalised vectors when I shouldn't or vice versa.I've had similar problem when I tried to implement the peroxide version of the algorithm.It would be great if the returning t value is the actual distance of the centre of the sphere at the start to where it end up when it actually collided with line. How would you modify the alogrithm to achieve this?thanks for any help   [edited by - shaobohou on February 12, 2004 12:32:14 PM]