Task 1 of 6

What a Cell Has to Carry

Scatter a handful of seeds over a grid and colour every cell by whichever seed is closest. That is a Voronoi diagram, and it is one of the most useful pictures in graphics: it is a distance field, a nearest-neighbour lookup, a watershed, a shatter pattern and a texture, depending on who is asking.

A CPU builds one in O(n) in the number of pixels — Felzenszwalb's exact distance transform runs a couple of linear scans along every row, then the same down every column, and it is done. This module builds the same picture in O(n log n) and wins anyway, because each of those scans is a chain: the answer at column j is read off a running lower envelope that columns 0…j−1 built, so the exact algorithm offers one thread per row and nothing finer. Jump flooding hands all 16,384 cells to their own threads, seven times over. That is the whole reason this algorithm exists, and it is a different claim from "the GPU is faster": jump flooding does more total work than the algorithm it beats.

Start where anyone would: ask each cell to check all 16 seeds. What matters is not the loop — it is what the cell writes down. Not the distance. The seed's position, because the next pass will have to measure that seed again from a different pixel. A gpu.js cell holds one number, so the pair is packed: id = sy * 128 + sx, and -1 for "nothing yet".

Goal: make nearest return the packed position of the closest seed — seedY[best] * n + seedX[best] — rather than the distance the starter hands back.

Requirements

Loop over all this.constants.sites seeds and keep the closest
Compare squared distances — no Math.sqrt in the loop
Return the winner packed as seedY[best] * this.constants.n + seedX[best]

Hint 1 — remember the winner, not just its distance

The starter already finds the smallest bestD. Add a second variable that remembers which seed produced it, and update both together.

if (d < bestD) {
  bestD = d;
  best = i;
}

Hint 2 — packing the pair

A cell holds one number and you need two. Rows first, exactly as in grid[y][x]:

return seedY[best] * this.constants.n + seedX[best];

Unpacking it later is the same arithmetic backwards: sy = Math.floor(id / n), then sx = id - sy * n.

Same idea elsewhere

Packing a payload into the value a thread can write is universal GPGPU housekeeping — a CUDA kernel stuffs an index and a key into one uint64 so a single atomicMin carries both, and a WebGPU jump-flood pass stores its seed in an rg32float texture for the same reason. The lesson underneath is the one that transfers: a parallel algorithm's state has to be enough to continue from, not just enough to display.

All tasks in Jump Flooding: Voronoi in log n Passes

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.