# From Seeds to Distances

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

The finished field already *is* a distance field — you just have to ask it.
Every cell knows where its nearest seed is, so the distance to that seed is one subtraction
and one square root away, in a single extra pass with no memory of its own.

This is where carrying the position rather than the distance pays off twice over. Had the
cells accumulated distances, every pass would have compounded whatever rounding the last one
introduced. Carrying coordinates means the distance is computed **once, at the
end**, from two exact integers — so the field is as accurate as the seed assignment
is, and no more approximate than that.

## Goal

**Goal:** write `distance` — unpack each cell's seed and return
the Euclidean distance from the cell to it.

## Requirements

- One kernel, one argument: the finished `grid` of packed ids
- Unpack with `Math.floor(id / n)` then `id − sy * n`
- Return `Math.sqrt(…)` — this pass is where the square root belongs

## Hint 1 — the same unpack as the flood pass

Nothing new: it is the two lines you already wrote inside the loop, applied
once.

```js
const sy = Math.floor(id / this.constants.n);
const sx = id - sy * this.constants.n;
```

## Hint 2 — the whole body

```js
return Math.sqrt((sx - x) * (sx - x) + (sy - y) * (sy - y));
```

A seed cell measures 0 from itself, which is exactly right — those are the black
pinpricks in the rendered field.

## Same idea elsewhere

Distance fields are the workhorse texture of real-time graphics: glyph rendering
(Valve's signed-distance text), outlines and glows, soft particle collision, path planning
and morphological dilation are all "threshold a distance field". Every one of them wants the
field regenerated per frame from changing input, which is why this algorithm — not the
asymptotically better sweep — is the one that ships.

## Starter code

```js
// The seed field IS a distance field. One pass to read it out.
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;
  for (let dy = -1; dy <= 1; dy++) {
    for (let dx = -1; dx <= 1; dx++) {
      const nx = x + dx * k;
      const ny = y + dy * k;
      if (nx >= 0 && nx < this.constants.n && ny >= 0 && ny < this.constants.n) {
        const id = grid[ny][nx];
        if (id >= 0) {
          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);
          if (d < bestD) {
            bestD = d;
            best = id;
          }
        }
      }
    }
  }
  return best;
}, { output: [128, 128], constants: { n: 128 } });

const distance = gpu.createKernel(function (grid) {
  const x = this.thread.x;
  const y = this.thread.y;
  const id = grid[y][x];
  // TODO: unpack id into (sx, sy) and return the distance from (x, y) to it.
  return id;
}, { output: [128, 128], constants: { n: 128 } });

const shade = gpu.createKernel(function (field) {
  const t = Math.min(1, field[this.thread.y][this.thread.x] / this.constants.scale);
  this.color(t, t, t, 1);
}, { output: [128, 128], graphical: true, constants: { scale: 56 } });

let grid = seedGrid;
for (let k = 64; k >= 1; k = k / 2) grid = await flood(grid, k);

const field = await distance(grid);
await shade(field);
render(shade.canvas);

plot(field[64], { title: 'distance to the nearest seed, along row 64' });
console.log('distance at (0, 0):', field[0][0]);
```

---

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

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