Decoding Sparse Voxel Octrees in GLSL Raymarchers

This article explains how to unpack and traverse a Sparse Voxel Octree (SVO) inside a GLSL fragment or compute shader. Rendering SVOs in real time requires mapping tree structures into GPU-friendly buffers, transforming ray vectors into localized tree space, and using a stack-based or stackless traversal loop to descend through nodes while skipping empty regions. Below, you will find the fundamental data representation, the mathematical traversal logic, and a concrete GLSL implementation of the decoding algorithm.

SVO Data Layout for the GPU

GPUs execute efficiently when data is linear and cache-friendly. Store the SVO in a Shader Storage Buffer Object (SSBO) or a 1D usamplerBuffer.

A standard 32-bit or 64-bit node layout typically consists of:

  • Child Mask (8 bits): Indicates which of the eight sub-cubes (octants) contain valid geometry.
  • Leaf Flag (1 bit): Marks whether the node is a terminal voxel or an internal branch.
  • Child Pointer (23 to 31 bits): The base index in the buffer where the contiguous block of active children begins.

Because only non-empty children are stored, the memory offset for child \(i\) (where \(i \in [0, 7]\)) is calculated dynamically by counting how many set bits precede bit \(i\) in the child mask:

\[\text{Child Index} = \text{Base Pointer} + \text{bitCount}(\text{ChildMask} \ \& \ ((1 \ll i) - 1))\]

The Traversal Algorithm

The prevailing algorithm for GPU raymarching of octrees is based on the parametric Ray-Box intersection technique adapted from Revelles et al. and popularized by Laine and Karras.

Instead of stepping through space at fixed spatial intervals, the ray is defined parametrically:

\[\mathbf{P}(t) = \mathbf{O} + t \cdot \mathbf{D}\]

The traversal tracks the parametric entry (\(t_{min}\)) and exit (\(t_{max}\)) times through each bounding cube.

1. Coordinate System Standardization

To eliminate conditional branching based on ray direction, invert negative ray components at the start. Mirror the ray origin across the octree boundaries if a ray direction component is negative. This ensures the ray always travels in the positive direction (\(D_x, D_y, D_z > 0\)), allowing uniform child index ordering.

2. Downward Traversal (Push)

At the current node level:

  1. Compute the center planes separating the eight child cubes: \(t_{center} = \frac{\mathbf{Center} - \mathbf{O}}{\mathbf{D}}\).
  2. Determine which octant contains the current \(t_{min}\) by comparing the ray position at \(t_{min}\) against the node center.
  3. Check if the child exists in the child mask.
  4. If it exists and is an internal node, push the current node index, size, and \(t_{max}\) onto a local stack, then descend into that child by scaling down the current search boundary by half.
  5. If it is a leaf node, terminate and return hit information.

3. Sibling Traversal and Upward Traversal (Pop)

If the child is empty or the ray exits the current child:

  1. Find the next sub-octant the ray will cross by finding the minimum of the exit times across the split planes: \[\text{next } t = \min(t_{center.x}, t_{center.y}, t_{center.z})\]
  2. If the exit time exceeds the current node's overall \(t_{max}\), pop the parent node from the stack to ascend to a larger scale.
  3. If still within the current node, advance \(t_{min}\) to this boundary and test the adjacent sibling octant.

GLSL Implementation

The following GLSL snippet outlines the decoding and traversal logic within a fragment shader:

struct OctreeNode {
    uint childMask; // Bits 0-7: children presence, Bit 8: isLeaf
    uint childBase; // Pointer to the first child in memory
};

layout(std430, binding = 0) readonly buffer OctreeBuffer {
    OctreeNode nodes[];
};

struct StackItem {
    uint nodeIndex;
    vec3 minCorner;
    float size;
};

// Returns true if a leaf voxel is hit
bool raymarchSVO(vec3 ro, vec3 rd, out vec3 hitPos, out vec3 hitNormal) {
    // 1. Ray-Box intersection with Root ([0, 1]^3)
    vec3 invDir = 1.0 / rd;
    vec3 t0 = (vec3(0.0) - ro) * invDir;
    vec3 t1 = (vec3(1.0) - ro) * invDir;
    vec3 tmin_v = min(t0, t1);
    vec3 tmax_v = max(t0, t1);

    float tmin = max(max(tmin_v.x, tmin_v.y), tmin_v.z);
    float tmax = min(min(tmax_v.x, tmax_v.y), tmax_v.z);

    if (tmin > tmax || tmax < 0.0) return false;
    tmin = max(tmin, 0.0);

    // 2. Traversal State
    StackItem stack[16];
    int stackPtr = 0;

    stack[0] = StackItem(0u, vec3(0.0), 1.0);
    
    while (stackPtr >= 0) {
        StackItem current = stack[stackPtr];
        OctreeNode node = nodes[current.nodeIndex];

        // If current node is a leaf, report intersection
        if ((node.childMask & 0x100u) != 0u) {
            hitPos = ro + rd * tmin;
            return true;
        }

        // Determine center point of the current node
        float halfSize = current.size * 0.5;
        vec3 center = current.minCorner + vec3(halfSize);

        // Find child octant containing current ray entry point
        vec3 p = ro + rd * (tmin + 0.00001); // Epsilon offset to prevent boundary artifacts
        uint octant = 0u;
        if (p.x >= center.x) octant |= 1u;
        if (p.y >= center.y) octant |= 2u;
        if (p.z >= center.z) octant |= 4u;

        // Check if the octant is occupied
        bool exists = (node.childMask & (1u << octant)) != 0u;

        if (exists) {
            // Count set bits before this octant to find index offset
            uint mask = node.childMask & ((1u << octant) - 1u);
            uint childOffset = bitCount(mask);
            uint nextNodeIdx = node.childBase + childOffset;

            vec3 childMin = current.minCorner + vec3(
                (octant & 1u) != 0u ? halfSize : 0.0,
                (octant & 2u) != 0u ? halfSize : 0.0,
                (octant & 4u) != 0u ? halfSize : 0.0
            );

            // Push next node
            stackPtr++;
            stack[stackPtr] = StackItem(nextNodeIdx, childMin, halfSize);
        } else {
            // Step to next boundary plane
            vec3 tCenter = (center - ro) * invDir;
            
            // Advance tmin to the nearest exiting plane of this sub-octant
            float tNext = 1e20;
            if (rd.x > 0.0 && p.x < center.x) tNext = min(tNext, tCenter.x);
            if (rd.x < 0.0 && p.x >= center.x) tNext = min(tNext, tCenter.x);
            if (rd.y > 0.0 && p.y < center.y) tNext = min(tNext, tCenter.y);
            if (rd.y < 0.0 && p.y >= center.y) tNext = min(tNext, tCenter.y);
            if (rd.z > 0.0 && p.z < center.z) tNext = min(tNext, tCenter.z);
            if (rd.z < 0.0 && p.z >= center.z) tNext = min(tNext, tCenter.z);

            tmin = tNext;

            // If the ray leaves current node bounds, pop the stack
            vec3 nodeExit = (current.minCorner + vec3(current.size) - ro) * invDir;
            vec3 nodeEntry = (current.minCorner - ro) * invDir;
            float currentNodeTMax = min(min(max(nodeEntry.x, nodeExit.x), 
                                           max(nodeEntry.y, nodeExit.y)), 
                                       max(nodeEntry.z, nodeExit.z));

            if (tmin >= currentNodeTMax) {
                stackPtr--;
            }
        }
    }
    return false;
}

Performance Considerations

  1. Stack Memory: Storing 16 levels of tree depth requires 16 stack entries. Using registers for this small array prevents spilling into local scratch memory.
  2. Ray Coherence: Pixels within the same \(8 \times 8\) screen tile traverse similar memory locations. Storing root-adjacent nodes near the beginning of the SSBO maximizes L1/L2 texture cache hits.
  3. Bit Manipulation: Using native GLSL intrinsics like bitCount() ensures that child index resolution evaluates in a single GPU cycle.