Finding the Gap

The previous post reduced every shape in the engine to a CoreHull: a handful of world-space points and a radius to fold back in afterwards. That leaves the narrowphase one question to answer, for every pair of shapes in the game, several times a frame: how far apart are these two point sets, and if they are not apart at all, what is the closest feature?

The answer is Gilbert–Johnson–Keerthi, and the reason it is worth writing out rather than describing is that the idea is much simpler than its reputation.

The trick: one set instead of two

The distance between two convex sets A and B is the distance from the origin to the set of all differences a − b — the Minkowski difference. If the two sets overlap, some a equals some b, so the difference set contains the origin. The problem stops being about two shapes and their relative position, and becomes about one shape and a fixed point.

That set is never built. It is only ever asked questions, and there is only one question:

/// One vertex of the simplex: a point of the Minkowski difference `A - B` together
/// with the two support points it came from, so witness points can be recovered.
public struct SimplexVertex: Equatable, Sendable {
    public var w: Vec2
    public var a: Vec2
    public var b: Vec2
}

@inline(__always)
static func support(_ a: CoreHull, _ b: CoreHull, _ d: Vec2) -> SimplexVertex {
    let pa = a.support(d), pb = b.support(-d)
    return SimplexVertex(w: pa - pb, a: pa, b: pb)
}

The farthest point of the difference set along d is the farthest point of A along d minus the farthest point of B along −d. Each vertex keeps the two points it came from, which is what makes the witness points — the actual closest points on the two real shapes — recoverable at the end instead of thrown away.

The loop

GJK keeps a simplex: one, two or three vertices of the difference set. Each iteration it finds the point on that simplex closest to the origin, discards the vertices that do not contribute to it, and asks for a support point in the direction of the origin. Either that new point gets meaningfully closer — in which case it joins the simplex and the loop goes again — or it does not, and the current closest point is the answer.

case 2:
    let (c, t) = closestOnSegment(simplex[0].w, simplex[1].w)
    if t <= 0 { simplex = [simplex[0]]; weights = [1] }
    else if t >= 1 { simplex = [simplex[1]]; weights = [1] }
    else { weights = [1 - t, t] }
    closest = c
default:
    if originInside(simplex[0].w, simplex[1].w, simplex[2].w) {
        return Result(distance: 0, pointA: .zero, pointB: .zero,
                      overlapping: true, simplex: simplex)
    }
    // Not inside: the closest feature is one of the three edges.
    // ... keep the best edge, reduce to the one or two vertices that carry it

Those weights are the quiet half of the algorithm. The closest point is a barycentric combination of the surviving simplex vertices, and the same combination of the as and the bs gives the closest points on the original two shapes:

var pa = Vec2.zero, pb = Vec2.zero
for (v, w) in zip(simplex, weights) {
    pa += v.a * w
    pb += v.b * w
}
return Result(distance: (pa - pb).length, pointA: pa, pointB: pb,
              overlapping: false, simplex: simplex)

Without that, GJK answers "1.4 metres" and the caller still has to work out where, which is the part a contact needs.

Three ways to stop, and all three are needed

The loop is capped at 24 iterations, but the cap is not how it normally ends. There are two earlier exits and they do different jobs:

let searchDir = -closest
let v = support(a, b, searchDir)
// No progress toward the origin: the closest point is found.
let progress = v.w.dot(searchDir) - closest.dot(searchDir)
if progress <= Scalar.epsilon * max(1, d2.squareRoot()) { break }
if simplex.contains(where: { $0.w == v.w }) { break }

The first is the real termination condition: the new support point is no farther toward the origin than the current closest point already is, so there is nothing left in the difference set between here and the origin. Note the tolerance is scaled by the distance — an absolute epsilon that is sensible for two shapes 10 cm apart is noise for two shapes 40 m apart, and a fixed one gives you either premature exits at range or a spin at close quarters.

The second is the paranoid one: if the support point is a vertex already in the simplex, the search direction is bouncing between two features and no amount of further iteration will improve it. In exact arithmetic the first test catches this case; in Float arithmetic it sometimes does not, and the difference between catching it and not is a frame that takes 24 iterations per pair instead of 3.

Touching is the awkward case

Two shapes exactly flush produce a difference set whose boundary passes through the origin. Distance is zero; there is no separation to report, and the penetration is zero too. The algorithm cannot express that in its normal vocabulary, so it picks a side:

let d2 = closest.lengthSquared
if d2 < Scalar.epsilon * Scalar.epsilon {
    // The origin lies on the simplex: touching. Report as overlap with a
    // triangle so EPA has something to expand, even if it is thin.
    return Result(distance: 0, pointA: .zero, pointB: .zero, overlapping: true,
                  simplex: padToTriangle(simplex, a, b))
}

Touching is reported as overlapping, and the degenerate simplex is grown to three vertices by sampling a fixed set of perpendicular directions, so that the penetration algorithm downstream always receives a triangle rather than a point or a segment it would have to special-case.

This is a decision with a cost, and it comes due two posts from now: a zero-area triangle is exactly the input from which the expansion algorithm can name the wrong face. The shape-cast code has a dedicated routine for the flush case as a direct consequence. It is worth flagging here because it is the shape of a lot of collision-detection work — the geometry is clean and the boundaries between its cases are where all the bugs live.

What it buys

Because the input is a CoreHull, one implementation covers every rounded pair in Veta's engine. A circle against a capsule is a 1-point hull against a 2-point hull; the distance between their cores, minus the two radii, is the exact gap between the real surfaces. The test says it plainly:

func testDistanceBetweenCircleCoresIsCentreDistance() { /* ... */ }

— because a circle's core is its centre, and that is the whole point. The same code also serves the shape casts and the character controller, which sweep a shape forward in steps of "however far apart these two things currently are". A distance query is a more useful primitive than an overlap test, and getting one is the reason to run GJK rather than a pile of per-pair formulas.

Next

Distance is the easy half. The next post is what happens when the answer is zero: recovering penetration depth with EPA, why polygon-against-polygon skips both algorithms entirely and goes through the separating-axis theorem instead, and why a resting box needs two contact points rather than one.