GPU Morton Codes & LBVH

3 min read•1 page

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 …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

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.

Fractal Recursive Depth

2.00

5 min read•2 pages

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 sorted 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 64 - (i ^ j).bit_length()  # Tie-break identical keys using index
8    return 32 - xor_val.bit_length()
9
10def karras_lbvh_split(morton_codes, i):
11    """
12    Tero Karras (2012) Parallel Radix Tree Construction in O(log N) per GPU thread.
13    Determines range direction d in {-1, +1}, upper bound l_max, and split index gamma.
14    """
15    delta_next = common_prefix_length(morton_codes, i, i + 1)
16    delta_prev = common_prefix_length(morton_codes, i, i - 1)
17    d = 1 if delta_next > delta_prev else -1
18    delta_min = common_prefix_length(morton_codes, i, i - d)
19
20    l_max = 2
21    while common_prefix_length(morton_codes, i, i + l_max * d) > delta_min:
22        l_max *= 2
23
24    l = 0
25    t = l_max // 2
26    while t >= 1:
27        if common_prefix_length(morton_codes, i, i + (l + t) * d) > delta_min:
28            l += t
29        t //= 2
30    j = i + l * d
31
32    delta_node = common_prefix_length(morton_codes, i, j)
33    s = 0
34    step = l
35    while step > 1:
36        step = (step + 1) // 2
37        if common_prefix_length(morton_codes, i, i + (s + step) * d) > delta_node:
38            s += step
39    gamma = i + s * d + min(d, 0)
40    return min(i, j), max(i, j), gamma

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 (δ).

Radix Tree Level

2.00

Related Concepts

GPU & Neural Representations

Morton codes, parallel LBVH, NeRF positional encoding, and 3D Gaussian Splatting.

Explore concept →

GJK & EPA Contact Physics

Interactive geometrical visualization of GJK collision detection and EPA penetration manifolds.

Explore concept →

Continuous Collision (CCD)

Interactive geometrical visualization of CCD swept volumes and speculative contact constraints.

Explore concept →