Mesh to 3D SDF Volume via Jump Flooding in GLSL

Generating a 3D Signed Distance Field (SDF) volume from an arbitrary triangle mesh involves voxelizing the mesh boundary, propagating distances across a discrete 3D grid, and resolving the sign to distinguish the interior from the exterior. By utilizing the Jump Flooding Algorithm (JFA) inside GLSL compute shaders, the process runs massively parallel on the GPU, reducing computational complexity from quadratic to logarithmic passes while generating accurate volumetric distance fields suitable for physics, rendering, and collision detection.

Pipeline Architecture

Transforming a mesh into an SDF volume via GLSL follows four distinct stages:

  1. Mesh Initialization and Seeding: Identifying which grid voxels intersect the triangle mesh and writing their closest surface coordinates.
  2. Jump Flooding Passes: Iteratively propagating seed positions across the 3D grid using exponentially decreasing step sizes.
  3. Distance Calculation: Evaluating the absolute Euclidean distance from each voxel's center to its propagated nearest surface point.
  4. Sign Determination: Classifying voxels as inside (negative) or outside (positive) using mesh winding numbers, ray parity, or normal vectors.

Step 1: Initializing Seed Voxels

The grid is typically allocated as an OpenGL 3D texture using a floating-point format such as GL_RGBA32F to hold the \((x, y, z)\) position of the closest surface point, with an empty identifier (e.g., an out-of-bounds sentinel value or infinity) for uninitialized voxels.

A compute shader or conservative rasterizer evaluates triangles against the voxel grid:

  • Each triangle is projected onto the grid coordinates.
  • For each voxel that the triangle touches, the shader calculates the exact closest point on that triangle to the voxel center.
  • The shader writes this coordinate into the initial 3D texture using imageStore().
#version 450 core
layout(local_size_x = 8, local_size_y = 8, local_size_z = 8) in;

layout(rgba32f, binding = 0) uniform writeonly image3D uSeedTexture;

// Triangle data passed via SSBO
struct Triangle {
    vec3 v0, v1, v2;
};
layout(std430, binding = 1) buffer MeshData {
    Triangle triangles[];
};

vec3 ClosestPointTriangle(vec3 p, vec3 a, vec3 b, vec3 c);

void main() {
    ivec3 voxelCoord = ivec3(gl_GlobalInvocationID.xyz);
    // Find closest triangle intersecting this boundary voxel
    // ...
    // Store closest point coordinates in RGB; unseeded voxels store vec4(1e20)
    imageStore(uSeedTexture, voxelCoord, vec4(closestPoint, 1.0));
}

Step 2: The 3D Jump Flooding Algorithm

The Jump Flooding Algorithm propagates information across an \(N \times N \times N\) grid in \(\log_2(N)\) iterations.

  1. Step Size Schedule: The step size \(s\) begins at \(\lfloor N / 2 \rfloor\) and halves on each successive dispatch: \(s_{k+1} = \lfloor s_k / 2 \rfloor\), terminating after \(s = 1\).
  2. Neighbor Sampling: In each pass, every voxel samples 26 neighbors located at offsets: \[\mathbf{o} \in \{-s, 0, s\}^3 \setminus \{(0,0,0)\}\]
  3. Ping-Pong Buffering: Two 3D textures alternate between reading and writing to prevent race conditions during parallel execution.

GLSL Jump Flood Compute Shader

#version 450 core
layout(local_size_x = 8, local_size_y = 8, local_size_z = 8) in;

layout(rgba32f, binding = 0) uniform readonly image3D uInputTexture;
layout(rgba32f, binding = 1) uniform writeonly image3D uOutputTexture;

uniform int uStepSize;
uniform ivec3 uGridResolution;
uniform vec3 uVoxelSize;

void main() {
    ivec3 coord = ivec3(gl_GlobalInvocationID.xyz);
    if (any(greaterThanEqual(coord, uGridResolution))) return;

    vec3 voxelCenter = (vec3(coord) + 0.5) * uVoxelSize;
    vec4 bestData = imageLoad(uInputTexture, coord);
    float minDistanceSq = 1e20;

    if (bestData.w > 0.0) {
        minDistanceSq = dot(bestData.xyz - voxelCenter, bestData.xyz - voxelCenter);
    }

    // Sample 26 neighbors
    for (int z = -1; z <= 1; ++z) {
        for (int y = -1; y <= 1; ++y) {
            for (int x = -1; x <= 1; ++x) {
                if (x == 0 && y == 0 && z == 0) continue;

                ivec3 neighborCoord = coord + ivec3(x, y, z) * uStepSize;

                if (all(greaterThanEqual(neighborCoord, ivec3(0))) &&
                    all(lessThan(neighborCoord, uGridResolution))) {

                    vec4 neighborData = imageLoad(uInputTexture, neighborCoord);
                    if (neighborData.w > 0.0) {
                        float distSq = dot(neighborData.xyz - voxelCenter, neighborData.xyz - voxelCenter);
                        if (distSq < minDistanceSq) {
                            minDistanceSq = distSq;
                            bestData = neighborData;
                        }
                    }
                }
            }
        }
    }

    imageStore(uOutputTexture, coord, bestData);
}

Note on Accuracy (JFA+1): Standard JFA occasionally suffers from propagation error due to diagonal occlusion. Running an additional pass with a step size of 1 after the sequence completes removes most discretization artifacts.

Step 3: Distance Extraction

Once the jump flooding passes conclude, every voxel stores the world-space coordinate of its closest mesh surface point. A pass converts these coordinates into absolute Euclidean distances:

vec3 surfacePoint = imageLoad(uFinalJFA, coord).xyz;
float distance = length(surfacePoint - voxelWorldPos);

Step 4: Determining the Sign (Inside vs. Outside)

A standard distance field is unsigned (\(d \ge 0\)). Converting it to a signed distance field requires determining whether a voxel resides inside or outside the mesh geometry. For watertight, closed meshes, several GPU-friendly techniques can be used:

  1. Pseudo-Normals / Angle-Weighted Normals: During the seeding pass, store the normal of the closest triangle, edge, or vertex alongside the seed point. In the final pass, evaluate the dot product between the surface-to-voxel direction and the surface normal: \[\text{sign}(\mathbf{p}_{\text{voxel}}) = \text{sgn}((\mathbf{p}_{\text{voxel}} - \mathbf{p}_{\text{seed}}) \cdot \mathbf{n}_{\text{seed}})\] If the dot product is negative, the voxel lies inside the surface.

  2. Ray-Stabbing Parity: A separate compute pass casts rays from grid boundaries along one axis (e.g., \(+Z\)). Each intersection with a mesh face toggles a parity bit. Odd parity marks interior voxels, while even parity marks exterior voxels.

  3. Generalized Winding Numbers: For non-watertight or dirty meshes, hierarchical evaluation of spherical areas approximates the mesh winding number. Voxels with a winding number greater than approximately \(0.5\) are marked as interior.

Final Output

The final result is written to a single-channel GL_R16F or GL_R32F 3D texture representing the signed distance field:

float signedDistance = isInside ? -distance : distance;
imageStore(uSDFVolume, coord, vec4(signedDistance, 0.0, 0.0, 0.0));