GJK Algorithm

Basic Idea

Given two shapes, $A$ and $B$, the basic idea of the GJK algorithm is to spatially search by finding points along the Minkowski difference and iteratively discarding and adding them to a collection (referred to as the simplex) until they form a tetrahedron that encloses the origin. If ever such enclosing tetrahedron is found, then the Minkowski difference encloses the origin. This means that there is some point $a \in A$ and $b \in B$ such that $a - b = \vec{0}$, or, in other words, $a = b$, so the two shapes are touching.

Top-level Loop

The basic algorithm is as follows:

Vector s = support(b1,b2,new Vector(1,0,0));
Simplex simplex = new Simplex(s);
Vector dir = s.scaleBy(-1.0);

do {
Vector a = support(b1,b2,dir);
if (a.dot(dir) < 0) return false;

} while(!doSimplex(simplex,dir));

return true;


Accuracy Concerns

Because of the iterative method of the simplex handling, it is possible for you to never enclose the origin for shapes that are either only slightly touching or grossly intersecting. These problems are significant, and it is often the case that an alternative, more accurate algorithm (such at EPA or SAT) is used to compute details (such as penetration depth) of the collision.

Specific Implementation Details

Below are specific implementation snippets and explanations in an attempt to provide insight into the GJK algorithm implementation techniques.

Support Function

The GJK support function takes a pair of 3D bodies and a direction vector and returns the point along the Minkowski difference furthest in that direction. Because of the only approximate requirement of the algorithm, this mapping can be constrained to the vertices of the objects. In Java, the implementation is about as follows:

private Vector support(Body b1, Body b2, Vector dir) {
Vector p1 = b1.furthestPointInDirection(dir);
Vector p2 = b2.furthestPointInDirection(dir.scaleBy(-1.0));
Vector p3 = p1.minus(p2);
return p3;
}


It is interesting to note that the support function, $support(A-B)$, for bodies $A$ and $B$, can be distributed as $support(A) - support(B)$. So, the support function computes each individually by iterating through each vertex of the object and finding the one that has the largest dot product. That is, $support(A) = max(\vec{vertex} \cdotp \vec{direction})$. Then the subtraction is performed and the result is returned.

Simplex Solver

Here there be dragons.

page revision: 5, last edited: 15 Jul 2010 20:08