gjk.c – Gilbert-Johnson-Keerthi In Plain C

This is a rough but fast implementation of GJK collision detection algorithm in plain C. Just one C file, less than 200 lines, no dependencies. It is in 2D for now, full 3D version is upcoming... This 2D-version uses Minkowski sums and builds a triangle-simplex in Minkowski space to tell if two arbitrary convex polygons are colliding. 3D-version will be roughly the same, but will build a tetrahedron-simplex inside a 3-dimensional Minkowski space. It currently only tells if there is a collision or not. C-code for distance and contact points coming soon.

Disclaimer

Fuck licenses and copyright. I made it for learning purposes, this is public knowledge and it's absolutely free for any usage.

Usage Example

This is an illustration of the example case from dyn4j.

The two tested polygons are defined as arrays of plain C vector struct type. This implementation of GJK doesn't really care about the order of the vertices in the arrays, as it treats all sets of points as convex polygons.

struct _vec2 { float x; float y; };
typedef struct _vec2 vec2;

...

int main(int argc, const char * argv[]) {
    
    // test case from dyn4j

    vec2 vertices1[] = {
        { 4, 11 },
        { 4, 5 },
        { 9, 9 },
    };
    
    vec2 vertices2[] = {
        { 5, 7 },
        { 7, 3 },
        { 10, 2 },
        { 12, 7 },
    };

    size_t count1 = sizeof (vertices1) / sizeof (vec2); // == 3
    size_t count2 = sizeof (vertices2) / sizeof (vec2); // == 4
    
    int collisionDetected = gjk (vertices1, count1, vertices2, count2);
    
    printf (collisionDetected ? "Bodies collide!\n" : "No collision\n");
    return 0;
}

How It Works

The goal of this explanation is to help people visualize the logic of GJK. To explain it we have to oversimplify certain things. There's no complicated math except basic arithmetic and a little bit of vector math, nothing more, so that a 3rd-grader could understand it. It is actually not very difficult to have GJK algorithm explained in a proper understandable way from ground up.

At the very top level GJK tells if two arbitrary shapes are intersecting (colliding) or not. The algorithm is used to calculate the depth of intersection (collision distance). A collision occurs when two shapes try to occupy the same points in space at the same time. The space can be of any nature. It might be your in-game world simulation, or a calculation on a table of statistical data, or a built-in navigation system for a robot or any other application you can imagine. You can use it for calculating collisions of solid bodies and numeric intersections of any kind. You can have as many dimensions as you want, the amount of dimensions does not really matter, the logic is the same for 1D, 2D, 3D, etc... With GJK you can even calculate collisions in 4D if you're able to comprehend this.

The algorithm itself does not require any hard math whatsoever, it's actually very intuitive and easy. It takes an arithmetic difference of two shapes by subtracting all points of one shape from all points of another shape. If two shapes share a common point, subtracting that point from itself results in a difference of zero. So, if zero is found in the result then there's a collision. In fact, the algorithm does not have to calculate all differences for all possible pairs of points, only a small subset of significant points is examined, therefore it works very fast while being very accurate.

In order to understand GJK one has to build an imaginary visualization of what is going on under the hood. Once you see the picture in your head, you can implement it and even tweak it for your needs.

A 1D Intro

Let's start with a naive example of computing a difference of two shapes in one dimension. A segment of a number line is an example of 1D-shape. Imagine we have two segments on the number line: segment [1,3] and segment [2,4]:

Zero is our point of reference on the number line, so we call it the Origin. Easy enough. It is obvious that our segments occupy some common region of our 1D-space, so they must be intersecting or colliding, you can tell that just by looking at the representation of both segments in same 1D-space (on the same line). Let's confirm arithmetically that these segments indeed intersect. We do that by subtracting all points of segment [2,4] from all points of segment [1,3] to see what we get on a number line.

1 - 2 = -1
1 - 3 = -2
1 - 4 = -3

2 - 2 =  0
2 - 3 = -1
2 - 4 = -2

3 - 2 =  1
3 - 3 =  0
3 - 4 = -1

We got a lot of numbers, many of them more than once. The resulting set of points (numbers) is larger than each of our initial sets of points of two shapes. Let's plot these resulting points in our 1D-space and look at the shape of resulting segment on the number line:

So after all we have resulting segment [-3,1] that covers points -3, -2, -1, 0 and 1. Because two initial shapes had some points in common the resulting segment contains a zero. This comes from a simple fact, that when you subtract a point (which is a number) from itself you inevitably end up with a zero. Note, that our initial segments had points 2 and 3 in common. When we subtracted 2 from 2 we got 0. When we subtracted 3 from 3 we also got a zero. This is quite obvious. So, if two shapes have at least one common point, because you subtract that point from itself, the resulting set must contain zero (the Origin) at least once. This is the key of GJK which says: if the Origin is contained inside the resulting set then initial shapes must have collided or kissed at least. Once you get it, you can then apply it to any number of dimensions.

Now let's take a look at a counter-example, say we have two segments [-2,-1] and [1,3]:

We can visually ensure that segment [-2,-1] occupies a different region of number line than that of segment [1,3]. There's a gap between our initial shapes, so these two shapes do not intersect in our 1D-space, therefore there's no collision. Let's prove that arithmetically by subtracting all points of any of the two segments from all points of the other.

1 - (-1) = 1 + 1 = 2
1 - (-2) = 1 + 2 = 3

2 - (-1) = 2 + 1 = 3
2 - (-2) = 2 + 2 = 4

3 - (-1) = 3 + 1 = 4
3 - (-2) = 3 + 2 = 5 

And we again draw the resulting segment on a number line in our imaginary 1D-space:

We got another bigger segment [2,5] that represents a difference of all the points of two initial segments but this time it does not contain the Origin. That is, the resulting set of points does not include zero, because initial segments did not have any points in common so they indeed occupy different regions of our number line and don't intersect.

Now, if our initial shapes were too big (long initial segments) we would have to calculate too many differences from too many pairs of points. But it's actually easy to see, that we only need to calculate the intersection between the endpoints of two segments, ignoring all the inside points of both segments.

Consider two segments [10,20] and [5,40]:

Now subtract their four endpoints from each other:

10 - 5  =   5
10 - 40 = -30

20 - 5  =  15
20 - 40 = -20

The resulting segment [-30,15] would look like this:

Notice that when we subtract the opposite points of initial shapes from one another, the resulting difference number lands either to the left or to the right of the Origin (which is zero) on the number line. Say, we take the leftmost point of segment [5,40] (number 5) and subtract it from the rightmost point of segment [10,20] (number 20) the resulting number 20 - 5 = 15 is positive, so it lands to the right of zero on the number line. Then we take the rightmost point of segment [5,40] (number 40 this time) and subtract it from the leftmost point of segment [10,20] (number 10) the resulting number 10 - 40 = -30 is negative, so it lands to the left of zero on the number line that is exactly opposite to the first positive difference point 15. We say these points are opposite directionwise. Therefore the Origin is between two resulting points enclosing it.

We ignored all insignificant inter