Click and drag the shapes!
GJK is a collision testing algorithm with two key characteristics:These characteristics are extremely useful in physics simulations and video games where objects may have varied and complicated geometry.
It was originally published by E. G. Gilbert, D. W. Johnson, and S. S. Keerthi in 1988.
In order to test for intersection on generalized shapes, you need to define a shape. In this case, a shape is a set of points that are infinitely dense and contiguous.
An intersection is when two shapes share at least one point. Equivalently, it is when their vector difference is zero:
if: a = b
then: a - b = 0However, when describing shapes this way, it introduces a problem for actual implementations: How can we tell if two shapes share a point if they each contain an infinite number of points?
Click and drag the shapes! Click Animate to see how the Minkowski Sum is created.
Blue Circle + Pink Square = Purple Shape. The origin is the black dot.A Minkowski Sum is a mathematical sum of two shapes, defined as a set containing the vector sums of each of their infinitely many points. More intuitively, it can be formed by translating one shape and sweeping it around such that its origin is placed everywhere within the other.
The resulting shape’s center is located at the sum of the original shapes centers.
Minkowski Sums give us a potential way of fixing our first problem, since they allow us to operate on all the points as a unit. However, it is not yet clear how to check for a shared point between the original shapes.
Click and drag the shapes! Click Animate to see how the Minkowski Difference is created.
Blue Circle - Pink Square = Purple Shape. The origin is the black dot.
A Minkowski Difference is just like a sum, except that it is defined by the set of differences (not sums) of position vectors. As the animation shows, the resulting shape is created by summing the circle with the inverse of the square, which is reflected over the origin.
Note an important property of the Minkowski Difference:When the shapes intersect, the difference always contains the origin.
Why is this? Well, if the difference between points is zero, they are colliding. That difference will also be in the Minkowski difference. Therefore, the origin will be in the Minkowski difference!
This moves us another step towards our goal. Instead of comparing an infinite number of points, we only need to test if the origin is in the Minkowski difference. However, we can’t actually construct an infinite set of points, so how do we test this efficiently?
Gray Arrow: The direction passed to the support function.
Blue Dot: Farthest point on the Circle in the direction as given by the Circle's
support function
Pink Dot: Farthest point on the Square in the opposite direction as given by the
Square's support function
Orange Dot: The vector sum of the Blue Dot (in vector form) and the Pink Dot (in
vector form)
Orange Polygon: The area enclosed by dots (the convex hull).Click and drag the shapes!
Move the arrow to find support points, or click Auto-Rotate to have the arrow do a complete rotation.
Click Show Vector Difference to see how the point on the Minkowski difference is found.
Instead of trying to work with the entire Minkowsi difference, we can find individual points inside of it and do our calculations with those. To find useful points in their difference, each shape must have a defined Support Function.
A support function takes a direction vector and returns the point on the shape farthest along that direction. If we pass a direction to the support function of one shape and the opposite direction to the support function of the other, we can compute their vector difference to get a point in the Minkowski difference.
Not only that, but the points will be on the exterior of the difference, since we picked the points farthest in either direction. Using multiple points we can create a Convex Hull, an area bounded by the vertices. This convex hull is a good approximation of the entire difference, as long as the original shape is also convex.
Now we can already try testing for intersection between the convex hull and the origin, but how do we know when to stop? What directions should we choose? How do we make this fast?
The final algorithm looks like this:
Initialization:
1. Pick an arbitrary starting direction.
2. Find a point in the Minkowski difference using the support function.
3. Add this point to a Simplex, a shape created using the minimum number of
points in a given dimension. For example, a point in 0 dimensions, a
line in 2, a triangle in 3, and a tetrahedron in 4.
These shapes are easy to test for intersection, so we will find simplex
subsets of the convex hull and perform the intersection tests on them.
Main Loop:
4. Choose a new direction from the simplex towards the origin.
5. Get a point with the support function using the direction.
6. If the point didn't pass the origin, then the origin must be outside the
convex hull. Terminate and return false.
7. Add the new point to the simplex.
8. Test to see if the origin intersects the simplex.
If it does, keep the entire simplex.
If it does not, reduce to the closest, largest simplex that surrounds
the origin when it is mapped onto the simplex's dimension.
9. If we found a simplex of the maximum dimension that surrounds the origin,
terminate and return true. Otherwise, return to step 4.Click and drag the shapes! Click Run to see each iteration.
This algorithm converges fast, making it near constant time complexity. However, you find that there are unusual cases where the algorithm takes longer to converge. How many iterations can you make it take?
Click and drag the shapes!
The reason that concave shapes do not work with GJK is because of the assumption that the convex hull is a subset of the Minkowski difference. For concave shapes, this is not always the case.
Try moving the corner of the triangle into the hourglass near the center. The shapes will turn green before they have touched! GJK is treating the hourglass like a rectangle and ignoring the hollow parts.
This is because the support function only returns points farthest in a particular direction. It will never return a point on the interior of the shape. Concave shapes by definition have edges on their interior, which will never be found by the support function or influence the convex hull.
Click and drag the shapes!
This can be solved relatively easily by breaking up shapes into parts. By making the hourglass out of two triangles instead, the collision now works as intended. For complex concave shapes this may require many subshapes, reducing performance. This is usually not an issue though, since bounding convex shapes can be checked against first to rule out most collisions. For video games, they even have the option of ignoring small details since the collisions of the bounding shape are a good approximation.