AABB Trees

2 min read•1 page

An Axis-Aligned Bounding Box (AABB) Tree is a spatial partitioning tree where every node is bounded by a box aligned with the coordinate axes.

AABBNode(primitives):

1. Primitives: Standard mesh triangles or lines enclosed by the node. 2. BBox Union: Bounding box enclosing the union of all child bounding volumes. 3. Binary Children: References to left and right AABB child nodes.

python

1class AABBNode:
2    def __init__(self, primitives):
3        self.primitives = primitives # List of triangles/points
4        self.bbox = self.compute_bounds(primitives)
5        self.left = None
6        self.right = None
7
8    def compute_bounds(self, primitives):
9        min_x = min(p.min_x for p in primitives)
10        max_x = max(p.max_x for p in primitives)
11        min_y = min(p.min_y for p in primitives)
12        max_y = max(p.max_y for p in primitives)
13        min_z = min(p.min_z for p in primitives)
14        max_z = max(p.max_z for p in primitives)
15        return BoundingBox(min_x, max_x, min_y, max_y, min_z, max_z)

2 min read•1 page

To split primitives efficiently, we find the longest coordinate axis of the bounding box and partition the primitives at the midpoint. This yields balanced children bounding boxes.

SplitNode(node, primitives):

1. Longest Axis: Find axis with widest span `max - min`. 2. Centroid Sorting: Sort primitives along this axis. 3. Bisection Split: Split elements equally to balance tree depth.

python

1def split_node(node, primitives):
2    if len(primitives) <= 1:
3        return
4        
5    # 1. Determine longest axis of current bounding box
6    bbox = node.bbox
7    dx = bbox.max_x - bbox.min_x
8    dy = bbox.max_y - bbox.min_y
9    dz = bbox.max_z - bbox.min_z
10    
11    longest_axis = 0 # X
12    if dy > dx and dy > dz:
13        longest_axis = 1 # Y
14    elif dz > dx and dz > dy:
15        longest_axis = 2 # Z
16        
17    # 2. Sort primitives along this axis
18    primitives.sort(key=lambda p: p.centroid[longest_axis])
19    mid = len(primitives) // 2
20    
21    # 3. Create children
22    node.left = AABBNode(primitives[:mid])
23    node.right = AABBNode(primitives[mid:])

Longest Split Axis (0: X, 1: Y, 2: Z)

0.00

3 min read•1 page

Ray casting is accelerated by walking the AABB tree recursively. If a ray misses a parent bounding box, we prune its entire branch instantly.

Raycast(node, ray):

1. Box Test: Perform slab test of ray against AABB. 2. Branch Pruning: Return immediately on miss, saving millions of triangle checks. 3. Triangle Intersection: Perform actual ray-triangle math (Möller-Trumbore) only at leaf nodes.

python

1def ray_intersects_aabb(ray, bbox) -> bool:
2    tmin = (bbox.min_x - ray.origin.x) / ray.direction.x
3    tmax = (bbox.max_x - ray.origin.x) / ray.direction.x
4    if tmin > tmax: tmin, tmax = tmax, tmin
5    
6    for min_v, max_v, orig, dir in [
7        (bbox.min_y, bbox.max_y, ray.origin.y, ray.direction.y),
8        (bbox.min_z, bbox.max_z, ray.origin.z, ray.direction.z)
9    ]:
10        t1 = (min_v - orig) / dir
11        t2 = (max_v - orig) / dir
12        tmin = max(tmin, min(t1, t2))
13        tmax = min(tmax, max(t1, t2))
14        
15    return tmin <= tmax and tmax >= 0.0
16
17def query_raycast(node, ray) -> TriangleIntersection:
18    if not ray_intersects_aabb(ray, node.bbox):
19        return None # Prune subtree
20        
21    if node.is_leaf():
22        return find_closest_triangle(ray, node.primitives)
23        
24    left_hit = query_raycast(node.left, ray)
25    right_hit = query_raycast(node.right, ray)
26    return get_closer_hit(left_hit, right_hit)

Show Bounding Box Wireframes