Jump flooding algorithm

The jump flooding algorithm (JFA) is a flooding algorithm used in the construction of voronoi diagrams and distance transforms. The JFA was introduced at an ACM symposium in 2006.

The JFA has desireable attributes in GPU computation, notably constant-time performance.

Grand strategy game developer Paradox Interactive uses the JFA to render borders between countries and provinces.

Implementation

The JFA original formulation is simple to implement.

Take an $N\times N$ grid (like an image or texture). All pixels will start with an "undefined" color unless it is a uniquely-colored "seed" pixel. As the JFA progresses, each "undefined" pixel will be filled with a color corresponding to that of a "seed" pixel's.

For each step size $k\in \{{\frac {N}{2}},{\frac {N}{4}},\dots ,1\}$, run one iteration of the JFA:

1. Iterate over every pixel $p$ at $(x,y)$.
2. Query each neighbor at $(x+i,y+j)$ where $i,j\in \{-k,0,k\}$.
3. If:
   1. $p$ is "undefined" and a neighbor $q$ is colored, change $p$'s color to $q$'s
   2. $p$ is colored and a neighbor $q$ is colored, if $dist(p,s)>dist(p,s')$ where $s$ and $s'$ are the seed pixels for $p$ and $q$, respectively, then change $p$'s color to $q$'s.

The JFA finishes after evaluating the last pixel in the last step size. It walks a total of $log(N)$ times over each pixel.