Two Points, or the Box Rocks

A box resting on the ground touches it along a whole edge. A contact generator that reports one point in the middle of that edge is not wrong, exactly — but the box it describes is balanced on a pin, and the solver will let it rock. Two points along the edge and it sits. That single requirement is why Veta's engine has two narrowphase paths rather than one.

/// Narrowphase entry point. Dispatches a shape pair to the right algorithm and returns
/// contact manifolds whose normals point **from A to B**.
///
/// - Polygon vs polygon — `SAT`, for the two-point manifold a resting box needs.
/// - Circle vs circle — closed form.
/// - Anything involving a circle or capsule — `GJK` on the un-rounded cores, then
///   `EPA` when the cores overlap, then the radii folded back in (one point).
public static func shapes(_ a: Shape, _ ta: Transform2D,
                          _ b: Shape, _ tb: Transform2D) -> ContactManifold? {
    switch (a, b) {
    case (.polygon(let pa), .polygon(let pb)):
        return SAT.collide(pa, ta, pb, tb)
    case (.circle(let ra), .circle(let rb)):
        return circles(ta.position, ra, tb.position, rb)
    default:
        return rounded(a.coreHull(ta), b.coreHull(tb), fallback: tb.position - ta.position)
    }
}

A rounded shape only ever touches along a point, so one contact is all there is to report and GJK's answer is complete. Two polygons can touch along a face, and that case gets its own algorithm.

SAT, and then the clipping that actually matters

The separating-axis half is the textbook part: for two convex polygons, if a separating axis exists it is the normal of one of their faces, so measure the deepest penetration along every face normal of each and take the shallowest. Positive means disjoint, and you are done.

/// Greatest separation of `b` from any face of `a`. Positive — disjoint along that
/// face's normal.
public static func maxSeparation(_ a: WorldPoly, _ b: WorldPoly) -> (sep: Float, edge: Int) {
    var bestSep = -Float.greatestFiniteMagnitude
    var bestEdge = 0
    for i in a.vertices.indices {
        let n = a.normals[i]
        let v = a.vertices[i]
        // Deepest vertex of b along -n, measured from this face.
        var minDot = Float.greatestFiniteMagnitude
        for w in b.vertices { minDot = min(minDot, n.dot(w - v)) }
        if minDot > bestSep { bestSep = minDot; bestEdge = i }
    }
    return (bestSep, bestEdge)
}

The interesting part is what happens once you know they overlap. One polygon's face becomes the reference face; the other contributes the incident face, the one whose normal is most anti-parallel to it. The incident face, as a two-point segment, is then clipped against the side planes of the reference face — Sutherland–Hodgman, on a segment, twice — and whatever survives below the reference face is the manifold.

var clipped = clipSegment(incVerts, n: -tangent, offset: -tangent.dot(v11))
guard clipped.count == 2 else { return nil }
clipped = clipSegment(clipped, n: tangent, offset: tangent.dot(v12))
guard clipped.count == 2 else { return nil }

let front = refNormal.dot(v11)
var points: [ContactPoint] = []
for c in clipped {
    let sep = refNormal.dot(c.p) - front
    if sep <= 0 {
        let id = (UInt64(refEdge) << 16) | (UInt64(c.id) << 8) | (flip ? 1 : 0)
        points.append(ContactPoint(position: c.p - refNormal * (sep * 0.5),
                                   penetration: -sep, featureId: id + 1))
    }
}

Two points on a flat face, one point on a corner, and each carries its own penetration depth — a box landing at a slight angle gets a deep contact and a shallow one, which is what makes it settle flat instead of pivoting.

The tie-break that keeps contacts alive between frames

One line in the middle of that function is not geometry at all:

// Prefer A as the reference face unless B's is clearly better; the tolerance
// stops the roles flipping frame to frame on a near tie, which would make a
// resting contact's feature ids churn and lose their warm start.
let flip = sepB > 0.98 * sepA + 0.1 * Scalar.linearSlop

Two boxes resting square on each other have two equally good reference faces, separated by a rounding error that changes sign every frame. Without the hysteresis the reference and incident roles swap continuously, and because the feature ids are built out of which face was the reference, every contact looks brand new every frame. The solver then has nothing to carry forward, and a stack that should stand still visibly sinks and recovers. It is a stability bug that reads as a performance bug, and the fix is a bias, not a better algorithm.

The ids themselves are packed from the edge indices, the flip flag, and — one level up, in Collide.manifolds — the part indices of a compound shape:

// Part indices go into the feature id so two parts of one compound
// resting on the same face keep separate warm starts.
let partBits = (UInt64(ia) << 40) | (UInt64(ib) << 32)
for i in m.points.indices where m.points[i].featureId != 0 {
    m.points[i].featureId |= partBits
}

A star lying on a floor touches it with two of its spikes. Both produce the same reference edge on the floor's side; only the part index tells them apart. Without those bits the two contacts share one warm-start slot and fight over it.

EPA: expanding toward the nearest face

When two rounded cores overlap, GJK hands over a triangle containing the origin, and EPA grows it outward until the closest edge to the origin stops moving. That edge's normal is the shortest direction that separates them, and its distance is the depth.

let s = GJK.support(a, b, bestNormal).w
let sDist = s.dot(bestNormal)
if sDist - bestDist < tolerance || poly.count >= 64 {
    return Result(normal: bestNormal, depth: sDist)
}
poly.insert(s, at: bestIndex + 1)

Three of the guards around that loop are worth more than the loop:

if abs(area) < Scalar.epsilon * Scalar.epsilon {
    // A flat triangle: the shapes touch along a line. Use the longest edge's
    // normal with zero depth rather than looping on nothing.
    let e = poly[1] - poly[0]
    return Result(normal: e.perpCW.normalized, depth: 0)
}

That is the bill for the previous post's decision to report touching as overlapping: the padded triangle can have no area, and expanding a zero-area polytope is an infinite loop looking for somewhere to happen. The second guard handles a winding that rounding has inverted locally — flip the normal rather than let a negative distance win the "closest edge" contest. The third is the non-convergence fallback, which returns the best edge found so far rather than nil, on the grounds that a slightly wrong separating direction resolves next frame and no direction at all means two shapes silently sunk into each other.

Folding the radii back in

Everything above happened on the un-rounded cores. The last step puts the roundness back:

let gjk = GJK.distance(a, b)
if !gjk.overlapping {
    guard gjk.distance <= radii else { return nil }
    var n = (gjk.pointB - gjk.pointA)
    n = n.lengthSquared > Scalar.epsilon * Scalar.epsilon ? n.normalized : fallback.normalized
    if n == .zero { n = Vec2(0, 1) }
    let surfaceA = gjk.pointA + n * a.radius
    let surfaceB = gjk.pointB - n * b.radius
    return ContactManifold(normal: n, points: [
        ContactPoint(position: (surfaceA + surfaceB) * 0.5, penetration: radii - gjk.distance),
    ])
}

Two cores 0.3 m apart whose radii sum to 0.5 m are shapes overlapping by 0.2 m, and the contact sits midway between the two real surfaces. Note the two fallbacks for a degenerate normal — the vector between the body centres, and failing even that, straight up. Neither is correct in any meaningful sense; both are better than a normal of zero, which propagates a NaN into a velocity and removes a body from the game.

Next

Manifolds are the input to the part that actually makes things move: a sequential-impulse solver with friction, warm starting and a position bias — and a set of small constants, each of which exists because of something that jittered without it.