Determine if a line segment passes "through" a triangle ...

Question

Math gurus,

I apologize because in a previous post I asked how to determine if a line passes through a triangle; and an answer was given. Then, while testing, I came across the scenario where a vertical line “segment” was below the base of the triangle and the answer to my previous question was giving false positives. This was my own fault because clearly there is a difference between a line and a line segment.

Below is a diagram of what I would like to accomplish. All the green line segments are considered to be passing "through" the triangle. The red line segments (obviously) do not.

The data I am using has x, y and z values, but for this test, we can assume the triangle and line segment will be coplanar.

The triangle I am using for testing is defined by the points:

vo = (2,2,1) v1 = (7,2,1), v2 = (5,6,1)

and each of my tests cases are using these points:

1. Line segment outside – no intersection: p0 = (1,4,1) p1 = (3,7,1)
2. Intersection at vertex: p0 = (4,6,1) p1 = (8,6,1)
3. Intersection through 2 edges: p0 = (4,1,1) p1 = (5,7,1)
4. Intersection contains edge: p0 = (1,2,1) p1 = (5,8,1)
5. Intersection through 1 vertex and edge: p0 = (5,1,1) p1 = (5,8,1)

Is there some specific formula that will provide a “true” / “false” indication as to whether a line segment passes over the triangle as described above?

I do NOT need to know the point of intersection in the case of a "true" result (but if it is part of determining the result, that would be a bonus).

Thank-you in advance for your help and patience.

Answer 1

I would suggest transforming to planar coordinates, so that the triangle vertices are mapped to $(0,0)$, $(1,0)$, and $(1,1)$.

Let's say your triangle vertices are $( x_0 , y_0 , z_0 )$, $( x_1 , y_1 , z_1 )$, and $( x_2 , y_2 , z_2 )$. First, calculate $$\begin{array}{l} d_{XY} = x_0 ( y_1 - y_2 ) + x_1 ( y_2 - y_0 ) - x_2 ( y_1 - y_0 ) \\ d_{XZ} = x_0 ( z_1 - z_2 ) + x_1 ( z_2 - z_0 ) - x_2 ( z_1 - z_0 ) \\ d_{YZ} = y_0 ( z_1 - z_2 ) + y_1 ( z_2 - z_0 ) - y_2 ( z_1 - z_0 ) \end{array} \tag{1}\label{1}$$ Depending on which one of $\eqref{1}$ is largest in magnitude, we calculate eight constants.

• If $\lvert d_{XY} \rvert \ge \lvert d_{XZ} \rvert$ and $\lvert d_{XY} \rvert \ge \lvert d_{XZ} \rvert$, then $$\begin{array}{ll} U_u = (x_2 y_0 - x_0 y_2) / d_{XY} & V_v = (x_0 y_1 - x_1 y_0) / d_{XY} \\ U_x = (y_2 - y_0) / d_{XY} & V_x = (y_0 - y_1) / d_{XY} \\ U_y = (x_0 - x_2) / d_{XY} & V_y = (x_1 - x_0) / d_{XY} \\ U_z = 0 & V_z = 0 \end{array}$$

• Else, if $\lvert d_{XZ} \rvert \ge \lvert d_{XY} \rvert$ and $\lvert d_{XZ} \rvert \ge \lvert d_{YZ} \rvert$, then $$\begin{array}{ll} U_u = (x_2 z_0 - x_0 z_2) / d_{XZ} & V_v = (x_0 z_1 - x_1 z_0) / d_{XZ} \\ U_x = (z_2 - z_0) / d_{XZ} & V_x = (z_0 - z_1) / d_{XZ} \\ U_y = 0 & V_y = 0 \\ U_z = (x_0 - x_2) / d_{XZ} & V_z = (x_1 - x_0) / d_{XZ} \end{array}$$

• Otherwise, $\lvert d_{YZ} \rvert \ge \lvert d_{XY} \rvert$ and $\lvert d_{YZ} \rvert \ge \lvert d_{XZ} \rvert$, and $$\begin{array}{ll} U_u = (y_2 z_0 - z_2 y_0) / d_{YZ} & V_v = (y_0 z_1 - y_1 z_0) / d_{YZ} \\ U_x = 0 & V_x = 0 \\ U_y = (z_2 - z_0) / d_{YZ} & V_y = (z_0 - z_1) / d_{YZ} \\ U_z = (y_0 - y_2) / d_{YZ} & V_z = (y_1 - y_0) / d_{YZ} \end{array}$$

Using the above eight constants, we have a function that transforms any $(x, y, z)$ coordinates to out planar coordinates $(u, v)$: $$\begin{array}{ll} u = U_u + x U_x + y U_y + z U_z \\ v = V_v + x V_x + y V_y + z V_z \end{array}\tag{2}\label{2}$$

Use $\eqref{2}$ to transform the line segment endpoint coordinates, so that $( u_0 , v_0 )$ is the starting point, and $( u_1 , v_1 )$ is the end point: $$\begin{array}{l} u_0 = U_u + x_{start} U_x + y_{start} U_y + z_{start} U_z \\ v_0 = V_v + x_{start} V_x + y_{start} V_y + z_{start} V_z \\ u_1 = U_u + x_{end} U_x + y_{end} U_y + z_{end} U_z \\ v_1 = V_v + x_{end} V_x + y_{end} V_y + z_{end} V_z \end{array} \tag{3}\label{3}$$ Note that these are only valid if the line segment is coplanar with the triangle!

To find the line segment and edge intersections, we parametrise the line using $t \in \mathbb{R}$, $0 \le t \le 1$, so that $t = 0$ at one endpoint, and $t = 1$ at the other. This is straightforward linear interpolation; i.e. $$\begin{array}{l} u = (1 - t) u_0 + t u_1 \\ v = (1 - t) v_0 + t v_1 \end{array}$$This is useful, because we only need to find (and then verify) each solution in only one variable, the line parameter $t$.

The triangle has three edges the line segment can intersect. To verify the intersection point, we must find the $t$ corresponding to the intersection point. When $t$ is known, you can trivially calculate the 3D coordinates corresponding to the intersection: $$\begin{array}{ll} x = (1 - t) x_{start} + t x_{end} \\ y = (1 - t) y_{start} + t y_{end} \\ z = (1 - t) z_{start} + t z_{end} \end{array}\tag{4}\label{4}$$

Next, we check the possible cases, one at a time (but in whatever order you want):

1. If $u_0 = u_1 = 0$, the line segment is parallel to edge from $( x_0 , y_0 , z_0 )$ to $( x_2 , y_2 , z_2 )$.

   If $v_0 \le 0$ and $v_1 \gt 0$, or if $v_0 \gt 0$ and $v_1 \le 0$, the line segment intersects the triangle at vertex $( x_0 , y_0 , z_0 )$.

   If $v_0 \le 1$ and $v_1 \gt 1$, or if $v_0 \gt 1$ and $v_1 \le 1$, the line segment intersects the triangle at vertex $( x_2 , y_2 , z_2 )$.

   If both $0 \le v_0 \le 1$ and $0 \le v_1 \le 1$, then the entire line segment is contained within this edge.
    

2. If $v_0 = v_1 = 0$, the line segment is parallel to edge from $( x_0 , y_0 , z_0 )$ to $( x_1 , y_1 , z_1 )$.

   If $u_0 \le 0$ and $u_1 \gt 0$, or if $u_0 \gt 0$ and $u_1 \le 0$, the line segment intersects the triangle at vertex $( x_0 , y_0 , z_0 )$.

   If $u_0 \le 1$ and $u_1 \gt 1$, or if $u_0 \gt 1$ and $u_1 \le 1$, the line segment intersects the triangle at vertex $( x_1 , y_1 , z_1 )$.

   If both $0 \le u_0 \le 1$ and $0 \le u_1 \le 1$, then the entire line segment is contained within this edge.
    

3. If $u_0 + v_0 = 1$ and $u_1 + v_1 = 1$, the line segment is parallel to the edge from $( x_1 , y_1 , z_1 )$ to $( x_2 , y_2 , z_2 )$ (i.e., $u + v = 1$).

   If $u_0 \lt 0$ and $u_1 \ge 0$, or if $u_0 \ge 0$ and $u_1 \lt 0$, the line intersects the edge at vertex $( x_2 , y_2 , z_2 )$.

   If $u_0 \gt 1$ and $u_1 \le 1$, or if $u_0 \le 1$ and $u_1 \gt 1$, the line intersects the edge at vertex $( x_1 , y_1 , z_1 )$.

   If $0 \le u_0 \le 1$, $0 \le v_0 \le 1$, $0 \le u_1 \le 1$, and $0 \le v_1 \le 1$, the entire line segment is contained within this edge.
    

4. If $u_0 \le 0$ and $u_1 \gt 0$, or if $u_0 \ge 0$ and $u_1 \lt 0$, the line segment may intersect the edge from $( x_0 , y_0 , z_0 )$ to $( x_1 , y_1, z_1 )$ (i.e., $u = 0$).

   Calculate $$t_u = \frac{ u_0 }{ u_0 - u_1 }$$ If $$0 \le t_u \le 1$$ and $$0 \le ( 1 - t_u ) v_0 + t_u v_1 \le 1$$ there is an intersection between the line segment and this edge, at $t_u$.
    

5. If $v_0 \le 0$ and $v_1 \gt 0$, or if $v_0 \ge 0$ and $v_1 \lt 0$, the line segment may intersect the edge from $( x_0 , y_0 , z_0 )$ to $( x_2 , y_2, z_2 )$ (i.e., $v = 0$).

   Calculate $$t_v = \frac{ v_0 }{ v_0 - v_1 }$$ If $$0 \le t_v \le 1$$ and $$0 \le ( 1 - t_v ) u_0 + t_v u_1 \le 1$$ there is an intersection between the line segment and this edge, at $t_v$.
    

6. If $1 - u_0 - v_0 \ge u_1 - u_0 + v_1 - v_0 \gt 0$, or if $u_0 + v_0 - 1 \ge u_0 - u_1 + v_0 - v_1 \gt 0$, the line segment may intersect the edge from $( x_1 , y_1 , z_1 )$ to $( x_2 , y_2 , z_2 )$ (i.e., $u + v = 1$).

   Calculate $$t_{uv} = \frac{1 - u_0 - v_0}{u_1 - u_0 + v_1 - v_0}$$ If $$0 \le t_{uv} \le 1$$ and $$0 \le ( 1 - t_{uv} ) u_0 + t_{uv} u_1 \le 1$$ and $$0 \le ( 1 - t_{uv} ) v_0 + t_{uv} v_1 \le 1$$ there is an intersection between the line segment and this edge, at $t_{uv}$.

Each part and step above are written in a form that should ensure numerical stability. For example, $(1 - t) u_0 + t u_1 = u_0 + t (u_1 - u_0)$, but the left side yields exactly $u_1$ at $t = 1$, whereas the right side may differ due to domain cancellation, if $u_1$ and $u_0$ differ a lot in magnitude.

Answer 2

Barycentric coordinates seem like a reasonable way to go here. To review, the barycentric coordinates of a point $\mathbf p=(x,y)$ relative to a triangle with vertices $\mathbf v_0=(x_0,y_0)$, $\mathbf v_1=(x_1,y_1)$, $\mathbf v_2=(x_2,y_2)$ are a triple $\mathbf\lambda=[\lambda_0:\lambda_1:\lambda_2]$ such that $\mathbf p=\lambda_0\mathbf v_0+\lambda_1\mathbf v_1+\lambda_2\mathbf v_2$ and $\lambda_0+\lambda_1+\lambda_2=1$. One way to think of these coordinates is as the masses that must be be placed at the vertices of the triangle so that the center of mass is at $\mathbf p$. We can remove the normalization condition and work with unnormalized coordinates, in which case $\mathbf p={\lambda_0\mathbf v_0+\lambda_1\mathbf v_1+\lambda_2\mathbf v_2\over\lambda_0+\lambda_1+\lambda_2}$. These coordinates are homogeneous—the important part is the ratios among them, and two sets of coordinates that are non-zero scalar multiples of each other represent the same point.

The features of (normalized) barycentric coordinates that I’ll make use of are the following:

• Barycentric and Cartesian coordinates are related by a linear transformation.
• If a point is interior to or on the triangle, then all of its barycentric coordinates lie in the closed interval $[0,1]$.
• A zero coordinate indicates that the point lies on the side line opposite the corresponding vertex. A negative coordinate indicates that the point lies on the opposite side of that side line as the vertex. E.g., if the first coordinate is negative, then the point lies on the opposite side of the line through $v_1$ and $v_2$ as does $v_0$.

The Cartesian-to-barycentric mapping can be computed by expressing the definition of barycentric coordinates as the matrix equation $$\begin{bmatrix}x_0&x_1&x_2\\y_0&y_1&y_2\\1&1&1\end{bmatrix}\begin{bmatrix}\lambda_0\\\lambda_1\\\lambda_2\end{bmatrix}=\begin{bmatrix}x\\y\\1\end{bmatrix}.$$ The triangle is not degenerate, so that the matrix on the left is nonsingular and thus the barycentric coordinates are found by multiplying $(x,y,1)^T$ by the inverse of that matrix. This $3\times3$ inversion can be reduced to $2\times2$ by rewriting the coordinate equation as $$\begin{bmatrix}\mathbf v_0-\mathbf v_2 & \mathbf v_1-\mathbf v_2\end{bmatrix}\begin{bmatrix}\lambda_0\\\lambda_1\end{bmatrix}=\mathbf p-\mathbf v_2.$$ The third coordinate can then be computed as $\lambda_2=1-\lambda_0-\lambda_1$.

Another way to avoid a matrix inversion is to use the fact that the barycentric coordinate ratios are equal to the ratios of signed areas of the triangles formed by the point and pairs of vertices of the reference triangle. These areas can be computed as $$\frac12\begin{vmatrix}x_{i+1} & x_{i+2} & x \\ y_{i+1} & y_{i+2} & y \\ 1&1&1 \end{vmatrix}=\frac12(x_{i+1},y_{i+1},1)\times(x_{i+2},y_{i+2},1)\cdot(x,y,1)$$ with indices wrapping around mod 3. Recalling that the components of the product of a matrix and column vector are the dot products of the vector with the rows of the matrix, the area computations can be written as $$\frac12\begin{bmatrix}(\tilde{\mathbf v}_1\times\tilde{\mathbf v}_2)^T \\ (\tilde{\mathbf v}_2\times\tilde{\mathbf v}_0)^T \\ (\tilde{\mathbf v}_0\times\tilde{\mathbf v}_1)^T \end{bmatrix}\tilde{\mathbf p}.$$ (The tildes denote the homogeneous coordinates obtained by appending a $1$ to the Cartesian coordinate pair.) These coordinates can then be normalized by dividing by the area of the reference triangle, so the normalized barycentric coordinates of $\mathbf p=(x,y)$ are $$\mathbf\lambda=\frac1{\det\begin{bmatrix}\tilde{\mathbf v}_0&\tilde{\mathbf v}_1&\tilde{\mathbf v}_2\end{bmatrix}}\begin{bmatrix}(\tilde{\mathbf v}_1\times\tilde{\mathbf v}_2)^T \\ (\tilde{\mathbf v}_2\times\tilde{\mathbf v}_0)^T \\ (\tilde{\mathbf v}_0\times\tilde{\mathbf v}_1)^T \end{bmatrix}\tilde{\mathbf p}.$$ (You can also work with unnormalized coordinates, but you’ll have to use a different interval for determining when a point is in/on the triangle: the coordinates must be bounded by $0$ and $\lambda_1+\lambda_2+\lambda_3$, but the latter might be negative.)

Let the barycentric coordinates of the line segment’s end points be $\mathbf P=[\lambda_1:\lambda_2:\lambda_3]$ and $\mathbf Q=[\mu_1:\mu_2:\mu_3]$. If either of these points is in/on the triangle, i.e., $0\le\lambda_1,\lambda_2,\lambda_3\le1$ or $0\le\mu_1,\mu_2,\mu_3\le1$, then we’re done: the line segment obviously intersects the triangle.

Otherwise, we have two exterior points. Thanks to the linearity of Cartesian-to-barycentric mapping, the line through $\mathbf P$ and $\mathbf Q$ can be parameterized as $(1-t)\,\mathbf P+t\,\mathbf Q$ in both coordinate systems, with $t\in[0,1]$ giving the line segment. Values of $t$ for which a barycentric coordinate of the above linear combination is $0$ are the intersections with the corresponding side lines. These values of $t$ are easily found to be $t_i={\lambda_i\over\lambda_i-\mu_i}$, unless $\lambda_i=\mu_i$ in which case the line is parallel to that side of the triangle. The line segment intersects the triangle if any of these side line crossings occurs on the triangle. In addition, for a line segment with two exterior end points to intersect the triangle, there must be at least two side line crossings, regardless of where those crossing points are.

So, compare the corresponding barycentric coordinates of $\mathbf P$ and $\mathbf Q$. If fewer than two pairs have opposite signs, then the segment doesn’t intersect the triangle and we’re done. Otherwise, for each such coordinate pair $\lambda_i$ and $\mu_i$, compute the intersection point ${\mu_i\over\mu_i-\lambda_i}\mathbf P+{\lambda_i\over\lambda_i-\mu_i}\mathbf Q$. (It might be more convenient to use $1-{\lambda_i\over\lambda_i-\mu_i}$ instead for the coefficient of $\mathbf P$.) If any of these intersection points lies on the triangle, then the segment intersects the triangle.

The above computations were for points in $\mathbb R^2$, but you’re working in $\mathbb R^3$. Affine transformations preserve lines, their intersections, and relative segment lengths along a line, so the problem can be made two-dimensional via a parallel projection onto any convenient plane that’s not orthogonal to the plane of the triangle. Projecting onto one of the coordinate planes is simplest since that just involves dropping one of the Cartesian coordinates. If you’re using the $3\times3$ coordinate transformation matrix, projecting onto $z=1$ is convenient since that sets the third coordinate to $1$ as required to use the matrix.

It’s also possible to avoid an explicit projection if the triangle’s plane doesn’t pass through the origin. In that case, the areas of triangles on the plane are proportional to the volumes of tetrahedra defined by the triangle vertices and the origin, so we can use triple products of the points directly to compute barycentric coordinates. That is, we can compute $$\mathbf\lambda=\begin{bmatrix}(\mathbf v_1\times\mathbf v_2)^T\\(\mathbf v_2\times\mathbf v_0)^T\\(\mathbf v_0\times\mathbf v_1)^T\end{bmatrix}\mathbf p$$ using the raw coordinate triples of these points. If the triangle’s plane goes through the origin, shift all of the points by a small distance in a direction not parallel to the plane.

This solution is fundamentally similar to the one given by Nominal Animal. However, using barycentric coordinates allows all of the triangle’s sides to be treated uniformly. Also, if you think about it a bit, you’ll see that these computations are a series of “left-of” tests, unrolled.

---

The cross-product form of the Cartesian-to-barycentric mapping prompts me to toss this out as well, though I doubt that it’s as efficient as other solutions that have been presented. It takes advantage of the fact that in $\mathbb{RP}^2$, the line through two points and the intersection of two lines can both be computed by taking cross products of homogeneous coordinate vectors. Thus, the coordinate mapping matrix can be seen as having the three side lines of the triangle as its rows.

The barycentric coordinates of the three side line intersections can be computed “in bulk” as $B(\tilde{\mathbf p}\times\tilde{\mathbf q})_\times B^T$, where $B$ is the coordinate transformation matrix from above and the central matrix is the “cross-product matrix” defined as follows: for any vector $\mathbf w=(w_1,w_2,w_3)T$, $$\mathbf w_\times=\begin{bmatrix}0&-w_3&w_2\\w_3&0&-w_1\\-w_2&w_1&0\end{bmatrix}.$$ As before, you will need to check if any of these points are on the triangle and you will also have to check that viable candidates for the triangle intersections fall between $\mathbf p$ and $\mathbf q$. Moreover, these coordinates will be unnormalized, so you’ll have to take that into account when making these tests. You will also have to deal with points at infinity, which will be produced when the segment is parallel to one of the sides of the triangle. In barycentric form, the coordinates of points at infinity sum to zero.

Answer 3

Two conditions must be met:

• the line of support crosses the triangle. This can be checked by counting the triangle vertices on either side of the line, i.e. 3 LeftOf tests (PQV0, PQV1, PQV2).

• the two endpoints may not both lie on the same side of the lines of support of the sides that are crossed. Takes 2 or 4 more LeftOf tests (among PV0V1, PV1V2, PV2V0, QV0V1, QV1V2, QV2V0; 3 on average).

In the example, two vertices are on the right of PQ and one on the left so that line crosses. It crosses the orange and red sides. Then P and Q aren't on the same side of the orange line.