Jump Flood Signed Distance Field Computation Is Incorrect

Question

I am trying to implement the Jump Flood Algorithm (JFA) to compute the Signed Distance Field (SDF) of a glyph atlas for font rendering. I managed to set up my framework (OpenglGL-based) for running the algorithm. My implementation employs two frame buffer objects (FBO): at each step, the first FBO serves as input for the current processing step and the second receives the result. The order is then switched achieving a ping-pong effect. The process is repeated for $n=1+\log_2(max(width, height))$ iterations. In my implementation the $0-th$ step is employed for setting the first FBO up, intermediate steps $0\lt i\lt n$ execute iterations of JFA, and the $n-th$ step is employed for computing the actual distance. The very last execution of the shader causes the result to be drawn on a third frame buffer that is then stored for later use. Eventually, I employed the SDF for font rendering. All in all, the algorithm works but the resulting SDF presents odd artifacts and the final result is very poor.

Here is a portion of the SDF computed by my shader. The artifacts I am referring to can be seen on all letters an they look like "blobs" stretching horizontally from inside each letter. This image is obtained by lowering contrast and increasing brightness.

In this zoomed version of the O letter artifacts can be seen more clearly.

I noticed that different results are achieved simply by inverting the direction of the stepsize: doubling the step rather than halving it. This trick mitigates the problem but doesn't solve it.

I tried to sample the center of the texel having the distance encoded (add 0.5 to integer coordinates and then normalize) but this modification did not solve the issue I am experiencing.

Here is an example of the result employing the incorrect SDF.

Here is the first version of my fragment shader, up to now it is the one giving me the best result:

#version 330 core

in vec2 TexCoord;

out vec4 color;

uniform sampler2D inputTexture;

uniform vec2 size;
uniform uint stepNumber;
uniform vec3 solid;

bool IsSeed(vec4 candidate) {
    return candidate.r>.0 && candidate.g>.0;
}

vec4 JFA(vec2 uv, uint k) {
    float diagonal = 99999.9;
    float stepSize = exp2(k);

    vec2 bestNeighbour = vec2(0.0);
    float bestDistance = diagonal;

    for (int x = -1; x <= 1; x++)
        for (int y = -1; y <= 1; y++) {
            vec4 candidateSeed = texture(
                inputTexture,
                uv + (vec2(x, y) * stepSize / size)
            );
            if (IsSeed(candidateSeed)) {
                float distance = distance(uv, candidateSeed.rg);
                if (distance <= bestDistance) {
                    bestDistance = distance;
                    bestNeighbour = candidateSeed.rg;
                }
            }
        }
    return vec4(bestNeighbour, 0.0, 1.0);
}

void main() {
    uint LAST = uint(log2(max(size.x, size.y)));
    vec2 uv = gl_FragCoord.xy/size;
    /* When the step number is 0, we are just preparing the buffer. */
    if (stepNumber==uint(0)) {
        /* Solid is the only color we consider as seeds. */
        if (texture(inputTexture, uv).rgb == solid)
            color = vec4(uv, 0.0, 1.0);
        else
            color = vec4(vec3(0.0), 1.0);
    } else if (uint(1) <= stepNumber && stepNumber < LAST)
        /* Intermediate steps cause the algorithm to proceed. */
        color = JFA(uv, LAST - stepNumber);
    else if (stepNumber == LAST)
        /* The last iteration produces the distance field. */
        color = vec4(
            vec3(distance(uv, texture(inputTexture, uv).rg)),
            1.0
        );
    else if (stepNumber > LAST)
        color = texture(inputTexture, uv);
}

I do not understand what I am doing wrong. I had a look a this, tried the exact same approach but the problem is still here. All help is appreciated.

Answer 1

I doubt I solved the problem, however, eventually, I hacked it to work with the texture sizes I am employing.

Here is the resulting shader:

#version 330 core

in vec2 TexCoord;

out vec4 color;

uniform sampler2D inputTexture;

uniform vec2 size;
uniform uint stepNumber;
uniform vec3 solid;

bool IsSeed(vec4 candidate) {
    return candidate.r>.0 && candidate.g>.0;
}

vec4 JFA(ivec2 center, uint k) {
    float bestDistance = 999999.9;
    float stepSize = exp2(k);

    vec2 UV = vec2(center + 0.5);
    vec2 bestNeighbour = vec2(0.0);

    for (int x = -1; x <= 1; x++)
        for (int y = -1; y <= 1; y++) {
            vec4 candidateSeed = texture(
                inputTexture,
                vec2(UV + ivec2(x, y) * stepSize) / size
            );
            if (IsSeed(candidateSeed)) {
                float distance = distance((UV / size), candidateSeed.rg);
                if (distance <= bestDistance) {
                    bestDistance = distance;
                    bestNeighbour = candidateSeed.rg;
                }
            }
        }
    return vec4(bestNeighbour, 0.0, 1.0);
}

void main() {
    uint LAST = uint(log2(max(size.x, size.y)));
    vec2 uv = (vec2(gl_FragCoord.xy)+vec2(0.5))/size;
    /* When the step number is 0, we are just preparing the buffer. */
    if (stepNumber==uint(0)) {
        /* White is the only color we consider as seeds. */
        if (texture(inputTexture, uv).rgb == solid)
            color = vec4(uv, 0.0, 1.0);
        else
            color = vec4(vec3(0.0), 1.0);
    } else if (uint(1) <= stepNumber && stepNumber < LAST)
        /* Intermediate steps cause the algorithm to proceed. */
        color = JFA(ivec2(gl_FragCoord.xy), (stepNumber + uint(1)));
    else if (stepNumber == LAST)
        /* The last iteration produces the distance field. */
        color = vec4(
            vec3(distance(uv, texture(inputTexture, uv).rg)),
            1.0
        );
    else if (stepNumber > LAST)
        /* Here, we simply copy the output for avoiding to spoil it. */
        color = texture(inputTexture, uv);
}

Answer 2

I eventually solved the problem by radically changing the access method. I am not reading texels via the texture() method any longer, rather I employed texelFetch(). This allowed me to simplify the shader and get the result right in a single attempt.

All in all, I can now tell the problem was due to interpolation rather than to an incorrect comprehension of the algorithm. Hence, accessing texels offsetting them by 0.5 could have solved the problem but there must have been a source of instability somewhere. I also tried employing the pixel_center_integer flag to mimic the same behaviour but again, with poor results.

One last thing to notice is that to avoid numeric stability issues, when testing distances I denormalize them. I also decided to compute distances from the center of each texel, to do so I added 0.5: this approach is superfluous and could be removed at once.

Here is the resulting shader:

#version 330 core

in vec2 TexCoord;

out vec4 color;

uniform sampler2D inputTexture;

uniform vec2 size;
uniform uint stepNumber;
uniform vec3 solid;

bool IsSeed(vec4 candidate) {
    return candidate.r>.0 && candidate.g>.0;
}

vec4 JFA(ivec2 center, uint k) {
    float bestDistance = 999999999.9;
    float stepSize = exp2(k);

    vec2 bestNeighbour = vec2(0.5) / size;
    for (int x = -1; x <= 1; x++)
        for (int y = -1; y <= 1; y++) {
            vec4 candidateSeed = texelFetch(
                inputTexture,
                ivec2(center + (ivec2(x, y) * stepSize)),
                0
            );
            if (IsSeed(candidateSeed)) {
                float dist = distance(vec2(center) + 0.5, candidateSeed.rg * size);
                if (dist <= bestDistance) {
                    bestDistance = dist;
                    bestNeighbour = candidateSeed.rg;
                }
            }
        }
    return vec4(bestNeighbour, 0.0, 1.0);
}

void main() {
    uint LAST = uint(log2(max(size.x, size.y)));
    vec2 cnUv = (gl_FragCoord.xy+vec2(0.5))/size;
    /* When the step number is 0, we are just preparing the buffer. */
    if (stepNumber==uint(0)) {
        /* White is the only color we consider as seeds. */
        if (texelFetch(inputTexture, ivec2(gl_FragCoord.xy), 0).rgb == solid)
            color = vec4(cnUv, 0.0, 1.0);
        else
            color = vec4(vec3(0.0), 1.0);
    } else if (uint(1) <= stepNumber && stepNumber <= LAST + uint(1))
        /* Intermediate steps cause the algorithm to proceed. */
        color = JFA(ivec2(gl_FragCoord.xy), (stepNumber - uint(1)));
    else if (stepNumber == LAST + uint(2))
        /* The last iteration produces the distance field. */
        color = vec4(
            vec3(distance(cnUv * size, texelFetch(inputTexture, ivec2(gl_FragCoord.xy), 0).rg * size)),
            1.0
        );
    else if (stepNumber > LAST + uint(2))
        /* Here, we simply copy the output for avoiding to spoil it. */
        color = texelFetch(inputTexture, ivec2(gl_FragCoord.xy), 0);
}