Jump Flooding Algorithm for 2D Voronoi in GLSL

The Jump Flooding Algorithm (JFA) is an efficient, massively parallel technique designed to compute 2D Voronoi diagrams and Euclidean distance fields on the GPU in \(O(\log N)\) passes. By iteratively propagating seed positions across an image grid using geometrically decreasing step sizes, JFA determines the nearest seed for every pixel with high accuracy. This article provides a technical breakdown of the JFA methodology, the ping-pong framebuffer architecture, and a complete GLSL fragment shader implementation for generating 2D Voronoi diagrams.

How Jump Flooding Works

Traditional flood-fill propagates information to immediately adjacent neighbors (\(step = 1\)), requiring \(O(N)\) iterations across an \(N \times N\) grid. The Jump Flooding Algorithm accelerates this process by sampling neighbors at variable step sizes.

Given a grid of size \(N \times N\) (typically a power of two):

1. Pass 1: Step size \(k = N / 2\)
2. Pass 2: Step size \(k = N / 4\)
3. Pass \(i\): Step size \(k = N / 2^i\)
4. Final Pass: Step size \(k = 1\)

During each pass, every pixel inspects its current state and the states of eight neighbors located at an offset of \(k\) units along the horizontal, vertical, and diagonal axes (a \(3 \times 3\) grid pattern). The pixel retains the seed coordinate that is physically closest to its own fragment coordinate.

Texture Setup and State Encoding

To implement JFA in GLSL, you need two Framebuffer Objects (FBOs) configured for ping-pong rendering. Each render target should use a floating-point texture format (such as RGBA32F or RG32F) to avoid precision loss when storing coordinates:

• Initial State: Non-seed pixels are initialized to an invalid marker (e.g., vec2(-1.0, -1.0) or an infinitely distant point). Seed pixels store their own UV or pixel coordinates.
• Storage: The red and green channels (xy) store the coordinate of the nearest known seed. If color-based Voronoi cells are desired, an identifier or color can be stored in the blue and alpha channels (zw).

GLSL Fragment Shader Implementation

Below is the GLSL fragment shader responsible for executing a single step of the Jump Flooding Algorithm. This shader is executed once per pass.

#version 300 es
precision highp float;

out vec4 fragColor;

uniform sampler2D u_texture;  // Texture from previous pass
uniform vec2 u_resolution;    // Viewport resolution (e.g., 1024x1024)
uniform float u_step;         // Current step size in pixels (e.g., 512, 256, 128...)

void main() {
    vec2 fragCoord = gl_FragCoord.xy;
    
    // Track the best seed and minimum squared distance
    vec2 bestSeed = vec2(-1.0);
    float minDistanceSq = 1e20; // Initialize to a large value

    // Sample the 3x3 neighborhood at offset 'u_step'
    for (int y = -1; y <= 1; ++y) {
        for (int x = -1; x <= 1; ++x) {
            vec2 sampleCoord = fragCoord + vec2(float(x), float(y)) * u_step;

            // Bounds check
            if (sampleCoord.x >= 0.0 && sampleCoord.x < u_resolution.x &&
                sampleCoord.y >= 0.0 && sampleCoord.y < u_resolution.y) {
                
                vec2 sampleUV = sampleCoord / u_resolution;
                vec4 seedData = texture(u_texture, sampleUV);
                vec2 seedCoord = seedData.xy;

                // Check if the sampled pixel contains a valid seed
                if (seedCoord.x >= 0.0 && seedCoord.y >= 0.0) {
                    vec2 diff = fragCoord - seedCoord;
                    float distSq = dot(diff, diff);

                    if (distSq < minDistanceSq) {
                        minDistanceSq = distSq;
                        bestSeed = seedCoord;
                    }
                }
            }
        }
    }

    // Output the closest seed coordinate found
    fragColor = vec4(bestSeed, 0.0, 1.0);
}

Multi-Pass CPU Execution Loop

The host application controls the step reduction. For a viewport of dimension \(N = 1024\):

1. Set u_step = 512.0, bind input FBO (initial seeds), render to output FBO.
2. Swap FBOs.
3. Set u_step = 256.0, bind input, render to output.
4. Continue halving u_step until the pass with u_step = 1.0 completes (\(10\) passes total).

Mitigating Errors with 1-JFA

Standard JFA can produce minor topological errors due to missing seeds during early passes. To resolve this, run extra passes at the end with small step sizes, such as adding an additional pass with u_step = 1.0 (known as JFA+1), or using the \(1\text{JFA}\) variant which performs an extra \(step=1\) iteration after each regular step.

Visualizing the Voronoi Diagram

Once the passes finish, a final display shader reads the resulting buffer. Because each pixel now contains the exact coordinate of its Voronoi site in fragColor.xy:

• Voronoi Cells: Hash the coordinate bestSeed into a unique RGB color.
• Euclidean Distance Field: Calculate length(gl_FragCoord.xy - bestSeed) to obtain the exact distance to the nearest site.
• Cell Borders: Check neighboring pixels for differences in bestSeed; any discrepancy indicates an edge.