Sign in to follow this  
RonHiler

Error in my line intersection determination routine

Recommended Posts

Hey all, I wrote a routine which takes two line segments in the form of four points in 3D space, and it returns the intersection point, if any. It seems to work fine if the lines are coincident or parallel. However, if the lines are non-parallel (whether they intersect or not) it is giving me bad values, and I can't figure it out. The theory is: 1) I convert the four points into two parametric equations P1 + T1D1 P2 + T2D2 2) I check for parallel or coincident lines by taking the cross product of (D1xD2) 3) If not parallel or coincident, I calculate T1 and T2, using the equation T1 = [((P2 - P1)xD2).(D1xD2)]/[(Length(D1xD2))^2] T2 = [((P2 - P1)xD1).(D1xD2)]/[(Length(D1xD2))^2] 4) I check T1 and T2 to be between 0 and 1. If not, then the intersection point is not on the line segment, and the routine returns false. 5) I plug T1 and T2 back into the parametric equation to produce two points. If they are the same point, the lines intersect, otherwise they do not (skew). That's the theory. Here is the implementation:
//---------------------------------------------------------------------------
bool TriangulatorClass::LineSegmentIntersect(unsigned int Vertex1, unsigned int Vertex2, unsigned int Vertex3, unsigned int Vertex4, unsigned int *IntersectionPoint)
    {
    VertexStruct Direction1;
    VertexStruct Direction2;
    VertexStruct Cross;
    VertexStruct Cross1;
    VertexStruct Point1;
    VertexStruct Point2;
    double Dot1;
    double Length;
    double t1;
    double t2;

    //convert the four vertexes into two line segments (parametric equation)
    //  (we just need the direction, V1 and V3 will serve as the start points)
    Direction1.Position = InputVertex[Vertex2].Position - InputVertex[Vertex1].Position;
    Direction2.Position = InputVertex[Vertex4].Position - InputVertex[Vertex3].Position;

    D3DXVec3Cross(&Cross.Position, &Direction1.Position, &Direction2.Position);
    Length = D3DXVec3Length(&Cross.Position);
    if (IsEqual(Length, 0.0) == true)
        {
        //the lines are either parallel or coincident. 
        ....omitted code, this seems to work okay...
        }

    //the lines either intersect or they are skew. Determine the closest approaching points
    // first point
    D3DXVec3Cross(&Cross1.Position, &(InputVertex[Vertex3].Position - InputVertex[Vertex1].Position), &Direction2.Position);
    Dot1 = D3DXVec3Dot(&Cross1.Position, &Cross.Position);
    t1 = Dot1/(Length * Length);
    //if we are at either end point, return true with the endpoint as the intersection point
    if (IsEqual(t1, 0.0f))
        {
        *IntersectionPoint = Vertex1;
        return true;
        }
    if (IsEqual(t1, 1.0f))
        {
        *IntersectionPoint = Vertex2;
        return true;
        }
    //boundary check to make sure the calculated point is still on our line segement
    if (t1 < 0.0f || t1 > 1.0f)
        return false;
    Point1.Position = InputVertex[Vertex1].Position + t1 * Direction1.Position;

    //second point
    D3DXVec3Cross(&Cross1.Position, &(InputVertex[Vertex3].Position - InputVertex[Vertex1].Position), &Direction1.Position);
    Dot1 = D3DXVec3Dot(&Cross1.Position, &Cross.Position);
    t2 = Dot1/(Length * Length);
    if (IsEqual(t2, 0.0f))
        {
        *IntersectionPoint = Vertex3;
        return true;
        }
    if (IsEqual(t2, 1.0f))
        {
        *IntersectionPoint = Vertex4;
        return true;
        }
    //boundary check to make sure the calculated point is still on our line segement
    if (t2 < 0.0f || t2 > 1.0f)
        return false;
    Point2.Position = InputVertex[Vertex3].Position + t2 * Direction2.Position;

    //check the distance between the two points
    Length = D3DXVec3Length(&(Point1.Position - Point2.Position));
    if (IsEqual(Length, 0.0f) == true)
        {
        AppendVertex(Point1.Position.x, Point1.Position.y, Point1.Position.z);
        *IntersectionPoint = InputVertex.size()-1;
        return true;
        }

    //distance >0. The two lines must be skew
    return false;
    }

IsEqual() is a routine that deals with equality between doubles and floats using tolerances and all that :) The problem is T1 and T2 are coming back as 0 or 1 when they ought not to. I don't see what I'm doing wrong. Probably something stupid. Anyone see anything bad. Is there something in my theory that is off, perhaps? Or just a dumb typo somewhere? Thanks guys, I really appreciate any help. This one is stumping me.

Share this post


Link to post
Share on other sites
One of the problems you're going to have is that two lines in 3D are very "rarely" going to intersect, since there are so many different ways they can "go around" each other. Mathematically speaking, if we establish an equality between the parametric forms of the lines and convert it into matrix form, you end up with a 3x2 matrix. It isn't invertible because it's tall, however that doesn't necessarily mean there isn't a solution to the equation.

You can use matrices for this problem if you want, but the gist of it is that we project the lines down into 2D and solve for the intersection there. You then plug in the solution and see if the coordinates match for the third dimension, and if they do you have an intersection. The matrix method actually does this check before the projection by detecting linear dependencies, but the end result is the same.

In summary, the process might go something like:
0) Check for degenerate cases (parallel, coincident)
1) Take the cross-product of the two directions. The largest component of the cross-product if the dimension you should ignore.
2) Solve the intersection in 2D using the other two dimensions.
3) Make sure your solutions are within the valid range (usually [0,1])
4) Plug the results back into the dimension you removed, and if the coordinates match you have an intersection.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zipster
but the gist of it is that we project the lines down into 2D and solve for the intersection there.


I suggest instead that the distance between the two 3D lines be computed. If this distance is smaller than a user-prescribed epsilon, conclude that the lines intersect.

Share this post


Link to post
Share on other sites
Well, that's what I was doing! :)

Actually, I think I may have figured it out (just before I ripped it all out). My assumption that if T1 == 0 or T1 == 1 then the lines *must* intersect at an endpoint (and thus end the routine early) was completely wrong. That's why I was getting false positives. I think I also did actually have a derivitization error when I came up with the formula for T2, so I changed that somewhat.

I've fixed it to always compute the resulting points and calculate the difference between them, regardless of the results of T1 or T2. I haven't tested every possible case, but preliminarily at least, it seems to be behaiving much better.

One minor question I have. I'm testing T1 and T2 for <0 or >1 and returning false if so. Do the distance vectors (D1 and D2) in the parametric equation need to be unit vectors for that to work? I wasn't quite sure about that. I can easily normalize them if so.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave Eberly
Quote:
Original post by Zipster
but the gist of it is that we project the lines down into 2D and solve for the intersection there.


I suggest instead that the distance between the two 3D lines be computed. If this distance is smaller than a user-prescribed epsilon, conclude that the lines intersect.

Well in order to find the distance you'd need the two points, which you would either have to obtain through something like the 2D intersection method I mentioned or the projection-based method I think you're proposing. Either way it's the same results. I was actually going to suggest he find the two closest points, but that's a process I think of being matrix-based (at least for arbitrary dimension) so I chose to go with something else.

Share this post


Link to post
Share on other sites
Guys, no reason to argue over theory, the one I used is quite simple and it seems to work. Solving the equation

P1 + T1D1 = P2 + T2D2

for T1 and T2 will give you the two closest points on the lines (of infinite length). That's why I was calculating them, then plugging them back into the equations to deterimine those two points (I know it looks like two unknowns in one equation, but you can cancel out one of them by taking the cross product of D1 or D2 on both sides, i.e.

(T1D1) x D2 = (P2 - P1 + T2D2) x D2
(T1D1) x D2 = (P2 - P1) x D2 + (T2D2 x D2)
(T1D1) x D2 = (P2 - P1) x D2 + (T2(0))
(T1D1) x D2 = (P2 - P1) x D2

Then it's just solving for T1, which turns out to be
T1 = [((P2 - P1)xD2).(D1xD2)]/[(Length(D1xD2))^2]

I didn't entirely make this up on my own, much of it I got off the web somewhere, though I cannot tell you where now, and it underwent much modification)

If the lines are skew (i.e. non planar), the distance between those points is >0 (no intersection), return false. If they lie on the same plane, then there will be a single intersection point (unless they are coincident or parallel, but I already took steps to check those cases earlier).

If there is an intersetion point, and T1 and T2 are within the range of [0,1], then the line segments intersect, return true. If they don't fall within that range, then the intersection point is beyond the end points of the segments, return false.

That last sentence is the only one I'm a bit foggy on. That may only be true if the D1 and D2 parts of the equations are unit vectors. Not entirely sure on that one.

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