GJK Collision Detection with SDL3: A Step-by-Step Guide

The Gilbert-Johnson-Keerthi algorithm in video (GJK)

Explanation in steps of the GJK algorithm

Step 1: Support Function

Compute a point on the Minkowski Difference of the two shapes in a given direction.
This is done by:

support = furthest_point_in_A(direction) - furthest_point_in_B(-direction);

This gives one point on the combined shape that is furthest in the direction.

Step 2: Initialize Simplex

Start with an initial direction (e.g., towards the other shape or just direction = {1, 0}).
Add the first support point to a simplex, which is just a list of up to 3 points in 2D (or 4 in 3D).
Change the direction toward the origin (usually -support).

Step 3: Iterative Loop

Loop until either:

You confirm a collision, or
You prove no collision.

In each iteration:

Get a new support point in the current direction.
If the new point doesn’t pass the origin (dot(new_point, direction) < 0):
- No collision (exit).
Add the point to the simplex.
Use the simplex to:
- Check if the origin is enclosed.
- Update the direction for the next support point using geometric logic.

Step 4: Simplex Handling

The simplex is managed differently depending on how many points it has:

A. Line segment (2 points):

Compute direction perpendicular to the edge toward the origin using the triple product.

B. Triangle (3 points):

Check if the origin lies inside the triangle.

If yes → Collision
Else → Remove the point that doesn’t contribute and update direction.

Step 5: Collision or Not

If the origin is enclosed in the simplex (triangle in 2D), then: Collision detected
If support fails to get past the origin: No collision

The vector struct and functions

We need to have vector struct with some basics function for adding, substracting, the dot product, the normal:

typedef struct {
    float x, y;
} Vec2;

Vec2 vec2_add(Vec2 a, Vec2 b) { return (Vec2){a.x + b.x, a.y + b.y}; }
Vec2 vec2_sub(Vec2 a, Vec2 b) { return (Vec2){a.x - b.x, a.y - b.y}; }
Vec2 vec2_neg(Vec2 v) { return (Vec2){-v.x, -v.y}; }
float vec2_dot(Vec2 a, Vec2 b) { return a.x * b.x + a.y * b.y; }
Vec2 vec2_perp(Vec2 v) { return (Vec2){v.y, -v.x}; }

The triple product: A x (B x C)

Here we compute the triple dot product of three vectors: A x (B x C) = B * (A · C) - A * (B · C)

Vec2 triple_product(Vec2 a, Vec2 b, Vec2 c) {
    float ac = vec2_dot(a, c);
    float bc = vec2_dot(b, c);
    return (Vec2){
        b.x * ac - a.x * bc,
        b.y * ac - a.y * bc
    };
}

The support function

It computes a support point from the Minkowski Difference of two convex shapes A and B, in a given direction :
support(A - B, dir) = support(A, dir) - support(B, -dir)

Vec2 support(const Vec2* shapeA, int countA, const Vec2* shapeB, int countB, Vec2 dir) {
    float maxA = -INFINITY;
    Vec2 ptA;
    for (int i = 0; i < countA; ++i) {
        float d = vec2_dot(shapeA[i], dir);
        if (d > maxA) {
            maxA = d;
            ptA = shapeA[i];
        }
    }

    float maxB = -INFINITY;
    Vec2 ptB;
    Vec2 negDir = vec2_neg(dir);
    for (int i = 0; i < countB; ++i) {
        float d = vec2_dot(shapeB[i], negDir);
        if (d > maxB) {
            maxB = d;
            ptB = shapeB[i];
        }
    }

    return vec2_sub(ptA, ptB);
}

The function to handle the simplex

It checks whether the current simplex (set of points from the Minkowski Difference) contains the origin and updates the direction to continue searching toward the origin.

bool handle_simplex(Vec2* simplex, int* size, Vec2* dir) {
    if (*size == 2) {
        // Line segment case
        Vec2 A = simplex[1];
        Vec2 B = simplex[0];
        Vec2 AB = vec2_sub(B, A);
        Vec2 AO = vec2_neg(A);
        *dir = triple_product(AB, AO, AB);
    } else if (*size == 3) {
        // Triangle case
        Vec2 A = simplex[2];
        Vec2 B = simplex[1];
        Vec2 C = simplex[0];

        Vec2 AB = vec2_sub(B, A);
        Vec2 AC = vec2_sub(C, A);
        Vec2 AO = vec2_neg(A);

        Vec2 abPerp = triple_product(AC, AB, AB);
        Vec2 acPerp = triple_product(AB, AC, AC);

        if (vec2_dot(abPerp, AO) > 0) {
            // Remove C
            simplex[0] = B;
            simplex[1] = A;
            *size = 2;
            *dir = abPerp;
        } else if (vec2_dot(acPerp, AO) > 0) {
            // Remove B
            simplex[0] = C;
            simplex[1] = A;
            *size = 2;
            *dir = acPerp;
        } else {
            // Origin is inside the triangle
            return true;
        }
    }
    return false;
}

The main function of the GJK algorithm

GJK doesn’t directly test shape overlap. Instead, it:

Builds a shape (simplex) in Minkowski space.
Checks whether the origin is enclosed.
If yes → collision. If not → no collision.

bool gjk(const Vec2* shapeA, int countA, const Vec2* shapeB, int countB) {
    Vec2 simplex[3];
    int size = 0;
    Vec2 dir = {1, 0}; // Initial direction

    simplex[size++] = support(shapeA, countA, shapeB, countB, dir);
    dir = vec2_neg(simplex[0]);

    while (true) {
        Vec2 A = support(shapeA, countA, shapeB, countB, dir);
        if (vec2_dot(A, dir) <= 0) return false; // No collision
        simplex[size++] = A;
        if (handle_simplex(simplex, &size, &dir)) return true; // Collision
    }
}

The hard part is done! We can now make a simple program to test the GJK algorithm.

Initializations

Here we initialize the window the renderer and 2 polygons.

SDL_Init(SDL_INIT_VIDEO);
SDL_Window* window = SDL_CreateWindow("GJK with SDL3", 800, 600, 0);
SDL_Renderer* renderer = SDL_CreateRenderer(window, NULL);

Vec2 polyA[4] = {{100, 100}, {150, 100}, {150, 150}, {100, 150}};
Vec2 polyB[4] = {{200, 200}, {250, 200}, {250, 250}, {200, 250}};

The main loop

Here are all the code inside the main loop.

The event loop

We the mouse is moving we update the polygon to follow the mouse:

while (SDL_PollEvent(&e)) {
    if (e.type == SDL_EVENT_QUIT) running = false;
    if (e.type == SDL_EVENT_MOUSE_MOTION) {
        int mx = e.motion.x;
        int my = e.motion.y;
        Vec2 offset = {static_cast<float>(mx - 225), static_cast<float>(my - 225)};
        for (int i = 0; i < 4; ++i)
            polyB[i] = (Vec2){200 + (i % 2) * 50 + offset.x, 200 + (i / 2) * 50 + offset.y};
    }
}

The rendering

Clear the screen

SDL_SetRenderDrawColor(renderer, 20, 20, 20, 255);
SDL_RenderClear(renderer);

Check for collisions using the GJK algorithm

bool colliding = gjk(polyA, 4, polyB, 4);

Draw the polygons

draw_polygon(renderer, polyA, 4, (SDL_Color){255, 255, 255});
draw_polygon(renderer, polyB, 4, colliding ? (SDL_Color){255, 0, 0} : (SDL_Color){0, 255, 0});

Download the full project : GJK Collision Detection with SDL3

For macos: SDL3_GJKCollision_mac.7z
For windows: SDL3_GJKCollision_win.7z
For linux: SDL3_GJKCollision_linux.7z

Need another OS ? => Windows, Mac, Linux