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 lies strictly to one side of the plane containing , or lies strictly to one side of the plane containing , the triangles do not intersect. Otherwise, compute the line of intersection between the planes. Let , for and , denote the interval of intersections between the triangles and the line. Either interval may be empty. and intersect if and only if 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.
No comments yet.
Leave a comment
Sorry, the comment form is closed at this time.