3
$\begingroup$

I am looking for an efficient way to determine the intersection point of two lines which go through a triangle (face) of a 3D triangular surface mesh.

For both lines I know the two points at which they intersect with the edges of a triangle (face). Denoted $P_A^1, P_B^1$ for the first line and $P_A^2, P_B^2$ for the second line (See illustrative example figure).

Based on my investigations my preferred approach would be to:

  1. Transform the the points of intersection for both lines ($P_A^1, P_B^1$ and $P_A^2, P_B^2$) into barycentric coordinates resulting in $B_A^1, B_B^1$ and $B_A^2, B_B^2$.
  2. Define two lines: $L_1$ which goes through $B_A^1, B_B^1$ and $L_2$ going through $B_A^2, B_B^2$ based on the two-point form defined in section 4.1.1. of this document
  3. Determine the point $B_I$ as the barycentric coordinates where $L_1$ and $L_2$ intersect based on the equations in section 4.3 of this document.
  4. Transform $B_I$ back into the cartesian coordinate system to have its 3D coordinates, denoted as $P_I$.

Unfortunately steps 2 and 3 do not lead to meaningful results (i.e., the intersection points fall outside the triangle) and I have doubts that I am applying equations in section 4.1.1. and section 4.3 properly.

Even when using a simple example based on the upper illustration in this figure here by defining $B^1_A=(1,0,0), B^1_B=(0,1/2,1/2)$ and $B^2_A=(0,1,0), B^2_B=(1/2,0,1/2)$ I cannot determine $B_I$ correctly as $B_I=(1/3,1/3,1/3)$ with the above procedure.

$\endgroup$
2
$\begingroup$

For clarity, let's use $(u, v, w)$ for barycentric coordinates.

Let's say the first line passes through points $(u_1 , v_1 , w_1)$ and $(u_2 , v_2 , w_2)$ in barycentric coordinates; and the second line through points $(u_3, v_3, w_3)$ and $(u_4, v_4, w_4)$. If we parametrise these using $t_1$ and $t_2$, we have lines $$\left\lbrace ~ \begin{aligned} L_1(t_1) &= \Bigr(u_1 + t_1 (u_2 - u_1) ,~ v_1 + t_1 (v_2 - v_1) ,~ w_1 + t_1 ( w_2 - w_1) \Bigr) \\ L_2(t_2) &= \Bigr(u_3 + t_2 (u_4 - u_3) ,~ v_3 + t_2 (v_4 - v_3) ,~ w_3 + t_2 ( w_4 - w_3) \Bigr) \\ \end{aligned} \right.$$ At the intersection, $L_1(t_1) = L_2(t_2)$.

By definition, $u + v + w = 1$ for all $u, v, w \in \mathbb{R}$. Therefore, we can pick any pair ($u, v$ or $u, w$ or $v, w$) of barycentric coordinates. If we pick $u$ and $v$ (and therefore $w = 1 - u - v$), we have a system of two linear equations and two unknowns $t_1$ and $t_2$: $$\left\lbrace ~ \begin{aligned} u_1 + t_1 ( u_2 - u_1 ) &= u_3 + t_2 ( u_4 - u_3 ) \\ v_1 + t_1 ( v_2 - v_1 ) &= v_3 + t_2 ( v_4 - v_3 ) \\ \end{aligned}\right.$$ which has exactly one solution: $$\left\lbrace ~ \begin{aligned} t_1 &= \frac{ u_1 (v_4 - v_3) + u_3 (v_1 - v_4) + u_4 (v_3 - v_1) }{ (u_1 - u_2)(v_4 - v_3) - (u_4 - u_3)(v_1 - v_2) } \\ t_2 &= \frac{ u_1 (v_2 - v_3) + u_2 (v_3 - v_1) + u_3 (v_1 - v_2) }{ (u_1 - u_2)(v_4 - v_3) - (u_4 - u_3)(v_1 - v_2) } \\ \end{aligned}\right.$$ where the denominator is the same for both, and is zero if and only if the lines are parallel.

If $0 \le t_1 \le 1$, then the intersection is on the line segment between the specified points on the first line.
If $0 \le t_2 \le 1$, then the intersection is on the line segment between the specified points on the second line.

The intersection is at $(u, v, w)$, $$\left\lbrace ~ \begin{aligned} u &= u_1 + t_1 ( u_2 - u_1 ) = u_3 + t_2 ( u_4 - u_3 ) \\ v &= v_1 + t_1 ( v_2 - v_1 ) = v_3 + t_2 ( v_4 - v_3 ) \\ w &= w_1 + t_1 ( w_2 - w_1 ) = w_3 + t_2 ( w_4 - w_3 ) \\ \end{aligned} \right.$$ where you can use either of the right sides.

The point is inside the triangle if and only if $0 \le u \le 1$, $0 \le v \le 1$, and $0 \le w \le 1 \iff 0 \le u + v \le 1$.

If you have the Cartesian coordinates $(x_1, y_1, z_1)$ corresponding to $(u_1, v_1, w_1)$, and so on, you can calculate the 3D coordinates of the intersection $(x, y, z)$ using $$\left\lbrace ~ \begin{aligned} x &= x_1 + t_1 ( x_2 - x_1 ) = x_3 + t_2 ( x_4 - x_3 ) \\ y &= y_1 + t_1 ( y_2 - y_1 ) = y_3 + t_2 ( y_4 - y_3 ) \\ z &= z_1 + t_1 ( z_2 - z_1 ) = z_3 + t_2 ( z_4 - z_3 ) \\ \end{aligned} \right.$$ again using either one of the right sides, as they are equal at the intersection by definition.

$\endgroup$
1
  • $\begingroup$ That works perfectly. Thanks for this detailed explanation. $\endgroup$
    – Fab
    Jan 24 '21 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.