Hi, I am currently building, as a hobby project, a little game which has its own physics system. I do the physics myself because I think it's fun and great learning experience. It is 3D and I started off by doing an implementation of GJK and then put EPA on top of it to get the penetration depth. Then the trouble started. I wanted contact points, and EPA only gives a single contact point (using projection and barycentric coordinates), so one has to build up a "persistent cache" of points, but this gives noticeable artifacts from having too few contact points the first few frames. So instead I wanted to do the "one-shot" contact point building, which gives you ~4 contact points in one frame. But this seems very hard to do when you've gone down the GJK/EPA route. I have understood that it is possible to instead use SAT and plane clipping to get the one-shot points. But I want to make this work for arbitrary mesh colliders, which would probably be slow with SAT. Unless I'm mistaken, GJK really shines in the complex-mesh-collider case.

I have been thinking about this a lot. Is it possible to go down the GJK route, but with the GJK output somehow do a "quick SAT", which only considers a few of the SAT cases, and from the SAT output do the plane clipping and get the one-shot contact points? The alternative I am considering is simply going down the pure SAT route and try to use simpler colliders, and write all the OBBvsOBB, CircleVsCapsule etc etc tests, and get the one-shot points from plane clipping. And then perhaps add support for meshes, where I use GJK+EPA and a persistent contact cache. I.e. I get no visual artifacts except when I really really need mesh colliders.

I feel like I am trying to eat the cake and yet keep it.

About me, so you know how to reply: I have a background as a game engine developer, but I have never touched 3D game physics. However, I have a bachelor's degree in physics, but I still find myself lost in this algorithm jungle.

You can compute the closest points using GJK and build a normal from the difference of the two points. Then you iterate all the faces on your shapes and find the most parallel and anti-parallel faces to that normal and clip as you would do for the SAT. This will only work in the case when the objects are separated. So you still need SAT as a fallback if objects are penetrating. There is a small gotcha though. You need topology information when using clipping. And co-planar faces need to be merged. E.g. say you have two boxes with 12 triangles faces this will not work. GJK/EPA and the incremental manifold approach don't require topology information. You could consider this an advantage. I gave a bunch of talks about this you might find useful:

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

http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf

http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf

Regarding mesh colliders. GJK/SAT/EPA only work for convex polyhedra. Not for general meshes. People used SDF with some success for this, but in games we are still sticking with convex vs convex and convex vs mesh where meshes are usually static

HTH,

-Dirk

Thank you Dirk,
I am doing the famous "Casey GJK" right now, which I think gives less info than the one in, for example, Christer's Orange Book. A couple of questions, mostly to make sure I understood everything correctly:

14 minutes ago, Dirk Gregorius said:

This will only work in the case when the objects are separated. So you still need SAT as a fallback if objects are penetrating.

By separated, I assume you mean that I have a "skin" on the shapes sent to GJK, but it has yet to penetrate through this skin?

17 minutes ago, Dirk Gregorius said:

There is a small gotcha though. You need topology information when using clipping. And co-planar faces need to be merged.

By topology, do you mean that I need to specify the actual faces in the data I feed the algorithm? I.e. instead of just a bunch of vertices (like what GJK eats), I would need to make a struct what specifies all the faces, and in this struct also merge, for example, triangles that lie on the same, co-planar, face?

19 minutes ago, Dirk Gregorius said:

Regarding mesh colliders. GJK/SAT/EPA only work for convex polyhedra.

(I was sloppy with my language, by "mesh" when talking collision-stuff usually refer to a convex polyhedron)

Thanks for the links, I will look into this once more, I'll poke this thread again, should more confusion arise. Thanks for answering mine and other peoples questions, finding your replies on google has helped me a lot.

/Karl

GJK is an algorithm to compute the distance between disjoint convex polyhedra. "Casey's" GJK is the short form of this which just computes a separating axis. It is sometimes referred to as GJK-SAT (e.g. in Gino's book). To be honest, I don't know if you can use the separating axis returned from this approach. My guess is not though.

Yes, you need some mesh representation. I use a compact half-edge mesh representation which is very efficient and memory friendly. The SAT presentation ships with a bunch of sample code. 

Maybe have a look at the presentations. They cover a lot of stuff and should answer a bunch of your questions. If you have more questions I am here to help!

Cheers,

-Dirk

If you can populate your "persistent cache" of contacts over the course of successive frames, enduring an incorrect simulation state that causes artifacts, isn't it possible to repeat the contact computation in the same frame instead, until you find all contacts?

Regarding performance, knowing that nothing moves between iterations should allow some simplifications, and doing all work for the same collision at once would improve locality of reference.

4 hours ago, LorenzoGatti said:

If you can populate your "persistent cache" of contacts over the course of successive frames, enduring an incorrect simulation state that causes artifacts, isn't it possible to repeat the contact computation in the same frame instead, until you find all contacts?

Sort-of possible, but you need to perturb the rotation of the collider slightly, otherwise you would just get the same contact point. This however, seems like a slightly hacky solution, and possibly inefficient, although that's just my gut feeling.

I think people tried this. Gino talked about this in the past and even might have written about this in the Physics Pearls. If you do it physically you would need to anticipate the motion due to the current contact points. It might seem easy enough for a single box colliding with the world and one contact point, but how about if the shape is constrained using joints (e.g. in a ragdoll). How about a pile of objects? It gets pretty involved quickly.

Incremental manifolds have definitely issues (e.g. wrong torques and more importantly tunneling). They are quite simple though since you don't need topological mesh data, only vertices. No hull generation, it happens on the fly with GJK. You can start with this and get some decent results. I think this is fine. From my experience the tunneling becomes an issue very quickly and definitely at the end of production before shipping unless you really use it for physics  effects only and it does not affect gameplay. And then you start hacking around the limitations of this method which will be a major pain in the butt.