User login

Home

GJK Algorithm

Sun, 08/08/2010 - 20:22 — golgobot

Introduction

The Gilbert-Johnson-Keerthi Algorithm is a collision detection algorithm and an alternative to Separation of Axes discussed earlier. While slightly less intuitive geometrically, it is more efficient computationally. This algorithm uses the fact that the shortest distance between two convex polygons is the shortest distance between their Minkowski Difference and the origin. If the Minkowski Difference encompasses the origin then the two objects intersect.

The Minkowski Sum and Difference

The Minkowski Sum is simply the sum of two sets of points, say $ A $ and $ B $. That is, every point in set $ A $ is summed with every point in set $ B $. More formally:

$ A \oplus B = {\mathbf{a} + \mathbf{b} \colon \mathbf{a} \in A, \mathbf{b} \in B} $

For example, if $ A={(1,1), (2,0), (-1,-2)} $ and $ B={(-1,3), (4,2)} $ then $ A \oplus B={(0,4),(5,3),(1,3),(6,2),(-2,1),(3,0)} $. The Minkowski Difference is just the Minkowski Sum where one of the sets of points is negative.

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

The application below demonstrates the geometry of the Minkowski Difference. The red point sets are $ A $ and $ B $. The blue point set is the Minkowski Difference. The convex hull of each set of points is also shown to demonstrate the assertion made in the introduction that if the Minkowski Difference of two convex polygons contains the origin then the two polygons intersect. You can move the red vertices or the entire set of points. You can also increase or decrease the number of points in each set. Play around and try to get a feel for how this works geometrically. The convex hulls of point sets $ A $ and $ B $ turn red when they intersect.

GJK

Get Adobe Flash player

The GJK Algorithm

GJK reduces the problem of finding the closest distance between two convex polygons to the finding the closest difference between their Minkowski Difference and the origin. At first this does not seem like much of an improvement, but later on we'll see why this is actually more efficient. Let's start by solving this problem in terms of the full Minkowski Difference. Geometrically, this is the easiest way to visualize the algorithm. Later we'll see how to solve this problem without explicitly computing the full Minkowski Difference.

The algorithm starts by picking a point in the Minkowski Difference. This point can be randomly chosen or chosen based on previous knowledge. But for now let's pick a random point. This point is now our simplex. A simplex is a generalization of a tetrahedral region of space. A point is a 0-simplex. A line is a 1-simplex. A traingle is a 2-simplex, and a tetrahedron is a 3-simplex. That is, the points in a $ n $-simplex must be able to span an affine space in $ n $ dimensions.

The problem can be broken into three parts depending on the size of the simplex.

0-Simplex

If we have a 0-simplex, a point, then we create a vector, $ \mathbf{d} $ that is drawn from that point to the origin. Then we find the point in the Minkowski Difference that is furthest along that line. This is accomplished through a support mapping of $ C=A \ominus B $. This support mapping becomes important when eliminating the need to compute the entire Minkowski Difference. It takes a set of points and a vector, $ \mathbf{d} $, and returns the point in that set that is farthest along $ \mathbf{d} $. Each time we compute the point, $ \mathbf{a} $, farthest along $ \mathbf{d} $ we check to see if that point actually brings us closer to the origin. If it does not bring us closer then we terminate and there is no intersection. Otherwise we place the point that the support mapping returned into our simplex and we now have a 1-simplex. We only continue if

$ \mathbf{a} \cdot \mathbf{d} < 0 $

1-simplex

The red line below in our example is our 1-simplex. Like the 0-simplex we are going to try to find a direction to the origin and then find a point closer to the origin. If we cannot find that point we terminate.

Let's take a closer look at the 1-simplex shown below

Point $ \mathbf{a} $ is the last point placed in the simplex. The first step is to determine whether the origin is in region 1, 2, or 3. We can begin by immediately eliminating region 3. We know the origin cannot be in region 3 because in our last step $ \mathbf{a} $ is defined as being closer to the origin than $ \mathbf{b} $. Then it's simply a matter of doing a bit of math.

$Region =$ \begin{cases} 2, & \mbox{if $\vec{ab} \cdot \vec{aO} > 0$} \\ 1, & \mbox{otherwise} \end{cases}

Where $ \vec{aO} $ is a vector from $ \mathbf{a} $ to the origin. If the origin is in region 1 then we remove $ \mathbf{b} $ from the simplex and proceed with the 0-simplex case as shown above. If the origin is in region 2 then we create a new direction vector, $ \mathbf{d} $, that is the shortest line from the 1-simplex to the origin. This is the black vector in the example figure. Again we submit $ \mathbf{d} $ and $ C $ to our support mapping to find the point, $ \mathbf{a} $, in $ C $, the Minkowski Difference, that is farthest along $ \mathbf{d} $. If $ \mathbf{a} \cdot \mathbf{d} < 0 $ we terminate the algorithm because there is no point in $ C $ that is closer to the origin than the 1-simplex. Otherwise, if there is a point closer we add that to the simplex. We now have a 2-simplex.

2-Simplex

In our example we now have a 2-simplex. Like the other simplexes we are trying to find a vector, $ \mathbf{d} $, that is the shortest line between our simplex and the origin. Intuitively, we can look at the example and see that the black vector is $ \mathbf{d} $.

But in order to solve this problem algorithmically we need to break our simplex down into regions just as we did in the 1-simplex example. The 2-simplex has 7 regions in which the origin might lie. Let's break down each region shown below.

Remember that $ \mathbf{a} $ is the newest point in our simplex. We can immediately discount region 6 because $ \mathbf{a} $ is by definition closer to the origin than the line $ \vec{bc} $, which is our old simplex. We also discount regions 5 and 7. I'll leave the reason for discounting 5 and 7 as an exercise for the reader. Now we only have 4 regions to worry about. To start we can choose either line $ \vec{ac} $ or line $ \vec{ab} $ and determine which side of that line the origin lies on. Let's choose $ \vec{ac} $ to start. If $ \vec{aO} \times \vec{ac} > 0 $ then we know that the origin lies to the right of the line $ \vec{ac} $. So now it can be in either region 2 or 3. If $ \vec{ac} \cdot\vec{aO} > 0 $ then the origin is in region 2 and our new simplex is $ \vec{ac} $ and we proceed with the 2-simplex case. Otherwise, the origin lies in region 3 and the new simplex is simply the point $ \mathbf{a} $, in which case we proceed with the 1-simplex case.. If it turns out the origin lies to the left of the line $ \vec{ac} $ then we've eliminated region 2. So we're left with regions 1, 3, and 4. Now we can take line $ \vec{ac} $ and find out if the origin is to the left or right. If $ \vec{ab} \times \vec{aO} > 0 $ then the origin lies to the left of $ \vec{ab} $. So now the origin can only be in regions 3 or 4. If $ \vec{ab} \cdot\vec{aO} > 0 $ then the origin is in region 4 and our new simplex is $ \vec{ab} $ and we proceed with the 2-simplex case. Otherwise, the origin lies in region 3 and the new simplex is the point $ \mathbf{a} $, in which case we proceed with the 1-simplex case. If the origin lies both to the left of $ \vec{ac} $ and to the right of $ \vec{ab} $ then the origin must lie inside our simplex. Eureka! In this case, the Minkowski Difference contains the origin, the algorithm terminates and our two convex polygons intersect. We can show the 2-simplex case in pseudocode 

if aO cross ac > 0 //if O is to the right of ac
    if aO dot ac > 0 //if O is ahead of the point a on the line ac
        simplex = [a, c]
        d =-((ac.unit() dot aO) * ac + a)
    else // O is behind a on the line ac
        simplex = [a]
        d = aO
else if ab cross aO > 0 //if O is to the left of ab
    if ab dot aO > 0 //if O is ahead of the point a on the line ab
        simplex = [a, b]
        d =-((ab.unit() dot aO) * ab + a)
    else // O is behind a on the line ab
        simplex = [a]
        d = aO
else // O if both to the right of ac and to the left of ab
    return true //we intersect!

In the algorithm above we only have to ever branch twice. The last else returns true. This means this 2-simplex contains the origin. This is the case with our example shown below.

Support Mapping

Remember the support mapping is a function that takes a set of points, $ P $, and a direction vector, $ \mathbf{d} $, and returns the point in that set that is farthest along $ \mathbf{d} $. If our set of points we pass to the support mapping is the Minkowski Difference, $ C $, of point sets $ A $ and $ B $, the number of points being passed to that function is $ mn $ where $ m $ is the number of points in set $ A $ and $ n $ is the number of points in set $ B $. This gives an efficiency of the support mapping of $ O(mn) $. We can actually reduce that to $ O(m+n) $ by noting that the Minkowski Difference is a linear function. Our support mapping is the max value of a set of points created by a linear function. Therefor:

$ \max (\mathbf{d} \cdot C) = \max (\mathbf{d} \cdot (A \oplus -B)) = \max (\mathbf{d} \cdot A-\mathbf{d} \cdot B) = \max (\mathbf{d} \cdot A) - \max (-\mathbf{d} \cdot B) $

So our support mapping does not actually need the full Minkowski Difference. It can compute the max point along $ \mathbf{d} $ in the Minkowski Difference from the points in the individual sets, $ A $ and $ B $. This greatly increases the efficiency of the algorithm. Our support mapping can also contain performance increases by having specific knowledge of the set of points it is given. For example, it is very easy to compute the max distance from a point to a circle. The support function could also know the vertex order of the point set it is passed, so instead of searching each point randomly, it can choose a point and proceed along by visiting each neighboring vertex in the direction of the origin. This is a Hill Climbing algorithm.

Conclusion

The GJK algorithm is extremely efficient, and has lots of room for extra efficiencies. It is easy to implement, and easy to understand. References to come. Please leave comments and questions. If it seems like I skipped something I can make it more clear.