# One Pass, One Stride

*Task 2 of 6 · [Jump Flooding: Voronoi in log n Passes](https://gpu.rocks/learn/jump-flooding-a741a650.md) · GPU.js Learn*

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.

## Figures

- **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

**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:

```js
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:

```js
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.

## Starter code

```js
// The whole algorithm is nine reads. This is one pass of it.
const gpu = new GPU({ mode });

const flood = gpu.createKernel(function (grid, k) {
  const x = this.thread.x;
  const y = this.thread.y;
  let best = -1;
  let bestD = this.constants.n * this.constants.n * 2;
  // TODO: loop dy and dx over -1, 0, 1.
  //   nx = x + dx * k, ny = y + dy * k
  //   skip it unless it is on the grid AND grid[ny][nx] >= 0
  //   unpack that id, measure the seed FROM THIS PIXEL, keep the nearest
  return best;
}, { output: [128, 128], constants: { n: 128 } });

const paint = gpu.createKernel(function (grid) {
  const id = grid[this.thread.y][this.thread.x];
  let r = 0.11;
  let g = 0.12;
  let b = 0.17;
  if (id >= 0) {
    const sy = Math.floor(id / this.constants.n);
    const sx = id - sy * this.constants.n;
    r = 0.22 + 0.68 * (sx / this.constants.n);
    g = 0.30 + 0.55 * (sy / this.constants.n);
    b = 0.88 - 0.6 * (sx / this.constants.n);
  }
  this.color(r, g, b, 1);
}, { output: [128, 128], graphical: true, constants: { n: 128 } });

await paint(seedGrid);
render(paint.canvas);

const once = await flood(seedGrid, 64);
await paint(once);
render(paint.canvas);

let filled = 0;
for (let y = 0; y < 128; y++) {
  for (let x = 0; x < 128; x++) if (once[y][x] >= 0) filled++;
}
console.log('cells holding a seed: 16 ->', filled);
```

---

Interactive version: https://gpu.rocks/learn/jump-flooding-a741a650/2

[Previous task](https://gpu.rocks/learn/jump-flooding-a741a650/1.md) · [Next task](https://gpu.rocks/learn/jump-flooding-a741a650/3.md)