Background (Before learning algorithms)

Detection of intersection between ray and triangle is a common problem in game programming, the most typical application is Picking, this paper introduces a common method, this method is also used in DirectX, the method is fast, and less storage space. The theory is explained first, and the corresponding code implementation and display in Unity are shown at the end of the article. The simple and intuitive method is to determine whether the rays intersect the plane in which the triangle is located, and if so, whether the intersection is within the triangle. But this method is not very efficient because it computes the plane of the triangle. Moller-trumbore ray triangle intersection algorithm is a fast method to calculate the intersection point between ray and triangle in space. By vector and matrix calculation, the intersection point and barycenter coordinate can be obtained quickly without the need to predict the plane equation containing triangle. It is used in computer graphics to realize ray tracking calculation involving triangular meshes. The algorithm is named after the inventors, TomasMoller and Ben Trumbore.

Parameters that

Suppose the equation of Ray Ray=O+td(O is the starting point, D is the direction of Ray (direction vector), t is the weight), a point starts from the starting point O, moves any length along the direction D, and obtains the end point R. According to the different value of T, the obtained R value is also different, all these different R values constitute the whole Ray. The three vertices of a triangle, P0, P1, P2. U is the weight of P1, v is the weight of P2, and 1- U – V is the weight of P0, and you can kind of think of it as moving some distance along the edge AC, and then moving some distance along the edge AB, and then finding their sum. How far to move is controlled by the parameters U and V, and the mathematical meaning expressed is the equation of the triangle and all the points inside it.


R a y : O + t d ( t p 0 ) Ray: O + td {\ quad} (t 0 or higher)

( 1 – u – v ) P 0 + u P 1 + v P 2 (1-u-v)P0+uP1+vP2

Derivation process

Two important theorems

Clem’s rule for solving linear equations


[ – D E 1 E 2 ] [ t u v ] = S \left[ \begin{matrix} -D & E_1 & E_2\end{matrix} \right]\left[ \begin{matrix} t \\ u \\ v\end{matrix} \right]=S

D, E1, E2 are determinants containing three parameters, which can be expressed as


t = d e t [ S E 1 E 2 ] d e t [ – D E 1 E 2 ] = [ S x E x 1 E x 2 S y E y 1 E y 2 S z E z 1 E z 2 ] [ – D x E x 1 E x 2 – D y E y 1 E y 2 – D z E z 1 E z 2 ] t=\frac{det{\left[ \begin{matrix} S & E_1 & E_2\end{matrix} \right]}}{det{\left[ \begin{matrix} -D & E_1 & E_2\end{matrix} \right]}}=\frac{\left[ \begin{matrix} S_x & E_{x1} & E_{x2} \\ S_y & E_{y1} & E_{y2} \\ S_{z} & E_{z1} & E_{z2}\end{matrix} \right]}{\left[ \begin{matrix} -D_x & E_{x1} & E_{x2} \\ -D_y & E_{y1} & E_{y2} \\ -D_{z} & E_{z1} & E_{z2}\end{matrix} \right]}

u = d e t [ – D S E 2 ] d e t [ – D E 1 E 2 ] = [ – D x S x E x 2 – D y S y E y 2 – D z S z E z 2 ] [ – D x E x 1 E x 2 – D y E y 1 E y 2 – D z E z 1 E z 2 ] u=\frac{det{\left[ \begin{matrix} -D & S & E_2\end{matrix} \right]}}{det{\left[ \begin{matrix} -D & E_1 & E_2\end{matrix} \right]}}=\frac{\left[ \begin{matrix} -D_x & S_x & E_{x2} \\ -D_y & S_y & E_{y2} \\ -D_{z} & S_z & E_{z2}\end{matrix} \right]}{\left[ \begin{matrix} -D_x & E_{x1} & E_{x2} \\ -D_y & E_{y1} & E_{y2} \\ -D_{z} & E_{z1} & E_{z2}\end{matrix} \right]}

v = d e t [ – D E 1 S ] d e t [ – D E 1 E 2 ] = [ – D x E x 1 S x – D y E y 1 S y – D z E z 1 S z ] [ – D x E x 1 E x 2 – D y E y 1 E y 2 – D z E z 1 E z 2 ] v=\frac{det{\left[ \begin{matrix} -D & E_1 & S\end{matrix} \right]}}{det{\left[ \begin{matrix} -D & E_1 & E_2\end{matrix} \right]}}=\frac{\left[ \begin{matrix} -D_x & E_{x1} & S_{x} \\ -D_y & E_{y1} & S_y \\ -D_{z} & E_{z1} & S_z\end{matrix} \right]}{\left[ \begin{matrix} -D_x & E_{x1} & E_{x2} \\ -D_y & E_{y1} & E_{y2} \\ -D_{z} & E_{z1} & E_{z2}\end{matrix} \right]}

Vector mixed product


a ⋅ ( b x c ) = b ⋅ ( c x a ) = c ⋅ ( a x b ) a ⋅ ( b x c ) = – a ⋅ ( c x b ) a ⋅ ( b x c ) = – b ⋅ ( a x c ) a ⋅ ( b x c ) = – c ⋅ ( b x a ) A. (b * c) = b, (a) (c = c, (a * b) \ \ a. (b (c) = – a. (c * b) \ \ a. (b (c) = – b. (a * c) \ \ a. (b (c) = – c. (b (a)

Let’s put these equations together


O + t d = ( 1 – u – v ) P 0 + P 1 + P 2 ( u p 0 . v p 0 . u + v Or less 0 ) O + td = (1 – u – v) P0 (P1 + P2 + {\ quad} (u p 0, acuity 0 v, u + v 0 or less)

reduction


O – P 0 = u ( P 1 – P 0 ) + v ( P 2 – P 0 ) – t d S = u E 1 + v E 2 – t d ( S = O – P 0 . E 1 = P 1 – P 0 . E 2 = P 2 – P 0 ) O-P0=u(P1-P0)+v(P2-P0)-td\\ S=uE_1+vE_2-td\\{\quad}(S=O-P0,E_1=P1-P0,E_2=P2-P0)

[ – D E 1 E 2 ] [ t u v ] = S \left[ \begin{matrix} -D & E_1 & E_2\end{matrix} \right]\left[ \begin{matrix} t \\ u \\ v\end{matrix} \right]=S

Cram’s rule


t = d e t [ S E 1 E 2 ] d e t [ – D E 1 E 2 ] t=\frac{det{\left[ \begin{matrix} S & E_1 & E_2\end{matrix} \right]}}{det{\left[ \begin{matrix} -D & E_1 & E_2\end{matrix} \right]}}

The mixed product in the denominator, using the mixed product theorem, the minus sign in front of D, cancels out


d e t [ – D E 1 E 2 ] = – D ⋅ ( E 1 x E 2 ) = E 1 ⋅ ( D x E 2 ) Det {\ left [\ begin {matrix} – D & E_1 & E_2 {matrix} \ \ end right]} = – d. (E_1 (E_2), = E_1 (D * E_2),

make


S 1 = D x E 2 S1 = D x E_2

Molecular part:


d e t [ S E 1 E 2 ] = ( ( S x E 1 ) ⋅ E 2 ) Det {\ left [\ begin {matrix} S & E_1 & E_2 {matrix} \ \ end right]} = (E_2) x E_1 (S)

make


S 2 = S x E 1 S2 = S x E_1

Is equal to the original type


d e t [ S E 1 E 2 ] = S 2 ⋅ E 2 Det {\left[\begin{matrix} s&e_1&e_2 \end{matrix} \right]}=S2·E_2

so


t = S 2 ⋅ E 2 E 1 ⋅ S 1 T = \ frac {E_2, S2}, {E_1 S1},

Similarly, the other two parameters u and v can be deduced


u = S 1 ⋅ S E 1 ⋅ S 1 U = \ frac {S1 s.}, {E_1 S1},

v = S 2 ⋅ D E 1 ⋅ S 1 V = \ frac {S2, D}, {E_1 S1},

conclusion

In the end, we can calculate the three parameters t, U and V through the known data, and judge whether the intersection is through the range limit of the three parameters. If the intersection is not satisfied, it is not intersected, if it is satisfied, it is intersected

Code implementation

    // Vector3 a b c triangle vertexs
    // orig is ray original point, dir is direction vector
    bool rayTriangleIntersect(Vector3 orig, Vector3 dir,
        Vector3 a, Vector3 b, Vector3 c, float t, float b1, float b2)
    {
        bool isIn = false;
        Vector3 E1 = b - a;
        Vector3 E2 = c - a;
        Vector3 S = orig - a;
        Vector3 S1 = Vector3.Cross(dir, E2);
        Vector3 S2 = Vector3.Cross(S, E1);

        // Common coefficient
        float coeff = 1.0 f / Vector3.Dot(S1, E1);
        t = coeff * Vector3.Dot(S2, E2);
        b1 = coeff * Vector3.Dot(S1, S);
        b2 = coeff * Vector3.Dot(S2, dir);

        Debug.Log($"t = {t}, b1 = {b1}, b2 = {b2}");

        if (t >= 0 && b1 >= 0 && b2 >= 0 && (1 - b1 - b2) >= 0)
        {
            isIn = true;
        }

        return isIn;
    }
Copy the code

Demo effects in Unity

When a ray intersects a triangle, the triangle material turns red. The ray is in the form of LineRenderer. The triangle uses a script to edit the vertex of the material

Project Address:Github.com/shadow-lr/R…

digression

Although the detection of intersection between ray and triangle can be used to realize Picking, most programs do not adopt this method, because this method is very inefficient. We can imagine that in a large 3D game, the number of triangles in a certain model is likely to be millions. In this case, Finding the intersection of every triangle on the model is extremely time consuming. Therefore, the generally feasible method is to use the bounding sphere and bounding box (AABB, OBB, FDH) instead, to calculate the smallest sphere or equation that can accommodate the model, as long as the ray and the bounding sphere or bounding box intersection can be determined, there is a certain error in knowledge accuracy, but enough to meet the needs of most programs.