I've used SAT-GJK combined with EPA (Expanding polytope algorithm) for generating accurate contacts with success. It's actually not as slow as some would have you believe, I can easily simulate a few thousand objects in a large pile on one thread at 60fps with a brute-force broadphase. The main bottleneck is usually constraint solving, not collision. My implementation handles any type of convex shape, given a support function, and can refine the contact results to be within a user-defined epsilon of the actual contacts.

My implementations of these algorithms are pretty well commented/flexible and has been rewritten several times for performance/clarity. You can find it here (as part of om::physics::collision, sorry I don't have a direct link). (GJKSolver/EPASolver classes + supporting classes)

Actually Zaphyk I have implemented this optimization some years ago and found a copy in my old files. Be aware that this is totally not recommended for anything but studying due to the unecessary optimizations or readability. However at the time it just worked :wink:.

CGJK.h

CGJK.cpp

Hope that helps.

Thanks man, this really helps, can you please send me the CShapeInstance class so I can check the GetSupport method?

The support function does exactly the same what the support function in your original post does but additionally returns the vertex index.

The support function does exactly the same what the support function in your original post does but additionally returns the vertex index.

Oh thanks, I just ported your implementation and it works! But I have some collision it's not detecting, I would like to know if it is a problem with my port or if you had this issue in your implementaion.

No issue with my implementation at that time, but I remember only tested collisions between a box, sphere, and capsule. That code also assumes the shapes are convex and in the same space.

It can be many things. You definetly need to debug your code visually. One way is render the resulting tetrahedron in the case or overlap and check if the origin is really inside it or perhaps record all simplices built during the iterations and draw them. With the true GJK is even easier to debug because each iteration new closest points are found and they must become closer and closer after each iteration. Otherwise there is a bug in the code.

It was a typo when I did the port. Thanks you very much for the code, it seems to be working amazingly well. :)