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