Triangle-triangle continuous collision detection

Question

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 1

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.

Answer 2

Erin Catto GDC 2013, Continuous Collision Detection. The video is free for public viewing on the GDC vault. Erin keeps his own version of his slides available, but the GDC vault itself houses the free video.

Erin's link: https://code.google.com/p/box2d/downloads/detail?name=ErinCatto_GDC2013.zip&can=2&q=

I can't speak for the Eberly work, but the idea of Erin's work is to reduce the problem to that of a root finding problem. GJK is used to compute distances of which are used to step forward/backwards in time to find a time of impact as a root to the equation of separation.

In order to implement Erin's work one must have an understanding of how to implement GJK, which makes use of knowledge of the Minkowski Sum and Support Points. Both of these concepts are fairly simple in isolation, though the implementation of a full-featured continuous collision package is very difficult to author.

All I can say about the Eberly work is that it seems to (after a 10 second skim) compute time impact directly through a fully enumerated system of if statements. Eberly is extremely good with geometry, and in general his work and documentation is quite intensive making it difficult for beginners in read.

Eberly, swept SAT: http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf