GPU Morton Codes & LBVH

3 min read•1 page

Morton Codes (Z-Order Space-Filling Curves): Building hierarchical acceleration trees (BVHs) for hardware ray tracing is traditionally sequential and CPU-bound. Morton codes interleave the binary bits of 3D spatial coordinates $(x, y, z)$, mapping a 3D box onto a 1D fractal Z-order curve. Sorting 1D integer keys via GPU parallel radix sort clusters spatially adjacent 3D geometry into cache-coherent blocks in $O(N)$ time.

Morton Code Bit-Interleaving:

1. Bitwise Interleaving: Coordinate bits $(x_2 x_1 x_0, y_2 y_1 y_0, z_2 z_1 z_0)$ interleave to $x_2 y_2 z_2 x_1 y_1 z_1 \dots$ 2. Spatial Locality Preservation: Points close in 3D Euclidean space remain near each other on the 1D sorted curve. 3. Parallel GPU Acceleration: Enables instant real-time BVH rebuilds for dynamic particle physics and RT cores.

python

1def expand_bits(v):
2    """Expands 10-bit integer to 30-bit integer by inserting 2 zeros between each bit."""
3    v = (v * 0x00010001) & 0xFF0000FF
4    v = (v * 0x00000101) & 0x0F00F00F
5    v = (v * 0x00000011) & 0xC30C30C3
6    v = (v * 0x00000005) & 0x49249249
7    return v
8
9def morton_3d(x, y, z):
10    """
11    Computes 30-bit Morton code (Z-order curve) by interleaving bits of normalized (x, y, z).
12    Maps 3D spatial points into a 1D sequence preserving spatial locality.
13    Critical for GPU ray tracing BVH construction (Karras 2012).
14    """
15    xx = expand_bits(int(x * 1023.0))
16    yy = expand_bits(int(y * 1023.0))
17    zz = expand_bits(int(z * 1023.0))
18    return (xx << 2) | (yy << 1) | zz

Fractal Recursive Depth

2.00

3 min read•1 page

Linear Bounding Volume Hierarchies (Karras LBVH): Traditional top-down BVH construction requires recursive partitioning that stalls massively parallel GPU compute units. Tero Karras (NVIDIA 2012) revolutionized hardware ray tracing: after sorting primitives by Morton code, each of the $N-1$ internal BVH nodes can be constructed completely independently by a single GPU thread in parallel without locks or recursion, using binary search on bitwise Common Prefix Lengths ($\delta$).

Karras LBVH Parallel Invariant:

1. Zero Thread Communication: Every thread i generates exactly one internal node. 2. Common Prefix Metric: δ(i, j) = clz(M_i ^ M_j) measures hierarchy proximity. 3. Instant Dynamic Rebuilds: Reconstructs millions of primitives every frame in milliseconds.

python

1def common_prefix_length(morton_codes, i, j):
2    """Counts leading identical bits (clz) between Morton codes i and j."""
3    if j < 0 or j >= len(morton_codes):
4        return -1
5    xor_val = morton_codes[i] ^ morton_codes[j]
6    if xor_val == 0:
7        return 32 + (i ^ j)  # Break ties with index
8    return 32 - xor_val.bit_length()
9
10def karras_lbvh_split(morton_codes, i):
11    """
12    Tero Karras (2012) Parallel Radix Tree Split in O(1).
13    Each GPU thread i evaluates its range [first, last] and finds binary split position gamma
14    using binary search on longest common prefix length delta(i, j).
15    Eliminates all synchronization locks and tree recursion on GPU!
16    """
17    return "Parallel Radix Tree Node (Split Index gamma)"

Radix Tree Level

2.00