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 by Rong Guodong at an ACM symposium in 2006.¹

The JFA has desirable attributes in GPU computation, notably for its efficient performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.¹

The JFA original formulation is simple to implement.

Take an ${\displaystyle N\times N}$ grid of pixels² (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 ${\displaystyle k\in \{{\tfrac {N}{2}},{\tfrac {N}{4}},\dots ,1\}}$, run one iteration of the JFA:

Iterate over every pixel ${\displaystyle p}$ at ${\displaystyle (x,y)}$.

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

if ${\displaystyle p}$ is undefined and ${\displaystyle q}$ is colored, change ${\displaystyle p}$'s color to ${\displaystyle q}$'s

if ${\displaystyle p}$ is colored and ${\displaystyle q}$ is colored, if ${\displaystyle \mathrm {dist} (p,s)>\mathrm {dist} (p,s')}$ where ${\displaystyle s}$ and ${\displaystyle s'}$ are the seed pixels for ${\displaystyle p}$ and ${\displaystyle q}$, respectively, then change ${\displaystyle p}$'s color to ${\displaystyle 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 ${\displaystyle 9\log _{2}(N)}$ times over each pixel, for an overall computational complexity of ${\displaystyle O(N^{2}\log _{2}(N))}$.

Some variants of JFA are:

• Additional pass at the end: JFA+1 has one additional pass with step size of 1, i.e. the step sizes are N/2, N/4, ..., 1, 1; JFA+2 has two additional passes with step sizes of 2 and 1, i.e. the step sizes are N/2, N/4, ..., 1, 2, 1; JFA${\displaystyle ^{2}}$ has ${\displaystyle \log _{2}(N)}$ additional passes, i.e. the step sizes are N/2, N/4, ..., 1, N/2, N/4, ..., 1. JFA+1 has much fewer errors than JFA, and JFA+2 has even fewer errors.¹

• Additional pass at the beginning: 1+JFA has one additional pass with step size of 1, i.e. the step sizes are 1, N/2, N/4, ..., 1. 1+JFA has very low error rate (similar to JFA+2) and the same performance as JFA+1.³
• Half resolution: This variant runs normal JFA at a half resolution, and enlarge the result into the original resolution and run one additional pass with step size of 1. Because most of the passes has only half resolution, the speed of this variant is much faster than the full resolution JFA.³
• Randomized variants (JFA+ and JFA*): Introduced by Maciej A. Czyzewski in 2019, these variants modify the step size, sampling directions, and initial grid state to achieve faster convergence.⁴
  • JFA+ utilizes a pre-filled random noise mask. By treating empty pixels as random seeds initially, the algorithm mimics path compression in disjoint-set data structures. This passive grouping accelerates convergence, allowing the algorithm to terminate early and reducing the required steps to roughly ${\displaystyle \log _{4}(N)}$ while maintaining the standard ${\displaystyle N/2^{i}}$ step sequence.
  • JFA* (JFA-star) shifts the time complexity dependency from the grid resolution (${\displaystyle N}$) to the total number of initial seeds (${\displaystyle n}$). It adjusts the step sequence to base-3 (${\displaystyle N/3^{i}}$) and replaces the 8-way fixed square sampling with a 12-way circular sampling. This circular sampling is designed to eliminate disconnected "wedge artifacts"—a known flaw in the standard JFA where narrow Voronoi cells can "steal" a center pixel without including neighboring pixels, causing them to appear visually disconnected.¹ Combined with the noise mask, the loop terminates early based on the iterated logarithm, converging in ${\displaystyle \log ^{*}(n)}$ steps followed by one final pass with a step size of 1. While empirically faster, formal proof of its absolute correctness remains open.

Numerous variants of the JFA modify the step sequences or sampling mechanics to trade between execution speed and error rates. The table below assumes an ${\displaystyle N\times N}$ grid and ${\displaystyle n}$ initial seeds.

Jump Flooding Algorithm Variants

Variant	Step Sequence	Total Steps	Characteristics
JFA (2006)	${\displaystyle N/2,N/4,\dots ,1}$	${\displaystyle \log _{2}(N)}$	Baseline 8-way sampling.1
JFA+1	${\displaystyle N/2,\dots ,1,1}$	${\displaystyle \log _{2}(N)+1}$	One additional pass. Much fewer errors than standard JFA.1
JFA+2	${\displaystyle N/2,\dots ,1,2,1}$	${\displaystyle \log _{2}(N)+2}$	Two additional passes. Even fewer errors than JFA+1.1
1+JFA	${\displaystyle 1,N/2,\dots ,1}$	${\displaystyle \log _{2}(N)+1}$	Initial pass added. Very low error rate (similar to JFA+2) with speed of JFA+1.3
Half-res	${\displaystyle (N/4,\dots ,1)\to 1}$	${\displaystyle \approx \log _{2}(N)}$	Runs at half resolution, then enlarges with one final pass. Execution speed is significantly faster because the grid contains 75% fewer pixels per pass.3
JFA+ (2019)	${\displaystyle N/2^{i}}$	${\displaystyle \approx \log _{4}(N)}$	Injects a random noise mask to pre-fill the grid, accelerating convergence and allowing early termination.4
JFA* (2019)	${\displaystyle N/3^{i}\dots ,1}$	${\displaystyle \log ^{*}(n)+1}$	Scales by seed count (${\displaystyle n}$). Uses base-3 steps, 12-way circular sampling to fix wedge artifacts, early termination, and a final step size of 1. Correctness unproven.4

Because JFA* (JFA-star) scales with the number of seeds rather than the grid resolution, it requires significantly fewer passes for sparse datasets. For example, generating a Voronoi diagram on a 720×720 grid with 2,000 seeds requires roughly 10 passes using standard JFA, but only 4 passes using JFA*.

Convergence steps for a 720×720 grid.

JFA (Standard): Requires ~10 steps.

JFA* (Randomized): Converges in just 4 steps for 2,000 seeds due to ${\displaystyle \log ^{*}n}$ scaling.

The jump flooding algorithm and its variants may be used for calculating Voronoi maps¹³ and centroidal Voronoi tessellations (CVT),⁵ 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.¹¹

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

In the computer vision domain, the JFA has inspired new belief propagation algorithms to accelerate the solution of a variety of problems.¹³¹⁴