Please help. 3D Intersection

jacksoncapper · #1 $Old$ January 18th, 2008, 06:21 AM

I have been trying so long to do this simple thing. I have two 3D line segments, each represented by two points. I need to know if and where these two lines intersect, but I need a method that I can implement programmatically in an algorithm. Please any help would be greatly appreciated.

CaptainBlack · #2 $Old$ January 18th, 2008, 07:56 AM

Quote:

Originally Posted by jacksoncapper $View Post$

I have been trying so long to do this simple thing. I have two 3D line segments, each represented by two points. I need to know if and where these two lines intersect, but I need a method that I can implement programmatically in an algorithm. Please any help would be greatly appreciated.

Let the points be $\bf{x}$ and $\bf{y}$ and $\bf{u}$ and $\bf{v}$ . Then the line segments are:

$\bold{l_1}=\bold{x}+ \lambda (\bold{y}-\bold{x}),\ \lambda \in [0,1]$
$\bold{l_2}=\bold{u}+ \mu (\bold{v}-\bold{u}),\ \mu \in [0,1]$

The lines intersect if there are $\lambda,\ \mu \in [0,1]$ such that:

$\bold{x}+ \lambda (\bold{y}-\bold{x})=\bold{u}+ \mu (\bold{v}-\bold{u})$

Now write these out in terms of the components and you have three
simultaneous linear equations for $\lambda$ and $\mu$ . If there is a solution
with $\lambda$ and $\mu \in [0,1]$ then the line segments intersect.

RonL

jacksoncapper · #3 $Old$ January 18th, 2008, 04:58 PM

Thankyou so much for your explaination. This [0,1] part, does that mean the value has to be between 0 and 1? Can these 3 component equations be used in a gaussian matrix to work it out programatically? Thankyou again, this is great.

CaptainBlack · #4 $Old$ January 18th, 2008, 11:38 PM

Quote:

Originally Posted by jacksoncapper $View Post$

Thankyou so much for your explaination. This [0,1] part, does that mean the value has to be between 0 and 1?

Yes, if they are outside this range the lines intersect but not in the segments
but outside one or both.

Quote:

Can these 3 component equations be used in a gaussian matrix to work it out programatically? Thankyou again, this is great.

Yes, but some work may be needed as there are three equations and two
unknowns. Any two of them should give a solution, and this shoud be
consistent with the solution when the left out equation is substituted for
one of the equations used.

RonL

jacksoncapper · #5 $Old$ January 19th, 2008, 03:42 AM

Thankyou again for taking your time to reply to my question.

I am having real difficulties in implementing this. Please if you could spend a moment on this simple problem and tell me where I'm going wrong? Say I have these two simple line segments:

Line segment 1 defined by points a( -6, 0, 0 ), and b( 4, 0, 0 ) and
Line segment 2 defined by points c( -1, -5, 0 ), and d( -1, 5, 0 ) with the origin o( 0, 0, 0 ).

The line segments would look something like this (slightly offset from the origin):

c
|
|
a------o---b
|
|
d

The point of intersection should be ( -1, 0, 0 ).

So from here I build an equation for each of the dimensions. What would these equations look like? I am doing something wrong.

Once I have the equations and they are re-arranged I should be able to use just two of the equations in a gaussian elimination to find the point of intersection? Or am I just finding the point along the lines where they do intersect (the number between 0 and 1) and I have to work from that (a whole other problem)? What would a gaussian elimination give me in this situation, the point or the [0,1] values?

Please if you could just explain where I am going wrong with my interpretation and what these equations might look like given the example.

Your help and time is appreciated much, thankyou so much.

jacksoncapper · #6 $Old$ January 19th, 2008, 03:44 AM

Sorry that diagram didn't come out correctly because of the spaces I was using to align the pipe characters. Ugh, I hope you know what I meant. Thankyou again.

CaptainBlack · #7 $Old$ January 19th, 2008, 08:19 AM

Note correction to my earlier post

RonL

CaptainBlack · #8 $Old$ January 19th, 2008, 09:11 AM

Quote:

Originally Posted by jacksoncapper $View Post$

Thankyou again for taking your time to reply to my question.

I am having real difficulties in implementing this. Please if you could spend a moment on this simple problem and tell me where I'm going wrong? Say I have these two simple line segments:

Line segment 1 defined by points a( -6, 0, 0 ), and b( 4, 0, 0 ) and
Line segment 2 defined by points c( -1, -5, 0 ), and d( -1, 5, 0 ) with the origin o( 0, 0, 0 ).

Here the equations are:

$-6+\lambda(4+6)=-1+\mu(-1+1)$

$0+\lambda (0) = -5 +\mu(5+5)$

$0+\lambda (0)=0+\mu (0)$

The last of these tell us nothing, the second tells us $\mu=1/2$ , and the first tells us that $\lambda=1/2$ .

And the point of intersection is: $(-1,0,0)$

RonL

jacksoncapper · #9 $Old$ January 21st, 2008, 04:54 AM

Ok! I have made some progress. From the above example, the gaussian matrix is returning 0.5, 0.5 meaning the two line segments intersect both at half way, which is correct as you pointed out. So now I'm not sure what to do with these two values, and how to incorporate the z axis into this whole thing... (sigh) this is so difficult... How do I convert 0.5 and 0.5 into (-1, 0, 0)?

CaptainBlack · #10 $Old$ January 21st, 2008, 05:32 AM

Quote:

Originally Posted by jacksoncapper $View Post$

Ok! I have made some progress. From the above example, the gaussian matrix is returning 0.5, 0.5 meaning the two line segments intersect both at half way, which is correct as you pointed out. So now I'm not sure what to do with these two values, and how to incorporate the z axis into this whole thing... (sigh) this is so difficult... How do I convert 0.5 and 0.5 into (-1, 0, 0)?

Choose one of the lines (lets say ${\bold l_1}$ ) and plug the appropriate parameter into
it (in the case of ${\bold l_1}$ that is $\lambda$ ), and it will give you the point of intersection.

$(-6+\lambda(4+6), 0+\lambda (0), 0+\lambda (0))=(-6+0.5 \times 10, 0,0)=(-1,0,0)$

RonL

jacksoncapper · #11 $Old$ January 22nd, 2008, 02:10 AM

Okay thanks to your advice I've worked out the x and y co-ordinates of where two 3D line segments would intersect (if they did). There only one more thing to figure out, and that is how to incorporate the z co-ordinate. Only the x and y co-ordinates could be used in the gaussian matrix (as far as I know). Please any guidance?

CaptainBlack · #12 $Old$ January 22nd, 2008, 11:59 AM

Quote:

Originally Posted by jacksoncapper $View Post$

Okay thanks to your advice I've worked out the x and y co-ordinates of where two 3D line segments would intersect (if they did). There only one more thing to figure out, and that is how to incorporate the z co-ordinate. Only the x and y co-ordinates could be used in the gaussian matrix (as far as I know). Please any guidance?

There is no need the values of $\lambda$ or $\mu$ tell you all you need about the point.

RonL

jacksoncapper · #13 $Old$ January 22nd, 2008, 04:09 PM

It's just the z co-ordinate was not in any way included in the gaussian matrix, therefore I can't see any way that the z co-ordinates played a part in determining whether the 3D lines intersect. I can extract the z value at the end just fine, but the [0,1] lambda value (and the other one) was only determined from the x and y co-ordinates. Do you know what I mean? Sorry if I am not explaining this well. I trust you know better than I do, please correct me if I'm wrong.

CaptainBlack · #14 $Old$ January 22nd, 2008, 10:24 PM

Quote:

Originally Posted by jacksoncapper $View Post$

It's just the z co-ordinate was not in any way included in the gaussian matrix, therefore I can't see any way that the z co-ordinates played a part in determining whether the 3D lines intersect. I can extract the z value at the end just fine, but the [0,1] lambda value (and the other one) was only determined from the x and y co-ordinates. Do you know what I mean? Sorry if I am not explaining this well. I trust you know better than I do, please correct me if I'm wrong.

The point of intersection of two lines is a problem with two free parameters
that have to be determined. Thus we only need two equations to find these
parameters (usually). But we have three equations, and there are three
posibilities for what that third equation does for us:

1. It can be inconsitent with the first two
2. It can be consistent and give the same result when used in place of one of the other equations
3. It can add no information about the parameters at all (which is the case here)

Hence you only need two of the three equations (as long as they are independent) to find the parameters, then the third needs to check to see that it is not inconsistent with the values found.

RonL

jacksoncapper · #15 $Old$ January 22nd, 2008, 10:50 PM

Okay I kind of understand that, however in the example I gave, z was set to 0 in both points in both line segments because I wanted to make it as simple as possible. When I implement this solution the values for the lines could be anything.

So what you are suggesting is that I perform the gaussian matrix elimination twice, once with say x and y, and the second time with say y and z.

If both turn out to be consistent with each other, the point of intersection has been found. If they turn out to be inconsistent, there is NO point of intersection.

Is this correct?

Thankyou once again for your time.