3D lines intersection algorithm

I have line direction using x,y,z

and two points A, B , I used li开发者_如何学运维ne segment using B- A

how to get the intersection point between them

Best regards

Sytem of equations:

The parametrice equation of a line with direction (a,b,c) and one point X(x1,x2,x3) is :

D1:(x, y, z) = (x1, y1, z1) + t1(a, b, c)

The parametrice equation of a line with 2 points A and B is :

 D2:(x, y, z) = (xa, ya, za) + t2(xb-xa, yb-ya, zb-za)

you just need to equalize D1 and D2 to get the result finding the parameter t1 and t2 that will work. (3 equations with 2 unknown)

If there is no solution there is no intersection.

Intersection with the segment only:

Now let M be you result you just need to verify :

t2 in [0,1] 

 or  0<AM.AB<||AB||^2 (M is in the segment AB)

remark:

If the representation of your line are from cartesian equations (intersection of plans) than the problem is the same but with 4 equations an 3 unknown

Example:

A (1,1,1)
B (0,0,0)
D2:(x,y,z)=(1-t2,1-t2,1-t2)

(a,b,c)=(1.-1.1)
(x1,y1,z1)=(1,0,1)
D1:(x,y,z)=(t1+1,-t1,1+t1)

(D1 and D2 are 2 diagonals of the cube of side =1 placed on 0,0,0)

let M(x,y,z) be the intersection D1, D2

we find t1 and t2 that equalize the above equation: D1 and D2

we get easily t1=-1/2 and t2=1/2

moreover t2 is in [0,1] so the resulting intersection is in [A,B]

M(1/2,1/2,1/2) =D1(t1)=D2(t2) is the solution