How to Learn GJK Collision Detection: Minkowski Difference, Support Mappings, Simplexes and Robust Convex Geometry

Quick Read: GJK, the Gilbert–Johnson–Keerthi algorithm, answers a geometric question with a beautiful reduction: do two convex shapes overlap? Instead of comparing their boundaries directly, transform the problem into asking whether the origin lies inside their Minkowski difference. From there, support mappings and a moving simplex drive an iterative search.

Why collision detection is an algorithm problem

In a game, robot, simulation or CAD system, objects may move every frame. The software must decide quickly whether two shapes touch, overlap or remain separated. A naive approach might compare every edge, face or vertex pair. That becomes expensive as models grow.

GJK succeeds by changing the representation of the problem. It does not ask “where do these two boundaries intersect?” It asks a more structured question in a transformed space.

Beginner foundation: convexity

A shape is convex if the straight line segment between any two points in the shape stays entirely inside the shape. Circles, rectangles and convex polygons are convex. A crescent or star-shaped polygon is not.

GJK’s standard form assumes convex shapes. Non-convex objects are typically decomposed into convex pieces or handled with a broader collision-detection pipeline.

The support point: ask the shape one precise question

For a direction vector d, a support mapping returns the point on a convex shape that is farthest in direction d. For a polygon, this can be found by maximizing the dot product point · d.

support(shape, d):
    best = shape.vertices[0]
    for p in shape.vertices:
        if dot(p, d) > dot(best, d):
            best = p
    return best

This interface is one reason GJK is powerful. The algorithm does not need to know every internal detail of a shape. It only needs a correct support function.

The big transformation: Minkowski difference

For shapes A and B, the Minkowski difference contains points of the form a - b, where a comes from A and b comes from B.

The key fact is:

Two convex shapes intersect if and only if the origin lies inside their Minkowski difference.

Why? If the shapes share a point, then for some a and b we have a = b. Therefore a - b = 0, so the origin belongs to the difference set. Conversely, if zero is in the difference, then some a and b coincide.

You never build the whole Minkowski difference

Constructing every point of the Minkowski difference would defeat the purpose. GJK instead obtains support points of the difference directly:

supportMinkowski(A, B, d):
    return support(A, d) - support(B, -d)

This formula is worth understanding deeply. The farthest point of A−B in direction d comes from pushing A as far as possible along d and B as far as possible in the opposite direction.

The simplex: a tiny geometric working set

GJK maintains a small set of support points called a simplex. In 2D, the simplex can be a point, line segment or triangle. In 3D it may progress up to a tetrahedron.

The algorithm repeatedly asks: using the simplex we currently have, which direction should we search next to move toward the origin?

A beginner-friendly 2D intuition

Choose an initial direction.
Get a support point in that direction.
Reverse toward the origin.
Get another support point.
Use the line segment formed by the two points to decide which region can still contain the origin.
Add another support point in the new direction.
If a triangle encloses the origin, the original shapes intersect.
If a new support point fails to pass the origin in the search direction, the shapes cannot intersect.

The separating early exit

Suppose the current search direction is d and the newest support point is a. If dot(a, d) < 0, then even the farthest point in direction d does not reach past the origin. The origin cannot lie inside the Minkowski difference, so the original convex shapes are separated.

This dot-product test is one of the cleanest pieces of GJK. It converts geometry into a directional inequality.

Conceptual pseudocode

gjk(A, B):
    d = choose_initial_direction(A, B)
    simplex = [supportMinkowski(A, B, d)]
    d = -simplex[0]

    loop:
        a = supportMinkowski(A, B, d)

        if dot(a, d) < 0:
            return false

        simplex.add(a)

        if update_simplex_and_direction(simplex, d):
            return true

The function update_simplex_and_direction is where most of the geometry lives. It removes simplex points that are no longer relevant and chooses the next direction toward the region that may contain the origin.

Intermediate level: line-simplex reasoning

Suppose the simplex contains two points A and B, with A the newest point. Let AO = -A point from A toward the origin, and AB = B - A. If the origin lies in the direction of AB, the next search direction should be perpendicular to AB toward the origin. Otherwise B can be discarded and the simplex returns to the single point A.

This is a general pattern: the simplex is not a record of history. It is a compact certificate of the region still worth searching.

Intermediate level: triangle-simplex reasoning

With a triangle, the question becomes whether the origin lies inside it or outside one of its edges. Edge normals identify the outside regions. If the origin is outside an edge, the opposite vertex can be dropped and the search continues with a line simplex. If the origin is not outside any relevant edge, the triangle contains the origin and the original shapes intersect.

Why triple products appear in 2D implementations

Many implementations use a vector triple-product construction to obtain a perpendicular direction pointing toward the origin without manually choosing left or right. This is elegant, but learners should first understand the geometry visually. A compact vector identity is useful only after the region test makes sense.

Professional level: intersection is only one GJK problem

GJK can also be formulated to find the distance between separated convex shapes and their closest points. Collision engines may pair GJK with the Expanding Polytope Algorithm (EPA) after an intersection is detected to estimate penetration depth and direction.

This matters professionally because collision detection is usually a pipeline. A broad phase cheaply rejects distant object pairs. A narrow phase such as GJK tests convex shapes precisely. A penetration solver or contact manifold stage may then provide information for physics response.

Complexity: theory versus geometry

GJK is iterative, and practical performance depends heavily on the number of support queries and the cost of each support mapping. For a polygon represented by an unsorted list of vertices, a support query can scan all vertices. More specialised representations can accelerate that step.

For real-time systems, constant factors, warm starts, geometric coherence between frames and robust termination criteria often matter more than a single asymptotic expression.

Numerical robustness is part of correctness

Floating-point arithmetic introduces cases that a diagram does not show. Points that should be distinct may become nearly identical. Directions may approach zero. Shapes may almost touch. Dot products can fall near a tolerance boundary.

Define and document tolerances.
Detect repeated support points.
Use a maximum iteration count as a safety guard.
Handle a near-zero search direction deliberately.
Test touching, nearly touching and degenerate cases.
Separate the mathematical algorithm from floating-point policy in your design.

Common implementation mistakes

Using support(B, d) instead of support(B, -d) in the Minkowski support function.
Keeping obsolete simplex points instead of discarding regions that cannot contain the origin.
Choosing a perpendicular direction with the wrong sign.
Treating exact floating-point equality as a reliable geometric test.
Confusing intersection GJK with distance GJK.
Applying GJK directly to a non-convex mesh without decomposition.

How to learn GJK without getting lost

The most effective route is visual and incremental. First implement support points for a single polygon. Then draw the Minkowski difference explicitly for two tiny polygons even though production GJK never constructs it. Next implement the line-simplex case. Only after that add the triangle case.

This staged approach mirrors strong programming pedagogy: predict the next search direction, run one iteration, inspect the simplex, modify one case, and only then build the complete algorithm.

A practice ladder

Beginner: calculate support points by hand for a square in eight directions.
Foundation: draw the Minkowski difference of two intervals in 1D.
Intermediate: build Minkowski differences explicitly for two triangles and test whether the origin lies inside.
Intermediate: implement a support function and a 2D GJK intersection test.
Advanced: add diagnostic drawing of simplex points and search directions.
Professional: test random convex polygons against an independent reference method such as SAT, then investigate all disagreements.

Test cases that reveal weak implementations

Two shapes far apart.
One shape completely inside another.
Shapes overlapping by a large amount.
Shapes touching at one vertex.
Shapes sharing a nearly parallel edge.
Very thin convex polygons.
Identical shapes at identical positions.
Large coordinates mixed with tiny separations.

Professional questions to ask

What shape representation makes support queries fast?
Can the previous frame’s simplex warm-start the next query?
What tolerance policy is appropriate for the coordinate scale?
How will non-convex objects be decomposed?
Is penetration depth required after intersection?
How is the narrow phase integrated with the broad phase?
What reference implementation will validate edge cases?

The final idea

GJK is a lesson in algorithmic reframing. A hard boundary-intersection problem becomes an origin-containment problem. A huge geometric object becomes a support oracle. A potentially complex search becomes a tiny moving simplex. That ability to change representation is one of the central skills that separates algorithm users from algorithm designers.