gdalgorithms-list

Re: [Algorithms] 3d Lines Intersection

[Sam K. <sa...@ip...>]

Albert,

It seems to me the chances of two 3d lines intersecting in space is
*enormously slim* exept in a few obvious situations, like two lines crossing
each other from the corners of a cube etc.

It might help if you outlined your reasons for wanting to do this.

sam



>Hi,
>
>Is there a good algo for finding a point of intersection between two *3D
lines*?
>The lines is specified by their point (x,y,z) and their direction
(dx,dy,dz)
>
>I've searched the web, but all of them seems to explain about 2D lines
intersection only.
>
>Thanks in advance.
>Albert J
>
>
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Albert_J [mailto:Alb...@te...]
> 
> Is there a good algo for finding a point of intersection 
> between two *3D lines*?
>

Somewhere there might be something already coded.

>
> The lines is specified by their point (Y,y,z) and their 
> direction (dY,dy,dz)
> 

I'm assuming you meant (X,Y,Z) and (DX, DY, DZ).

>
> I've searched the web, but all of them seems to eYplain about 
> 2D lines intersection only.
> 

That's because not many people need it.  You also will not find it in
analytical geometry books.

Here is the math:

PROBLEM:
2 Lines: a and b where they intersect at point (X,Y,Z)

DEFINITIONS:
Line a is: Known point (Xa, Ya, Za) with "normalized" direction numbers
(DXa, DYa, DZa)
with Ta = distance between known point on line and the intersection
Ta = sqr[ (Xa - X)^2 + (Ya - Y)^2 + (Za - Z)^2 ]

Line b is: Known point (Xb, Yb, Zb) with "normalized" direction numbers
(DXb, DYb, DZb)
with Tb = distbnce between known point on line bnd the intersection
Tb = sqr[ (Xb - X)^2 + (Yb - Y)^2 + (Zb - Z)^2 ]

SOLUTION:
If (X,Y,Z) is on both lines then the solution can be:

Tb = (Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa)/(Dxb * Dza - Dzb)
and
Ta = (Zb + DZb * Tb - Za)/DZa

Plug Ta and Tb into 1, 2, and 3 below (use tolerances to account for
rounding) to see if they intersect.

If they do then plug Ta into:

X = Xa + DXa * Ta, Y = Ya + DYa * Ta, Z = Za + DZa * Ta

PROOF:

1. Xa + DXa * Ta = Xb + DXb * Tb
and
2. Ya + DYa * Ta = Yb + DYb * Tb
and
3. Za + DZa * Ta = Zb + DZb * Tb

That's three equations with 2 unknowns.

My preferred method is to solve for Ta in equation 3:

4. Ta=(Zb + DZb * Tb - Za)/DZa

Then solve for Tb with the first equation:

5. Tb = (Xa + DXa * Ta - Xb)/DXb

Then substitue Ta in 4 into Ta in 5:

6. Tb = [Xa + DXa * (Zb + DZb * Tb - Za)/DZa - Xb]/DXb

Then solve for Tb:

Tb * DXb = Xa + DXa * (Zb + DZb * Tb - Za)/DZa - Xb
Tb * DXb * DZa = Xa * Dxa * Dza + DXa * Zb + DZb * Tb - Za - Xb * DZa
Tb * Dxb * Dza - Tb * DZb = Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa
Tb (Dxb * Dza - Dzb) = Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa

7. Tb = (Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa)/(Dxb * Dza - Dzb)

Plug Tb into equation 1.

Then use Ta and Tb in equation 2...if it's true then they intersect at
(X,Y,Z).

Steve

Re: [Algorithms] 3d Lines Intersection

[<ro...@do...>]

Steve Wood  wrote:

>> -----Original Message-----
>> From: Albert_J [mailto:Alb...@te...]
>> 
>> Is there a good algo for finding a point of intersection 
>> between two *3D lines*?
>>
>
>Somewhere there might be something already coded.
>

But the explanation of the math behind an algorithm, or maybe a couple
of different algorithms, is a lot more informative than a pointer to
somone else's code, isn't it?


>> I've searched the web, but all of them seems to eYplain about 
>> 2D lines intersection only.
>> 
>
>That's because not many people need it. 

Yeah, right, tell that to an air traffic controller.  
Or even a game programmer. 

> You also will not find it in
>analytical geometry books.
>

And in how many such books have you searched?  And don't forget to
check the exercises.

Re: [Algorithms] 3d Lines Intersection

[<ro...@do...>]

Steve Wood  wrote:


>Here is the math:
>

This is to advise the readers of this thread that they need not fret
if they could not follow the ensuing mess, and they ought not waste
any more time on it if they are still trying.  Whatever it might look
like at first glance, on close inspection it is certainly not anything
that could properly be called math.

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Jim Offerman [mailto:j.o...@in...]
> 
> - calculate (x, y) intersection (result <x1, y>)
>

OK, the intersection of the two lines as projected onto the x,y coordinate
plane.

>
> - calculate (x, z) intersection (result <x2, z>)
>

OK, the intersection of the two lines as projected onto the x,z coordinate
plane.

>
> - if (x1 == x2) the lines intersect at <x1, y, z>
>

That sounds right...good work.

> 
> Of the top of my head I can't say whether this algorithm is 
> 100% correct (I
> am not a math guy...), but, if properly implemented, it will 
> certainly be
> fast and provide at least a reasonable estimation.
> 
> Jim Offerman
> 
> Innovade
> - designing the designer
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] 3d Lines Intersection

[<ro...@do...>]

Steve Wood  wrote:

>> -----Original Message-----
>> From: Jim Offerman [mailto:j.o...@in...]
>> 
>> - calculate (x, y) intersection (result <x1, y>)
>>
>
>OK, the intersection of the two lines as projected onto the x,y coordinate
>plane.
>
>>
>> - calculate (x, z) intersection (result <x2, z>)
>>
>
>OK, the intersection of the two lines as projected onto the x,z coordinate
>plane.
>
>>
>> - if (x1 == x2) the lines intersect at <x1, y, z>
>>
>
>That sounds right...good work.
>

Unfortunately, there is no logical basis for it and it is quite wrong.

Re: [Algorithms] 3d Lines Intersection

[Peter D. <pd...@mm...>]

[Jim Offerman's algorithm snipped]

> Unfortunately, there is no logical basis for it and it is quite wrong.

It is clearly wrong, but it does have logical basis.

If the lines intersect, there exists a plane where their projections
intersect at the same point (in the {s, t} sense.)

The problem is that the XY and XZ coordinate planes may not have this
property.

A plane that does have this property is the plane formed by the two
direction vectors, d1 and d2 (in fact they describe a family of planes, any
of them will do.)

So, given the equation

p1 + t * d1 = p2 + s * d2

we "project" it onto the (d1, d2) plane by dotting with d1 and d2,
respectively:

p1 . d1 + t * (d1 . d1) = p2 . d1 + s * (d2 . d1)
p1 . d2 + t * (d1 . d2) = p2 . d2 + s * (d2 . d2)

and solve the linear system for (s, t).

If p1 + t * d1 = p2 + s * d2, the lines intersect at (s, t). Otherwise, p1 +
t * d1 and p2 + s * d2 are the two closest points.

(Unless of course d1 = a * d2, in which case the lines are parallel or
overlapping.)

Another application of the "find some vectors in the problem statement and
dot the equation with them, then conjure up a fake explanation of the
mathematical basis of the solution by using the word 'projection' a lot"
approach to vector equations with scalar unknowns. No Ron Levine skill level
needed - you can do it, too! :)

--
Peter Dimov
Multi Media Ltd.

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> 
[snip]
> 

What if we test by projecting against the yz plane? Using your example:

The projection of line1 on the yz plane is the point (0,0,0)
The projection of line 2 on the yz plane is the line z = y+1
There is no intersection.

R&R

Re: [Algorithms] 3d Lines Intersection

[<ro...@do...>]

Steve Wood  wrote:

>> -----Original Message-----
>> From: ro...@do... [mailto:ro...@do...]
>> 
>[snip]
>> 
>
>What if we test by projecting against the yz plane? Using your example:
>
>The projection of line1 on the yz plane is the point (0,0,0)
>The projection of line 2 on the yz plane is the line z = y+1
>There is no intersection.
>

Exactly.  I constructed the counterexample that way so that it would
be plain as the nose on your face that there is no intersection.  It
doesn't change the fact that it is a counterexample to the algorithm
as stated. 

Another counter example in which the non-intersection is not quite as
plain.

Line 1 :
Parametric (s, s, 0)
Implicit    y = x, z=0

Line2 :  (same as before)
Parametric (0,t, t+1)
Implicit   z = y+1, x=0

Projections on xy plane:
Line 1  y= x , z=0
Line 2 x=0, z = 0, i.e, the y axis
Intersection (0,0,0)

Projections on xz plane
Line 1 z=0, y=0  i.e. the x axis
Line 2  x=0 y=0 i.e the z axis,
Intersection (0,0,0)

So the putative algorithm says that the lines intersect at (0,0,0)
when in fact they still don't intersect anywhere (an exercise for the
reader),

In this counterexample the projections onto the yz plane do intersect
at  (0,-1, 0), so it is a little harder for you to show
non-intersection.  

This suggests that  maybe one could try modify the suggested algorithm
to involve comparing the x coordinates of the intersections of the xy
and xz projections AND comparing the y coordinates of the
intersections of the xy and yz projections AND comparing the z
coordinates of the intersections of the xz and yz projections. I do
think you'd have to do all three projection directions to unravel all
the special cases, as when two lines project onto the same line (which
can happen when they intersect and also when they don't intersect).  

And then of course, you will never get exact equality in ANY of the
tests due to rounding errors and the fact that lines in space hardly
ever intersect anyway, but  the algorithm does not give a clue how to
estimate the distance of closest approach of the lines in space  from
the differences in the respective x, y, and z coordinates of the
intersections of the various projections.    For example, for the
algorithm as originally stated, I can construct a counter example
where x1 and x2 are pretty damned close but the lines in space miss by
a mile.  

No, the whole project would be a pretty big and expensive mess
compared to just solving the simple 2x2 system that I showed how to
derive in two different ways based on elementary mathematics, and
which is based directly on measuring the distance of closest approach.
(Of course it, too, has special cases to deal with as well. I think
that the only case where the 2x2 system fails to have a unique
solution is the case that it has infinitely many solutions, which is
the case that the two lines are parallel and so have infinitely many
mutual perpendiculars, so infinitely many pairs of nearest points, all
at the same distance, and this special case is immediately detectable
in the solution of the simple 2x2 system). 

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> 
> But the explanation of the math behind an algorithm, or maybe a couple
> of different algorithms, is a lot more informative than a pointer to
> somone else's code, isn't it?
> 

Many of the people here would rather have the code than the
explanation...code they can use. If they could use the explanation then they
probably could have been worked it out themselves as it sounds you might be
able to.  They probably came to this list because they couldn't find the
code library to use...i.e. a function that returns a point when giving it
two lines.  Or, they want to write the code themselves in which case they
just want the formula/algorithm in a format that they can code with.

> > You also will not find it in analytical geometry books.
> >
> 
> And in how many such books have you searched?  And don't forget to
> check the exercises.
> 

Checking a book is usually the first step...and yes, sometimes problems not
covered in the topics are presented as an exercise.  However, the solution
of the intersection of 2 lines in R3 does not present any new material and
thus is usually not included in a text book even as an exercise.  If you
find such a book that contains solutions to problems such as intersection of
2 lines in 3D then please let us know.

R&R

Re: [Algorithms] 3d Lines Intersection

[Conor S. <cs...@tp...>]

Well, the best way to start is to see if the lines intersect. This can be
done with a Plücker space dot product (see
http://www.flipcode.com/tutorials/tut_pluecker.shtml).

Then, you can simply find where one line intersects a plane which the other
line is on (in Plücker space this is incredibly easy to find).

Conor Stokes

Re: [Algorithms] 3d Lines Intersection

[Dave S. <Dav...@sd...>]

> > But the explanation of the math behind an algorithm, or maybe a couple
> > of different algorithms, is a lot more informative than a pointer to
> > somone else's code, isn't it?
> >
> 
> Many of the people here would rather have the code than the
> explanation...code they can use. If they could use the explanation then they
> probably could have been worked it out themselves as it sounds you might be
> able to.  They probably came to this list because they couldn't find the
> code library to use...i.e. a function that returns a point when giving it
> two lines.  Or, they want to write the code themselves in which case they
> just want the formula/algorithm in a format that they can code with.

I'm with Ron on this one.  I would rather have the
explanation first, that way if I get code with it,
I may or may not be able to use it in my own stuff.

The biggest problem is people trying to write black
boxes for everything and saying here use this.  Only
after all your searching and browsing do you find out 
that you have two female connectors. DOH! (ie. Data
structures are RARELY compatible between software
components.)

Also, code is harder to read than english.  At least
I think so.

Just my 2cents,
-DaveS

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

Ron,

Your post in this matter is off topic and is nothing but a personal
attack...especially since you could not find any fault with the math
(otherwise I presume you would have written a lengthy essay on how you find
it incomplete).  I've forwarded the matter to this lists' administrator.
You seem to have some problems that we can not help you with.  This is an
algorithms list to learn and share algorithms, not play at being a math cop
as you say you are.

As to the math I shared...the people on this list don't take everything for
granted, and I make mistakes. If you want to point out any mistakes then
please do it elsewhere unless you want to work together to solve the
problem.

If it builds it and only bugs come, but turns it into a bug squasher then
it's,
Rockn-Roll

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> Sent: Saturday, July 29, 2000 10:53 PM
> To: gda...@li...
> Subject: Re: [Algorithms] 3d Lines Intersection
> 
> 
> Steve Wood  wrote:
> 
> 
> >Here is the math:
> >
> 
> This is to advise the readers of this thread that they need not fret
> if they could not follow the ensuing mess, and they ought not waste
> any more time on it if they are still trying.  Whatever it might look
> like at first glance, on close inspection it is certainly not anything
> that could properly be called math.
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] 3d Lines Intersection

[Conor S. <cs...@tp...>]

Don't worry Steve, we've established Ron is a grumpy old man :) But a useful
grumpy old man. Occasionally people taste his acid tongue, but it is worth
it for the sweet bits he sometimes imparts.

Still, it would be nice if he didn't play Socrates when there is no need. We
don't need the production of a group of Plato's at the inevitable execution
he will face if he follows this path.

Conor Stokes

> Ron,
>
> Your post in this matter is off topic and is nothing but a personal
> attack...especially since you could not find any fault with the math
> (otherwise I presume you would have written a lengthy essay on how you
find
> it incomplete).  I've forwarded the matter to this lists' administrator.
> You seem to have some problems that we can not help you with.  This is an
> algorithms list to learn and share algorithms, not play at being a math
cop
> as you say you are.
>
> As to the math I shared...the people on this list don't take everything
for
> granted, and I make mistakes. If you want to point out any mistakes then
> please do it elsewhere unless you want to work together to solve the
> problem.
>
> If it builds it and only bugs come, but turns it into a bug squasher then
> it's,
> Rockn-Roll
>
> > -----Original Message-----
> > From: ro...@do... [mailto:ro...@do...]
> > Sent: Saturday, July 29, 2000 10:53 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] 3d Lines Intersection
> >
> >
> > Steve Wood  wrote:
> >
> >
> > >Here is the math:
> > >
> >
> > This is to advise the readers of this thread that they need not fret
> > if they could not follow the ensuing mess, and they ought not waste
> > any more time on it if they are still trying.  Whatever it might look
> > like at first glance, on close inspection it is certainly not anything
> > that could properly be called math.
> >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] 3d Lines Intersection

[Steve W. <Ste...@im...>]

Roger.

> -----Original Message-----
> From: Conor Stokes [mailto:cs...@tp...]
> Sent: Sunday, July 30, 2000 9:04 AM
> To: gda...@li...
> Subject: Re: [Algorithms] 3d Lines Intersection
> 
> 
> Don't worry Steve, we've established Ron is a grumpy old man 
> :) But a useful
> grumpy old man. Occasionally people taste his acid tongue, 
> but it is worth
> it for the sweet bits he sometimes imparts.
> 
> Still, it would be nice if he didn't play Socrates when there 
> is no need. We
> don't need the production of a group of Plato's at the 
> inevitable execution
> he will face if he follows this path.
> 
> Conor Stokes
> 
> > Ron,
> >
> > Your post in this matter is off topic and is nothing but a personal
> > attack...especially since you could not find any fault with the math
> > (otherwise I presume you would have written a lengthy essay 
> on how you
> find
> > it incomplete).  I've forwarded the matter to this lists' 
> administrator.
> > You seem to have some problems that we can not help you 
> with.  This is an
> > algorithms list to learn and share algorithms, not play at 
> being a math
> cop
> > as you say you are.
> >
> > As to the math I shared...the people on this list don't 
> take everything
> for
> > granted, and I make mistakes. If you want to point out any 
> mistakes then
> > please do it elsewhere unless you want to work together to solve the
> > problem.
> >
> > If it builds it and only bugs come, but turns it into a bug 
> squasher then
> > it's,
> > Rockn-Roll
> >
> > > -----Original Message-----
> > > From: ro...@do... [mailto:ro...@do...]
> > > Sent: Saturday, July 29, 2000 10:53 PM
> > > To: gda...@li...
> > > Subject: Re: [Algorithms] 3d Lines Intersection
> > >
> > >
> > > Steve Wood  wrote:
> > >
> > >
> > > >Here is the math:
> > > >
> > >
> > > This is to advise the readers of this thread that they 
> need not fret
> > > if they could not follow the ensuing mess, and they ought 
> not waste
> > > any more time on it if they are still trying.  Whatever 
> it might look
> > > like at first glance, on close inspection it is certainly 
> not anything
> > > that could properly be called math.
> > >
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] 3d Lines Intersection

[Matthew C. <MC...@ig...>]

Hi 

I just recieved the following virus warning this morning and it looks like
its
from a message from this list. It won't cause us any problems but I just
thought
I should let you know incase you were unaware of it.

>>

The Star Scanning System discovered a potential virus
or unauthorised code in a message sent to you. 
The original message was diverted into the virus holding
pen (id 651537_966551211) and will be held for 10 days before 
being destroyed.

------------------------------------------------
To help identify the message:

The message was titled 'RE: [Algorithms] pissing in the well [was: Collision
detection pa tent]'
The message date was Thu, 17 Aug 2000 16:37:03 -0700
The message identifier was
<LPB...@ea...>
The message was detected on server mail-server-10.star.net.uk
The message sender was 
    gda...@li...
    sye...@ea...
    gda...@li...

------------------------------------------------

##==>>>> VIRUS POSSIBLE IN FILE: "./651537_1MT_message.txt"
##==>>>> VIRUS ID: CVDL X97M/Divi-f
##==>>>>  Number of files read:                 1
##==>>>>  Number of possible virus infections:  1

Matthew Craig
Programmer
Intelligent Games.

Email: mc...@ig...  Internet: www.igl.co.uk
Phone +44 20 7386 3000  Fax +44 20 7386 0404
IG House, Palliser Road, London W14  9EB,  UK
This email may contain confidential information and is only for the intended
recipient.  Unauthorised review or use of any confidential information in
this message is prohibited. If you received this in error, please contact
the sender and delete it from any computer.