Narrowphase

The primary function of the narrowphase is to compute the exact points of intersection between two colliding shapes. This is far more precise than the bounding volume approximations used in the broadphase. For convex shapes, algorithms like GJK (Gilbert–Johnson–Keerthi) and EPA (Expanding Polytope Algorithm) are used to find the closest points or penetration depth. The output is a set of one or more contact points in world space, which are passed to the constraint solver to generate appropriate collision responses.

Beyond just finding contact points, the narrowphase must calculate the contact normal (a unit vector pointing from one body to the other, defining the direction of separation) and the penetration depth (the scalar distance the shapes overlap). This data is critical for the physics engine's constraint solver (e.g., solving a Linear Complementarity Problem) to apply correct impulses that resolve the collision, prevent interpenetration, and simulate realistic bouncing or sliding with friction.

The narrowphase implements specialized, efficient algorithms for different primitive shape pairs. Common tests include:

• Sphere vs. Sphere: Simple distance check between centers.
• Box vs. Box: Separating Axis Theorem (SAT) is commonly used.
• Capsule vs. Mesh: Often involves line segment to triangle tests.
• Convex vs. Convex: GJK/EPA is the standard.
• Concave vs. Anything: Typically requires decomposition into convex parts or use of Signed Distance Fields (SDFs). The choice of algorithm directly impacts simulation accuracy and performance.

For fast-moving objects, discrete collision detection (testing at single time steps) can fail, causing tunneling (where an object passes through another). A key advanced function of the narrowphase is Continuous Collision Detection (CCD), which tests the swept volume of an object's path between time steps. This involves more complex continuous geometric queries (e.g., conservative advancement) to compute the time of impact (TOI) and generate speculative contacts, ensuring robust simulation of bullets, thin walls, or rapidly moving robotic parts.

To improve stability and performance, the narrowphase often implements contact caching or warm starting. If a contact pair was colliding in the previous simulation step, its contact manifold (set of points) is stored and reused as a starting point for the next step. This persistence reduces jitter, allows the constraint solver to converge faster, and is essential for stable stacking and resting contacts. Managing this cache—adding new contacts, merging, and pruning old ones—is a core narrowphase responsibility.

The narrowphase does not operate in isolation. It is a critical link between the broadphase and the constraint solver. Its performance dictates the solver's workload. Efficient narrowphase implementations are often parallelized, processing multiple collision pairs simultaneously. The computed contact data (point, normal, depth) is formatted into a contact manifold and passed to the solver (like a Projected Gauss-Seidel solver) which calculates the final forces and torques to apply, completing the collision resolution loop.

The narrowphase calculates the exact point of contact and the surface normal at that point. In robotics, this determines the direction of contact forces. An error of a few millimeters or degrees in simulation leads to incorrect force application in the real world, causing a robot to slip, drop an object, or apply unsafe pressure. For example, a gripper's success in picking up a delicate object is entirely dependent on the precise normal vector computed during contact.

This is the measure of how much two shapes overlap. Accurate penetration depth is non-negotiable for the constraint solver, which uses it to calculate the impulse needed to push the objects apart in a single time step.

• Too shallow: Objects appear to float or make unstable contact.
• Too deep: The solver applies massive, unrealistic corrective forces, causing 'jitter' or explosive behavior. This inaccuracy directly corrupts the force/torque data a reinforcement learning policy uses to learn stable manipulation.

Different narrowphase algorithms trade speed for accuracy, directly impacting sim-to-real transfer.

• GJK/EPA (Gilbert–Johnson–Keerthi/Expanding Polytope Algorithm): The gold standard for convex shapes. Provides exact contact features but is computationally intensive.
• SAT (Separating Axis Theorem): Efficient for axis-aligned geometries but limited in general cases.
• Mesh-vs-Mesh: Extremely expensive. Often approximated with primitive decomposition (breaking meshes into spheres, capsules, convex hulls) for real-time performance, introducing fidelity loss. The choice here dictates what contact phenomena can be learned in simulation.

Narrowphase outputs (contact point, normal, depth) are the primary inputs for friction and restitution (bounciness) models. An error in the contact normal will miscalculate the tangential (friction) force direction. Inaccurate penetration depth affects the normal force magnitude, which in turn scales the friction force (via the Coulomb model). A policy that learns to slide a box in simulation will fail if the simulated friction is 20% off from real-world values due to underlying narrowphase inaccuracies.

In reinforcement learning for robotics, the observation space often includes proprioceptive data (joint torques) and sometimes estimated external contact forces. These signals are derived from the physics engine's resolution of contacts. Noisy or biased narrowphase computations inject erroneous observations into the policy during training. The policy then learns to rely on these simulation artifacts, which vanish on real hardware, causing immediate distributional shift and failure.

A canonical test for narrowphase and solver fidelity is simulating a compliant cantilever beam (e.g., a ruler) pressed against a peg until it snaps past. This test stresses:

• Continuous Collision Detection (CCD): To prevent the beam tip from tunneling through the peg.
• Accurate contact generation during sliding.
• Stable constraint resolution under high stress. A physics engine that fails this simple benchmark cannot be trusted to train policies for real-world contact-rich tasks like assembly or cable manipulation.

The broadphase is the first, coarse stage in the collision detection pipeline. Its primary function is culling: it uses spatial data structures like a Bounding Volume Hierarchy (BVH) or spatial hash to quickly identify pairs of objects that are potentially colliding, while efficiently discarding pairs that are obviously far apart. This drastically reduces the number of expensive pairwise checks passed to the narrowphase.

• Purpose: Performance optimization via early rejection.
• Output: A list of candidate colliding pairs.
• Common Algorithms: Sweep and prune, grid-based methods, dynamic BVH.

Collision detection is the overarching computational process of determining when two or more simulated objects intersect or come into contact. It is typically implemented as a two-stage pipeline:

1. Broadphase: Fast, approximate culling of non-interacting objects.
2. Narrowphase: Precise geometric tests on remaining pairs.

This process is fundamental to simulating physical interactions like contact, stacking, and grasping in robotics. The narrowphase provides the exact geometric data required for the subsequent constraint solver to compute realistic collision responses.

Contact generation is the core computational task performed within the narrowphase stage. Once a collision is detected, this sub-process calculates the precise geometric details of the intersection, which are essential for a physically accurate response.

• Contact Point: The exact location(s) where shapes intersect.
• Contact Normal: A unit vector perpendicular to the collision surface, defining the direction of separation.
• Penetration Depth: The distance the objects have overlapped.

These contact manifolds are the primary output of the narrowphase and serve as direct input to the physics engine's solver to resolve interpenetration and apply friction.

A constraint solver is the algorithmic component that resolves the forces and impulses necessary to satisfy all physical constraints in a simulation time step. It consumes the contact data (points, normals, depth) generated by the narrowphase.

• Primary Function: To compute collision responses that prevent interpenetration and model friction.
• Mathematical Framework: Often formulated as a Linear Complementarity Problem (LCP) or solved via iterative methods like Projected Gauss-Seidel (PGS).
• Constraints Handled: Contact non-penetration, joint limits, ragdoll joints, and rope constraints.

The GJK algorithm is a highly efficient iterative method central to modern narrowphase collision detection for convex shapes. Instead of testing all geometric features, it uses support functions to find the closest points between two shapes' Minkowski difference.

• Output: Minimum distance between shapes and a collision boolean.
• Efficiency: Its iterative nature provides sub-linear time complexity in typical cases.
• Companion Algorithm: Often paired with the Expanding Polytope Algorithm (EPA) to generate contact manifolds (normals and penetration depth) when a collision is detected.

Continuous Collision Detection (CCD) is an advanced narrowphase technique that prevents tunneling—where fast-moving or small objects pass through thin geometry between discrete simulation time steps. Instead of testing static shapes, CCD tests the continuous swept volume along an object's trajectory.

• Use Case: Critical for simulating bullets, fast-moving robots, or cloth with small gaps.
• Method: Computes the time of impact (TOI) along the motion path.
• Trade-off: Significantly more computationally expensive than discrete collision detection, so it is often applied selectively to high-velocity objects.