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.