Broadphase

Broadphase algorithms rely on spatial data structures to organize objects in the simulation world, enabling efficient proximity queries. Common structures include:

• Uniform Grids: Space is divided into fixed-size cells. Objects are assigned to cells based on their position, and only objects in the same or adjacent cells are tested.
• Spatial Hashing: A hash function maps object positions to keys in a hash table, grouping nearby objects into the same bucket without a fixed grid structure.
• Quadtrees (2D) / Octrees (3D): Hierarchical trees that recursively subdivide space. A node is split if it contains too many objects, creating a multi-resolution spatial map.
• Bounding Volume Hierarchies (BVHs): A tree where each node has a bounding volume (like an Axis-Aligned Bounding Box) that encompasses all its children. The hierarchy is traversed to quickly reject disjoint branches.

Sweep and Prune (also known as Sort and Sweep) is a classic broadphase algorithm that operates by projecting object bounding volumes onto coordinate axes. It works in three steps:

1. Sort: The minimum and maximum extents of each object's Axis-Aligned Bounding Box (AABB) are sorted along the X, Y, and Z axes.
2. Sweep: The algorithm sweeps along each sorted list, maintaining an active list of objects whose extents overlap on the current axis.
3. Prune: A pair is considered potentially colliding only if its AABBs overlap on all three axes. This method is highly efficient for simulations where objects move incrementally between frames, as the sorted lists can be updated incrementally with minimal re-sorting.

Broadphase implementations are optimized based on the motion profile of objects in the scene:

• Dynamic Broadphase: Designed for scenes where most objects move every frame (e.g., robotic parts, falling debris). Algorithms like Dynamic Bounding Volume Trees (DBVTs) or incremental Sweep and Prune are used. They prioritize fast update times for moving objects, often at the cost of slightly less optimal query performance.
• Static Broadphase: Used for environments with large static geometry (e.g., floors, walls, buildings). Structures like kd-trees or static BVHs are built once and provide extremely fast query performance for rays or moving objects against the static backdrop, but cannot be updated efficiently. Modern engines often use a hybrid approach, maintaining separate structures for dynamic and static objects to maximize overall performance.

The core output of the broadphase is a set of potentially colliding pairs. Efficient management of this pair list is crucial:

• Pair Caching: The algorithm caches pairs from the previous frame. If two objects remain in spatial proximity, the pair is kept without expensive re-identification.
• Incremental Updates: Instead of rebuilding the entire spatial structure each frame, algorithms update only the nodes or cells affected by moving objects.
• False Positive Tolerance: Broadphase is designed to be over-inclusive. It is acceptable (and expected) to pass some pairs that do not actually collide to the narrowphase. The primary goal is to never miss a colliding pair (a false negative), as this would cause objects to pass through each other. The computational cost is shifted to the precise, but more locally applied, narrowphase checks.

Broadphase is the first step in a tightly integrated physics pipeline. Its performance directly dictates the workload for downstream stages:

1. Input: Takes the set of all collidable objects with their updated bounding volumes (typically AABBs).
2. Process: Executes spatial partitioning and pair generation.
3. Output: A reduced list of object pairs sent to the Narrowphase.
4. Narrowphase: Performs exact geometric intersection tests (using algorithms like GJK/EPA) on the broadphase candidate pairs to generate precise contact points, normals, and penetration depths.
5. Constraint Solver: Uses the contact data to resolve collisions and enforce non-penetration. An inefficient broadphase that passes too many false pairs can bottleneck the entire simulation, making its algorithmic choice and implementation critical for real-time performance.

Different simulation engines choose broadphase algorithms based on their specific performance characteristics and use cases:

• Bullet Physics: Uses a Dynamic AABB Tree (a type of BVH) as its primary broadphase, which is highly efficient for a mix of moving and static objects.
• Box2D: Employs a Dynamic Tree (BVH) for broadphase, which is well-suited for 2D simulations with many dynamic bodies.
• Unity PhysX / NVIDIA PhysX: Utilizes a Multi-Box Pruner (an optimized Sweep and Prune variant) and a Scene Query System built on BVHs for complex queries.
• Havok: Implements a sweep-and-prune system combined with spatial hashing for different object layers, optimized for game-scale environments. The choice involves trade-offs between build time, update time, query time, and memory usage, tailored to the expected content of the simulation (e.g., many small objects vs. few large objects).

Narrowphase is the second, precise stage in the collision detection pipeline. It takes the list of potentially colliding object pairs generated by the broadphase and performs exact geometric tests to determine if a collision has actually occurred. This stage computes detailed contact information, including:

• Contact points: The exact locations where shapes intersect.
• Surface normals: The direction to push objects apart.
• Penetration depth: How far one object has intruded into another. Common narrowphase algorithms include the Gilbert–Johnson–Keerthi (GJK) algorithm for convex shapes and the Separating Axis Theorem (SAT).

A Bounding Volume Hierarchy (BVH) is a core spatial data structure used to accelerate broadphase collision detection. It organizes objects in a scene into a tree, where each node is a simple bounding volume (like an Axis-Aligned Bounding Box (AABB) or sphere) that contains all objects within its branch. During broadphase, the engine traverses this tree, quickly culling entire groups of objects whose parent bounding volumes do not overlap. This reduces the number of costly pairwise checks from O(n²) to O(n log n) or better. BVHs are dynamic and must be updated or rebuilt as objects move.

Sweep and Prune is a classic broadphase algorithm that sorts objects along a coordinate axis (e.g., X, Y, Z) to find overlapping intervals. It works by:

1. Projecting each object's AABB onto the chosen axis.
2. Sorting the start and end points of these projections.
3. Sweeping along the sorted list; objects are added to an active list when their start point is encountered and removed when their end point is found.
4. Pruning by checking for overlaps only between objects currently in the active list. This method is highly efficient for scenes where objects move incrementally, as the sorted list can be updated with minimal cost.

Spatial Hashing (or a uniform grid) is a broadphase technique that divides the simulation world into fixed-size cells. Each object is assigned to one or more cells based on its position. The broadphase then only checks for collisions between objects that share at least one cell. This method is exceptionally fast for large numbers of small, uniformly sized objects. Key considerations include:

• Cell size: Must be carefully chosen relative to object sizes.
• Dynamic updates: Objects moving between cells require re-hashing.
• Memory efficiency: Can be implemented with hash maps to avoid allocating empty cells in sparse worlds.

Continuous Collision Detection (CCD) is a technique that prevents tunneling, where fast-moving or small objects pass through each other between discrete simulation time steps. While broadphase operates on static object states per frame, CCD-aware broadphase must consider an object's swept volume—the space it occupies along its entire trajectory during the time step. This often involves using enlarged or extruded bounding volumes in the broadphase pass to ensure all potentially colliding pairs across the motion path are captured and passed to a continuous narrowphase solver.

The Physics Pipeline is the complete, sequential workflow of a physics engine within a single simulation step. Broadphase is the critical first stage in this pipeline. A standard pipeline proceeds as follows:

1. Broadphase: Identifies pairs of potentially colliding objects.
2. Narrowphase: Computes exact contact details for these pairs.
3. Contact Generation & Persistence: Manages contact points over multiple frames.
4. Constraint Solver: Resolves forces and impulses to satisfy contacts and joints (e.g., using a Projected Gauss-Seidel (PGS) solver).
5. Time Integration: Updates object positions and velocities based on net forces. The efficiency of the entire pipeline is bottlenecked by the broadphase's ability to minimize wasted work in later, more expensive stages.