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:
- Collision Detection in Interactive 3D Environments, Gino Van der Vergen
- Real-Time Collision Detection, Christer Ericson
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.
Anyway, no more time to write, now..
take care !