The GJK algorithm is a popular algorithm used to determine collision among convex objects. The mathematics behind the algorithm is quite simple. However, implementing it in code is a bit complicated. It requires a good visualization of what the algorithm is doing. And this is what I want to share with you. I want to help you visualize the algorithm so you can implement it in your code.
Note, one of my goal is to avoid using mathematics while explaining the algorithms. I will try my best to explain them using just visuals.
Let's begin,
Simplex
In collision detection, the term Simplex is used a lot. A Simplex refers to either a point, line segment, triangle or tetrahedron. For example, the 0-simplex is a point, the 1-simplex is a line segment, the 2-simplex is a triangle, and the 3-simplex is a tetrahedron.
Supporting Point
In a convex object, the supporting point is the most distant point in a given direction. In some books, they are referred as extreme points. In the illustration below, the supporting point in direction d is P.
Minkowski Difference
In collision detection, there are two important operations which you need to understand. They are the Minkowski Sum and the Minkowski Difference. Visually, the Minkowski sum can be seen as the region swept by Object A translated to every point in Object B. See the illustration below:
The Minkowski difference is the region swept by Object A translated to every point negated in Object B. See the illustration below:
The Minkowski difference is a significant operation in collision detection because two objects A and B collide if their Minkowski difference contains the origin. The GJK algorithm uses this fact to determine if two convex objects have collided.
GJK Algorithm
The GJK uses supporting point in the Minkowski Difference to get close to the origin point. As it gets close to the Origin point, the GJK stores the supporting point in a set Q. If the set Q encloses the origin, a collision has occurred. Here is a visual representation of the GJK. (Assume M is a Minkowski difference.)
- The algorithm arbitrarily starts with the vertex A as the initial simplex in set Q, Q={A}.
- Searching for the supporting point in direction -A results in B. B is added to the Simplex set, Q={A, B}
- The point in the convex hull Q closest to the origin is C. Because both A and B are needed to express C as a convex combination, both are kept in Q.
- D is the supporting point in direction -C and it is added to Q, giving Q={A, B, D}.
- The closest point in the convex hull Q closest to the origin is now E.
- Because only B and D are needed to express E as a convex combination of vertices in Q, Q is updated to Q={B, D}. The supporting point in direction -E is F, which is added to Q.
- The point on the convex hull Q closest to the origin is now G.
- D and F are the smallest set of vertices in Q need to express G as a convex combination. Q is updated to Q={D, F}.
- At this point, because no vertex is closer to the origin in direction -G than G itself, G must be the closest point to the origin, and the algorithm terminates. No collision occurred.
I hope this visualization helps.
Note: These visualization steps were taken from this amazing book Real-Time Collision Detection. If you are serious about developing a Collision-Detection system in computer graphics, you need to buy this book.
