# A divide-and-conquer implementation of the GJK algorithm

20 Aug 2018The *Gilbert-Johnson-Keerthi* (GJK) algorithm is a method for collision detection of convex polyhedra.
The method is used in multiple rigid body simulations for computer games.

Given:

- a set of points defining the convex polyhedron
*A* - a set of points defining the convex polyhedron
*B*

The algorithm returns:

- the distance of the polyhedra
- two closest points
- the two simplices (convex subsets of up to 4 points in 3 dimensions) of
*A*and*B*containing the two closest points

An n-dimensional simplex is the convex hull of n+1 points as shown in the figure below.

The algorithm makes use of the fact, that the distance between two sets *A* and *B* is the distance of the Minkowski difference to the origin:

where

The *GJK* algorithm iteratively updates a simplex until the closest point to the origin is found.

The algorithm iterates using support points.
Given a set *M* and a vector *d*, the support point is defined as the furthest point of *M* in direction *d*:

The *GJK* algorithm detects the two closest points of *A* and *B* as follows:

- Choose any point
*m*in*M(A,B)*in the Minkowski difference of*A*and*B*. - Set the initial simplex
*w*to_{0}*w*._{0}={m} - Let
*d*be the closest point of*w*to the origin._{k} - If
*d s(w*then return_{k}, -d)>=d s(M,-d)*d*. - Set
*w’*_{k+1}=w_{k}∪{s(M,-d)} - Set
*w*to the smallest simplex in_{k+1}*w’*still containing_{k+1}*s(M,-d)*. - Continue with step 3.

Note that step 3 requires finding the closest point of the simplex *w _{k}* to the origin.
Most implementations of the

*GJK*algorithm seem to use the following approach:

- Check if the origin is contained in the 3D simplex.
- If not, check whether the origin is near one of the 4 surfaces of the simplex.
- If the origin is not in the Delaunay region of any surface, check whether the origin is near one of the 6 edges.
- If not in a Delaunay region of an edge, find the closest point of the 4 points.

A much more compact implementation can be obtained using a divide-and-conquer approach:

- Let
*w*_{k}={w_{k0},w_{k1},…,w_{kn}} - Solve the least squares equation system
- If all
*t*and_{i}>=0*t*(or_{1}+t_{2}+…+t_{n}<=1*n=0*), then*w*is the closest point._{k0}+Ht - Otherwise take the closest point of all sub-simplices with
*n-1*dimensions using the approach above (*i.e.*recursion).

Note that this approach will visit each edge up to two times, and each point up to three times. The performance is not optimal, but it makes for a much more concise implementation.

The least squares solution is:

Here follows an implementation in Scheme (GNU Guile).
By using pairs of points from *A* and *B* instead of the Minkowski difference, one can keep track of the information required to determine the pair of closest points of *A* and *B* (instead of the closest point of *M* to the origin).

Here an example of two colliding cuboids simulated using this implementation is shown:

Any feedback, comments, and suggestions are welcome.

Enjoy!

**Update:**

I noticed that Baraff just uses a separating plane algorithm to achieve the same!