# point of intersection of two lines in barycentric coordinate system

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.

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.

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