Contents (12)
- Mastering BVH and BVTT (Article written and edited by AI)
- 1. Why is it necessary? — The O(n²) wall
- 2. Bounding Volume (BB) — Sacrificing Precision for Speed
- 3. BVH — Divides space hierarchically
- BVH Node Structure
- BVH Construction (Top-down, recursive partitioning) - Median partitioning
- Ray Cross Search - Utilizing SAH Partitioning
- 4. BVTT — Descend both BVHs simultaneously
- BVTT Tour
- 5. Summary of BVH and BVTT
- 6. In the actual engine
- finish
Mastering BVH and BVTT (Article written and edited by AI)
1. Why is it necessary? — The O(n²) wall
Let's say there are 1,000 objects in a 3D scene. To check "Do these objects collide with each other?" every frame, you simply need to check every pair.
for A in objects: for B in objects: if A != B: check_collision(A, B)The complexity of this brute-force method is O(n²) . For 1,000 objects, it requires approximately 500,000 checks; for 10,000 objects, it requires 50 million checks . In a 60fps game, this operation must be repeated per frame. Obviously, it is not practical.
The core idea of the solution is , "Objects that have no possibility of overlapping are not inspected at all."
What comes into play here are the Bounding Volume (BB) and BVH .
2. Bounding Volume (BB) — Sacrificing Precision for Speed
Checking for collisions directly using complex mesh shapes is too expensive. Instead, bounding volumes that wrap objects in simple geometric shapes are used to check for collisions.

The figure above is an example of a Bounding Box model.

The most commonly used is the AABB (Axis-Aligned Bounding Box) . It is a simple rectangular prism aligned to the world coordinate axes, and checking for overlap between two AABBs is completed with just six comparisons of each axis. While fast, it does result in more waste for rotated objects. Therefore, you can use bounding boxes that rotate the axes, such as the OBB.
3. BVH — Divides space hierarchically
Bounding volumes alone are still insufficient. Although it has made it easier to compare collisions, you still have to check every object. It is like having to traverse every object in a scene in a game. Bounding Volume Hierarchy (BVH) groups these objects into a binary tree structure, allowing you to "skip the entire child if it does not overlap with the parent box."

BVH Node Structure
struct BVHNode: aabb: AABB // The bounding box surrounding this node left: BVHNode // Left child (leaf if null) right: BVHNode // Right child (leaf if null) object: Object // Valid only when it is a leaf nodeBVH Construction (Top-down, recursive partitioning) - Median partitioning
function buildBVH(objects): node.aabb = computeAABB(objects) // A box that wraps around the whole thing if len(objects) == 1: node.object = objects[0] // leaf node return node axis = longestAxis(node.aabb) // Divide along the longest axis (the direction in which the object is longest) sorted = sortByAxis(objects, axis) mid = len(sorted) / 2 node.left = buildBVH(sorted[:mid]) node.right = buildBVH(sorted[mid:]) return nodeRay Cross Search - Utilizing SAH Partitioning
function rayIntersect(node, ray): if not intersects(node.aabb, ray): return null // Skip this entire subtree if isLeaf(node): return preciseIntersect(node.object, ray) hitLeft = rayIntersect(node.left, ray) hitRight = rayIntersect(node.right, ray) return closest(hitLeft, hitRight)SAH (Surface Area Heuristic) : Instead of simply partitioning by the median, it calculates the estimated search cost based on the surface area ratio of each partition candidate to select the most efficient partitioning axis. It is said to be essential for ray tracing engines. The figure below shows the difference between partitioning by the median and partitioning by SAH.

4. BVTT — Descend both BVHs simultaneously
With BVH alone, you can find out "which object a ray hits." However, it is different if you want to find collisions between two complex objects, such as "Does Character A collide with Character B?"
When each object has its own BVH, the BVTT (Bounding Volume Traversal Tree) recursively traverses both BVHs simultaneously to narrow down collision pairs.

BVTT Tour
function traverseBVTT(nodeA, nodeB, results): // If the AABBs of the two nodes do not overlap, skip the entire pair. if not overlaps(nodeA.aabb, nodeB.aabb): return // Both undergo precision crash tests on the leaf surface if isLeaf(nodeA) and isLeaf(nodeB): results.add(preciseCheck(nodeA.object, nodeB.object)) return // Split the larger node first (minimize cost) if volume(nodeA) >= volume(nodeB): traverseBVTT(nodeA.left, nodeB, results) traverseBVTT(nodeA.right, nodeB, results) else: traverseBVTT(nodeA, nodeB.left, results) traverseBVTT(nodeA, nodeB.right, results)The key point is simple. If the AABB of two nodes does not overlap, their child pairs can never collide. That is why the entire subtree is pruned. The complexity becomes O(log n · log m) .
5. Summary of BVH and BVTT

In practice, the two are usually used together. Scene-wide BVH is used to identify "collision candidate pairs" ( broad phase ), and for those pairs, the BVH of each object is precisely inspected using BVTT ( narrow phase ).
6. In the actual engine
- Unity Physics / PhysX : Broad phase using Scene BVH (DBVT), narrow phase using each object's convex hull BVH
- Unreal Engine : The `FBVHTree` class manages BVH, and `FChaosPhysics` collects BVTT-based collision pairs.
- Ray Tracing (DXR, NVIDIA OptiX) : GPU-accelerated BVH exploration, processed by RTX BVH hardware units
- FCL (Flexible Collision Library) : Open source for robotics/simulation, provides BVTT-based collision queries
finish
BVH and BVTT are ultimately two applications of the same core idea: "Discard non-overlapping space early." If BVH solved the problem between scenes and rays, BVTT extended that idea to the problem between two complex objects.

The image above is a rendering I created using VTK to highlight the intersection points between multiple objects. I utilized VTK to enable fast re-rendering even when the data changes. Initially, I had the simple idea that overlapping vertices would suffice, but upon reflection, it became complex because collisions only occur when faces intersect. So, while searching for ways to quickly find collision points, I ended up studying BVH and BVTT.
