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.

While you try to enclose the origin you must also move closer. So the tolerance is about distance progression. If you are not getting closer to the origin in the next iteration you are done (e.g. you start cycling). Note that for polygonal shapes you don't need a tolerance. For curved shapes the trick is usually to only use the center (sphere) or inner segment (capsule) in the GJK and handle the radius afterwards. Getting GJK running in 32bit floating precision for general curved shapes is a challenge and might effect other algorithms which are build on GJK (e.g. continuous collision detection).

Did you see Erin Catto's GDC presentation:

http://box2d.org/files/GDC2010/GDC2010_Catto_Erin_GJK.pdf

This is the best explanation on GJK in my opinion. You can find an example implementation in Box2D. It handles a bunch of the numerical issues you are talking about.

This is another great resource about GJK by Casey Muratori. Just watch out that GJK is about the distance between two convex and disjoint shapes. The algorithm described in this video is often referred to as SAT-GJK and only determines separation/overlap (e.g. a boolean query), but not distance. So you need a different termination criteria for the distance query.

Note that for the distance GJK I always found Casey's optimizations not working for me in some cases. For the boolean query they might be fine. Didactically this is a great presentation though!

http://mollyrocket.com/849

HTH,

-Dirk

HTH,

Since Dirk mentioned Casey Muratori's SAT-GJK, you can compare your GJK with mine. It's available here: https://irlanengine.wordpress.com/downloads/physics/. It's 3D but is straightfoward to pass to 2D. There is also a demo you can run etc.

Casey's video had been my main reference up to this point. I cut out many (all?) of the optimisations he presents, so I'm now testing all voronoi regions for containing the origin at each step; as if by magic it started working as intended. I've also implemented the tolerance in comparing progress towards the origin, and with a little tweaking round shapes are working far more reliably (I've yet to hit the iteration cap). Next step is to determine penetration depth for intersections, and then on to 3D.

Thanks for the help, I'll be sure to report back the next time I break something!

–

On a side note, for round shapes I'm taking support points from the surface, not the core shape. The reason being I want to be able to transform rounded shapes, to get ovals, squished/skewed capsules etc. so factoring in the radius later on didn't seem like a viable option. So far it seems to be working well.

To do curved shapes properly you will need something like the Expanding Polytope Algorithm (EPA) to expand the simplex to the surfaces of the curved shapes (to within some tolerance) and get an accurate penetration depth. It shouldn't be that hard to implement in 2D, it's very similar to the quickhull convex hull algorithm.

Without EPA, you can get objects with large penetration depth that produce contact points inside the convex shapes. This happens when the simplex does not lie on the surface of the Minkowski difference. As a result the objects don't know that they should be separated and appear 'soft' when there is a large penetration (e.g. from a fast-moving object).

When I was implementing the GJK algorithm, I was also looking at the mollyrocket.com video, but to me that was a bit confusing, and I think he explains some of the maths wrong for some of the region tests in the 3D space, although unfortunately I don't remember any more what the confusion was. I ended up with the following code for the 3D case, perhaps that can be useful for reference:

- https://github.com/juj/MathGeoLib/blob/master/src/Algorithm/GJK.h

- https://github.com/juj/MathGeoLib/blob/master/src/Algorithm/GJK.cpp

I've pretty much got it working now, thanks. (Curved shapes still need some perfection, though). Yeah I found the same thing. I never tracked down the exact problem, but something about the optimisations to region tests kept causing it to fail.