Game Engine Update- Why I chose the GJK over the SAT algorithm

As of 7/15 I have been working on Collision Detection between 3D objects. Initially I was using the SAT (Separation Axis Test) algorithm to detect collision between objects but decided that it would be better to use the GJK (Gilbert-Johnson-Keerthi) + EPA (Expanding Polytope Algorithm) instead.

Why? The GJK algorithm allows collision detection between any convex object. Meaning that the engine will not be restricted to only Oriented Bounding Boxes (OBB). Also, the GJK needs only support points which are easily computed using the Minkowski difference. Once the GJK returns that a collision did ocurred, it contains within itself the necessary simplex to calculate the closest points involved in the collision.

I do have to mention that the SAT has an advantage over the GJK, that is, it works great for penetrating shapes.

As of 8/31/15, the GJK algorithm has been implemented in the engine. My next step is to implement the EPA algorithm. The reason is that aside from finding if a collision occurred and where it happened, I also need to find out the penetration depth and the normal contact vector. These data is needed for the collision response.

These data:

  • Contact Points
  • Penetration Depth
  • Normal Contact vector

are known as Contact Manifold.

Harold Serrano

Computer Graphics Enthusiast. Currently developing a 3D Game Engine.