# What a Cell Has to Carry

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

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

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

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

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

## Starter code

```js
// 16 seeds, 16,384 cells, one thread each. Brute force — for now.
const gpu = new GPU({ mode });

const nearest = gpu.createKernel(function (seedX, seedY) {
  const x = this.thread.x;
  const y = this.thread.y;
  let bestD = this.constants.n * this.constants.n * 2;
  for (let i = 0; i < this.constants.sites; i++) {
    const dx = seedX[i] - x;
    const dy = seedY[i] - y;
    const d = dx * dx + dy * dy;
    if (d < bestD) {
      bestD = d;
    }
  }
  // TODO: a distance is a dead end — the next pass cannot re-measure from it.
  // Remember WHICH seed won, and return its packed position instead:
  //   seedY[best] * this.constants.n + seedX[best]
  return Math.sqrt(bestD);
}, { output: [128, 128], constants: { n: 128, sites: 16 } });

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 } });

const cells = await nearest(seedX, seedY);
await paint(cells);
render(paint.canvas);
console.log('cell (0, 0) carries', cells[0][0]);
```

---

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

[Next task](https://gpu.rocks/learn/jump-flooding-a741a650/2.md)