<p>I eventually solved the problem by radically changing the access method. I am not reading texels via the <code>texture()</code> method any longer, rather I employed <code>texelFetch()</code>. This allowed me to simplify the shader and get the result right in a single
attempt.</p>
<p>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 <code>pixel_center_integer</code> flag to mimic the same behaviour but again, with poor results.</p>
<p>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.</p>
<p>Here is the resulting shader:</p>
<pre><code>#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&gt;.0 &amp;&amp; candidate.g&gt;.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 &lt;= 1; x++)
        for (int y = -1; y &lt;= 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 &lt;= 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) &lt;= stepNumber &amp;&amp; stepNumber &lt;= 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 &gt; LAST + uint(2))
        /* Here, we simply copy the output for avoiding to spoil it. */
        color = texelFetch(inputTexture, ivec2(gl_FragCoord.xy), 0);
}
</code></pre>

CC BY-SA 4.0
2024-08-11T13:04:37.407Z
2024-08-11T13:04:37.407Z
Chaos
<p>I doubt I solved the problem, however, eventually, I hacked it to work with the texture sizes I am employing.</p>
<p>Here is the resulting shader:</p>
<pre><code>#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&gt;.0 &amp;&amp; candidate.g&gt;.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 &lt;= 1; x++)
        for (int y = -1; y &lt;= 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 &lt;= 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) &lt;= stepNumber &amp;&amp; stepNumber &lt; 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 &gt; LAST)
        /* Here, we simply copy the output for avoiding to spoil it. */
        color = texture(inputTexture, uv);
}
</code></pre>

CC BY-SA 4.0
2024-08-04T20:52:06.487Z
2024-08-04T20:52:06.487Z
Chaos
<p>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 <span class="math-container">$n=1+\log_2(max(width, height))$</span> iterations. In my implementation the <span class="math-container">$0-th$</span> step is employed for setting the first FBO up, intermediate steps <span class="math-container">$0\lt i\lt n$</span> execute iterations of JFA, and the <span class="math-container">$n-th$</span> 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.</p>
<p>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 &quot;blobs&quot; stretching horizontally from inside each letter. This image is obtained by lowering contrast and increasing brightness.</p>
<p><a href="https://i.sstatic.net/pBdctSnf.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/pBdctSnf.png" alt="SDF with artifacts" /></a></p>
<p>In this zoomed version of the O letter artifacts can be seen more clearly.</p>
<p><a href="https://i.sstatic.net/YjoBQgmx.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/YjoBQgmx.png" alt="SDF with artifacts, letter O" /></a></p>
<p>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.</p>
<p>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.</p>
<p>Here is an example of the result employing the incorrect SDF.
<a href="https://i.sstatic.net/TCkPVtJj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/TCkPVtJj.png" alt="The result." /></a></p>
<p>Here is the first version of my fragment shader, up to now it is the one giving me the best result:</p>
<pre><code>#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&gt;.0 &amp;&amp; candidate.g&gt;.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 &lt;= 1; x++)
        for (int y = -1; y &lt;= 1; y++) {
            vec4 candidateSeed = texture(
                inputTexture,
                uv + (vec2(x, y) * stepSize / size)
            );
            if (IsSeed(candidateSeed)) {
                float distance = distance(uv, candidateSeed.rg);
                if (distance &lt;= 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) &lt;= stepNumber &amp;&amp; stepNumber &lt; 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 &gt; LAST)
        color = texture(inputTexture, uv);
}
</code></pre>
<p>I do not understand what I am doing wrong.
I had a look a <a href="https://computergraphics.stackexchange.com/questions/12338/having-trouble-implementing-distance-transform-with-jump-flood">this</a>, tried the exact same approach but the problem is still here.
All help is appreciated.</p>

CC BY-SA 4.0
2024-07-10T10:49:54.437Z
Have you seen this shader toy? https://www.shadertoy.com/view/4syGWK It is a good implementation that you can edit and help understand where issues are in your code.
pmw1234
CC BY-SA 4.0
2024-07-10T13:16:42.140Z
Hello, I am looking at it right now; I never encountered that exact example on ShaderToy. It is amazing, to say the least.
Chaos
CC BY-SA 4.0
2024-07-10T20:38:04.567Z
I have updated the JF algorithm, employing integer math when accessing the center of a given texel with no improvement. I also observed the problem occurs only when at least one of the dimensions of the atlas exceeds 1100 pixels. Under that threshold the SDF is perfect.
Chaos
<signed-distance-field><font-rendering>
Jump Flood Signed Distance Field Computation Is Incorrect
Chaos
# Jump Flood Signed Distance Field Computation Is Incorrect

(Asked by: username_0 on 2024-07-09)

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.

[![SDF with artifacts](https://i.sstatic.net/pBdctSnf.png)](https://i.sstatic.net/pBdctSnf.png)

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

[![SDF with artifacts, letter O](https://i.sstatic.net/YjoBQgmx.png)](https://i.sstatic.net/YjoBQgmx.png)

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.
[![The result.](https://i.sstatic.net/TCkPVtJj.png)](https://i.sstatic.net/TCkPVtJj.png)

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](https://computergraphics.stackexchange.com/questions/12338/having-trouble-implementing-distance-transform-with-jump-flood), tried the exact same approach but the problem is still here.
All help is appreciated.

**Tags:** signed-distance-field, font-rendering

> **Comments:**
> **username_1**: Have you seen this shader toy? https://www.shadertoy.com/view/4syGWK It is a good implementation that you can edit and help understand where issues are in your code.  
> **username_0**: Hello, I am looking at it right now; I never encountered that exact example on ShaderToy. It is amazing, to say the least.  
> **username_0**: I have updated the JF algorithm, employing integer math when accessing the center of a given texel with no improvement. I also observed the problem occurs only when at least one of the dimensions of the atlas exceeds 1100 pixels. Under that threshold the SDF is perfect.  

---

## 2 answers

### Answer by username_0 on 2024-08-11. Score: 0 | Accepted answer

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);
}

```


---

### Answer by username_0 on 2024-08-04. Score: 0

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);
}

```


---

