Collision Detection - why GJK?

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.

Sure, just ask here if you have questions.

On 15.09.2017 at 11:11 PM, Dirk Gregorius said:

They use a custom algorithm called GSK.

This is Gilbert–Schlesinger–Kozinec (GSK)? Where I can find some more info about it and some implementation example?

You won't. It is proprietary.

On 18.04.2018 at 9:59 PM, Dirk Gregorius said:

You won't. It is proprietary.

Just to make clear:
1. Gilbert–Schlesinger–Kozinec (GSK) algorithm is NOT the same thing as Havok's GSK? Maybe they found new way to use it? Looking at their 1st lvl source code I suppose Havok's GSK is an alternative to EPA. And why it was invented? Also I see GJK things among GSK.
2. Why Valve decided to implement their own GJK for HL2 instead of Havok?
3. Why did not Havok publish that GSK algorithm on SIGGRAPH or GDC or IEEE int. Conf. on Robotics and Automation? I think it's quite natural to publish new algorithms, solutions and techniques.
4. Is there anything is capable to outperform GSK?

1) Correct!

2) I was not at Valve when HL2 was developed. Don't know, sorry! We have something that is internally called Jay's GJK. Not sure if you are referring to this. This is a method we use for linear sweeps during character movements. It is actually more like MPR (Minkowski Portal Refinement) though it was developed much earlier. The original GJK is a method to compute closest points between disjoint convex shapes. Different problems, silly naming

3) I don't know either. I disagree though that publishing new algorithms is a 'natural' thing. In particular if they are a business advantage you might be better off keeping them to yourself.

4) Sorry, I cannot talk about GSK.

Oh, this is still a problem? This was figured out in the 1990s, but the technology may have been lost.

Back in the 1990s, I developed Falling Bodes, a 3D ragdoll system, and probably the first one that worked. Not real-time, for animation. Internally, it had axis-oriented bounding boxes as the outer phase, and GJK for the actual collision.

I started with the implementation from Prof. Steven Cameron at Oxford. I discovered that, due to floating point roundoff error, the algorithm may not terminate, but can cycle between a few vertices. This usually happens in a physics engine as two bodies settle into contact and two faces become closer and closer to perfectly parallel. This generates a numerical situation where the small difference between two large numbers matters. That's why it won't work with 32 bit floats. Cameron's code had been tested with random polyhedra, which didn't force the failure. I could run for hours with no fails on random orientations, but when two bodies settled into face-parallel contact, it failed within seconds.

I came up with an programmer-type solution which stored the last few states to detect that the algorithm was in a loop. That worked in practice. Prof. Cameron worked on a mathematical solution, and that's in his current code. It took months to get that right. He makes it available without comments online; commercial use requires a fee.

Incremental GJK, where you use the previous state to start the closest points search on the next frame, is near constant time after the first time a body pair gets computed. The first time, it's O(sqrt(N)), where N is the number of vertices. The solver walks across the edges of the polyhedron towards the closest point. That's the big win with GJK. High-poly convex mesh collisions work well. I was doing animation, not games, so it didn't have to be real-time and the models tended to be high poly.

Geometry for GJK has to be strictly convex. This means you must not have coplanar triangles. Coplanar faces will make the algorithm hang or stick, because there's no direction that leads the search for a closer point towards a solution. Your meshes for GJK thus can't be all triangles; they have to be arbitrary flat polygons. You need a minimum break angle of a few degrees at each edge for best performance. Your convex hull algorithm has to handle all this. I used to use QHull.

When you do everything right, it works fine. But the details of how to get this working right may have been lost over the years.

I sold the technology and patent to Havok back in the 1990s. Worked out quite well. The patent and NDA expired long ago, so I can talk about it now.

It's my understanding that nowadays termination criteria are largely based on indices of the input geometry, as opposed to actual floating point positions. Then to prevent multi-step cycling, a clever distance check to the origin can be used to verify incremental progress. This was all from Erin's online resources.

GJK is good for sphere/capsule vs hull collision - you need to compute the distance from point/segment to the hull, which SAT doesn't give you. For other cases, it only tells you that the intersection exists, so it's not very useful when you need to know interpenetration and collision normal.

4 hours ago, d07RiV said:

For other cases, it only tells you that the intersection exists, so it's not very useful when you need to know interpenetration and collision normal.

That must be some dumbed-down version of GJK. See Cameron's paper, section 5, for how to compute interpenetration. Here's the code.

When I used this approach, I generated a collision geometry slightly inside the visual geometry. So I'd get a closest-points vector between the collision geometries and use that to keep them apart. You can compute a closest-points vector from the final simplex of GJK. The closest points can be vertex-vertex,vertex-edge, edge-edge, vertex-face, or edge-face. Not face-face, though; that's reported as vertex-face.

I wanted a more accurate simulation than games usually use. So, from that I'd compute the two most parallel faces and the plane through the midpoint of the closest points vector and normal to it. Then the two closest faces were projected onto that plane to get two polygons. The polygons were intersected. That's the contact polygon. Then the distance from the vertices of the contact polygon to each of the closest faces was computed, to get the distance to contact at each corner of the polygon.

The closest points distance was used to compute the spring energy for a spring-damper system. That energy was then distributed among the contact points in inverse proportion to their distance to contact. This made face-face contact stable. Single-point contact systems tend to have the contact jump around as objects settle, resulting in jitter. This approach doesn't have that problem.

Friction was computed at the multiple contact points. So spinning object friction worked right. Here's a video from the 1990s. Even a rattleback worked.

This is slower than impulse-constraint physics, but it doesn't have the "boink" problem. In impulse-constraint physics, objects change direction in zero time, which looks all wrong for big objects. This is the main reason game physics doesn't look like real physics. Here's a big mecha falling, from 1997.

Quote

That energy was then distributed among the contact points in inverse proportion to their distance to contact.

This might be actually useful for warm-starting in the impulse based systems. How did you re-distribute the energy? I assume you would redistribute in a way that the net forces on the associated bodies are relatively stable between frames?