Computer Graphics
Jump Flooding: Voronoi Diagrams on the GPU
Jump Flooding is a GPU algorithm that computes a whole Voronoi diagram — the map that colours every pixel by which seed it is closest to — in only log₂(N) parallel passes instead of the hundreds a spreading wavefront would need. Each seed pixel begins knowing its own coordinates and everyone else is blank; then, in passes whose reach halves each time (N/2, N/4, …, 1), every pixel looks at eight neighbours a fixed distance away and adopts the closest seed any of them has heard of.
The remarkable part is the schedule: the big early jumps splatter seed positions across the entire image in a handful of steps, and the shrinking later jumps sharpen the cell boundaries. A 1024×1024 diagram falls out in ten passes, each of which updates all million-plus pixels at once — which is why JFA underlies real‑time signed distance fields, Voronoi textures, and GPU morphology.
- Passes⌈log₂ N⌉ (10 for 1024²)
- Total workO(N² log N)
- Per passO(1)/pixel, 8+1 samples
- Step sizesN/2, N/4, …, 1
- OriginRong & Tan, I3D 2006
- Error<1% pixels; ~0 with JFA+1
Interactive visualization
Press play, or step through manually. The visualization is yours to drive — try it before reading on.
Watch the 60-second explainer
A condensed visual walkthrough — narrated, captioned, under a minute.
The mechanism: seeds that jump in halving steps
Fix a grid of N×N pixels. Every pixel holds one field: the coordinates of the nearest seed it currently knows about, or a sentinel meaning “none yet.” Seed pixels initialise this field to their own position; all others start empty. The algorithm then runs a sequence of passes with a shrinking step length k, starting at k = N/2 and halving to N/4, N/8, …, down to 1.
In each pass, every pixel p reads the eight neighbours at offsets (±k, 0), (0, ±k) and (±k, ±k), together with its own current value — nine candidates in all. For each candidate that carries a seed s, p computes the ordinary Euclidean distance ‖p − s‖ and, if that seed is nearer than the one p already stores, p adopts it. The rule is pure keep-the-nearest: a pass can only replace a stored seed with a strictly closer one.
All pixels apply this rule simultaneously against the state from the previous pass, so the passes ping‑pong between two textures: read texture A, write texture B, swap. The big early jumps (k = 512, 256…) fling a seed’s coordinates clear across the image in a couple of steps; the small late jumps (k = 4, 2, 1) let neighbouring cells contest the exact boundary pixel by pixel. When the passes finish, each pixel names its nearest seed — that labelling is the Voronoi diagram, and the stored distance is the distance transform.
Why log N passes are enough
The schedule is not a heuristic; it is the same trick as pointer jumping in parallel list-ranking. Consider a single seed s and any pixel p at offset (dx, dy), where |dx|, |dy| < N. Write |dx| in binary. Because the step lengths are exactly the powers of two N/2, N/4, …, 1, and each pass can move information by ±k independently in x and y through the eight-neighbour stencil, the jumps compose to cover any offset up to N — just as any integer below N is a sum of distinct powers of two. So after ⌈log₂ N⌉ passes, s has reached p. With one seed there is no competitor, so JFA is provably exact in that case.
Concretely, a 1024×1024 image needs ten passes; 4096×4096 needs twelve. Contrast this with a wavefront distance transform — a BFS front, or a Danielsson-style raster sweep — where seed information advances one pixel per pass and the image therefore takes O(N) passes to fill. Trading O(N) passes for O(log N) is the whole game: on a 4K grid that is a dozen passes instead of thousands, and every pass is a single fully-parallel shader over the framebuffer.
The invariant, and why it is only approximate
JFA maintains a clean monotonicity invariant: the distance a pixel stores never increases, because a pass only ever swaps in a strictly closer seed. Every stored distance is thus an upper bound on the true distance, tightening pass by pass. What the invariant does not guarantee is that the bound reaches the true minimum for every pixel — and that is where JFA becomes approximate.
The failure mode is a flooding shadow. For seed s to reach pixel p, some intermediate neighbour q must be holding s at the exact pass whose step lands on p. But q is contested too: at that moment q may store a different, farther seed and only learn about s later, after the jump that would have relayed it to p has already passed. p then settles for a slightly-too-far seed. In practice these errors are rare and tiny — on the order of a few tenths of a percent of pixels wrong, each off by only a pixel or two, concentrated near cell boundaries where seeds are nearly equidistant anyway.
Rong and Tan quantified this and offered cheap fixes, all built from extra step-1 passes:
- JFA+1 — append one final pass with k = 1. Mopping up the immediate neighbourhood eliminates most residual errors.
- 1+JFA — prepend a k = 1 pass so local seeds are settled before the big jumps fan out.
- JFA² — run the entire log N schedule twice; the second sweep repairs shadows left by the first.
Each adds only one or two passes, so the O(log N) budget is essentially untouched, while the wrong-pixel count typically drops to a handful or to zero. For most graphics uses — where the diagram feeds a soft glow or a distance field that is itself blurred — plain JFA is already indistinguishable from exact.
Complexity and the bandwidth wall
Per pass, each pixel does O(1) work: nine texture fetches and nine distance comparisons. Across ⌈log₂ N⌉ passes over N² pixels, total work is O(N² log N), independent of the number of seeds S — a crucial contrast with brute force, whose O(N²·S) blows up when thousands of seeds crowd the image. Cone rasterization (Hoff et al., SIGGRAPH 1999) draws one depth cone per seed and lets the z-buffer pick the winner — exact and elegant, but O(S) geometry that scales with seed count, whereas JFA does not care whether there are ten seeds or ten thousand.
Because every pass reads and writes the full framebuffer, JFA is firmly bandwidth-bound, not compute-bound. The working set is two textures (ping and pong), each storing a 2D seed coordinate per texel — typically two channels at 16- or 32-bit precision, since packing coordinates into 8-bit channels caps addressable resolution and injects rounding error. The nine-tap stencil has excellent locality, so the fetches hit the texture cache well; the practical cost is roughly log₂N × (framebuffer read + write). On 2006 hardware (a GeForce 7800) the original paper built megapixel Voronoi diagrams in a few milliseconds; a modern GPU does the same in well under a millisecond, comfortably inside a real-time frame. The generalisation to 3D is direct: a 26-neighbour (3×3×3) stencil over an N³ volume, still in O(log N) passes.
From Voronoi to signed distance fields
The same run yields two products. The seed labels give the Voronoi partition; the stored distances give the Euclidean distance transform. That second output is why JFA became a workhorse of real-time rendering.
- Signed distance fields (SDF). Treat a shape’s boundary pixels as seeds and JFA returns, at every pixel, the distance to the nearest edge. Flip the sign inside the shape (via a simple inside/outside test) and you have an SDF. Valve’s influential SDF text technique (Chris Green, SIGGRAPH 2007) renders crisp glyphs at any magnification from a small distance texture; JFA is a standard way to generate those fields on the GPU, and engines from Unity to bespoke UI stacks lean on it for outlines, glows, and soft shadows.
- Morphology. Dilation and erosion by radius r are just thresholds on the distance field — keep pixels within (or beyond) distance r of the boundary. One JFA pass replaces an iterative structuring-element sweep, turning O(r) morphology into a single field lookup.
- Voronoi textures and effects. Cellular noise, shattered-glass and crackle patterns, stippling, and proximity/collision queries all read straight off the diagram, recomputed every frame when seeds move.
Crucially, JFA is GPU-resident: seeds can be written by a prior shader and the diagram consumed by the next, with no round trip to the CPU. That makes dynamic seeds — moving agents, animated boundaries, painted masks — cheap, which sequential exact methods cannot match.
How it compares to exact methods, and when it wins
If you need the continuous, mathematically exact Voronoi diagram of a point set, Fortune’s sweepline is optimal at O(S log S) — but it is an inherently sequential CPU algorithm producing a graph of edges and vertices, and its cost scales with seed count, not pixels. The Voronoi diagram’s dual, the Delaunay triangulation, comes from the same family. These are the right tools when you want geometry (a mesh, exact cell adjacencies) rather than a raster.
JFA wins precisely when the target is an image, updated every frame, on hardware that is already massively parallel. It is output-insensitive to seed count, needs no data structures beyond two textures, has no branch-heavy control flow to stall the SIMT lanes, and its approximate answer is more than accurate enough for shading. The trade is exactness for latency: a few boundary pixels may be misassigned, recoverable with the JFA+1 family for one or two extra passes. When a scene has thousands of moving seeds and a millisecond budget, that trade is overwhelmingly worth it — which is why jump flooding, twenty years after Rong and Tan proposed it, is still the default way to put a Voronoi diagram or a distance field on the GPU.
| Method | Cost | Parallel | Exact? |
|---|---|---|---|
| Brute force (test all seeds) | O(N²·S) | Fully (per pixel) | Exact |
| Cone rasterization (Hoff 1999) | O(S) draws + z-test | GPU fixed-function | Exact (to raster) |
| BFS / raster wavefront (EDT) | O(N) passes | Front only | Exact |
| Fortune's sweepline | O(S log S) | No (CPU, sequential) | Exact (continuous) |
| Jump Flooding (JFA) | O(log N) passes | Fully, every pixel | Approximate |
| JFA+1 / 1+JFA / JFA² | O(log N)+1..2 passes | Fully | Near-exact |
Frequently asked questions
Why do the step sizes shrink instead of grow?
Starting large and halving is what makes O(log N) passes cover the whole image. The big early jumps carry seed coordinates across the entire grid in a couple of steps, so no region is left empty; the small late jumps then refine the exact boundary pixel by pixel. Growing the step (1, 2, 4, …) would leave far-away pixels blank for most of the run and does not give the clean binary-reachability guarantee.
Is JFA exact?
For a single seed it is provably exact. With many seeds it is approximate — typically a few tenths of a percent of pixels are assigned a seed one or two pixels too far, all near contested boundaries. Appending a step-1 pass (JFA+1), prepending one (1+JFA), or running the schedule twice (JFA²) drives the error to nearly zero for one or two extra passes.
How many passes does it take for a 1024×1024 image?
Exactly ⌈log₂ 1024⌉ = 10 passes, with step sizes 512, 256, 128, 64, 32, 16, 8, 4, 2, 1. A 4096² image needs 12. Each pass updates every pixel once in parallel, so wall-clock time scales with log of the resolution, not the resolution itself.
Does JFA slow down with more seeds?
No — its cost is O(N² log N), independent of the seed count S, because every pixel does the same fixed work regardless of how many seeds exist. That is its key advantage over brute force (O(N²·S)) and cone rasterization (O(S) draws), both of which scale with the number of seeds.
What is the difference between the Voronoi diagram and the distance transform it produces?
They are two readings of the same output. The Voronoi diagram is the label — which seed each pixel is closest to. The distance transform is the number — how far each pixel is from that nearest seed. JFA computes both in one run, and signing the distance (inside vs. outside a shape) turns the distance transform into a signed distance field.
Why is JFA good for signed distance field text?
SDF text (popularized by Valve in 2007) stores distance-to-edge instead of coverage, so glyphs stay sharp at any scale. JFA generates that distance field on the GPU in a handful of passes from the glyph's boundary pixels, making it fast enough to bake or even regenerate fields at runtime for dynamic shapes, outlines, and glow effects.