Having trouble implementing distance transform with jump flood

Question

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/here.

In the demo 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
10 - begins to do jump-flood-y stuff
18 - weird artifacting and errors

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.

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 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.

Answer 1

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