Task 6 of 6

Payoff: Measure the Lie

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

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:

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.

All tasks in Jump Flooding: Voronoi in log n Passes

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.