Ever wondered how the paint bucket in Photoshop or Microsoft Paint works? In very old versions of Paint you could see that it was performing a breath-first search. Slowly expanding at its edge. But modern implementations fill the space almost instantly. How is that possible?
Let's first define what we are doing. Place a few coloured seed cells on a grid; every other cell wants to know one thing: which seed is closest? The answer to this question is very useful.
Idea 1: Brute Force
The plan is simple: for each pixel just check every other pixel, determine whether it is a seed and keep track of which seed is closest.
You can see that this method is extremely slow and only gets slower when you increase the grid size. There must be a smarter way
Idea 2: Neighbours
What if pixels just talked to their 8-connected neighbours? Each one starts out knowing only whether it's a seed, then every shader pass it turns to its 8 neighbours: the closest seed I know about is over there. Cool, that beats mine, thanks. Now we don't have to do as many queries, and the closest seed propagates outwards like BFS.
It's a massive win over brute force. It's also still painfully slow: news travels one pixel per pass, so a seed on one edge takes the full width of the grid to reach the other. But what if we didn't move one pixel at a time?
Idea 3. The Jump Flood Algorithm
Pass one: every pixel ignores its immediate neighbours and looks half the grid away, in all eight directions, asking each pixel: who's your nearest seed? If the response is anything closer than what it already knows, it updates. Pass two, the jump halves. Pass three, halves again. All the way down to one.
After just log₂(width) passes, every pixel knows its nearest seed. That's five passes at 32 across, seven at 128. These are numbers that are viable for running on a GPU in real-time.
You can inspect what is happening by stepping through and hovering over the grid. The yellow squares are the eight cells being sampled.
4. What a pixel knows
Every method so far computes the exact same thing: for each pixel, it stores the coordinates of its nearest seed in UV space in its RG channels, the distance in its B channel and the ID of the seed in the alpha channel. You can use the information that results after all passes in several ways.
4.1 Voronoi
After the jump-flood algorithm is done simply do a lookup using the value in the alpha channel. The result shows you which pixel ID is closest to each pixel.
4.2 Distance
Use the B channel to show how far the nearest seed is. You can use this information for example as a attraction or repelling force multiplier for particles.
4.3 UV
The R and G channel store the coordinates in normalised space of the nearest seed.
4.4 Direction
The UV coordinates alone aren't so interesting, but using the pixel's own UV coordinates you can infer something interesting: the direction. Simply subtract the seed's UV coordinate (stored in RG channels) from the local UV coordinate and normalise. normalize(UV − RG) Here I mapped the angle to a hue. But you can use this information to guide particles towards a seed.
5. JFA+1
JFA isn't perfect. Sometimes a pixel changes its mind on who is closer, but the JFA pass that could pass it to the relevant pixel can't catch up. Usually there's just one or a few pixels on the border that are incorrect.
The fix is really easy: run one more pass at stride 1. We call this JFA + 1. Other options are to run a single pass at stride 1 at the start. We call this 1 + JFA.
I hope you enjoyed this interactive page about JFA. If you'd rather sit back and watch: here's a YouTube video I made about JFA: