GM Shaders Mini: JFA

Using the "Jump Flooding Algorithm" for a distance field

Hello folks,

Today is all about the “Jump Flooding Algorithm” which has a few variations and uses, but today I want to focus on using it for generating distance fields around textures.

Isolines around the text, show the distance field

In our case, we are looking to find the distance around the opaque pixels on a texture. This can then be used for outlines, soft shadows, glows, and much more! Let’s start with an overview.

Algorithm Overview

The process is fairly simple to understand. To make the process simple, let’s stick to only opaque pixels (alpha = 1) and empty space (alpha = 0).
This is a multipass effect that samples a 3x3 area at multiple power-of-2 scales. I call this jump for the texel “jump” distance. For example, the first pass’s jump may be 64, the second 32, the third 16, and so on all the way down to 1.

With each pass, we need to sample 3x3 with the sample coordinates ranging from -jump to +jump texels on both axes. Something like this:

for(int x = -1; x<=1; x++)
for(int y = -1; y<=1; y++)
{
    vec2 offset = jump*vec2(x,y)
    vec4 samp = texture2D(tex, texcoord + offset*texel);
}

Then we need to check which of the samples hit something and if so, store how far away they are and the texel offset of that sample:

//Initialize "dist" outside of the for-loops
float samp_dist = length(offset);
//Store the closest opaque sample
if (samp_dist<dist && samp.a == 1.0)
{
    dist = samp_dist;
    tex_off = offset;
}

So “dist” holds the distance to the nearest opaque sample and “tex_off” holds the relative xy position of that sample.

The final trick here is to set the fragment red and green channel output to the texel offset so that we factor it into “samp_dist” in the next pass.
I’m using the regular surface format, so I need to convert this to the 8-bit 0-1 range like so:

gl_FragColor.rg = (tex_off.rg + 127.0) / 255.0;

That’s the gist of the algorithm. Here’s a great visual example by paniq that may be helpful.

Note: there are several variations you can make depending on your needs. For example, you can use floating-point surfaces so you aren’t limited to a max distance of 127 (since the offsets range from -127 to +128). You can also calculate the internal distance for a proper SDF. In my variation, I preserve the opaque pixel colors and only generate the distance field around them.

My Code

I figured it’d be easier to see a complete working example, so here’s my code:

//Center RG value
#define CENTER 127.0/255.0
//RG value range
#define RANGE  255.0

//Jump Flooding Algorithm
//RG encodes XY offset
//Alpha encodes inverted distance
vec4 JFA(sampler2D t, vec2 uv)
{
	//True if this is the first pass
	bool first = u_first>0.5;
	//Initialize output
	vec4 encode = vec4(0.0);
	//Initialize the closest distance (1.0 is outside the range)
	float dist = 1.0;
    
	//Loop through neighbor cells
	for(int x = -1; x <= 1; x++)
	for(int y = -1; y <= 1; y++)
	{
		//Pixel offset with jump distance
		vec2 off = vec2(x,y) * u_jump;
		//Compute new texture coordinates
		vec2 coord = uv + off * u_texel;
		//Skip texels outside of the texture
		if (coord != clamp(coord, 0.0, 1.0)) continue;
		
		//Sample the texture at the coordinates
		vec4 samp = texture2D(t, coord);
        
		//If we're over the surface, preserves the color
		if (x==0 && y==0 && samp.a>=1.0)
		{
		    return samp;
		}
		//Encode the offset (-0.5 to +0.5)
		vec2 tex_off = (samp.rg - CENTER) * vec2(samp.a<1.0) + off / RANGE;
		//Compute offset distance (inverted)
		float tex_dist = length(tex_off); 
    	
		//Check for the closest
		if (dist > tex_dist && (!first || samp.a>=1.0))
		{
			//Store texel offset
		    encode.rg = tex_off + CENTER;
			//Store the closest distance
			dist = tex_dist;
			encode.a = 1.0 - tex_dist*3.0;
		}
	}
	return encode;
}

You can download my full example from GitHub.

Conclusion

To summarize, the if you need a distance field for complex shapes, this is the algorithm you need. It’s relatively cheap and allows you to do thicker outlines, glow effects, soft shadows, and many more things. Hopefully, this can get you started. If you do something cool with it, feel free to tweet at me! I love see all your projects. Thanks!

Have a great weekend!