<p>I took a few minutes and hacked this to life for you. The bugs were all pretty basic things like using floating point math where it should have been using interger math. All those little fractions add up so be careful there. I'm not sure what the alpha channel was up to, I removed that completely. The biggest issue was the large if statement was skipping some of the distance transforms which snowballed as the iters stepped. I'm not sure how pass is being computed I came up with my own version for that. The code below isn't perfectly fixed but it should be enough to get you up and running (hopefully).</p>
<pre><code>vec4 step_jfa(vec2 pCoord,float pass)
{
 //offset neighbors according to pass number
 pass = clamp( pass-1.0, 0.0, 15); 
 int offset= int(exp2(log2(img_width)  - pass));

 vec4 rgba=vec4(0.,0.,0.,0.);
 float bestDist=900000.;

 // loop through P and 8 surrounding neighbor pixels
 ivec2 nCoord= ivec2(pCoord+0.5);
 for(float x = -1.; x &lt;= 1.; x++) 
 {
   for(float y = -1.; y &lt;= 1.; y++) 
   {
     ivec2 sCoord = nCoord + ivec2(x,y)*offset;

     // if the loop item Q exists
      vec4 neighbor=load0(sCoord);
      
      // compute the distance of P to Q's saved origin
      vec2 nOrigin=vec2(neighbor.rg);
      float d=distance(pCoord,nOrigin);
      if(d&lt;bestDist)
      {
        // if it's shorter than the currently saved distance record, overwrite the saved origin in P.
        bestDist=d;
        rgba.rg=nOrigin.rg;

       } 
     } 
   } 
   return rgba;        
 }
</code></pre>
<p>Here is the load0 function:</p>
<pre><code>vec4 load0(ivec2 p) {
    vec2 uv = (vec2(p)-0.5) / textureSize.xy;
    return texture(usampler, uv);
}
</code></pre>
<p>Here is a jfaPrep function example, it should be pretty close to just plug and play.</p>
<pre><code>// pCoord is normalized uv coords
vec4 jfa_prep( vec2 pCoord ) 
{
    // don't use load0 here...just us the normalized uv coords
    vec4 color = texture2D(original_image_sampler, pCoord);
    
    // decide if color is meaningful in some way
    // such as...do any of the rgb channels contain a value?
    float useful = color.r+color.g+color.b;
    vec4 save_value = vec4(0.0);
    if( useful &gt; 0.0) { // assumes image is on a black background (all zero's)
       // save the unnormalized coords
       // 8bit images work, but for debugging 16bit images are better
       // such as r16g16b16a16
       save_value = vec4( uv*imageSize, 0.0, 0.0);
    } 

    // Save value to jfa image
    return save_value;
} 
</code></pre>

CC BY-SA 4.0
2021-11-16T17:21:14.047Z
Wow thanks! This isn't working for me yet but maybe I can get it going if I can clarify a few things. Here’s #1: the alpha value in mine is being used to check which neighbors are seeds during a given pass, and only compare distance/fill the pixel in if this is the case for at least one neighbor. I’m surprised this check isn’t needed at all?
Nico
CC BY-SA 4.0
2021-11-16T17:29:09.353Z
Initial values should be 0 so bestDist will filter anything that isn't already seeded by way of computing values that are in orbit.
pmw1234
CC BY-SA 4.0
2021-11-16T17:37:46.097Z
Take a look at your load0 function, my edits are passing it an unnormalized texture coordinate and the load0 I use normalizes the texture coords before doing the texture lookup, so you may need to edit load0 to normalize the passed in coords.
pmw1234
CC BY-SA 4.0
2021-11-16T17:51:46.893Z
Ah yes now I'm noticing that in the first place I was incorrectly normalizing the texture coordinate
Nico
CC BY-SA 4.0
2021-11-16T23:58:20.543Z
Just coming back to this — do you mind if I see your setup function for the initial values? I think initially encoding the seed coordinates is tripping me up as well.
Nico
CC BY-SA 4.0
2021-11-18T13:24:46.893Z
I updated my answer with a setup function
pmw1234
CC BY-SA 4.0
2021-11-16T16:20:22.523Z
2021-11-18T13:36:34.217Z
2021-11-18T13:36:34.217Z
pmw1234
<p>I'm attempting to use the jump flood algorithm to compute distance transforms of an arbitrary texture derived from a canvas2d context, roughly following the explanations detailed <a href="https://blog.demofox.org/2016/02/29/fast-voronoi-diagrams-and-distance-dield-textures-on-the-gpu-with-the-jump-flooding-algorithm/" rel="nofollow noreferrer">here</a>/<a href="https://www.youtube.com/watch?v=A0pxY9QsgJE" rel="nofollow noreferrer">here</a>.</p>
<p>In the <a href="https://nchilla.github.io/shaders/sdf-posters/experiments/parallel-flood-fill/" rel="nofollow noreferrer">demo</a> I have going, nothing happens for the first 9 waves, and then all of a sudden it begins to display something that is wrong in a way that I don't quite understand. See images:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Wave count</th>
<th>Display</th>
</tr>
</thead>
<tbody>
<tr>
<td>1-9 - no change</td>
<td><img src="https://github.com/nchilla/shaders/raw/main/troubleshooting/Screen%20Shot%202021-11-15%20at%203.26.22%20PM.png" alt="rg stores position of original seeds" /></td>
</tr>
<tr>
<td>10 - begins to do jump-flood-y stuff</td>
<td><img src="https://github.com/nchilla/shaders/raw/main/troubleshooting/Screen%20Shot%202021-11-15%20at%203.26.39%20PM.png" alt="begins to do jump-flood-y stuff" /></td>
</tr>
<tr>
<td>18 - weird artifacting and errors</td>
<td><img src="https://github.com/nchilla/shaders/raw/main/troubleshooting/Screen%20Shot%202021-11-15%20at%203.26.59%20PM.png" alt="weird artifacting in the bottom left" /></td>
</tr>
</tbody>
</table>
</div>
<p>Here is the main jump flood step function. I'm using the A value to check if a pixel is filled in, and using RG to store the seed origin.</p>
<pre class="lang-glsl prettyprint-override"><code>vec4 step_jfa(vec2 pCoord,float pass){

  // looking at pixel P:

  //offset neighbors according to pass number
  float offset=exp2(log2(img_width)  - pass - 1.);

  vec4 rgba=vec4(0.,0.,0.,0.);
  float bestDist=900000.;

    // loop through P and 8 surrounding neighbor pixels
  for(float x = -1.; x &lt;= 1.; x++) {
    for(float y = -1.; y &lt;= 1.; y++) {
      vec2 nCoord=pCoord;
      nCoord.x+=x*offset;
      nCoord.y+=y*offset;

      // if the loop item Q exists
      if(nCoord.x&gt;0.&amp;&amp;nCoord.x&lt;=img_width&amp;&amp;nCoord.y&gt;0.&amp;&amp;nCoord.y&lt;=img_height){
        vec4 neighbor=load0(nCoord);
        //if Q is a seed
        if(neighbor.a&gt;0.){
          // compute the distance of P to Q's saved origin
          vec2 nOrigin=vec2(neighbor.rg);
          float d=distance(pCoord,nOrigin);
          if(d&lt;bestDist){
            // if it's shorter than the currently saved distance record, overwrite the saved origin in P.
            bestDist=d;
            rgba.rg=nOrigin.rg;
            rgba.a=1.;

          } 

        } 

      } 
    }
  }


  return rgba;

}
</code></pre>
<p>I'm assuming the problem is within this function, so to save space I'm going to omit some helper functions for now, but the full code is <a href="https://github.com/nchilla/shaders/blob/main/sdf-posters/experiments/parallel-flood-fill/jfa.frag" rel="nofollow noreferrer">here</a> and I'll update this post if something external turns out to be the problem.</p>
<p>My best guess at the moment is that there's an issue with how I'm calculating the offset in each shader pass. When I tried mapping the offset to the B value of each pixel in the shader, it turns out to be wildly off from where it should be based on the pass.</p>

<shader><glsl><algorithm><mathematics><signed-distance-field>
Having trouble implementing distance transform with jump flood
Nico
# Having trouble implementing distance transform with jump flood

(Asked by: username_0 on 2021-11-14)

I'm attempting to use the jump flood algorithm to compute distance transforms of an arbitrary texture derived from a canvas2d context, roughly following the explanations detailed [here](https://blog.demofox.org/2016/02/29/fast-voronoi-diagrams-and-distance-dield-textures-on-the-gpu-with-the-jump-flooding-algorithm/)/[here](https://www.youtube.com/watch?v=A0pxY9QsgJE).

In the [demo](https://nchilla.github.io/shaders/sdf-posters/experiments/parallel-flood-fill/) I have going, nothing happens for the first 9 waves, and then all of a sudden it begins to display something that is wrong in a way that I don't quite understand. See images:

| Wave count | Display |
| --- | --- |
| 1-9 - no change | rg stores position of original seeds |
| 10 - begins to do jump-flood-y stuff | begins to do jump-flood-y stuff |
| 18 - weird artifacting and errors | weird artifacting in the bottom left |

Here is the main jump flood step function. I'm using the A value to check if a pixel is filled in, and using RG to store the seed origin.

```glsl
vec4 step_jfa(vec2 pCoord,float pass){

  // looking at pixel P:

  //offset neighbors according to pass number
  float offset=exp2(log2(img_width)  - pass - 1.);

  vec4 rgba=vec4(0.,0.,0.,0.);
  float bestDist=900000.;

    // loop through P and 8 surrounding neighbor pixels
  for(float x = -1.; x <= 1.; x++) {
    for(float y = -1.; y <= 1.; y++) {
      vec2 nCoord=pCoord;
      nCoord.x+=x*offset;
      nCoord.y+=y*offset;

      // if the loop item Q exists
      if(nCoord.x>0.&&nCoord.x<=img_width&&nCoord.y>0.&&nCoord.y<=img_height){
        vec4 neighbor=load0(nCoord);
        //if Q is a seed
        if(neighbor.a>0.){
          // compute the distance of P to Q's saved origin
          vec2 nOrigin=vec2(neighbor.rg);
          float d=distance(pCoord,nOrigin);
          if(d<bestDist){
            // if it's shorter than the currently saved distance record, overwrite the saved origin in P.
            bestDist=d;
            rgba.rg=nOrigin.rg;
            rgba.a=1.;

          } 

        } 

      } 
    }
  }

  return rgba;

}

```

I'm assuming the problem is within this function, so to save space I'm going to omit some helper functions for now, but the full code is [here](https://github.com/nchilla/shaders/blob/main/sdf-posters/experiments/parallel-flood-fill/jfa.frag) and I'll update this post if something external turns out to be the problem.

My best guess at the moment is that there's an issue with how I'm calculating the offset in each shader pass. When I tried mapping the offset to the B value of each pixel in the shader, it turns out to be wildly off from where it should be based on the pass.

**Tags:** shader, glsl, algorithm, mathematics, signed-distance-field


---

## 1 answers

### Answer by username_1 on 2021-11-16. Score: 3 | Accepted answer

I took a few minutes and hacked this to life for you. The bugs were all pretty basic things like using floating point math where it should have been using interger math. All those little fractions add up so be careful there. I'm not sure what the alpha channel was up to, I removed that completely. The biggest issue was the large if statement was skipping some of the distance transforms which snowballed as the iters stepped. I'm not sure how pass is being computed I came up with my own version for that. The code below isn't perfectly fixed but it should be enough to get you up and running (hopefully).

```
vec4 step_jfa(vec2 pCoord,float pass)
{
 //offset neighbors according to pass number
 pass = clamp( pass-1.0, 0.0, 15); 
 int offset= int(exp2(log2(img_width)  - pass));

 vec4 rgba=vec4(0.,0.,0.,0.);
 float bestDist=900000.;

 // loop through P and 8 surrounding neighbor pixels
 ivec2 nCoord= ivec2(pCoord+0.5);
 for(float x = -1.; x <= 1.; x++) 
 {
   for(float y = -1.; y <= 1.; y++) 
   {
     ivec2 sCoord = nCoord + ivec2(x,y)*offset;

     // if the loop item Q exists
      vec4 neighbor=load0(sCoord);
      
      // compute the distance of P to Q's saved origin
      vec2 nOrigin=vec2(neighbor.rg);
      float d=distance(pCoord,nOrigin);
      if(d<bestDist)
      {
        // if it's shorter than the currently saved distance record, overwrite the saved origin in P.
        bestDist=d;
        rgba.rg=nOrigin.rg;

       } 
     } 
   } 
   return rgba;        
 }

```

Here is the load0 function:

```
vec4 load0(ivec2 p) {
    vec2 uv = (vec2(p)-0.5) / textureSize.xy;
    return texture(usampler, uv);
}

```

Here is a jfaPrep function example, it should be pretty close to just plug and play.

```
// pCoord is normalized uv coords
vec4 jfa_prep( vec2 pCoord ) 
{
    // don't use load0 here...just us the normalized uv coords
    vec4 color = texture2D(original_image_sampler, pCoord);
    
    // decide if color is meaningful in some way
    // such as...do any of the rgb channels contain a value?
    float useful = color.r+color.g+color.b;
    vec4 save_value = vec4(0.0);
    if( useful > 0.0) { // assumes image is on a black background (all zero's)
       // save the unnormalized coords
       // 8bit images work, but for debugging 16bit images are better
       // such as r16g16b16a16
       save_value = vec4( uv*imageSize, 0.0, 0.0);
    } 

    // Save value to jfa image
    return save_value;
} 

```

> **Comments:**
> **username_0**: Wow thanks! This isn't working for me yet but maybe I can get it going if I can clarify a few things. Here’s #1: the alpha value in mine is being used to check which neighbors are seeds during a given pass, and only compare distance/fill the pixel in if this is the case for at least one neighbor. I’m surprised this check isn’t needed at all?  
> **username_1**: Initial values should be 0 so bestDist will filter anything that isn't already seeded by way of computing values that are in orbit.  
> **username_1**: Take a look at your load0 function, my edits are passing it an unnormalized texture coordinate and the load0 I use normalizes the texture coords before doing the texture lookup, so you may need to edit load0 to normalize the passed in coords.  
> **username_0**: Ah yes now I'm noticing that in the first place I was incorrectly normalizing the texture coordinate  
> **username_0**: Just coming back to this — do you mind if I see your setup function for the initial values? I think initially encoding the seed coordinates is tripping me up as well.  
> **username_1**: I updated my answer with a setup function  

---

