Thanks to some cool discussions with my friend Nathan Carlson I’ve learned a bit about GJK. There are two versions floating around in the computer science community, and one of them is much easier to implement than the other. I will assume readers have a basic understanding of the theory (general idea) of how GJK works before reading.

The easier style of GJK is colloquially referred to as “bastardized”, in that it isn’t truly the original GJK, but instead a modified version for boolean collision detection. The idea is to evolve through the volume of two convex polyhedra until an axis of separation is found. Since any axis of separation can work a few assumptions can be made during the implementation which can lead to interesting optimizations. Such optimizations, however, can lead to a common pitfall in the tetrahedron case.

Most implementations of the tetrahedron case will conduct 3 dot products and execute a series of branches, or a switch statement. When arriving at the tetrahedron case it is known the origin of Minkowski space is above (or below) a hyperplane defined by the previous triangular simplex. The three dot products are used to see which of the newly created face normals on the tetrahedron point towards the origin. The fatal assumption is that these three dot products alone can be used to deduce which Voronoi region contains the origin. There are 15 different voronoi regions for the tetrahedron case, and the three dot products alone can be used only to test the case of the tetrahedron containing the origin.

When imagining two 3D faces adjacent to one another, where the angle between each face normal is acute (or in other words the two faces are nearly coplanar), it is easy to notice that the dot product of a point above both faces can be positive. While positive a point can still be entirely within the Voronoi region of only one of the two faces, instead of within the Voronoi region of the shared edge. This means that the tetrahedron’s barycentric coordinates are not enough information to deduce which of the 15 voronoi regions the origin lays within.

If this mistake is made the simplex can become a triangle when one of the edges of this triangle is truly the closest feature to the origin. Similarly a face can be chosen when instead a vertex region should have been chosen. An entire iteration upon a triangle will be performed! What’s even worse is if the triangle iteration assumes that certain voronoi regions were checked the previous iteration and skips them, then this assumption may be invalid after a tetrahedron iteration.

So although incorrect, this mistake on its own will not cause GJK to fail but converge with more iterations. This mistake can also give rise infinite (and sometimes complex) cycling without ever converging (see comments below).