Task 2 of 6

One Pass, One Stride

Brute force cost 16 distance tests per cell, and it would cost 16,000 for 16,000 seeds. Jump flooding never looks at the seed list at all. It looks at nine cells: itself, and eight neighbours at offset ±k — the corners and edges of a square of side 2k. Each of those nine already carries a seed (or -1). Measure every carried seed from here, keep the nearest, write it down. That is the entire algorithm.

Notice the shape of it: every thread reads nine cells and writes only its own. Nothing is ever pushed outwards to a neighbour. That is the course's gather formulation — the one gpu.js forces on you because it has no scatter — and jump flooding is the cleanest example of it there is, because the obvious way to describe the algorithm ("each seed spreads outwards") is scatter, and the way you actually write it is the exact inverse.

Two traps live in that paragraph. The distance is measured from this pixel to the neighbour's seed, never from the neighbour to its own seed. And the neighbour at dx = dy = 0 is you: keeping what you already had is one of the nine cases, not a special one.

nine cells, and one of them is you — which is how a cell keeps what it already had — A lattice of grid cells with nine marked: the thread's own cell at the centre and eight neighbours k cells away in each direction, forming the corners and edge midpoints of a square of side 2k.

Goal: write flood — nine candidates at stride k, keep the one whose seed is nearest to this pixel — and run it once at k = 64.

Requirements

Visit the nine offsets dx, dy ∈ {−1, 0, 1}, each scaled by k
Skip a candidate that falls off the grid, and one holding -1
Unpack each candidate's id and measure that seed from this.thread.x/y
Return the packed id of the nearest — or -1 if no candidate had one

Hint 1 — the nine candidates

Two nested loops, each running −1, 0, 1. The offset is scaled by the stride:

const nx = x + dx * k;
const ny = y + dy * k;

At k = 64 that reaches 64 cells away in each direction; at k = 1 it is the ordinary 3×3 neighbourhood.

Hint 2 — unpacking a candidate

id = sy * n + sx comes apart the way it went together:

const sy = Math.floor(id / this.constants.n);
const sx = id - sy * this.constants.n;
const d = (sx - x) * (sx - x) + (sy - y) * (sy - y);

x and y in that last line are this thread's coordinates — not nx and ny.

Hint 3 — the guards

Two of them, nested. First that the neighbour exists — nx >= 0 && nx < this.constants.n and the same for ny — and then that it carries something, id >= 0. Start bestD larger than any distance on the grid so the first real candidate always wins.

Same idea elsewhere

A fixed nine-tap stencil with a runtime stride is what every platform's jump-flood implementation looks like: a WebGPU compute pass sampling a seed texture at ±k, a CUDA kernel doing the same over global memory, a Metal fragment shader with k as a push constant. Nothing about it needs atomics, shared memory or scatter — which is precisely why it ports to anything with a texture unit.

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.