GJK: Common Implementation Mistake

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

TwitterRedditFacebookShare

3 thoughts on “GJK: Common Implementation Mistake

  1. Tim

    So although incorrect, this mistake on its own will not cause GJK to fail but converge with less iterations.

    I assume you mean that this mistake will cause GJK to iterate longer, not shorter.

    In my experience, this bug actually does harm the success of the algorithm. Once an incorrect simplex normal is used, GJK appears to lose its guarantee of convergence: The test can occasionally (~1 in 10k invocations) become trapped in a cycle of simplex tests, even if there are no simplex degeneracies and the origin is well-separated from the test simplex.

    In the worst case (three nearly-coplanar triangles; origin is adjacent to the vertex), as many as 12 plane tests may be needed.

    I stumbled on this bug myself, and found the cycles after writing a tool to visualize the failure cases. (Once it was corrected, the algorithm never failed to converge in 100 million invocations).

    Reply
    1. Randy Gaul Post author

      Ah, thanks for the thoughtful comment. It is true that in 3D GJK can cycle infinitely. One way to prevent this is to keep track of distance to the origin and early out if no progress is made during an iteration. An example of this (although commented out) is in Box2D’s b2Distance function.

      Reply
  2. Riv

    There are actually 8 valid regions since if the point is in any of the other 7 (the original triangle, its edges and vertices), we wouldn’t have a tetrahedron case to begin with.

    We do certainly need a few more dot products in order to determine the correct region, though. The ‘bastardized’ version can avoid the case where we end up with only one point, though.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *