This post is part of my Game Physics Series.
As mentioned earlier, all collision detection algorithms are essentially determining if the CSO of two shapes contains the origin. The collision detection I am going to introduce to you here, the Gilbert-Johnson-Keerthi (GJK) algorithm, is no different.
GJK is one of the most popular collision detection algorithms, because it is very efficient and intuitive (once you get it, of course). It basically attempts to find a subset, or a “simplex” to be precise, of the CSO that contains the origin. A simplex in n-dimension, by definition, is a minimal geometry in n-dimension that can be tightly tiled to fill up the space; for instance, a triangle is a 2D simplex, and tetrahedron is a 3D simplex. Inside the CSO of two colliding shapes, we can find a point (0D simplex), a line (1D simplex), a triangle (2D simplex), or a tetrahedron (3D simplex) that contains the origin.
Here’s GJK in its entirety:
- Initialze simplex to empty set (-1D simplex, technically).
- Use an initial direction to find a support point of the CSO.
- Add that support point to simplex (now the simplex has a single vertex).
- Find the closest point in the simplex to the origin.
- If the closest point is the origin, then the CSO contains the origin and the two objects are colliding. End GJK.
- Otherwise, reduce the simplex to the lowest dimension possible that still contains the closest point by discarding vertices.
- Use the direction from the closest point to the origin to find a new support point.
- If the new support point is not further along the search direction than the closest point, the two objects are not colliding. End GJK.
- Add support point to simplex as a new vertex. Go to 4.
Visual Example in 2D
A picture is worth a thousand words. Let’s look at what is going on visually in 2D (the highest-dimension simplex we will get here would be a triangle).
Suppose we have a CSO that is shaped like an ellipse. The cross indicates the origin. The arrow is the initial direction we pick to find the first support point (the black dot).
The simplex now only contains one vertex, so the vertex is the closest point to the origin. The next search direction is from the vertex to the origin. A new support point is found and added to the simplex as a new vertex. The simplex is now a line segment.
The origin is not on the line segment, so we continue the algorithm. The search direction points from the closest point on the line segment to the origin towards the origin. The direction is basically the line normal. A third support point is found and added to the simplex. Now the simplex is a triangle.
The triangle does not contain the origin. And the closest point to the origin in the triangle lies on the bottom right side. Thus, the top left vertex of the simplex is discarded. The simplex is now a line segment again. The direction from the closest point to the origin on the line towards the origin is used to find a new support point.
With the new support point added to the simplex, the simplex is now a triangle again.
This time, the simplex contains the origin, so we end the GJK algorithm and conclude that the CSO contains the origin.
If during any iteration we find that the new support point is not further along the search direction than the existing simplex vertices, then the origin must be outside the CSO, and we can terminate GJK.
For GJK in 3D, not only can the simplex reduction phase end up with a point or a line segment, it can also end up with a triangle due to the one extra dimension compared to 2D.
End of GJK
GJK only tells us whether two shapes collide (it essentially returns true or false). The next step is to generate contact information required during the resolution phase in the physics engine.
Recall that the support function of a CSO is a combination of the results of support functions of two individual shapes. In order to properly generate the required contact information, we will need to keep track of both the individual results and the combined result.
Basically, when we store this:
We also want to store these:
I will elaborate on this matter when I talk about the Expanding Polytope Algorithm (EPA).