# A Signed Distance Field From a Bitmap

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

Seeds do not have to be dots. Seed the flood with *every pixel inside a
shape* and the finished field answers "how far is the nearest inside pixel?" — which is
0 inside and grows outside. Seed it with every pixel *outside* and you get the mirror
image. Subtract one from the other and the result is a **signed distance field**:
negative inside, zero on the boundary, positive outside.

*Ray-Marched Metaballs* marches an SDF that is defined **analytically**
— a sphere is `length(p) − r`, and the whole scene is a formula. This is the other
half of that story: here you **manufacture** one from an arbitrary bitmap.
Nothing about a five-pointed star wants to be a formula, and it does not have to be. Two
ladders and a subtraction, and it is marchable, glowable, outlineable — exactly like the
analytic kind.

The bookkeeping is the interesting part. `dIn` is 0 for every inside pixel and
positive outside; `dOut` is 0 for every outside pixel and positive inside. So
`dIn − dOut` is signed automatically, with no test on the mask at all — one of
the two terms is always zero.

## Figures

- **one term is always zero, so the subtraction is the entire sign logic** — Three panels of the same star: the field flooded from the inside pixels (zero inside), minus the field flooded from the outside pixels (zero outside), equals a signed field that is negative inside and positive outside.

## Goal

**Goal:** write `seedWhere(mask, want)` — seed the cells where
the mask equals `want` — and `combine(dIn, dOut)`, which returns
`dIn − dOut`.

## Requirements

- `seedWhere` returns the packed id where `mask[y][x] === want`, else `-1`
- Flood once with `want = 1` and once with `want = 0`, awaiting each ladder
- `combine` returns `dIn − dOut` — negative inside, positive outside

## Hint 1 — seeding a region

The same packed id as ever, gated on the mask:

```js
let id = -1;
if (mask[y][x] === want) id = y * this.constants.n + x;
return id;
```

The `want` argument is what lets one kernel seed both sides.

## Hint 2 — two ladders, one driver

`ladder()` takes any seeded field, so it runs twice unchanged:

```js
const dIn = await distance(await ladder(await seedWhere(mask, 1)));
const dOut = await distance(await ladder(await seedWhere(mask, 0)));
```

Fourteen passes in total, and every one of them awaited in order.

## Hint 3 — why no sign test is needed

Inside a pixel of the shape, the nearest inside pixel is itself, so
`dIn = 0` and the answer is `−dOut`. Outside,
`dOut = 0` and the answer is `+dIn`. The subtraction is the whole
sign logic.

## Same idea elsewhere

Manufacturing an SDF from a raster is production practice: Valve's distance-field
glyphs, Unity and Godot's SDF text, mesh voxelisation into a 3D distance field for collision
and soft shadows — all of it is "flood a bitmap, subtract two fields". The measurement is a
pixel-centre one, so this field is quantised to the raster it came from; the usual fix is to
seed sub-pixel boundary positions rather than pixel centres, which changes the seeding and
nothing else about the algorithm.

## Starter code

```js
// Seed the inside. Seed the outside. Subtract. That is an SDF.
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];
  const sy = Math.floor(id / this.constants.n);
  const sx = id - sy * this.constants.n;
  return Math.sqrt((sx - x) * (sx - x) + (sy - y) * (sy - y));
}, { output: [128, 128], constants: { n: 128 } });

const seedWhere = gpu.createKernel(function (mask, want) {
  const x = this.thread.x;
  const y = this.thread.y;
  // TODO: return the packed id y * n + x where mask[y][x] === want, else -1.
  return -1;
}, { output: [128, 128], constants: { n: 128 } });

const combine = gpu.createKernel(function (dIn, dOut) {
  // TODO: return dIn - dOut for this cell — negative inside, positive outside.
  return dIn[this.thread.y][this.thread.x];
}, { output: [128, 128] });

const paintSdf = gpu.createKernel(function (field) {
  const s = field[this.thread.y][this.thread.x];
  const band = 0.55 + 0.45 * Math.cos(s * 0.9);
  const t = Math.min(1, Math.abs(s) / 26);
  let r = 0.22 + 0.72 * t * band;
  let g = 0.44 + 0.26 * t * band;
  let b = 0.24 + 0.16 * t * band;
  if (s < 0) {
    r = 0.14 + 0.20 * t * band;
    g = 0.42 + 0.30 * t * band;
    b = 0.55 + 0.44 * t * band;
  }
  this.color(r, g, b, 1);
}, { output: [128, 128], graphical: true });

async function ladder(seeded) {
  let g = seeded;
  for (let k = 64; k >= 1; k = k / 2) g = await flood(g, k);
  return g;
}

const dIn = await distance(await ladder(await seedWhere(mask, 1)));
const dOut = await distance(await ladder(await seedWhere(mask, 0)));
const sdf = await combine(dIn, dOut);

await paintSdf(sdf);
render(paintSdf.canvas);
console.log('sdf at the centre:', sdf[64][64], '- at a corner:', sdf[0][0]);
```

---

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

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