Voronoi Stippling: Turning Brightness Into a Field of Dots

Turning brightness into dot density

Stippling -- rendering an image as a field of discrete dots -- has been a hand technique in printmaking and illustration for centuries: pack dots tightly in dark regions, space them out in light regions, and the eye reconstructs continuous tone from pure density. Weighted Voronoi stippling, introduced by Adrian Secord in 2002, automates this by turning it into a point-optimisation problem: given a target image and a desired number of points N, arrange the N points so that their local density matches the image's brightness everywhere -- dense where the image is dark, sparse where it's light (or the reverse, for a light-on-dark aesthetic).

Voronoi diagrams: giving every point its own territory

A Voronoi diagram partitions the plane into regions, one per point, where every location in a given region is closer to that region's point than to any other point's -- imagine every point as a shop and every region as the area closer to that shop than to any competitor. Once you have a set of scattered points, computing their Voronoi diagram is a well-understood geometric construction (Fortune's sweep-line algorithm builds it in O(n log n)); the interesting part is not the diagram itself but what algorithm decides where to put the points in the first place.

Lloyd's relaxation: nudge every point to its cell's centre of mass

Lloyd’s algorithm (1957, originally developed for signal quantisation, independently rediscovered many times since) is the iterative loop that produces the even, organic-looking spacing. Starting from a random scatter of points:

repeat until converged:
    compute the Voronoi diagram of the current points
    for each point p, find the centroid of its Voronoi cell
        (weighted by local image darkness, not plain area)
    move p toward that weighted centroid
# a cell's centroid pulls its point toward where the "mass" inside that cell is concentrated

The weighting is what connects this to the source image: instead of computing each cell's plain geometric centroid, every pixel inside the cell contributes to the centroid in proportion to its darkness (or, more precisely, 1 minus brightness, so black pixels count fully and white pixels count for nothing). A point sitting in a Voronoi cell that straddles a dark region gets pulled toward the dark side of its cell; over repeated iterations this pull effect compounds, dragging points to migrate from bright regions into dark ones, thinning out where the image is light and clustering where the image is dark -- exactly the density pattern a stipple drawing needs.

Why relaxation makes the pattern look organic, not like a grid

Plain random placement of N points weighted by brightness would produce a correctly-weighted but visually noisy, clumpy result -- some regions would randomly get too many points close together, others too few, purely by chance. Lloyd's relaxation fixes this because a converged Voronoi diagram has a specific, provable regularity property: neighbouring cells tend toward roughly equal area (after accounting for the density weighting), which pushes points toward a locally near-uniform spacing within any region of roughly constant brightness. The result reads as organically evenly spaced -- like the visual regularity of a hexagonal packing, but perturbed just enough by the underlying density variation to still look natural rather than mechanically gridded. A handful of iterations (10-30) is usually enough to visibly settle; more iterations produce diminishing improvement as the points approach the fixed point of the relaxation process.

Choosing the density function

Nothing in the algorithm requires the weighting field to come from a photograph. Feeding it a mathematical function instead -- a spiral, a set of concentric waves, the escape-time field of the Mandelbrot set, or a simulated star cluster's density -- produces the same organic point-packing behaviour driven by that function's own peaks and valleys instead of image darkness, which is why this technique doubles as a generative-art tool: the visual signature of Lloyd's relaxation (locally uniform, globally density-matched packing) is the same regardless of whether the density comes from a photo or from an equation.

Cost and convergence in practice

Each iteration needs a full Voronoi diagram rebuild (O(n log n) with a proper sweep-line construction, though many practical implementations approximate it faster on a pixel grid by rasterising a distance-based nearest-point map directly) plus one weighted-centroid pass per cell, O(pixels) total per iteration since every pixel is visited once to accumulate into its owning cell. For interactive canvases with a few thousand points, a grid-rasterised approximate Voronoi computed each frame is cheap enough to relax live in the browser, which is what lets a stippling demo visibly animate points migrating and settling in real time rather than only showing a single final frame.

Frequently asked questions

Try it live

Everything above runs in your browser — open Stippling & Pointillism and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.