# The Halving Ladder

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

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.

## Figures

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

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

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

```js
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

```js
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.

## Starter code

```js
// Seven passes. Halve the stride each time and the picture arrives.
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 paint = gpu.createKernel(function (grid) {
  const id = grid[this.thread.y][this.thread.x];
  let r = 0.11;
  let g = 0.12;
  let b = 0.17;
  if (id >= 0) {
    const sy = Math.floor(id / this.constants.n);
    const sx = id - sy * this.constants.n;
    r = 0.22 + 0.68 * (sx / this.constants.n);
    g = 0.30 + 0.55 * (sy / this.constants.n);
    b = 0.88 - 0.6 * (sx / this.constants.n);
  }
  this.color(r, g, b, 1);
}, { output: [128, 128], graphical: true, constants: { n: 128 } });

function countFilled(grid) {
  let n = 0;
  for (let y = 0; y < 128; y++) {
    for (let x = 0; x < 128; x++) if (grid[y][x] >= 0) n++;
  }
  return n;
}

let grid = seedGrid;
const filled = [countFilled(grid)];
await paint(grid);
render(paint.canvas);

// TODO: seven passes. Start k at 64 and HALVE it every time, flooding the
// CURRENT grid — then record countFilled(grid), paint it and render() it, so
// the console gives you a scrubber over the whole ladder.

plot(filled, { title: 'cells holding a seed, pass by pass', log: true });
console.log('passes:', filled.length - 1, '- filled:', filled);
```

---

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

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