c++ - Triangle-triangle continuous collision detection

I am making a 3D game engine and I use continuous collision detection. I am using Sphere-Trees to cull primitive collision checks to a minimum. However, I'd like to perform continuous triangle-to-triangle collision checking.

How does continuous triangle-triangle collision detection work, assuming triangles with linear velocities?

Answer

Continuous triangle intersection is explained in a classic Computer Graphics paper (PROVOT) and almost all research in Continuous Collision Detection use it to perform elementary tests.

The paper describes how to mathematically model the continuous triangle X triangle intersection problem. There are two types of collision involved: a vertex intersecting a triangle (vertex-face collision) and an edge intersecting another edge (edge-edge collision).

A triangle X triangle intersection is reduced to 6 vertex-face tests (1 for each triangle vertex) and 9 edge-edge tests (each triangle edge against each edge in the other triangle).

Let t0 be the start of the time interval [t0, t0 + ∆t] and assume that the positions and velocities in t0 are known. Assume also that the velocities are constant in the interval.

Vertex-face Collision

Let P (t) be the vertex and A(t), B(t), C(t) the vertices of the triangle. Let also Vp , Va , Vb , Vc be their respective constant velocities during the time interval. Thus,

P(t) = P(t0) + tVp,

A(t) = A(t0) + tVa,

B(t) = B(t0) + tVb,

C(t) = C(t0) + tVc.

If there is collision, then

∃t ∈ [t0, t0 + ∆t] such that

∃u, v ∈ [0, 1], u + v = 1, AP(t) = uAB(t) + vAC(t) (Equation 1)

Equation 1 just shows that in the collision time t, P must be inside the triangle ABC. But it is non-linear since u, v, t are unknown and there are factors that depend on two of them. To solve this, another condition is considered: that the triangle normal is orthogonal to the triangle. Thus

AP(t) · N(t) = 0, where N(t) is the triangle normal. (Equation 2)

It is important to note that this equation is not sufficient to verify the collision since it is true if A(t), B(t), C(t), P(t) are coplanar. However it calculates t and therefore eliminates Equation 1 dependency on this variable and turns it linear. N(t) is a t^2 term and AP(t) is a t term, so Equation 2 is cubic. The approach to solve it is described in Section Cubic Equations Solver. Equation 2 can result in three values for t. The lowest positive value t′ for which P(t′) ∈ ABC(t′) is chosen as the final result.

Edge-edge Collision

The ideas in Section Vertex-face Collision can be used in the edge-edge collision case with minor changes. Let AB(t) be one edge and CD(t) be the other one. The collision occurs if and only if

∃t ∈ [t0, t0 + ∆t] such that

∃u, v ∈ [0, 1], uAB(t) = vCD(t) (Equation 3)

Once again, this is a nonlinear system. The relation used to calculate t is that A, B, C, D must be coplanar, like before.

(AB(t) × CD(t)) · AC(t) = 0 (Equation 4)

This also is a cubic equation, which can lead to 3 values for t. The lowest positive value that makes it possible for Equation 3 to be solved is chosen as the final result.

Cubic Equations Solver

There are several methods to get the roots of cubic equations. NUMERICAL RECIPES 3RD ED. shows a good algorithm using a combination of Newton-Raphson and bisection methods. The bisection method gets an interval [a, b], where the root is known to be, i.e., f (a) and f (b) have opposite signals. The algorithm iterates by dividing the interval at the midpoint, reducing interval to [a′,b′] as a result, and evaluating f(a′) and f(b′). This is done until the error in the root value is acceptable. The bisection method is assured to find the root, but has slower convergence than other methods.

On the other hand, the Newton-Raphson uses the derivative of the function to refine a root guess. If f is the function and a is the root guess, the Newton-Raphson method iterates by evaluating the zero crossing of the tangent line of f passing through f(a). The new root guess will be the abscissa of this zero crossing. The image shows the method. It converges fast, but has some special cases that can lead to divergence or cycling.

The approach of the book suggests using Newton-Raphson while it is converging fast enough and bisection otherwise. This allows fast and safe convergence. The code to implement it can be found in the book.