# Line Seg to Line Seg Collision Detect [Now With Screen Shot]

## Recommended Posts

matthughson    588
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 segments 3) 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]

##### Share on other sites
jyk    2094
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.

##### Share on other sites
matthughson    588
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

##### Share on other sites
jyk    2094
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.

##### Share on other sites
matthughson    588
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 <= R	float 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 radius		if (Abs(dist_to_b) > inRadius)			return false;		// Intersection on the entire range		outT1 = 0.0f;		outT2 = 1.0f;	}	else	{		// Determine interval of intersection		outT1 = (inRadius - dist_to_b) / n_dot_d;		outT2 = (-inRadius - dist_to_b) / n_dot_d;		// Order the results		if (outT1 > outT2)			Swap(outT1, outT2);		// Early out if no hit possible		if (outT1 > 1.0f || outT2 < 0.0f)			return false;		// Clamp it to the range [0, 1], the range of the swept sphere		if (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 :S

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!

Thanks again!
Matt

##### Share on other sites
jyk    2094
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 :S
Signed 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.

##### Share on other sites
jyk    2094
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).

##### Share on other sites
matthughson    588
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

##### Share on other sites
robert_p    157
Swept circle to segment:

First step is to find the closest point
The closest point to the line is either the edge, or one of the vertices.

A, B are the seg vertices
P is the circle center

To 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-A
B1=B-A

then find the projection of the circles center on the line segment
t = Dot(P1,B1) = |P||B|cosAP

if t < 0 then the circle is on the side A of the line

P A----------B
and the closest point is A

if(t > Dot(B1,B1)) then the circle is on side B of the line
|P||cosAP| < |B|

A--------------B P
then the closest point is B

if it is inbetween, the closest point is a line coming 90 deg from the segment
this 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 point

seperation = P - closestPoint

Then 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| - r

if(Dot(velocity, dir) > distance)

or to solve for time
time = distance / Dot(velocity, dir)

This method will give you a time, normal and point, so it's pretty good.

##### Share on other sites
jyk    2094
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 lineP A----------Band the closest point is Aif(t > Dot(B1,B1)) then the circle is on side B of the line|P||cosAP| < |B|A--------------B Pthen 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.)

##### Share on other sites
robert_p    157
The algorithm has been tested, and used in alot of small games/demos that I have written, always seemed to work fine. Of course you need to add a static intersection test, and I dont have the code on this computer im typing on so I may have missed some details.

It may be a little wierd because I derived it myself, but it always worked. But if you see any particular 'holes' in the code, I sure would like to know because I use it pretty often =).

btw I have never tested this in 3d before. 2d only.

Edit: also above velocity is poorly named, it should be called displacement.

##### Share on other sites
jyk    2094
Quote:
 Original post by robert_pIt may be a little wierd because I derived it myself, but it always worked. But if you see any particular 'holes' in the code, I sure would like to know because I use it pretty often =).
Yeah, looking over it more carefully, I have to admit that I still don't get it. I drew up a little diagram illustrating a possible failure case:

It may be that it's always seemed to work for you because the displacements have been small and therefore the error has been minimal. But you might try testing it with something like the above illustration, where the circle displacement is large relative to the object sizes, and clearly does not bring the circle into intersection with the segment. Anyway, it's possible that I'm misunderstanding your algorithm, but my guess is that with some more rigorous testing you may find that there are some problems with it.

##### Share on other sites
matthughson    588
Well I can implement your algorithm pretty easily robert (already doing the closest point on a line stuff) so I'll let you know if it works. The only thing I don't understand is this:
dir = seperation / |seperation|distance = |seperation| - r

Would the first line be the the normalized vector for the center of the circle to the closest point on the line?

And the next line... umm... my lack of math experiece is showing. I take it |*| means magnitude? So mag minus the circles radius?

Matt

##### Share on other sites
jyk    2094
Quote:
 Original post by matthughsonWould the first line be the the normalized vector for the center of the circle to the closest point on the line?And the next line... umm... my lack of math experiece is showing. I take it |*| means magnitude? So mag minus the circles radius?
Right on both counts. However, I'm still not convinced that that algorithm is correct.

##### Share on other sites
matthughson    588
Quote:
Original post by jyk
Quote:
 Original post by matthughsonWould the first line be the the normalized vector for the center of the circle to the closest point on the line?And the next line... umm... my lack of math experiece is showing. I take it |*| means magnitude? So mag minus the circles radius?
Right on both counts. However, I'm still not convinced that that algorithm is correct.

Hmm yeah, after my first pass at using it, it isn't working. But it is acting really crazy, like colliding with walls on the other side of the level, so I can't image that would be an unnoticible flaw, so I'm going to assume I'm doing something wrong for now.

Matt

##### Share on other sites
matthughson    588
Did a simplified test, in which the level has only 1 collision line. With this it seems that the problem is within a certain distance of the line, the circle will always return a collision if it is moving away from the line.

That seems like the basic idea of the solution, it just doesn't seem to verify that the circle has passed over the line in the process.

Here is my code (maybe I just did something stupid):

	D3DXVECTOR3 v3LineStart((*it)->m_rgfData[LINE_POSA_X], (*it)->m_rgfData[LINE_POSA_Y], (*it)->m_rgfData[LINE_POSA_Z]);	D3DXVECTOR3 v3LineEnd((*it)->m_rgfData[LINE_POSB_X], (*it)->m_rgfData[LINE_POSB_Y], (*it)->m_rgfData[LINE_POSB_Z]);	D3DXVECTOR3 v3ClosestPoint = closestPointOnLine(v3LineStart, v3LineEnd, v3PrevPos);	//seperation = P - closestPoint	D3DXVECTOR3 v3Seperation = v3PrevPos - v3ClosestPoint;	//dir = seperation / |seperation|	D3DXVECTOR3 v3Direction;	D3DXVec3Normalize(&v3Direction, &v3Seperation);	//distance = |seperation| - r	float fDistance = D3DXVec3Length(&v3Seperation) - m_boundsCol.m_rgfData[SPHERE_RAD];	//if(Dot(velocity, dir) > distance)			D3DXVECTOR3 v3NewVel = m_orientation.translation - v3PrevPos;	float fDot = D3DXVec3Dot(&m_v3Vel, &v3Direction);	if(fDot > fDistance)	{		pDbgMsg->addConstantMessage("COLLISION!");		//m_orientation.translation = v3ClosestPoint;	}

Does that result sound like what you predicted, jyk?

Matt

##### Share on other sites
jyk    2094
Before deciding whether or not robert's algorithm works, there are a couple of things that should probably be cleared up. One thing that confuses me about his original explanation is the line:
seperation = P - closestPoint
This is the vector from the closest point to P. So if the circle were moving towards the segment the dot product with the velocity would actually be negative, whereas the conditional robert gave assumes it's positive. Maybe robert can explain this, but in the meantime I'd change the line:
D3DXVECTOR3 v3Seperation = v3PrevPos - v3ClosestPoint;
To:
D3DXVECTOR3 v3Seperation = v3ClosestPoint - v3PrevPos;
The only other thing I saw was the line:
D3DXVECTOR3 v3NewVel = m_orientation.translation - v3PrevPos;
I'm not sure if this is wrong, or whether the terminology is just off. First of all, an orientation doesn't really 'have' a translation per se, so I'm not sure what the translation as a member variable of m_orientation means. Also, a translation is a vector, not a point, so mathematically this doesn't make much sense.

My guess though is that m_orientation.translation is meant to be the new position of the circle, and therefore this equates to velocity = newPos - oldPos, which is correct, terminology issues aside.

So given the above changes/questions, your code does appear to implement robert's proposed method. And it should work, more or less, in certain cases. Once you've got it working, though, you might try a scenario like the one in my diagram; it's not immediately clear to me how the algorithm can possibly handle this situation correctly.

##### Share on other sites
robert_p    157
Sorry, I did post code kinda off, gave you something like the static test. You do need to do a circle circle test for the ends, the quadratic minimization method of jyk works good.

##### Share on other sites
matthughson    588
Heh... so after all this I just ended up doing it my own way :|

I just translate the circle along the object's forward vector, jumping by its radius each iteration. Not perfect, and pretty slow in some situations, but the important part is I actually understand it [wink]

Thanks for all the help guys!
Matt