How Manifold Constraints in Box3D Handle Multi-Point Contact Between Convex Shapes

Box3D generates multi-point contact manifolds by clipping intersecting convex hulls into a contact polygon, then reducing the raw point set to a maximum of four stable contacts that persist across simulation frames.

The manifold constraints in the erincatto/box3d physics engine manage complex collisions between convex shapes through a three-stage pipeline. This process transforms raw geometric intersections into a compact, stable set of contact points that drive impulse-based collision response.

The Three-Stage Pipeline for Multi-Point Contact Generation

Box3D constructs contact manifolds through a deterministic pipeline implemented in src/manifold.c and src/convex_manifold.c. The system evaluates potential separating axes, builds geometric contacts through clipping or closest-point calculations, and finally reduces the result to a manageable point set.

Stage 1: Separating-Axis Test (SAT)

The process begins with b3ComputeSeparatingAxis (defined at src/manifold.c:1304), which evaluates all face-face and edge-edge axes of the two convex hulls. This function returns the best axis—the one with the largest separation—and identifies the generating feature type through the b3AxisType enum:

• b3_faceAxisA – Reference face on hull A
• b3_faceAxisB – Reference face on hull B
• b3_edgePairAxis – Closest edge pair

The SAT implementation tests potential separating axes iteratively, selecting the axis with minimum penetration to determine which features are actually colliding.

Stage 2: Manifold Construction (Face vs. Edge Contacts)

Depending on the axis type returned by the SAT, Box3D invokes specialized contact builders to generate the raw contact geometry.

Face-Contact Clipping

When the separating axis indicates a face-face collision, the system executes b3BuildFaceAContact or b3BuildFaceBContact (lines 886-945). These functions:

1. Identify the reference face (the face perpendicular to the separating axis)
2. Identify the incident face (the most opposing face on the other hull)
3. Execute b3ClipPolygon (lines 31-70), implementing the Sutherland-Hodgman algorithm to clip the incident polygon against the side planes of the reference face

This clipping process can generate up to B3_MAX_CLIP_POINTS contact points, creating a polygon that represents the full intersection region of the two shapes.

Edge-Edge Contacts

For edge-pair axes, b3BuildEdgeContact (lines 310-368) solves the closest-points problem between two line segments. Unlike face contacts that produce polygons, edge contacts generate exactly one contact point representing the nearest approach of the two edges.

Stage 3: Point Reduction to Stable Manifold

Raw clipped polygons may contain dozens of points, but physics solvers require a compact representation. b3ReduceManifoldPoints in src/convex_manifold.c:6 implements a heuristic reduction algorithm that selects up to four representative points:

1. Deepest point – The point with maximum penetration depth
2. Farthest point – The point farthest from the deepest in the tangent plane
3. Maximum area point – The point creating the largest triangle area with existing selections
4. Optional fourth point – A point that maximizes area outside the current triangle

This reduction ensures the final b3LocalManifold contains four or fewer points, providing stable contact persistence while maintaining sufficient constraints to prevent rotation and translation through the collision.

Data Structures and Feature Persistence

The manifold system relies on carefully designed structures to maintain contact stability across simulation steps. The b3LocalManifold structure defined in src/manifold.h stores:

typedef struct b3LocalManifold {
    b3Vec3               normal;      // Contact normal (points from A to B)
    int32_t              pointCount;  // ≤ 4 after reduction
    b3LocalManifoldPoint points[4];
} b3LocalManifold;

Each b3LocalManifoldPoint contains a b3FeaturePair that uniquely identifies the generating hull features (vertex, edge, or face indices). The functions b3MakeFeaturePair (lines 69-79) and b3FlipPair (lines 82-96) ensure consistent feature identification even when the reference and incident faces swap between simulation frames, enabling warm-starting of the contact solver.

Practical Implementation Example

The sample_manifold.cpp file demonstrates how to invoke the complete manifold generation pipeline for two convex hulls:

// sample_manifold.cpp (excerpt)
b3HullData* hullA = b3LoadHull("cube.obj");   // convex shape A
b3HullData* hullB = b3LoadHull("tetra.obj");  // convex shape B

b3Transform xfBtoA = b3MakeTransform(b3Vec3_zero, b3Quat_identity);
b3LocalManifold manifold;
b3SimplexCache cache = {0};

// Compute manifold (capacity 4 points)
b3CollideHullAndHull(&manifold, 4, hullA, hullB, xfBtoA, &cache);

// manifold.normal, manifold.pointCount, manifold.points[] now hold the reduced contacts

The core function b3CollideHullAndHull (implemented at src/convex_manifold.c:124) orchestrates the entire process: it executes the SAT test, dispatches to the appropriate contact builder (b3BuildFaceAContact, b3BuildFaceBContact, or b3BuildEdgeContact), and invokes b3ReduceManifoldPoints to produce the final manifold.

Summary

• Multi-point contact generation in Box3D begins with a Separating-Axis Test (b3ComputeSeparatingAxis) to identify the best collision axis and feature types.
• Face contacts use Sutherland-Hodgman polygon clipping (b3ClipPolygon) to generate intersection polygons, while edge contacts solve for the closest points between line segments.
• Point reduction limits manifolds to four stable contacts using depth and area heuristics (b3ReduceManifoldPoints), ensuring solver efficiency and frame-to-frame stability.
• Feature pairs (b3FeaturePair) provide persistent contact identification across simulation steps, enabling warm-starting of the impulse solver.
• The high-level entry point b3CollideHullAndHull in src/convex_manifold.c combines these stages into a single callable routine for convex hull collisions.

Frequently Asked Questions

Why does Box3D limit manifolds to four contact points?

Box3D reduces contact manifolds to a maximum of four points because four non-coplanar points provide sufficient constraints to prevent all degrees of freedom (three translational and three rotational) between rigid bodies while keeping the linear complementarity problem (LCP) computationally tractable. Additional points beyond four rarely improve stability but significantly increase solver iteration cost.

What is the purpose of the Sutherland-Hodgman clipping algorithm in manifold generation?

The Sutherland-Hodgman algorithm (b3ClipPolygon) clips the incident face polygon against the side planes of the reference face to produce the exact intersection region of two penetrating convex faces. This geometric clipping generates the raw contact polygon that represents the true surface area of collision, which is then reduced to representative points for the physics solver.

How does Box3D maintain contact persistence between simulation frames?

Box3D maintains contact persistence through feature pairs stored in each b3LocalManifoldPoint. The b3MakeFeaturePair function encodes the specific vertex, edge, or face indices that generated the contact, while b3FlipPair ensures consistent feature ordering regardless of which body is designated as reference. This allows the solver to match contacts between frames and apply warm-starting impulses based on previous solutions.

When does Box3D use edge-edge contacts instead of face contacts?

Box3D generates edge-edge contacts (b3BuildEdgeContact) when the Separating-Axis Test identifies the closest features as a pair of edges rather than opposing faces. This occurs during collisions involving sharp corners or when polyhedra meet at grazing angles where no single face provides the primary collision normal. Edge contacts produce a single contact point representing the nearest approach of the two line segments.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}