The jump flooding algorithm (JFA) is a
flooding algorithm {{Short description, Class of algorithms
A flooding algorithm is an algorithm for distributing material to every part of a graph. The name derives from the concept of inundation by a flood.
Flooding algorithms are used in computer networking and g ...
used in the construction of
Voronoi diagram
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
s and
distance transforms. The JFA was introduced at an
ACM symposium in 2006.
The JFA has desirable attributes in
GPU
A graphics processing unit (GPU) is a specialized electronic circuit designed to manipulate and alter memory to accelerate the creation of images in a frame buffer intended for output to a display device. GPUs are used in embedded systems, mobil ...
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 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 , run one iteration of the JFA:
:Iterate over every pixel at .
::For each neighbor at where :
:::if is undefined and is colored, change 's color to 's
:::if is colored and is colored, if where and are the seed pixels for and , respectively, then change 's color to '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 times over each pixel, for an overall computational complexity of .
Variants
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 has 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.
Uses
The jump flooding algorithm and its variants may be used for calculating Voronoi maps and centroidal Voronoi tessellations (CVT), generating distance field
A distance transform, also known as distance map or distance field, is a derived representation of a digital image. The choice of the term depends on the point of view on the object in question: whether the initial image is transformed into another ...
s, point-cloud rendering, feature matching, the computation of power diagram
In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional Dirichlet tesselation, is a partition of the Euclidean plane into polygonal cells defined from ...
s, and soft shadow rendering. The grand strategy game developer Paradox Interactive
Paradox Interactive AB is a video game publisher based in Stockholm, Sweden. The company started out as the video game division of Target Games and then Paradox Entertainment (now Cabinet Entertainment) before being spun out into an independen ...
uses the JFA to render borders between countries and provinces.
Further developments
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
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
domain, the JFA has inspired new belief propagation
A belief is an attitude that something is the case, or that some proposition is true. In epistemology, philosophers use the term "belief" to refer to attitudes about the world which can be either true or false. To believe something is to take i ...
algorithms to accelerate the solution of a variety of problems.
References
{{CCBYSASource
, sourcepath = https://computergraphics.stackexchange.com/questions/2102/is-jump-flood-algorithm-separable
, sourcearticle = Is Jump Flood Algorithm Separable?
, revision = 0
, author(s)
alan-wolfe
trichoplax
at Stack Exchange
Flooding algorithms