Bounding Volume Hierarchy (BVH)

A BVH recursively subdivides a set of objects by enclosing them in nested bounding volumes. The root node bounds the entire scene. Each internal node contains a volume that bounds all objects within its child nodes, forming a tree. This hierarchy allows for efficient culling of large groups of objects that cannot possibly intersect a query ray or volume, dramatically reducing the number of expensive pairwise tests required.

The most common bounding volume type used in BVH construction is the Axis-Aligned Bounding Box (AABB). An AABB is defined by its minimum and maximum extents along the world coordinate axes (x, y, z). Their alignment simplifies and accelerates intersection tests:

• Volume computation is fast.
• Overlap tests between two AABBs require only six comparisons.
• Ray-AABB intersection uses efficient algorithms like the Slabs Method. While spheres or oriented bounding boxes (OBBs) can be used, AABBs offer the best trade-off between tightness of fit and computational cost for most dynamic simulations.

The quality of a BVH is determined by how it's built. The Surface Area Heuristic (SAH) is the standard method for constructing high-quality BVHs. It estimates the expected cost of traversing a node by modeling the probability of a random ray intersecting it. During construction, the SAH evaluates candidate split planes by calculating: Cost = C_trav + (SA_left / SA_node) * N_left * C_intersect + (SA_right / SA_node) * N_right * C_intersect Where SA is surface area and N is the number of primitives. The split that minimizes this estimated cost is chosen, leading to trees that minimize the average number of primitive intersection tests per query.

Unlike static spatial structures (e.g., k-d trees), BVHs are well-suited for scenes where objects move. Strategies include:

• Refitting: After object motion, update bounding volumes by recalculating AABBs from the leaf upwards. This is fast but can degrade tree quality over time.
• Incremental Rebuild: Periodically or when tree quality falls below a threshold, partially or fully rebuild the BVH using fast, approximate methods.
• BVHs for Deformables: Specialized two-level BVHs are used, where a top-level BVH contains rigid parts, and each part has its own BVH for deforming geometry, which is refitted every frame. This makes BVHs the data structure of choice for real-time physics engines and interactive ray tracing.

Querying a BVH involves a depth-first or best-first traversal of the tree. The core operation is the node intersection test. For a ray query:

1. Test ray against the node's AABB. If it misses, prune the entire subtree.
2. If it hits, push child nodes onto a stack or priority queue.
3. Descend to children, repeating the process.
4. Upon reaching a leaf node, perform exact intersection tests with the primitives (triangles, spheres) contained within. Traversal is optimized using packed SIMD instructions to test multiple child AABBs against a ray simultaneously, and with early ray termination when the closest hit is found.

To maximize cache coherence during traversal, BVH nodes are stored in a compact, array-based format. Common layouts include:

• Depth-First Order: Nodes are stored in the order they are visited during a depth-first traversal, improving locality for coherent rays.
• Breadth-First Order: All nodes at the same tree level are stored contiguously.
• Morton-Ordered LBVH: For very fast parallel construction, a Linear BVH (LBVH) can be built by sorting object centroids by their Morton code (a bit-interleaved value from 3D coordinates) and then hierarchically grouping them. This structure, while slightly less optimal than an SAH-built tree, can be constructed in milliseconds on a GPU for millions of primitives.

The initial, high-efficiency stage of the collision detection pipeline that rapidly culls pairs of objects that are obviously not colliding. It uses spatial partitioning data structures—like BVHs, grids, or sweep-and-prune—to reduce the number of expensive precise checks required in the narrowphase. This stage is critical for performance in scenes with thousands of objects.

The second, precise stage where potentially colliding pairs from the broadphase are tested in detail. This stage computes exact contact manifolds, including:

• Contact points (exact locations of intersection)
• Surface normals (direction for impulse resolution)
• Penetration depth (how far objects overlap) Algorithms like GJK (Gilbert–Johnson–Keerthi) and EPA (Expanding Polytope Algorithm) are used here for convex shapes.

The general class of techniques for organizing objects in space to accelerate geometric queries. A BVH is one such technique. Other common structures include:

• Uniform Grids: Space is divided into fixed-size cells.
• Octrees/Quadtrees: Recursive, adaptive subdivision of space.
• kd-Trees: Space is split by axis-aligned planes, often used for ray tracing.
• BSP Trees: Binary space partitioning using arbitrary splitting planes. The choice depends on the query type (e.g., ray vs. collision) and scene dynamics.

A volumetric representation where each point in 3D space stores the shortest distance to a surface, with sign indicating inside (negative) or outside (positive). SDFs enable extremely fast proximity and collision queries against complex, non-convex shapes. They are a complementary representation to polygon meshes and are central to sphere tracing in rendering and certain continuous collision detection methods.

The algorithmic core of a physics engine that resolves forces and impulses to satisfy physical constraints after collisions are detected. It solves for:

• Contact constraints (prevent inter-penetration)
• Friction constraints (model surface interaction)
• Joint constraints (e.g., hinges, sliders) This often involves formulating and solving a Linear Complementarity Problem (LCP) or using iterative solvers like Projected Gauss-Seidel (PGS).

A technique that prevents tunneling, where fast-moving or small objects pass through thin geometry between discrete time steps. Instead of testing static shapes, CCD tests the continuous swept volume of an object's motion. BVHs are often adapted for CCD by using enlarged temporal bounding volumes that encompass an object's entire path during a time step.