# Payoff: Measure the Lie

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

Jump flooding is an **approximation**. It is not "exact but for
rounding": there are seed layouts for which a cell's true nearest seed never reaches it. The
route of halving jumps the ladder counted on always exists — but a cell part-way along it
only forwards the seed it is holding at that moment, and it may be holding a different one
that looked nearer when the pass ran. The chain breaks in the middle. Every honest
description of this algorithm says so, and the way to believe it is to count.

Careful about what "wrong" means, though. Two seeds can be exactly the same distance
away, and then *both* answers are right — comparing the ids the two methods chose
would report roughly twice as many failures as there are. A cell is wrong only when the seed
it holds is **strictly farther** than the true nearest one.

The layout here is 24 seeds chosen to make the flaw visible. It is not typical: across
200 random 24-seed layouts on this grid, 95 came out perfect and the average was 1.4 wrong
cells out of 16,384 — 0.009%. This one manages 67. The standard patch, one extra pass at
stride 1 ("JFA+1"), takes it to 55 — better, and still not exact. If you need exact, you
need a different algorithm; what you get here is a fast answer with a bounded, measurable
error, and for a glow or an outline or a shatter pattern that is the right trade.

## Goal

**Goal:** write `worse(jfa, truth)` — 1 where the flooded seed
is strictly farther than the true nearest one, 0 otherwise — and `countOnes` to
total it.

## Requirements

- Unpack both ids and compare **squared** distances — whole numbers, so ties are exact
- Equal distance is **not** an error: only strictly farther counts
- A cell still holding `-1` counts as wrong
- `countOnes` sums the field in plain JavaScript

## Hint 1 — two unpacks, one comparison

Unpack `jfa[y][x]` and `truth[y][x]` the usual way, measure
both seeds from this pixel, and compare the squared distances. Strictly greater:

```js
let bad = 0;
if (dJfa > dTruth) bad = 1;
return bad;
```

## Hint 2 — the unassigned case

An id of `-1` unpacks to nonsense, so give it a distance larger than
anything on the grid before the comparison — the same
`n * n * 2` the flood pass starts from.

## Hint 3 — counting in JavaScript

The field is 0s and 1s, so the count is the sum:

```js
let n = 0;
for (let y = 0; y < 128; y++) {
  for (let x = 0; x < 128; x++) n += grid[y][x];
}
return n;
```

## Same idea elsewhere

"Asymptotically worse, measurably approximate, and shipped anyway" is a recurring GPU
story — screen-space ambient occlusion approximates an integral nobody can afford, temporal
upscalers approximate frames that were never rendered, and JFA approximates a transform that
has an exact linear-time algorithm nobody can parallelise. What makes each of them
defensible is exactly this task: somebody counted the error, published the number, and
decided it was small enough. An approximation whose error you have not measured is not an
engineering decision.

## Starter code

```js
// How often is the fast answer the wrong answer? Count 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;
  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 exact = gpu.createKernel(function (seedX, seedY) {
  const x = this.thread.x;
  const y = this.thread.y;
  let best = -1;
  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;
      best = seedY[i] * this.constants.n + seedX[i];
    }
  }
  return best;
}, { output: [128, 128], constants: { n: 128, sites: 24 } });

const worse = gpu.createKernel(function (jfa, truth) {
  const x = this.thread.x;
  const y = this.thread.y;
  // TODO: unpack both ids, measure both seeds from (x, y), and return 1 only
  // when the flooded one is STRICTLY farther. A tie is not an error.
  // An id of -1 is farther than anything: n * n * 2.
  return 0;
}, { output: [128, 128], constants: { n: 128 } });

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

function countOnes(grid) {
  // TODO: total the 128x128 field of 0s and 1s and return the count.
  return 0;
}

const truth = await exact(seedX, seedY);
let grid = seedGrid;
const wrong = [countOnes(await worse(grid, truth))];
for (let k = 64; k >= 1; k = k / 2) {
  grid = await flood(grid, k);
  wrong.push(countOnes(await worse(grid, truth)));
}

plot(wrong, { title: 'cells not yet holding their nearest seed', log: true });
console.log('after the ladder:', wrong[wrong.length - 1], 'of 16384 cells are wrong');

const patched = await flood(grid, 1);
console.log('after one extra stride-1 pass:', countOnes(await worse(patched, truth)));

await paintErr(grid, await worse(grid, truth));
render(paintErr.canvas);
```

---

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

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