Algorithm for solving line line intersection in 3d

Question

I am trying to find an algorithm that a computer can execute that finds the intersection point between two lines each defined by a point on the line and a direction vector. Does anyone know of one? It is preferable that I can do any solving ahead of time to make the code a matter of plugging numbers into a formula.

Answer 1

Let's call your points $A, B$, with corresponding vectors $u,v$. Then your intersection $M$, if it exists, satisfies

$$\overrightarrow{AM}=\lambda \vec{u}$$ $$\overrightarrow{BM}=\mu \vec{v}$$

That's two unknowns, which is not pleasing. But you can rewrite this as: $\overrightarrow{AM}=\lambda \vec{u}$, and $\overrightarrow{BM}$ is parallel to $\vec v$. The latter is expressed with cross product, so you have to find $\lambda$ such that $\overrightarrow{BM} \wedge \vec v=0$, with $\overrightarrow{BM}=\overrightarrow{BA}+\overrightarrow{AM}$, or:

$$\left(\overrightarrow{BA}+\lambda\vec u\right)\wedge \vec v=0$$

This will give you three linear equations (one per axis), but one is enough, the other are just safe checks, since $M$ may not exist at all.

By the way, for such a point $M$ to exist, you need that $\vec u,\vec v$ and $\overrightarrow{AB}$ be coplanar, that is

$$\det(\vec u,\vec v,\overrightarrow{AB})=0$$

It's not necessarily enough, since you could have parallel coplanar lines.