GJK Collision Detection with SDL3: A Step-by-Step Guide
Learn how to implement the GJK (Gilbert-Johnson-Keerthi) algorithm for accurate 2D collision detection in SDL3. This step-by-step guide includes code examples and explanations.
- SDL3
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