Task 5 of 6

A Signed Distance Field From a Bitmap

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.

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

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:

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.

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.