ElliottOti.com

# Collision detection: triangle-triangle intersection

## Programming Ocaml Graphics

Collision detection is an important part of any physical simulation. The basis is formed by the intersection of primitives, and the triangle-triangle intersection test is one of the most commonly used tests.

As described in the CGA FAQ:

Let the two triangles be $T_1$ and $T_2$. If $T_1$ lies strictly to one side of the plane containing $T_2$, or $T_2$ lies strictly to one side of the plane containing $T_1$, the triangles do not intersect. Otherwise, compute the line of intersection $L$ between the planes. Let $I_k = T_k cap L$, for $k = 1$ and $2$, denote the interval of intersections between the triangles and the line. Either interval may be empty. $T_1$ and $T_2$ intersect if and only if $I_1$ and $I_2$ overlap.

The Ocaml implementation of this test can be viewed online. Compiling with the command `ocamlopt graphics.cmxa unix.cmxa collision.ml -o collision ` produces the following program:

A quick comparison with the canonical implementation by Thomas Moeller shows that my straightforward Ocaml implementation runs roughly 5 times as slowly as Moeller’s implementation in C.

My implementation currently handles coplanar triangles rather erratically, so I will either have to add a special function to check and handle coplanar triangles, or possibly check triangle normals for parallelism and perturb one of the triangles slightly to bring it out of plane before applying the normal test.