Hierarchical Z Raymarching Algorithm in GLSL

Hierarchical Z-buffer (Hi-Z) raymarching is an acceleration technique for Screen-Space Reflections (SSR) that traverses a depth map pyramid to skip vast regions of empty screen space. By storing conservative depth bounds in lower-resolution mip levels, the algorithm enables rays to take large geometric steps when no geometry is near, progressively refining to full-resolution checks only when an intersection is imminent. This article details the cell traversal algorithm, its mathematical foundation, and its implementation in GLSL.

Core Concepts of Hi-Z Traversal

The standard depth buffer is downsampled into a mip chain where each texel at mip level \(L\) represents the maximum depth (or minimum depth, depending on whether reverse-Z is used) of the corresponding \(2 \times 2\) texels at level \(L-1\). In a standard OpenGL depth buffer (where near is 0.0 and far is 1.0), each mip cell stores the maximum depth value within its bounds.

The traversal algorithm models the depth pyramid as an adaptive bounding volume hierarchy in screen space (UV coordinates \([0, 1]^2\) and depth \([0, 1]\)). The ray advances through grid cells using two primary actions:

  1. Step Up (Coarsen): If the ray passes completely through a cell without intersecting its stored depth, the ray advances to the boundary of that cell, and the algorithm increases the mip level (mipLevel++) to cover larger spatial distances on the next iteration.
  2. Step Down (Refine): If the ray dips behind the depth stored in the current cell, a potential intersection exists. The ray does not advance across the cell boundary; instead, the mip level is decremented (mipLevel--) to check finer geometric boundaries.

An intersection is confirmed when a collision occurs at mipLevel == 0 within an acceptable thickness threshold.

Cell Boundary Intersection Math

To move along the ray through the grid, the algorithm determines the parametric distance \(t\) along the ray to the nearest X or Y boundary of the current cell at the active mip level.

Given a ray with origin \(\mathbf{P}\) and direction \(\mathbf{D}\):

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

  1. Determine the integer cell index and boundary at the current mip level resolution: \[\text{cellSize} = 1.0 / \text{mipResolution}\] \[\text{cellIndex} = \lfloor \mathbf{P}_{xy} / \text{cellSize} \rfloor\] \[\text{boundary}_{xy} = (\text{cellIndex} + \text{max}(\text{sign}(\mathbf{D}_{xy}), 0.0)) \cdot \text{cellSize}\]

  2. Calculate the distance along the ray to cross the boundaries: \[t_{xy} = \frac{\text{boundary}_{xy} - \mathbf{P}_{xy}}{\mathbf{D}_{xy}}\]

  3. The distance to the exit of the 2D cell is: \[t_{\text{exit}} = \min(t_x, t_y)\]

A small epsilon offset is applied when advancing to \(t_{\text{exit}}\) to push the ray into the neighboring cell and prevent self-intersection loops.

GLSL Traversal Implementation

Below is a complete GLSL function implementing cell traversal for a standard Z-buffer configuration:

// Assumes depth is 0.0 (near) to 1.0 (far)
// hiZBuffer is a sampler2D with MAX reduction filter mips

vec3 intersectCellBoundary(vec3 pos, vec3 dir, vec2 cellIndex, vec2 numCells) {
    vec2 cellBound = (cellIndex + max(sign(dir.xy), 0.0)) / numCells;
    vec2 t = (cellBound - pos.xy) / dir.xy;
    float tMin = min(t.x, t.y);
    return pos + dir * tMin;
}

bool hiZTrace(
    vec3 rayOrigin, 
    vec3 rayDir, 
    sampler2D hiZBuffer, 
    vec2 screenDim, 
    int maxIterations, 
    int maxLevel, 
    out vec3 hitPixel
) {
    float currentLevel = 0.0;
    vec3 currentPos = rayOrigin;
    
    // Slight offset along direction to enter adjacent space
    const float eps = 0.0001;
    
    for (int i = 0; i < maxIterations; ++i) {
        // Break if ray leaves screen bounds [0, 1]
        if (any(lessThan(currentPos.xy, vec2(0.0))) || any(greaterThan(currentPos.xy, vec2(1.0)))) {
            return false;
        }

        vec2 mipResolution = screenDim / exp2(currentLevel);
        vec2 cellIndex = floor(currentPos.xy * mipResolution);
        
        // Sample the maximum depth at the current cell and mip level
        float cellDepth = textureLod(hiZBuffer, currentPos.xy, currentLevel).r;
        
        // Find ray position at the boundary of the current 2D cell
        vec3 boundaryPos = intersectCellBoundary(currentPos, rayDir, cellIndex, mipResolution);
        
        // Intersect ray with the cell's depth plane
        float tDepth = (cellDepth - currentPos.z) / rayDir.z;
        vec3 depthIntersectPos = currentPos + rayDir * tDepth;
        
        // Check if the ray penetrates the geometry before leaving the 2D cell boundary
        bool intersectsZ = (rayDir.z > 0.0) 
            ? (currentPos.z <= cellDepth && depthIntersectPos.z <= boundaryPos.z)
            : (depthIntersectPos.z >= boundaryPos.z);

        if (intersectsZ && depthIntersectPos.z >= currentPos.z) {
            // Potential intersection: descend to higher detail
            if (currentLevel == 0.0) {
                // Confirm intersection thickness to avoid false positives behind objects
                float thickness = 0.005;
                if (depthIntersectPos.z - cellDepth <= thickness) {
                    hitPixel = depthIntersectPos;
                    return true;
                }
                // Step past if it exceeds thickness
                currentPos = boundaryPos + rayDir * eps;
            } else {
                currentLevel -= 1.0;
            }
        } else {
            // No collision in this cell: advance ray to boundary and step up
            currentPos = boundaryPos + rayDir * eps;
            currentLevel = min(currentLevel + 1.0, float(maxLevel));
        }
    }
    
    return false;
}

Handling Boundary Artifacts and Performance

  • Cross-Cell Leakage: Advancing precisely to \(t_{\text{exit}}\) can cause numeric stagnation where floating-point inaccuracies cause the sample coordinate to remain inside the current cell. Multiplying the direction by a small scalar offset (\(\epsilon\)) pushes the origin definitively across the cell boundary into the adjacent texel.
  • Skipping Consecutive Level Increments: After stepping down to resolve an occlusion, stepping immediately back up on a failure can trigger an infinite step-down/step-up cycle. Many implementations mandate at least one cell advancement before allowing currentLevel to increase again.
  • Reverse-Z Adaptations: If using Reverse-Z (\(1.0 = \text{near}, 0.0 = \text{far}\)), the Hi-Z pyramid must store the minimum depth value of child texels rather than the maximum, and inequality comparisons in the intersection stage must be inverted.