GJK Algorithm 4

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.


Figure 1: The Minkowski sum between polygons A and B.

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.


Figure 2: The Minkowski difference between polygons A and B.

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.


Figure 3: When polygons A and B intersect, their Minkowski difference contains the origin.

Support Function

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:

A\oplus B=\{a+b\;\mid\; a\in A,\; b\in B\}

The Minkowski difference can then be written as this:

A\ominus B=A\oplus(-B)

The support function must therefore return the following:

\{\max(dir\cdot x)\;\mid\; x\in A\ominus B\}

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:

\{\max(dir\cdot(a-b))\;\mid\; a\in A,\; b\in B\}

The distributing the dot product gives this:

\{\max(dir\cdot a-dir\cdot b)\;\mid\; a\in A,\; b\in B\}

The maximize function can now be divided:

\{\max(dir\cdot a)-\max(-dir\cdot b)\;\mid\; a\in A,\; b\in B\}

Because both maximize functions are independent, these can be split into separate function:

\{\max(dir\cdot a)\;\mid\; a\in A\}-\{\max(-dir\cdot b)\;\mid\; b\in B\}

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.

0-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.

1-Simplex

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.


Figure 4: A 1-simplex and the regions around it where the origin may lie.

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.

2-Simplex

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.


Figure 5: The 2-simplex and surrounding regions.

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

-Eric

  • aadne

    Hi, great article. I am trying to implement this in 3D. To be more precise, find the shortest distance between two cubes. Can I use the same stuff for 3D. What do I have to do differently? I appreciate all help I can get. Thanks again!

    • http://EntropyInteractive.com/ Eric

      The basic idea is the same. You are just building a 3D simplex (tetrahedron) instead of a 2D simplex (triangle). The part that gets more complicated is deciding which region around the simplex you are in as there are more of them. You will have to search around for how to do that, or try to figure it out yourself.

    • aadne

      I was hoping you could help me with a question. I am trying to find the minimum distance between two boxes in 3D using GJK distance algo. I would like to find the point (on the closest face of Minkowski Sum) closest to origin. I have GJK up and running and I get a final triangle-simplex on the closest face of minkowski sum. I then want to find the closest point on this face to origin (using point-plane distance check). The problem is that the point found might not be inside the face. It will for sure be on the plane, but could be outside the face. So I will need a check whether the point found is inside or outside the face. This should be easy to figure out if I only knew the fourth (4) minkowski sum point on this face. (I can get a triangle on closest face from GJK). Since I am dealing with OBBs (find minimum distance between 2 OBBs in 3D) my minkowski sum shape will also be an OBB. So how can I find this last point for the current closest face? I get a triangle from GJK (3 points in minkowski sum) but I actually need all 4 points in order to know if the closest point found is actually inside the rectagle based face. I hope you understand my question and could give some help. Thanks!

  • BuBa

    Very good article! Thanks!
    Would be nice to be extended for 3D cases :-)