Sign in to follow this  
matthughson

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

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by jyk
A 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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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
r is the circle radius

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)
You have had an intersection

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 this post


Link to post
Share on other sites
Quote:
Original post by robert_p
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
r is the circle radius

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)
You have had an intersection

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.
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by robert_p
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 =).
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by matthughson
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?
Right on both counts. However, I'm still not convinced that that algorithm is correct.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by matthughson
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?
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this