Hi there,

in my Master's Thesis, I dealt with the two most common collision detection algorithms, SAT and GJK.

SAT works like a charm. It is quick, requires only a very limited amount of code and is accurate. And then there is GJK.

I sticked to the instructions at this blog entry http://hacktank.net/blog/?p=93

... and all I can say is that this algorithm is horrible. It requires LOTS of code which makes it almost impossible to debug properly, and it takes a lot of time to compute.

I computed 1000 collisions of spheres with both implementations. While SAT only took 0.02964 seconds to compute them (with perfect detection rate), GJK took almost five times longer and only with 94% success.

So I'm asking, is GJK really that bad? Or must this be a flaw in my implementation? What are your experiences?

GJK in 32bit floating point precision is can be indeed be a numerical nightmare. Most practical solutions restrict themselves to polygonal shapes  for that reason since in that case they are somewhat manageable. Spheres and capsules are handled as points and segments and the radius is added later. This avoid most numerical problems. This is not perfect, but if done correctly it can work well enough in practice.

The other issue with GJK people usually don't talk about arises when used as a distance function inside CCD (e.g. conservative advancement). People often use a relative distance threshold as termination criteria. In the context of CCD this can lead to a termination which doesn't bring you close enough for contact creation and you tunnel.

The funny thing is that a GJK/EPA pipeline usually has a third fallback which samples random directions over the unit sphere to find a local minimum. You really need this since you will fail in practice. EPA is numerical even worse then GJK in 3D. It is conceptually a convex hull algorithm, but all public available implementations don't deal with the numerical issues. 

Finally it is worth to mention that often Havok is often named for using GJK to justify the use. This is not true. They use a custom algorithm called GSK.

So I agree GJK is hard to get right in 32 bit floating math and you really need to know what you are doing to get it right. I recommend Erin Catto's presentation from Box2D which  makes the right compromises to work in practice in my opinion.           

For spheres there were probably flaws in your implementation. Unfortunately most resources on GJK in existence are numerically unstable and don't actually perform well for robust collision detection, your linked article included.

Every single resource I've been able to find has been quite flawed except for Erin's GDC lecture. I've heard positive things about Gino's book, but I myself haven't read it.

Quote

Unfortunately most resources on GJK in existence are numerically unstable and don't actually perform well for robust collision detection, your linked article included.

Funnily, all resources out there start with a discussion of Minkowski addition which is absolutely not essential for the algorithm. GJK as an algorithm is about finding the closest point on a convex shape to the origin. Minkowski addition is only an extension to generalize the algorithm to compute the closest points between two disjoint convex shapes. It is not needed to understand the actual algorithm though.

I agree with Randy. The best resources on GJK are from Erin, Gino and also Christer Ericsion (both books and  papers). 

Oh, and I noticed that the link you showed here uses 'Casey's optimizations'. Casey's video is actually not about GJK, but only a simplified boolean query sometimes referred to as SAT-GJK (e.g. in Gino's book). The original GJK computes the distance between two disjoint convex shapes and is not just a boolean overlap test. Funnily, this optimization seems still to be considered correct even though at least in the professional world it is well known you can indeed get into complex cycling situations where you need to search the 'old' regions. And this actually happens a lot in practice. It only needs two boxes with random orientations and some assertions to show this. 

So the issues you are having with your implementation might be due to making some false assumptions in your implementation.

6 minutes ago, Dirk Gregorius said:

Funnily, all resources out there start with a discussion of Minkowski addition which is absolutely not essential for the algorithm. GJK as an algorithm is about finding the closest point on a convex shape to the origin. Minkowski addition is only an extension to generalize the algorithm to compute the closest points between two disjoint convex shapes. It is not needed to understand the actual algorithm though.

I am totally aware of that. Doesn't make the algorithm quicker though.

Also, I looked through Erin Catto's lecture and I have to say that those border cases and their solutions don't help me ... so in all terms, SAT looks like the better choice here, also because it is easily extensible to higher dimensions. My Master's thesis deals with collisions in 4D, so debugging GJK is even harder.

Sure, but SAT usually doesn't give you the distance. If you want to use SAT for distance computation there are a lot more separating axes to test. E.g. all feature pairs that can realize closest points like vertex-edge or vertex-vertex. This will be insanely slow compared to GJK.

2 minutes ago, Dirk Gregorius said:

Sure, but SAT usually doesn't give you the distance. If you want to use SAT for distance computation there are a lot more separating axes to test. E.g. all feature pairs that can realize closest points like vertex-edge or vertex-vertex. This will be insanely slow compared to GJK.

I want a boolean decision if there is a collision or not, and if yes, a collision normal to determine the reflection of the projectile. This collision normal is also already calculated in the SAT algorithm (it's simply the perpendicular to the separating axis) while with GJK you need the EPA extension to obtain this information.

I see, that makes sense. Did you see my presentation about the SAT here (sorry for shameless self promotion):

http://media.steampowered.com/apps/valve/2013/DGregorius_GDC2013.zip

It goes into quite some detail and also optimizes the O(n^3) edge cases and might be useful. 

1 minute ago, Dirk Gregorius said:

I see that makes sense. Did you my presentation about the SAT here (sorry for shameless self promotion):

http://media.steampowered.com/apps/valve/2013/DGregorius_GDC2013.zip

 

It goes into quite some detail and also optimizes the O(n^3) edge cases. 

Thanks a lot, I will give it a shot, maybe I can cite this in my work.