Morton Codes in Spatial Octrees and BVH Construction

Spatial indexing algorithms translate multi-dimensional coordinate data into one-dimensional keys using Morton codes (also known as the Z-order curve), allowing complex spatial structures like octrees and Bounding Volume Hierarchies (BVHs) to be built with high efficiency. By interleaving the binary bits of spatial coordinates, Morton codes preserve spatial locality within a 1D sequence. This article explains the binary mechanics behind Morton encoding and demonstrates how modern algorithms use these binary representations to construct linear octrees and GPU-accelerated BVHs via sorting and bitwise prefix matching.

Binary Mechanics of Morton Codes

A Morton code maps a multi-dimensional point into a single integer by interleaving the binary representations of its coordinate components. For a 3D coordinate \((X, Y, Z)\) where each axis is normalized to a fixed-width integer (such as an unsigned 10-bit or 21-bit integer):

1. Coordinate Quantization: Floating-point coordinates are mapped to a discrete integer grid within a normalized bounding box.
2. Bit Interleaving: The bits of each coordinate are interleaved sequentially. If \(X = x_2x_1x_0\), \(Y = y_2y_1y_0\), and \(Z = z_2z_1z_0\), the resulting 9-bit Morton code is: \[\text{Code} = z_2y_2x_2 \ z_1y_1x_1 \ z_0y_0x_0\]

In the binary number system, this operation can be computed efficiently using bitwise shift and mask operations or dedicated hardware instructions (such as the PEXT/PDEP instructions in the x86 BMI2 instruction set).

Building Linear Octrees Using Morton Codes

An octree recursively subdivides 3D space into eight octants. In binary, each subdivision level corresponds exactly to 3 bits of a Morton code (representing the choices across the \(X\), \(Y\), and \(Z\) axes).

• Direct Octant Addressing: The most significant 3-bit group determines which of the 8 root-level octants contains the point. The subsequent 3-bit groups determine the child octants at descending depth levels.
• Prefix Matching for Hierarchy: Two points share an ancestor node at depth \(d\) if and only if their Morton codes share the same initial \(3 \times d\) prefix bits.
• Linear Octree Generation: Instead of inserting elements recursively from the top down, spatial indexing algorithms sort all data points by their Morton codes. In a sorted array of Morton codes, points belonging to the same spatial region form contiguous memory blocks. An entire linear octree can be constructed in a single pass by identifying where the bit prefixes change between adjacent sorted elements.

Constructing Bounding Volume Hierarchies (LBVH)

Linear Bounding Volume Hierarchy (LBVH) algorithms, widely used in real-time ray tracing and physics simulations, rely on Morton codes to build balanced binary bounding volume trees in parallel on the GPU.

1. Centroid Encoding: For each primitive (such as a triangle or mesh), the algorithm computes its bounding box centroid, quantizes it, and calculates its 64-bit or 32-bit Morton code.
2. Radix Sorting: Primitives are sorted globally in ascending order of their Morton codes using parallel radix sort, placing spatially adjacent primitives next to each other in memory.
3. Determining Hierarchy via Longest Common Prefix (LCP): To split an interval of primitives \([i, j]\) into left and right child nodes, the algorithm finds the split position where the directional path diverges. This divergence is found by computing the Most Significant Bit (MSB) of the XOR difference between adjacent keys: \[\delta(i, j) = \text{CLZ}(\text{MortonCode}_i \oplus \text{MortonCode}_j)\] where \(\text{CLZ}\) denotes the Count Leading Zeros instruction.
4. Independent Node Allocation: Because the parent-child relationships depend strictly on the common binary prefixes of sorted keys, each internal node in the BVH can compute its bounding box and child pointers independently and concurrently without global tree synchronization.

Advantages of the Binary Approach

Utilizing Morton codes reduces geometric tree construction to sorting and basic bitwise logic (\(\text{AND}\), \(\text{XOR}\), \(\text{SHIFTS}\), \(\text{CLZ}\)). This eliminates expensive geometric intersection tests during hierarchy generation, maximizes CPU/GPU cache locality through contiguous array layouts, and guarantees predictable \(O(N \log N)\) sorting with \(O(N)\) tree construction times.