The Gilbert-Johnson-Keerthi (GJK) algorithm is an efficient method for computing the distance between two convex shapes. It has become a popular method for real-time 3D collision detection. While less commonly used for 2D collision detection, the GJK algorithm still maintains several of its advantages. Its biggest disadvantage is that the algorithm can be conceptually difficult to understand (although it is easy to implement). This tutorial will explain how the GJK algorithm works in detail and demonstrate how to apply it to 2D collision detection.
Minkowski Sum (and Difference)
The Minkowski sum is a simple operation to describe, but can be difficult to visualize. Given two sets, the Minkowski sum is the set of every element in the first set, added to every element in the second set. For example, consider the following two sets of points:
Set A: (1, 1), (2, 1)
Set B: (-2, 2), (-1, 2)
The Minkowski sum of A and B would be these four points:
(1, 1) + (-2, 2) = (-1, 3)
(1, 1) + (-1, 2) = (0, 3)
(2, 1) + (-2, 2) = (0, 4)
(2, 1) + (-1, 2) = (1, 3)
Figure 1 shows the Minkowski sum between the polygons A and B. Notice that while the resulting shape contains an infinite number of points, its boundary is defined by a very small subset of those. Not even all of the combinations of the vertices of A and B are needed to create the shape. This will turn out to be one of the reasons the GJK algorithm is efficient.
The GJK algorithm uses a closely related operation, often called the Minkowski difference. Instead of adding the points, they are subtracted. This would be the equivalent of a Minkowski sum with the negative of the second set of points. Using the same to shapes from before, figure 2 shows their Minkowski difference.
The most important property of the Minkowski difference is the fact that if two objects are overlapping, the Minkowski difference of their shapes must contain the origin. It is simple to see why this is the case. Because the Minkowski difference subtracts every point in one set from every point in another, if there is any point in common between the two sets, that point is subtracted from itself. The Minkowski difference must therefore contain the point (0, 0), which is the origin. Figure 3 demonstrates the Minkowski difference between two intersecting polygons. The resulting shape contains the origin as expected.
We can determine if two shapes intersect by finding whether their Minkowski difference contains the origin or not. The GJK algorithm does this by attempting to construct a triangle (or tetrahedron in the three dimensional case), with corners on the boundary of the Minkowski difference, that contains the origin. If the two shapes are convex, it is possible to form such a triangle if and only if the two shapes intersect.
Instead of constructing the Minkowski difference directly, a support function is used. It takes a direction, and returns the point in the Minkowski difference that is furthest in that direction. Let the Minkowski sum between shapes A and B be expressed as the following:
The Minkowski difference can then be written as this:
The support function must therefore return the following:
This has not improved the situation yet. The point in the Minkowski difference that maximizes this dot product still needs to be found, but using some algebra, this can be reduced to a simpler problem. Substituting the definition of the Minkowski difference into the support function results in this:
The distributing the dot product gives this:
The maximize function can now be divided:
Because both maximize functions are independent, these can be split into separate function:
The original support function can be divided into two separate support functions. By taking the support of the first shape and subtracting the support of the second shape in the opposite direction, we get the same result. Intuitively it is easy to understand why this works. If we want the point that is furthest in a given direction in the Minkowski difference, first we would go as far as possible in that direction in the first shape. Because the second shape is being subtracted from the first, we would then want the point that is furthest in the opposite direction. Using this technique, the Minkowski difference no longer needs to be explicitly constructed.
Construction the Simplex
A simplex is simply a generalization of a triangle. A 0-simplex is a single point, 1-simplex is a line, a 2-simplex is a triangle, and a 3-simplex is a tetrahedron. Because we are working in two dimensions, only the 0-simplex, 1-simplex, and 2-simplex are of interest. The goal of the GJK algorithm is to build a 2-simplex (a triangle) that contains the origin or determine that such a simplex cannot be constructed. This can be done by choosing a random direction and calling the support function. After that, points will be iteratively added and removed from the simplex. The algorithm is outlined in the following pseudo-code.
function boolean intersects(Shape a, Shape b) // chose an initial direction Vector direction = (1, 0) // create the initial simplex Simplex simplex simplex = [getSupport(a, b, direction)] // set the direction to point towards the origin direction = -simplex.first() while(true) // add a new point simplex.add(getSupport(a, b, direction)) // see if the new point was on the correct side of the origin if(!isSameDirection(direction, simplex.a) return false // process the simplex if(processSimplex(simplex, direction)) return true function Vector getSupport(Shape a, Shape b, Vector direction) return a.getSupport(direction) - b.getSupport(-direction) function boolean isSameDirection(Vector v1, Vector v2) return v1.dot(v2) > 0
Other than processSimplex, that is the entire algorithm. The first thing we do is create an initial simplex. Since only one point is needed, an arbitrary direction is chosen and the support function is called with that direction. After the first point is added, a new direction is needed. Every time a new direction is chosen, it should be in towards the origin. With only one point, this is easy. The negative of our first point is the vector from that point, to the origin. After the initial simplex is created, the main loop is entered.
The main loop performs three actions. First a new point is added to the simplex using the getSupport function and the previous direction. We then check if the new point is on the same side of the origin as the last direction. If it is not, we have tried to get a point that was as far as possible in the chosen direction, but could not get all the way to the origin. This means there are no points on the other side of the origin, so the simplex will never be able to contain it. The algorithm can therefore terminate with the conclusion that the shapes do not intersect. The last step is the most complicated and that is the processSimplex function.
The process simplex function does three things. It checks if the origin is in the existing simplex. If this is the case, the shapes intersect. Second, it choses a new direction to expand the simplex in. This direction should be the vector from the closest point on the simplex to the origin. Finally, it removes any points from the simplex that are no longer necessary. How this is done is dependent on the size of the simplex. As mentioned earlier, because we are working in 2D, we are concerned with the 0-simplex, 1-simplex, and 2-simplex.
The 0-simplex is a single point, and is the easiest to handle. The desired direction if simply the vector from the point to the origin. This case does not even need to be handled explicitly. We always have at least one point in the simplex and just before calling processSimplex, another is added. A 0-simplex will therefore never be passed into processSimplex.
The 1-Simplex is a line. Let A be the most recent point added to the simplex. The area around the line can be divided into four regions as shown in figure 4.
We need to determine which of these regions the origin lies in. First, region 4 can immediately be eliminate because we were previously at B, then move towards the origin. A must be in the same direction as the origin or we would have terminated already so region 4, which is in the opposite direction, cannot contain the origin. To test if the origin is in region 1, we simply need to determine if the vector AB is in the same direction as AO. If it is, A becomes the new simplex (a 0-simplex) and the new direction vector is AO.
If the origin is not in region 1, it must be in region 2 or 3. These can be handled as a group. We first need a vector perpendicular to AB. In two dimensions, a vector perpendicular to (x, y) is simply (-y, x). This vector also needs to be in the direction of AO. If it is not, simply negate it. Instead of performing this check using an if statement, the dot product is used. Remember that the dot product is positive if two vectors are in the same direction, and negative if they are in opposite directions.
The 2-simplex is the most complicated of the three cases. Let A, B, and C be the points of the simplex with A being the most recently added followed by B then C. Figure 5 shows the seven regions around the 2-simplex.
Again, we need to determine which region contains the origin. Regions 1, 2, and 3 can be immediately eliminated. This is because in the previous iterations we already determined that the origin must be between B and C and in the direction of A.
There are four remaining regions. If the origin is in the direction of AB and in the direction of the vector perpendicular to AB facing away from C, it is in region 4. Similarly, if the origin is in the direction of AC and in the direction of the vector perpendicular to AC facing away from B, it is in region 6. If the origin is in the opposite direction as both AB and AC, it is in region 5. Finally, if none of these cases are true, the origin is in region 7.
If the origin is in region 4, A and B become the new simplex and the search direction is perpendicular to AB facing away from C. Region 6 is similar with AC becoming the new simplex. If the origin is in region 5, A becomes the new simplex and the search direction is AO. Finally, if the origin is in region 7, we have determined that the Minkowski difference does contain the origin and the shapes intersect. The 2-simplex can be resolved using four if statements, of which only two ever need to be evaluated.
function boolean processSimplex(Simplex simplex, Vector direction) // we only need to handle to 1-simplex and 2-simplex if(simplex.size == 2) // 1-simplex // AO is in the same direction as AB if(isSameDirection(-simplex.a, simplex.b - simplex.a)) // get the vector perpendicular to AB direction = (simplex.b - simplex.a).perpendicular // set direction to face O // if AO is not in the same direction as AB, the dot product will be negative // the scaling will therefore flip the direction to the opposite (correct) direction direction.scale(-simplex.a.dot(direction)) // A and B remain in the simplex simplex = [simplex.a, simplex.b] else direction = -simplex.a // only A remains in the simplex simplex = [simplex.a] else // 2-simplex Vector AB = simplex.b - simplex.a Vector AC = simplex.c - simplex.a Vector AO = - simplex.a // the vector perpendicular to AB facing away from C Vector ACB = AB.perpendicular ACB = ACB.scale(ACB.dot(-AC)) // the vector perpendicular to AC facing away from B Vector ABC = AC.perpendicular ABC= ABC.scale(ABC.dot(-AB)) if(ACB.isSameDirection(AO)) if(AB.isSameDirection(AO)) // region 4 direction = ACB simplex = [simplex.a, simplex.b] return false else // region 5 direction = AO simplex = [simplex.a] return false else if(ABC.isSameDirection(AO)) if(AC.isSameDirection(AO)) // region 6 direction = ABC simplex = [simplex.a, simplex.c] return false else // region 5 (again) direction = AO simplex = [simplex.a] return false else // region 5 else // region 7 return true