Implementation of GJK

Wow, quite a lot without posting here... I will try to be better on this.

After some relaxing weeks implementing intersection tests for basic primitives (triangles, box, spheres, etc) I have decided to go further and implement a generic algorithm to detect collisions: I decided to implement the well known GJK algorithm (also known as Gilbert-Johnson-Keerthi algorithm).

Here, I will just describe my general thoughts and experience while implementing this (time of implementation, bibliography) but I will not give details on the theory, which might take lots and lots of lines.

Actually, the GJK algorithm is only a part of a whole collision detection architecture. It only gives you the distance between two convex objects but it is possible to adapt it to a clever architecture to provide you with contact points a penetration depths.

So, I did a fast "state-of-the-art" just to realize that it was not an easy task. Even worst, my dear boss was asking me for details on the time that it can be implemented and just looking all the maths, I was just scared !

Unless you have a good experience working with convex theory, Minkowski sums, affine transformations, you will do the implementation very fast or, if you are like me, not a real expert on this, it will take about "1 month" working 8 hrs a day to implemented the whole thing. I should say that you can get it much faster from Bullet or Solid libraries, but here in the company, due to license constraints, we have to implement everything from nothing.

I should accept that I had good inspiration from these books:

1. Collision Detection in Interactive 3D Environments, Gino Van der Vergen
2. Real-Time Collision Detection, Christer Ericson

In the first book, the one from Gino, there are a lot of maths (quite a lot, I would say), but you can get the Solid library where GJK is implemented. The book explains everything in the code, mainly the numerical problems, and provides you of a hybrid method to get penetration depths using GJK. I compiled the library and it runs very nice. It was a huge source of inspiration. However, there is no way it will make it for our PS3 compilation standards and many many problems arise while integrating SIMD operations.

The second book gives you a better introduction to the GJK problem but it will no go farther into the details. So, I think both books complement each other very well.

I also took some inspiration from Bullet. It computes distance to simplexes in a more direct way but still, it remains quite complex.

So, I implemented GJK + EPA as explained in Gino's book and so far it compiles perfectly in within our SIMD standards and PS3 compilation constraints.

The main idea is to add an extra convex radius to each convex shape (as Havok does) . Then

• GJK is used when inter-penetrations are small. Using EPA when penetration are larger is quite unstable. To use GJK we surround the objects with a little margin (the convex radius in Havok terms) When the inter-penetration is within this margin, we compute the closest distance between the original objects. The witness points of the distance are projected to the boundaries of the enlarged objects in order to return the penetration depth.
  

• If the original objects penetrate as well, we use EPA (Expanding Polytope Algorithm). EPA is fully explained in Gino's book. It is really worthy to take a look on it. Be sure on reading page 162 which is very helpful to get rid of many numerical errors. The general idea is to expand a 3D politope which is further used to extract the penetration depth. You can have a better idea if you have a look on Solid 3D.

To avoid jittering you should better allowed some little penetration and create a persistent manifold as Bullet does. The little penetration is easy to allow since we have already implemented a convex radius. At the beginning I "snobbed" the persistent manifold and only catched contact points (the deepest). But it turns out that this is very important and an optimal persistent manifold should be implemented. GJK retunrs always one contact point, so imagine for a capsule/box collision: it will give you a jittering due to only one contact at a time. You have to keep one contact point. The most clever, I have found, to do this, is to do it as bullet. Keeping the contact points that covers the maximum area of the manifold. Although, if you go further into Bullet's code, you will notice a risk for slippering.

Anyway, no more time to write, now..

take care !