   Line Seg to Line Seg Collision Detect [Now With Screen Shot]
  Hey guys,Collision between object and terrain in my game is handled by sphere (objects) to line segment (terrain) collision detection.  This works pretty well except with fast moving objects, or poor frame rates, in which the objects can pass right over the terrain line segements in a single frame.To combat the problem I have decided to add an extra step to my collision routine:1) Define a line segment from the object's previous position to its final position.2) Check if that line segment intersects the terrain line segments3) If it does, move the object to the intersecting point and continue with regular sphere to line collision routine.I'm having trouble finding (easy to understand) info on doing line-line collision checks.  Can anyone supply some infomation/code on doing this?Also, is this how this kind of situation is handled?  It seems to have a flaw in that the line that defines the object's movement isn't actually completly accurate since the object really has a radius.  I'm fine with that sarafice, but it kind of made me think that this might be usually handled differently.Thanks!Matt[Edited by - matthughson on December 3, 2005 10:01:30 PM]
Quote:Also, is this how this kind of situation is handled?I would say 'no'; as you went on to say, there are some problems with this approach.The first thing here is that you probably don't really mean segment-segment intersection but rather segment-triangle. Segments rarely if ever actually intersect in 3d, and even then that wouldn't give you any useful information. Or perhaps I'm misunderstanding and you're actually talking about reducing it to a 2d problem...Actually, now I'm confused, as you seem to be saying that your current method tests spheres against line segment only. Is this 3d or 2d? Even with a static test, a sphere in 3d could be intersecting a triangle face without touching a line segment, so I don't see how sphere-segment tests only would work. Maybe you could clarify exactly what it is you're doing.Anyway, as you note, representing the sphere motion with a simple line segment will miss quite a few collisions. In fact, it could even leave the sphere intersecting the terrain at the end of the step. For this reason, this problem is usually addressed using a swept sphere vs. triangle algorithm, which catches all intersections and returns the contact point and normal as well. It's more complicated to code, but gives good results.   ;  Thanks for the responses guys!To clarify, the game is in 2.5D (3D graphics but most of the logic is handled in 2D).  Basically, anything that is interactive is locked to 0 on the z axis.  I have been doing all logic in 3D (ie using spheres) but I am able to make assumtions (ie. all objects are locked to the x,y plane).  Thus my line collision is really plane collision, but all the planes rotate only around the z axis.I'm no good at explaining things so here is a screen (all the collision bounds are drawn in white):Alrecenk, does that function return the point of intersection?  If so what happens when the lines do not intersect?Thanks!Matt   ;  That looks cool :) Alrecenk's function does give you the point of intersection, but I don't think that's the method you'll want to use. It always returns true because a) it considers infinite lines rather than line segments, b) it assumes the lines are never vertical, and c) it assumes the lines aren't colinear. Those may have been reasonable assumptions in the original context, but will probably not work for your case.If you want to try the approximate method of representing the sphere motion with a line segment, I'd try googling for 'line intersection' or 'line segment intersection'. There are a couple of common solutions (one treats the lines as hyperplanes, and the other expresses them in parametric form), each of which reduces to solving a 2x2 linear system. In your case you can probably just return false if the segments are parallel; if they're not parallel, the algorithms find the intersection point of the supporting lines and then check the result to see if it lies on both line segments. From there you might be able to move your sphere to the collision point and then apply your static test. As has been noted, this will miss some collisions, but it may be that this won't be noticed, and/or the static test will catch these cases.A more accurate solution would be swept circle vs. segment tests, but that might take a little more effort to code.   ;Quote:Original post by jykA more accurate solution would be swept circle vs. segment tests, but that might take a little more effort to code.Thanks for the explaination there jyk!  I've done a bit of looking into swept collision, and that seems to be exactly what I want.  I came across this function:bool PlaneSweptSphereIntersect(const Plane &inPlane, const Vector3 &inBegin, const Vector3 &inDelta,float inRadius, float &outT1, float &outT2){// If the center of the sphere moves like: center = inBegin + t * inDelta for t e [0, 1]// then the sphere intersects the plane if: -R <= distance plane to center <= Rfloat n_dot_d = inPlane.mNormal.Dot(inDelta);float dist_to_b = inPlane.GetSignedDistance(inBegin);if (n_dot_d == 0.0f){// The sphere is moving nearly parallel to the plane, check if the distance// is smaller than the radiusif (Abs(dist_to_b) > inRadius)return false;// Intersection on the entire rangeoutT1 = 0.0f;outT2 = 1.0f;}else{// Determine interval of intersectionoutT1 = (inRadius - dist_to_b) / n_dot_d;outT2 = (-inRadius - dist_to_b) / n_dot_d;// Order the resultsif (outT1 > outT2)Swap(outT1, outT2);// Early out if no hit possibleif (outT1 > 1.0f || outT2 < 0.0f)return false;// Clamp it to the range [0, 1], the range of the swept sphereif (outT1 < 0.0f) outT1 = 0.0f;if (outT2 > 1.0f) outT2 = 1.0f;}return true;}It doesn't seem that this is based on an infinate plane, so I think after this returns a collision, I would need to check if that point is on the line.  Is there a way to alter this algorthm to check a non-infinate plane?  Or is that just the nature of planes?Also, few things confuse me:1) What are outT1 and outT2?  Can I move the circle along it's forward vector by that amount to be at the point of intersection?2) The second line of the function get's the distance from the circle to the plane.  Does that mean really, it finds the closest point on the plane, and get's the signed distance to that?3) I didn't know there was such thing as signed distance.  How can something be a negative amount of space from you :SAny insight would be AMAZING!  Or if anyone has there own swept circle to line/plane method, and feels like sharing, that would be great as well!Thanks again!Matt   ;Quote:It doesn't [ does? ] seem that this is based on an infinate plane, so I think after this returns a collision, I would need to check if that point is on the line. Is there a way to alter this algorthm to check a non-infinate plane? Or is that just the nature of planes?First of all, as it seems you've already noted, the equations for intersecting a moving sphere with a plane are the same for a moving circle and a line, so you're good to go there. Also, as you note, the algorithm must be modified to handle polygons (3d) or line segments (2d).Quote:1) What are outT1 and outT2? Can I move the circle along it's forward vector by that amount to be at the point of intersection?It looks like outT1 is the time at which the circle starts intersecting the line, and outT2 is the time at which the circle stops intersecting the line. It's outT1 that you're interested in, so you would do exactly as you said, move the circle along its velocity vector by outT1.Quote:2) The second line of the function get's the distance from the circle to the plane. Does that mean really, it finds the closest point on the plane, and get's the signed distance to that?3) I didn't know there was such thing as signed distance. How can something be a negative amount of space from you :SSigned distance is sort of a way of encoding two pieces of information into one. The absolute value is the distance as we usually think of it, while the sign tells us something about the spatial relation between the two objects. In this case, a negative distance indicates that the point is in the negative halfspace (i.e. behind) the line or plane.Quote:Any insight would be AMAZING! Or if anyone has there own swept circle to line/plane method, and feels like sharing, that would be great as well!I'll try to dig up some code and post it in a bit.   ;  Here's some code:template <class T> struct Sweep2{    enum {NONE,STATIC,STATIC_INVALID_NORMAL,SWEPT};    int    type;    T t;    Vector2<T>  normal;    T distance;    int    numPoints;    Vector2<T>  points[2];};template <class T> bool Circle2Seg2(    const Vector2<T> C,   // Circle center    T r,   // Circle radius    const Vector2<T> V,   // Circle velocity    const Vector2<T> O,   // Line origin    const Vector2<T> D,   // Line direction    const Vector2<T> n,   // Line normal    T tMax,// Max time (go elsewhere)    Sweep2<T>& sweep,// Output info    bool cullBack,   // Cull if circle starts behind line    T epsilon = Math<T>::EPSILON)   // Epsilon for parallel test{Vector2<T> d = C - O;    T dn = d.Dot(n);   // Starts behind line    int sweepEndpoint;    if (dn < (T)0.0)    {   if (cullBack)  return false; // Sweep from back   if (dn < -r)   {  T Vn = V.Dot(n);  if (Vn < epsilon) return false;    T num = -dn - r;  if (num > tMax * Vn) return false;    sweep.t = num / Vn;  T s = Vector2<T>::Dot(d + sweep.t * V, D);  if (s < (T)0.0) sweepEndpoint = 0;  else if (s > D.Dot(D)) sweepEndpoint = 1;  else  { sweep.type = Sweep2<T>::SWEPT; sweep.normal = -n; sweep.numPoints = 1; sweep.points[0] = C + sweep.t * V - r * sweep.normal; return true;  }   }   // Initially intersects line   else   {  T s = d.Dot(D);  if (s < (T)0.0) sweepEndpoint = 0;  else if (s > D.Dot(D)) sweepEndpoint = 1;  else  { sweep.type = Sweep2<T>::STATIC; sweep.normal = -n; sweep.distance = r + dn; return true;  }   }    }    // Starts on or in front of line    else    {   // Sweep from front   if (dn > r)   {  T Vn = V.Dot(n);  if (Vn > -epsilon) return false;    T num = -dn + r;  if (num < tMax * Vn) return false;    sweep.t = num / Vn;  T s = Vector2<T>::Dot(d + sweep.t * V, D);  if (s < (T)0.0) sweepEndpoint = 0;  else if (s > D.Dot(D)) sweepEndpoint = 1;  else  { sweep.type = Sweep2<T>::SWEPT; sweep.normal = n; sweep.numPoints = 1; sweep.points[0] = C + sweep.t * V - r * sweep.normal; return true;  }   }   // Initially intersects line   else   {  T s = d.Dot(D);  if (s < (T)0.0) sweepEndpoint = 0;  else if (s > D.Dot(D)) sweepEndpoint = 1;  else  { sweep.type = Sweep2<T>::STATIC; sweep.normal = n; sweep.distance = r - dn; return true;  }   }    }   if (sweepEndpoint == 0)    {   sweep.normal = -n.Perp();   return (Circle2Point2(C, r, V, O, tMax, sweep));    }    if (sweepEndpoint == 1)    {   sweep.normal = n.Perp();   return (Circle2Point2(C, r, V, O + D, tMax, sweep));    }}template <class T> bool Circle2Point2(    const Vector2<T> C,   // Circle center    T r,   // Circle radius    const Vector2<T> V,   // Circle velocity    const Vector2<T> P,   // Point    T tMax,// Max time    Sweep2<T>& sweep,// Output info    T epsilon = Math<T>::EPSILON)   // Epsilon for normal validation{    Vector2<T> d = C - P;    T c = d.Dot(d) - r * r;   // Sweep    if (c > (T)0.0)    {   T b = V.Dot(d);   if (b >= (T)0.0) // Directed away  return false;T a = V.Dot(V);   T disc = b * b - a * c;   if (disc < (T)0.0) // Missed  return false;   sweep.t = -b - Math<T>::Sqrt(disc); if (sweep.t < (T)0.0) // Shouldn't happen  return false;if (sweep.t > tMax * a) // Intersection occurs after tMax  return false;   sweep.type = Sweep2<T>::SWEPT;   sweep.t /= a;   sweep.numPoints = 1;   sweep.points[0] = P;   sweep.normal = Vector2<T>::Normalize(d + sweep.t * V);    }    // Static intersection    else    {   sweep.type = Sweep2<T>::STATIC;   T l = d.Length();   if (l < epsilon) // No unique solution, normal not assigned  sweep.distance = r;   else   {  sweep.normal = d / l;  sweep.distance = r - l;   }    }    return true;}This is older code and isn't quite up to my current standards of robustness and so on, but it gets the job done, more or less. It handles both static and swept intersections, that is, if the circle is initially intersecting the segment it returns the necessary information to resolve the intersection, and if not it returns the first time (if any) at which the circle comes into contact with the segment. I don't know if this will be of any particular use to you, but feel free to ask if you have any questions about the code or how it works (you'll probably have to strip out the template stuff and substitute your own vector class if you want to integrate it with your own code).   ;  Awesome! thanks again!  It'll take me a little while to chop that into my code, but I'll let you know how it goes.Thanks again!Matt   ;  Swept circle to segment:First step is to find the closest pointThe closest point to the line is either the edge, or one of the vertices.A, B are the seg verticesP    is the circle center r    is the circle radiusTo find the closest point, first make the circle relative to one of the segment vertices, and make the other vertex relative to that one, now the problem is solved so that A=(0,0)P1=P-AB1=B-Athen find the projection of the circles center on the line segmentt = Dot(P1,B1) = |P||B|cosAPif t < 0 then the circle is on the side A of the linePA----------Band the closest point is Aif(t > Dot(B1,B1)) then the circle is on side B of the line|P||cosAP| < |B|A--------------BPthen the closest point is Bif it is inbetween, the closest point is a line coming 90 deg from the segmentthis can be found as scalarProj = t / Dot(B1, B1) closestPoint = A + t * (B-A)now that you know the closest point, you can find a vector that attaches the circle center to the closest pointseperation = P - closestPointThen check the projection of the velocity vector onto the direction of the seperation vector, if it moves farther than the lenght of the seperation vector, in the direction of the seperation vector, then there is an intersection.dir = seperation / |seperation|distance = |seperation| - rif(Dot(velocity, dir) > distance)    You have had an intersectionor to solve for time time = distance / Dot(velocity, dir)This method will give you a time, normal and point, so it's pretty good.;Quote:Original post by robert_pSwept circle to segment:First step is to find the closest pointThe closest point to the line is either the edge, or one of the vertices.A, B are the seg verticesP    is the circle center r    is the circle radiusTo find the closest point, first make the circle relative to one of the segment vertices, and make the other vertex relative to that one, now the problem is solved so that A=(0,0)P1=P-AB1=B-Athen find the projection of the circles center on the line segmentt = Dot(P1,B1) = |P||B|cosAPif t < 0 then the circle is on the side A of the linePA----------Band the closest point is Aif(t > Dot(B1,B1)) then the circle is on side B of the line|P||cosAP| < |B|A--------------BPthen the closest point is Bif it is inbetween, the closest point is a line coming 90 deg from the segmentthis can be found as scalarProj = t / Dot(B1, B1) closestPoint = A + t * (B-A)now that you know the closest point, you can find a vector that attaches the circle center to the closest pointseperation = P - closestPointThen check the projection of the velocity vector onto the direction of the seperation vector, if it moves farther than the lenght of the seperation vector, in the direction of the seperation vector, then there is an intersection.dir = seperation / |seperation|distance = |seperation| - rif(Dot(velocity, dir) > distance)    You have had an intersectionor to solve for time time = distance / Dot(velocity, dir)This method will give you a time, normal and point, so it's pretty good.Hm, that doesn't look like a complete swept circle vs. segment test to me. Have you tested it in various configurations? It seems like it would only work in a few specific cases...(Also, for what it's worth, the code sample I posted has been tested successfully so I'm pretty sure it will work as advertised.)   