# Having trouble implementing distance transform with jump flood

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){
//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.

• Welcome to CGSE. The question is generally okay for this site but we want questions to be self-contained so that no external links are necessary to understand the problem. Links may expire in the future, rendering your question useless for others that might have a similar problem. My suggestion is: Copy the shader code into a code block and add 2 or 3 images of your demo that show the problem. Add a caption to each image of how many times you have clicked the "next" button. Of cause, you can keep the links as further references. Nov 15 at 6:55
• thanks @wychmaster — I updated the post
– Nico
Nov 15 at 20:39

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

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


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

• 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
Nov 16 at 17:21
• Initial values should be 0 so bestDist will filter anything that isn't already seeded by way of computing values that are in orbit. Nov 16 at 17:29
• 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. Nov 16 at 17:37
• Ah yes now I'm noticing that in the first place I was incorrectly normalizing the texture coordinate
– Nico
Nov 16 at 17:51
• 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
Nov 16 at 23:58