Line-Sweep Ambient Occlusion in GLSL

This article explores Line-Sweep Ambient Occlusion (LSAO), an efficient screen-space ambient occlusion technique that computes horizon-based shadowing across discrete directional passes. By replacing expensive, isotropic kernel sampling with one-dimensional directional sweeps, the algorithm achieves linear time complexity relative to sweep distance. Below is an examination of how directional raster passes implement LSAO, the mathematical principles behind the height-field horizon propagation, and how to structure the pipeline in GLSL.

The Core Algorithm: 1D Directional Sweep Propagation

Line-Sweep Ambient Occlusion reformulates the screen-space occlusion problem into a series of one-dimensional heightfield tracking passes. Traditional screen-space methods, such as SSAO or HBAO, sample pixels in a circular neighborhood for every fragment, leading to \(O(N \cdot K)\) complexity, where \(N\) is the pixel count and \(K\) is the number of samples per pixel.

LSAO reduces this complexity by casting 1D rays across the screen along fixed directional vectors (typically 4, 8, or 16 directions, such as horizontal, vertical, and diagonal axes). Instead of independently casting rays from every pixel, a single sweep pass traverses an entire line of pixels sequentially. As the sweep progresses, it maintains the running horizon angle or maximum elevation angle relative to previous surfaces. This transforms the calculation into a dynamic programming problem evaluated along 1D paths.

Directional Raster Passes

The algorithm implements the line sweep through multiple directional raster passes using ping-pong framebuffers:

  1. Direction Discretization: The 2D screen is decomposed into discrete 1D sweeps (e.g., left-to-right, right-to-left, bottom-to-top, and top-to-bottom, alongside diagonal sweeps).
  2. Sweep Execution: Each sweep processes a row, column, or diagonal line. A raster pass can be executed as a full-screen quad or by drawing 1D line primitives over the buffer.
  3. Horizon State Tracking: During traversal, a state register or previous pixel's output stores the maximum horizon tangent: \[\tan(\theta) = \frac{z_{\text{sample}} - z_{\text{current}}}{d}\] Where \(z\) represents linear view-space depth and \(d\) is the screen-space distance.
  4. Attenuation and Integration: Occlusion is integrated based on the horizon angle relative to the surface normal, applying a distance-attenuation falloff function to prevent distant geometry from producing false occlusion.

GLSL Implementation Strategy

In modern OpenGL or WebGL, directional passes are commonly executed using either compute shaders with shared memory or fragment shaders utilizing screen-aligned directional blits.

Horizon Update Logic in Fragment Shaders

In a fragment shader running a 1D sweep pass, the current fragment queries the accumulated horizon value propagated from the immediately preceding pixel along the sweep vector:

// Inputs from uniforms and previous pass
uniform sampler2D uDepthBuffer;
uniform sampler2D uSweepBuffer; // Contains propagated horizon data
uniform vec2 uStepDirection;     // Normalized step vector (e.g., vec2(1.0/width, 0.0))
uniform float uAttenuationRadius;

in vec2 vTexCoord;
out vec4 fragColor;

void main() {
    float currentDepth = texture(uDepthBuffer, vTexCoord).r;
    vec2 prevCoord = vTexCoord - uStepDirection;

    // Fetch the propagated state from the previous step along the sweep line
    vec4 prevState = texture(uSweepBuffer, prevCoord);
    float maxHorizonAngle = prevState.r;
    float accumulatedOcclusion = prevState.g;

    // Calculate elevation angle to current sample
    float depthDiff = texture(uDepthBuffer, prevCoord).r - currentDepth;
    float distance = length(uStepDirection);
    
    // Compute current angle and update running maximum
    float currentAngle = atan(depthDiff, distance);
    float falloff = clamp(1.0 - (distance / uAttenuationRadius), 0.0, 1.0);

    if (currentAngle > maxHorizonAngle) {
        maxHorizonAngle = mix(maxHorizonAngle, currentAngle, falloff);
    } else {
        // Horizon decay over distance
        maxHorizonAngle = mix(maxHorizonAngle, -1.57079, 0.05);
    }

    // Integrate local occlusion contribution
    float stepOcclusion = max(0.0, sin(maxHorizonAngle));
    accumulatedOcclusion += stepOcclusion * falloff;

    fragColor = vec4(maxHorizonAngle, accumulatedOcclusion, 0.0, 1.0);
}

Final Accumulation and Filtering

After completing all directional sweeps:

  1. Summation Pass: A final composite fragment shader samples the accumulated occlusion textures from each directional pass, weights them by the projection of the surface normal onto the sweep direction, and averages the results.
  2. Bilateral Blur: A depth-aware spatial cross-bilateral filter is applied to eliminate striping artifacts resulting from discrete directional sampling, producing smooth contact shadows across continuous surfaces.