The BVH

1 min read•1 page

A Bounding Volume Hierarchy (BVH) organizes geometric primitives (like triangles) into a tree structure of bounding volumes. The root volume encloses the entire model, and children subdivide primitives into smaller subsets.

BVH Node:

1. Encapsulates an Axis-Aligned Bounding Box (AABB). 2. Points to children sub-volumes (left and right branches). 3. References triangles directly if the node is a leaf.

python

1# Bounding Volume Hierarchy Node
2class BVHNode:
3    def __init__(self, bounding_box, primitives=None):
4        self.bbox = bounding_box     # AABB bounding volume
5        self.primitives = primitives # List of geometric objects (if leaf)
6        self.left = None             # Left child
7        self.right = None            # Right child
8        self.is_leaf = True

2 min read•1 page

Building hierarchies requires enclosing sub-nodes. We merge boundary boxes by finding the minimum and maximum coordinate components of both volumes.

AABB Merging:

1. Take two input bounding volumes A and B. 2. Find component-wise min `[min(Ax, Bx), min(Ay, By), min(Az, Bz)]`. 3. Find component-wise max `[max(Ax, Bx), max(Ay, By), max(Az, Bz)]`.

python

1# Merging two Axis-Aligned Bounding Boxes (AABB)
2class AABB:
3    def __init__(self, min_pt, max_pt):
4        self.min = min_pt
5        self.max = max_pt
6        
7    def merge(self, other):
8        # Union box min is the component-wise minimum
9        new_min = [min(a, b) for a, b in zip(self.min, other.min)]
10        # Union box max is the component-wise maximum
11        new_max = [max(a, b) for a, b in zip(self.max, other.max)]
12        return AABB(new_min, new_max)

Box B X Offset

8.00

2 min read•1 page

A BVH is built top-down by sorting geometric primitive centroids along the longest bounding box axis and splitting them into left and right subsets recursively.

Top-Down Construction:

1. Compute AABB for the input primitives. 2. Select the longest axis of the box as the split direction. 3. Sort primitives by centroid and split them at the median index.

python

1# Top-Down BVH Construction
2def build_bvh(primitives, depth=0):
3    bbox = AABB.from_primitives(primitives)
4    node = BVHNode(bbox)
5    
6    if len(primitives) <= MAX_LEAF_PRIMITIVES:
7        node.primitives = primitives
8        return node
9        
10    # Split primitives along the longest axis
11    axis = bbox.longest_axis()
12    primitives.sort(key=lambda p: p.centroid()[axis])
13    mid = len(primitives) // 2
14    
15    node.left = build_bvh(primitives[:mid], depth + 1)
16    node.right = build_bvh(primitives[mid:], depth + 1)
17    node.is_leaf = False
18    return node

BVH Tree Depth

1.00

2 min read•1 page

To minimize ray intersection steps, we estimate partition costs based on surface areas of the children bounding boxes and the number of primitives they enclose.

SAH Cost Logic:

1. Split costs are proportional to the probability of hitting a child node (determined by surface area ratio). 2. Evaluate multiple split candidates along the split axis. 3. Choose the candidate split position that yields the minimum SAH cost score.

python

1# Surface Area Heuristic (SAH) split evaluation
2def evaluate_sah_cost(bounds, left_bounds, right_bounds, left_count, right_count):
3    sa_parent = bounds.surface_area()
4    sa_left = left_bounds.surface_area()
5    sa_right = right_bounds.surface_area()
6    
7    # Cost = Traversal_Cost + (SA_Left/SA_Parent)*Count_Left*Intersect_Cost 
8    #                       + (SA_Right/SA_Parent)*Count_Right*Intersect_Cost
9    cost = 1.0 + (sa_left / sa_parent) * left_count * 0.8 + (sa_right / sa_parent) * right_count * 0.8
10    return cost

Split Plane Offset

0.00

2 min read•1 page

The "Slab Method" tests intersections of a ray against three sets of parallel planes that define the bounding box limits, yielding entrance and exit parametric intervals.

Slab Intersection:

1. Calculate near and far intersection steps for each dimension interval. 2. Keep the maximum of entry steps (`t_min`) and minimum of exit steps (`t_max`). 3. A hit occurs if `t_min` is smaller than `t_max` and `t_max` is greater than zero.

python

1# Slab-method Ray-AABB intersection check
2def intersect_ray_aabb(ray_origin, ray_dir, bbox):
3    t_min = float('-inf')
4    t_max = float('inf')
5    
6    for i in range(3): # For X, Y, Z axes
7        invD = 1.0 / ray_dir[i]
8        t0 = (bbox.min[i] - ray_origin[i]) * invD
9        t1 = (bbox.max[i] - ray_origin[i]) * invD
10        
11        # Swap values if invD is negative
12        if invD < 0.0:
13            t0, t1 = t1, t0
14            
15        t_min = max(t0, t_min)
16        t_max = min(t1, t_max)
17        
18        if t_max <= t_min:
19            return False, 0.0 # Miss
20            
21    return True, t_min # Hit

Ray Y Position

0.00

3 min read•1 page

The Möller-Trumbore algorithm performs fast ray-triangle intersections by projecting coordinates directly into barycentric space without computing planar equations.

Möller-Trumbore:

1. Calculate edge vectors of the triangle. 2. Calculate barycentric coordinates `u` and `v` using vector scalar products. 3. A hit is registered if u >= 0, v >= 0, and u + v <= 1.

python

1# Möller-Trumbore Ray-Triangle intersection check
2def intersect_ray_triangle(ray_origin, ray_dir, v0, v1, v2):
3    edge1 = v1 - v0
4    edge2 = v2 - v0
5    h = cross(ray_dir, edge2)
6    a = dot(edge1, h)
7    
8    if -1e-6 < a < 1e-6:
9        return False, 0.0, 0.0, 0.0 # Parallel
10        
11    f = 1.0 / a
12    s = ray_origin - v0
13    u = f * dot(s, h)
14    if u < 0.0 or u > 1.0:
15        return False, 0.0, 0.0, 0.0
16        
17    q = cross(s, edge1)
18    v = f * dot(ray_dir, q)
19    if v < 0.0 or u + v > 1.0:
20        return False, 0.0, 0.0, 0.0
21        
22    t = f * dot(edge2, q)
23    return t > 1e-6, t, u, v

Ray X Position

0.00

2 min read•1 page

To find the closest triangle on a complex mesh, we traverse the BVH hierarchy, calculating distances to bounding volumes and pruning sub-nodes that cannot contain closer elements.

Closest Primitive Query:

1. Calculate distance from target to node bounding box. 2. Recursively search children, sorting by bounding box proximity. 3. Perform exact triangle distance checks at leaf nodes to update the closest candidate.

python

1# Finding closest point on mesh using BVH
2def closest_point_bvh(node, target_pt, best_dist=float('inf'), best_pt=None):
3    if distance_to_box(target_pt, node.bbox) >= best_dist:
4        return best_pt, best_dist # Prune branch
5        
6    if node.is_leaf:
7        for triangle in node.primitives:
8            pt, d = closest_point_on_triangle(target_pt, triangle)
9            if d < best_dist:
10                best_dist = d
11                best_pt = pt
12        return best_pt, best_dist
13        
14    # Search nearest branch first
15    # ...

Target X Position

4.00

Target Y Position

4.00

2 min read•1 page

To detect collision intersections between two meshes, we intersect their BVHs. We recursively traverse sub-nodes only when parent bounding boxes overlap, avoiding O(N²) triangle checks.

Mesh Collision:

1. Verify overlap between AABB node A and node B bounds. 2. If they overlap, recursively test left/right child pairs. 3. Perform exact triangle-triangle intersection checks at overlapping leaf nodes.

python

1# BVH-to-BVH mesh intersection clash detection
2def intersect_bvhs(nodeA, nodeB, overlaps):
3    if not boxes_overlap(nodeA.bbox, nodeB.bbox):
4        return # Prune
5        
6    if nodeA.is_leaf and nodeB.is_leaf:
7        # Check actual triangle-triangle overlaps at leaves
8        for triA in nodeA.primitives:
9            for triB in nodeB.primitives:
10                if triangles_intersect(triA, triB):
11                    overlaps.append((triA, triB))
12        return
13        
14    # Traverse child tree pairs recursively
15    intersect_bvhs(nodeA.left, nodeB.left, overlaps)
16    intersect_bvhs(nodeA.left, nodeB.right, overlaps)
17    intersect_bvhs(nodeA.right, nodeB.left, overlaps)
18    intersect_bvhs(nodeA.right, nodeB.right, overlaps)

Bunny Offset Separation

6.00