On Stippling

Stippling is the patient branch of drawing. An engraver’s apprentice, given a pen and a morning, builds a shadow out of dots: close together where the stone is dark, sparse where the light falls, never touching if it can be helped. There is no line to hide behind. Tone is simply a matter of how crowded the page is.

The picture behind this codex — the citadel on its hill, the harbour, the Mediterranean — is drawn that way, except that the apprentice is a small program and the morning is about a minute.

From painting to density

It begins as a monochrome painting of the scene, roughly 3024 by 1296 pixels, worked at a smaller 2016 by 864 for the stippling. A painting is not yet a drawing, so the first job is to turn its brightness into a map of ink: how much dark each pixel deserves.

That map is not a straight inversion. The image is lightly blurred to remove noise, then sharpened with an unsharp mask so the merlons stay crisp. An edge detector adds a little extra ink along contours, because human stipplers trace outlines and the eye expects them. And the scene is divided by hand-painted masks into sky, sea and castle, with the rest counted as land, so that each region can be treated differently:

1. The sky is kept airy, since it carries the text of the home page; clouds stay paper-white and the area around the sun is cleared.
2. The sea keeps its wave bands but is capped, so the water never goes as black as the rock.
3. Land and walls get the full range, on a steeper curve that separates sunlit masonry from shaded hill.
4. The night version is built separately and inverted in spirit: pale dots on dark paper, so only light is drawn — the moon where the sun was, its path on the water, the moonlit west faces of the walls.

Where should a dot go?

Scattering dots at random in proportion to the ink gives you grain, not drawing: clumps and holes everywhere. The technique used here comes from Adrian Secord’s paper “Weighted Voronoi Stippling” (NPAR 2002), and it is lovely in its simplicity.¹

Start with the dots scattered at random, weighted by the density map. Now give each dot a territory: the region of the image closer to it than to any other dot — its Voronoi cell. Compute the centre of ink of that cell, the average position of its pixels weighted by how dark they are, and move the dot there. Repeat. This is Lloyd’s relaxation, and after a few dozen rounds the dots stop jostling and settle into an even, blue-noise spacing that still crowds into the shadows.

Every dot moves to the centre of the ink it is responsible for, until none of them wants to move.

Finding which cell a pixel belongs to is the expensive part. The build uses d3-delaunay, whose find() walks across the triangulation from a starting guess toward the nearest point. Because neighbouring pixels almost always belong to the same dot, passing the previous answer as the guess makes the walk just a step or two long.

// One Lloyd step: every point moves to the ink-weighted centroid of its cell.
function lloydStep(points, density, W, H) {
  const delaunay = new Delaunay(points); // flat [x0, y0, x1, y1, …]
  const n = points.length / 2;
  const sx = new Float64Array(n), sy = new Float64Array(n), sw = new Float64Array(n);
  let hint = 0;
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      const w = density[y * W + x];
      if (w === 0) continue;
      hint = delaunay.find(x + 0.5, y + 0.5, hint); // walk from the last cell
      sx[hint] += w * (x + 0.5);
      sy[hint] += w * (y + 0.5);
      sw[hint] += w;
    }
  }
  for (let k = 0; k < n; k++) {
    if (sw[k] > 0) {
      points[2 * k] = sx[k] / sw[k];
      points[2 * k + 1] = sy[k] / sw[k];
    }
  }
}

The real build adds one liberty that is not in the paper: for the first sixty per cent of its 48 iterations it over-relaxes, moving each dot 1.6 times the distance to its centroid, overshooting a little to converge faster, and falls back to the plain centroid if that would push a dot off the edge of the frame.Over-relaxation is a common trick for speeding up Lloyd’s algorithm; the final iterations use the ordinary step so the dots settle where Secord’s method says they should.

Tone, regions and motion

When the dots have settled, each one remembers two small facts. Its tone is the average ink of its final cell, which later becomes its radius: dots in deep shadow are drawn slightly larger, as a pen pressed harder would make them. Its region — sky, sea, castle, land, and a few special ones for the stars, the moon, the sun and the ships — comes from the masks. Every dot is packed into six bytes: two for x, two for y, one for tone, one for region.

There are about 88,000 of them in the main scene: 64,000 for day and 24,000 for night, plus a scatter of stars, a vermilion ring around the sun, and two ships of a twelfth-century kind, a galley and a round-hulled nave, drawn procedurally and stippled in the same hand.

Those region labels are what let the picture breathe. In the browser, each set of dots is drawn in a single WebGL call and animated in the vertex shader. Sea dots bob, more near the viewer than at the horizon, and flicker where the sun’s glitter path crosses them. Sky dots drift very slowly. The castle and the land hold still, apart from a faint swelling and shrinking, like ink that has not quite dried. On first load, the dots ink in outward from the citadel.

It is, in the end, a very old way of making a picture, done by a very new kind of apprentice — and like every stippled plate, it is only a likeness. The citadel it shows is an interpretation of the twelfth century, not a record of it.

Notes

1. Adrian Secord, “Weighted Voronoi Stippling”, Proceedings of the 2nd International Symposium on Non-Photorealistic Animation and Rendering (NPAR 2002), pp. 37–43. The paper also describes a faster real-time variant that uses precomputed dot distributions; this site uses the slower, iterative one, offline, once. ↩