homeCollision detection: triangle-triangle intersection
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
and
. If
between the planes. Let
, for
and
, denote the interval of intersections between the triangles and the line. Either interval may be empty.
and
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.
Comments
No comments yet.
RSS feed for comments on this post.
Leave a comment
Sorry, the comment form is closed at this time.