Narrow phase

Generated from engine/collision/narrow_phase.h at 862e08b. The text under each declaration is the header's own comment, word for word. About the reference says how these pages are made.

Browse the collision module

#include "engine/collision/narrow_phase.h" · namespace labrador

narrow_phase

std::optional<Manifold> narrow_phase(const mattmath::Shape& a,
  const mattmath::Shape& b);

Measures one pair of shapes: nullopt when they do not overlap, and otherwise the axis of least penetration and how deep it is, with the normal pointing from a towards b.

This is the separating-axis theorem, run over both shapes' edge normals, and the axis it keeps is the one with the smallest overlap. The obvious alternatives - classifying the contact by which of the collider's bounding-box edges the other shape crossed, or searching for the depth - have no answer for the cases that matter:

- A wide thin platform crosses a standing player's left AND right edges. Comparing centres horizontally there shoves the player sideways off a platform they should have landed on. The minimum-overlap axis for that pair is vertical, always, because the platform is thin - which is the same fact the player can see. - One shape wholly containing the other crosses all four edges or none, so an edge-crossing classification has nothing to say about it. Containment has a well-defined minimum translation and this returns it. - Bisection - moving the shape back and forth by a shrinking fraction of its own size - has an unreportable failure and an approximate answer when it converges. This is analytic (PHILOSOPHY, Collision) and runs in the number of edges.

The axis set is COMPLETE, not a good-enough sample of one. In two dimensions, testing the face normals of both shapes decides convex overlap exactly - Ericson says so outright (4.4.1, p.102): the test "is either body wholly outside a face of the other" works in 2D and fails only in 3D, and the nine cross-product axes that published 3D SAT code carries exist solely to catch an edge-against-edge configuration that has no counterpart when nothing can be skew. There is no missing axis here to be found later, and adding cross-product axes imported from a 3D implementation would be adding noise, not rigour. This is also the answer to "should this be GJK": not for correctness, because this is already exact.

Two further reductions, both provably free. Opposite edges of a rectangle have antiparallel normals, and an axis and its negative give the same penetration - projecting on -n negates and swaps the interval, which swaps the two ways out, so their minimum is unchanged and the normal still comes back correctly signed. A rectangle therefore contributes two axes, not four, and for an axis-aligned one they are the cardinal directions and cost nothing to produce.

CONVEXITY IS A PRECONDITION, and it is the one thing here that is not self-enforcing. The separating-axis theorem decides nothing for a concave shape: it will report a confident overlap and a meaningless normal. Quad's constructor checks it. Triangle's does not - a collinear triangle is constructible - and RectangleF and RectangleRotated are convex by construction. Degenerate edges are skipped rather than contributing a bogus axis, and a shape left with no axes at all reports no contact.

Shapes that merely touch do not overlap: a zero-depth contact has no meaningful normal, so it is not a contact. This is deliberately the opposite convention to the bounding-box filter that runs before it, which is closed and counts a shared edge as intersecting. A closed filter feeding an open decider is the correct pairing: the cheap test must never reject something the expensive one would have accepted, and the expensive one owns the answer. See contacts.h.

Nonfinite polygon coordinates report no contact, checked before any projection can hide a poisoned vertex in a min/max reduction. Axis tests also reject nonfinite depths: no manifold may carry a NaN or infinite penetration into a position.

Supported shape types are the convex polygons - rectangle, rotated rectangle, triangle and quad. A circle throws std::invalid_argument rather than reporting no overlap, because silently missing collisions is the worse failure and nothing in the tree is a collidable circle. Adding them is one more axis, the centre-to-closest-point one.

Related types

Named in the public declarations above: Manifold, Shape.

In the samples and tests

The files that include this header directly. A file can also reach it through another header.

• tests/collision/ narrow_phase_tests.cpp, tunnelling_tests.cpp