6
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ I disagree - it seems like a perfectly fine and specific question to me. \$\endgroup\$ – Nathan Reed Feb 20 '14 at 6:51
  • \$\begingroup\$ Edited, converting the bit on where to find information to asking how to do it. It could still use some more description of what you've tried or are stuck on. \$\endgroup\$ – Anko Feb 20 '14 at 6:56
  • \$\begingroup\$ I have added one answer, so we can discuss the topic! \$\endgroup\$ – dsilva.vinicius Feb 20 '14 at 17:19
  • 1
    \$\begingroup\$ @Lighthink: You don't need to append [solved] to your questions title. Questions marked as solved with a flag on one of the answers, as you already did. \$\endgroup\$ – Kromster Feb 21 '14 at 13:49
8
\$\begingroup\$

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).

Elemental Triangle Intersection tests

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ Very, very informative. That's what I was actually looking for. I think my question is now answered. \$\endgroup\$ – Lighthink Feb 20 '14 at 18:18
  • \$\begingroup\$ I eventually implemented it and it worked just fine. I don't know where did you get that cubic equation, I managed everything without it. \$\endgroup\$ – Lighthink Jun 4 '14 at 17:02
3
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Good links, not an answer though. You could improve it by adding more explanation. \$\endgroup\$ – concept3d Feb 19 '14 at 20:16
  • \$\begingroup\$ @concept3d Well his question was specifically a reference request. There's not much explanation to be done here I think. \$\endgroup\$ – RandyGaul Feb 19 '14 at 20:23
  • \$\begingroup\$ Then I will vote to close it. \$\endgroup\$ – concept3d Feb 19 '14 at 20:49
  • 1
    \$\begingroup\$ @RandyGaul the question should be edited to ask how to do it instead of asking for a reference that explains how to do it and then I think it would be a fine question. Links to references cause link rot which essentially means if the link dies the answer is subsequently useless which is a bad thing for a Q&A site. \$\endgroup\$ – SpartanDonut Feb 19 '14 at 22:46
  • 1
    \$\begingroup\$ I would also like to see at least a little discussion of what methods are available and what the trade-offs may be between them, in addition to references to the specific methods. \$\endgroup\$ – Nathan Reed Feb 20 '14 at 6:53

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.