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 desirable attributes in GPU computation, notably constant-time performance. However, it does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.

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.

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

Iterate over every pixel $p$ at $(x,y)$.

For each neighbor $q$ at $(x+i,y+j)$ where $i,j\in \{-k,0,k\}$:

if $p$ is undefined and $q$ is colored, change $p$'s color to $q$'s

if $p$ is colored and $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.

Note that pixels may change color more than once in each step, and that the JFA does not specify a method for resolving cases where distances are equal, therefore the last-checked pixel's color is used above.

The JFA finishes after evaluating the last pixel in the last step size. Regardless of the content of the initial data, the innermost loop runs a total of $9\log _{2}(N)$ times over each pixel, for an overall computational complexity of $O(N^{2}\log(N))$

Uses

The jump flooding algorithm and its variants may be used for calculating Voronoi maps generating distance fields, point-cloud rendering, feature matching, the computation of power diagrams, and soft shadow rendering. The grand strategy game developer Paradox Interactive uses the JFA to render borders between countries and provinces.

Further developments

The JFA has inspired the developement of numerous similar algorithms. Some have well-defined error properties which make them useful for scientific computing.

References

As of this edit, this article uses content from "Is Jump Flood Algorithm Separable?", authored by alan-wolfe, trichoplax at Stack Exchange, which is licensed in a way that permits reuse under the Creative Commons Attribution-ShareAlike 3.0 Unported License, but not under the GFDL. All relevant terms must be followed.