Task 3 of 6

The Halving Ladder

One pass at k = 64 moved 16 seeds into 64 cells. Useless on its own — and then you halve the stride and run it again. And again. 64, 32, 16, 8, 4, 2, 1: seven passes on a 128-wide grid, log₂(n) of them, and the diagram is finished. Seven is enough because any distance up to 127 is a sum of those powers of two — 127 = 64 + 32 + 16 + 8 + 4 + 2 + 1, and a shorter one simply drops the terms it does not need — so every seed has a route of jumps to every cell. (Having a route and arriving are not quite the same thing, which is what the last task is for.) It is the same halving ladder Reductions climbs, run backwards.

The loop lives in JavaScript; the work stays on the GPU. Seven launches instead of a pair of scans, and each launch moves all 16,384 cells at once. Count the work honestly: n log n against the exact transform's n. Jump flooding loses that comparison and wins the race, because the exact transform spends its n walking chains — 128 cells deep along a row, then 128 deep down a column — while jump flooding spends its n log n as seven steps of 16,384 independent ones.

Render inside the loop and you get the best view in this course: a frame scrubber you can drag, watching the diagram arrive in seven jumps — sparse dust, then blocks, then the boundaries snapping straight on the last pass.

105 = 64 + 32 + 8 + 1 — no distance on a 128-wide grid needs an eighth pass — Seven stacked rows, one per pass, with the stride halving from 64 to 1. The bar reaches 64, then 96, stalls at 16, reaches 104 at stride 8, stalls at 4 and 2, and arrives at 105 on the final stride-1 pass.

Goal: drive the ladder — start k at 64, halve it to 1, feed each pass's output into the next, and render() every pass.

Requirements

Loop k = 64, 32, 16, 8, 4, 2, 1 — halve, never double
Each pass floods the previous pass's output, not seedGrid
await each pass before launching the next
Paint and render() inside the loop, and record countFilled

Hint 1 — the loop

Halving is just the update expression:

for (let k = 64; k >= 1; k = k / 2) {
  // …
}

Seven iterations, and the last one is k = 1.

Hint 2 — carrying the field forward

grid has to be reassigned, or every pass re-floods the same sparse starting field:

grid = await flood(grid, k);

Never Promise.all here — pass k + 1 reads pass k's output, so the ladder is sequential by construction.

Hint 3 — the whole body

for (let k = 64; k >= 1; k = k / 2) {
  grid = await flood(grid, k);
  filled.push(countFilled(grid));
  await paint(grid);
  render(paint.canvas);
}

Same idea elsewhere

Driving a shrinking sequence of dispatches from the host is the standard shape of every multi-pass GPU algorithm: CUDA launches a kernel per rung, WebGPU records repeated dispatches ping-ponging between two textures, Metal encodes one compute pass each. The stride schedule is data the host owns; the parallelism is what the device owns. Real implementations ping-pong between two buffers rather than reading back — here each pass already hands JavaScript a plain array, which is what makes countFilled and the per-pass render free.

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.