I've been working on an implementation of GJK to determine the closest points between pairs of shapes. For the time being I'm working in 2D, my goal is to build a simplex as close to the origin as possible, and terminate when a 3-point simplex contains the origin. It's almost working correctly but there are a couple of cases which are still tripping me up.
For implicit, curved shapes the algorithm regularly fails to converge, especially for relatively shallow penetrations. The chapter on GJK in Real-Time Collision Detection suggests a tolerance in the termination condition, but I can't figure out what exactly it's supposed to be tolerating... I suspect the problem has something to do with there being and infinite number of potential support points to choose from, but I'm uncertain of how to combat that.
The other problem is deciding what to do when a 2-point simplex passes directly through the origin. This seems common with curved shapes but I was also able to engineer situations where it would occur with polygons. Of course if a 2-point simplex is passing through the origin then the shapes are intersecting, but the aim is to build a complete simplex and use it later to determine penetration depth. When the origin lies on the line segment formed by a 2-point simplex, I can't create a valid search direction. I tried picking a random direction and working from there, but I found a large number of false positives reported, and wasn't able to reliably catch and fix these.