How to calculate triangle-line collision in 3D?

Question

If there is a given triangle (tx1, ty1, tz1), (tx2, ty2, tz2), (tx3, ty3, tz3) and two given point of a line (lx1, ly1, lz1), (lx2, ly2, lz2), then how to calculate, if the line hits the triangle, or not? And if yes, where?

Answer 1

Such an intersection point $\vec p$ would be a solution of $$ \tag1\begin{cases}\vec p=a \vec t_1+b \vec t_2+c \vec t_3=d \vec l_1+e \vec l_2\\ a+b+c=d+e=1\end{cases}$$ with additional constraint that $a,b,c\ge 0$ (and also $d,e\ge0$ if you want to intersect the line segment, not the infinitely long line). As $(1)$ is a linear system of five equations in five unknowns,

• either there is a unique solution $(a,b,c,d,e)$ corresponding to a unique intersection point of the line with the plane of the triangle. Check whether or not $a,b,c\ge 0$; if so, $p$ is the unique solution, otherwise, there is no intersection point.
• or there are infinitely many solutions of the form $\vec p=\vec {p_0}+h\cdot\vec {p'}$ with a parameter $h\in\mathbb R$ (for obvious reasons, $\vec{p'}$ is a nonzero multiple of $\vec l_2-\vec l_1$). Then $a,b,c$ are also expressible in the form $a=a_0+ha', b=b_0+hb', c=c_0+hc'$. These imply constraints on $h$. For example if $a'>0$ then $a\ge 0$ means $h\ge\frac{a-a_0}{a'}$; if $a'<0$, it means $h\le \frac{a-a_0}{a'}$; if $a'=0$ and $a_0\ge0$, there is no constraint; if $a'=0$ and $a_0<0$, there is no solution at all. Do the same wth $b$ and $c$ and combine the constraints. The combination will be of the form $h_1\le h\le h_2$ with $h_<\le h_2$ (including the possibility that $h_1=h_2$ and there is a unique solution), or $h_1\le h$, or $h\le h_2$, or no solution.
• more solutions (i.e. two or more parameters) cannot occur if we assume that the triangle is nondegenerate and $\vec l_1\ne\vec l_2$.

Answer 2

Since solving linear systems of equations may not be nice in realtime, consider the following:

Find the plane of the triangle. Project the line onto that plane. This may make it a point, may make it a line. If there is a solution, the projected line must cross at least one edge of the triangle or sit entirely inside it. Then for the line to be the solution to the collision test, it must have an intersection point with the plane of the triangle.

If it has an intersection point with that plane, the line intersects the triangle if and only if the point of intersection is within the triangle.

Answer 3

There is good C++ code at the Geometric Tools site.

He has functions that do triangle/segment, triangle/ray, or triangle/line intersections.

The advantage of reading code, as opposed to a mathematical description is that the code considers floating point tolerances (if it's good code, anyway). This is important in intersection problems, even in simple ones like this. The mathematical account just says you should check that two numbers are equal, or that some number is equal to zero. In floating point arithmetic, these sorts of tests won't work, of course.

So, take your pick -- a mathematics solution or a software solution. They are based on the same principles, mostly, but the details are different.