Skip to main content
🧙‍♂️ Kris Kowal 🐘 🐙 🧛 📌 📬 Book Store

Marching Topography

Updated November 4, 2026: I wrote up my 2020 sketch with its priors, drew it on hexagons, and set it beside marching squares. The original sketch is the third part of the 2019 Terminal Rivers.

Contours that tile #

A notebook page in blue ink headed 2020-08-30, topographic contour decentralizable rendering. Below, two sketches of a square tile in perspective with its corners labeled 00, 01, 10 and 11: one a sloping surface, the other a saddle, labeled saddle. Then: for each corner, if the corner is a local maximum, walk down clockwise and counterclockwise until reaching a local minimum on either side. At the foot, two square tiles: in one, contour lines run from the top edge to the bottom edge with arrows walking down both sides; in the other, lines cut diagonally across the corner between 00 and 11, with arrows walking around the edges.
Figure 1. Contours, decentralizable: walk down both ways from each high corner.

In August 2020, Lydia and I walked the 9 mile loop around Lake Chabot, bright and early one morning. My mind tends to gravitate down to watersheds when I’m walking around lakes. That day was no exception.

I’ve looked into how to render topographic contours in the past. It’s something of an art. Much of the material concerns how to make them look good. I’m more concerned about rendering tiles seamlessly, possibly on separate machines.

At the risk of re-treading well-known ground, it occurred to me that there might be a pretty straightforward algorithm for this. The ground was indeed well-tread. I had walked into marching squares from a different angle, and I did not know it until I built and tested the idea, six years later. This is the algorithm as I sketched it, as it works now, and where my reinvention meets and departs from its priors.

So, let’s suppose that we have a top-down grey-scale image that represents elevations. Now, suppose that each cell of this image is a corner of a tile in another image. We wish to render isolines, or “contour lines”, along paths of equal elevation, at regular intervals.

My sketched, but then unimplemented, untested algorithm was: for each tile (possibly in parallel), visit each corner of the tile. If the corner is higher than both of its neighbors, begin a march down from this height both clockwise and counter-clockwise, starting at the first contour elevation beneath that elevation. Interpolate elevations linearly along the edges and connect each point of equal contour line elevation. If one arm of this search descends beneath the opposite corner, either stop (if that corner is lower than both of its neighbors) or continue down the next edge.

Walking around a tile #

A tile knows its four corner elevations and nothing else. For each contour level, an edge whose corners straddle the level, one above and one at or below, has exactly one crossing, found by linear interpolation, and an edge whose corners are both above or both below has none. So a tile has zero, two or four crossings of each level: walking around the border, the elevation goes above the level and back below it the same number of times.

The tile walks its border clockwise and lists the crossings of a level in that order, each marked by whether the walk is going up, into ground above the level, or down. Then it joins each up crossing to the next crossing after it. That is the walk down both ways from each high corner, said from the edges: the two crossings joined are the two arms of the walk down from the high ground between them. It needs no case analysis of which corners are maxima, and every segment so drawn has the high ground on the same hand.

Contour lines in dark brown on cream paper over a faint square grid: closed rings around hills and hollows, winding bands where the slopes are steep, every fourth line heavier.
Figure 2. Twenty-four levels on 97 by 65 corners, drawn tile by tile, every fourth heavy. Every one of the 8,357 crossings on a shared edge ends exactly two segments, one from each tile, at exactly the same point.

Marching squares #

The priors are old and well known. Marching squares labels each corner of a cell above or below the level, makes a four-bit number of the labels, and looks up the cell’s segments in a table of sixteen cases. Its parent is marching cubes, the same idea for surfaces in volumes, from Lorensen and Cline in 1987, after Wyvill and others in 1986. From the mapping side, Paul Bourke’s CONREC of 1987 contours a grid cell by cell too. All of them treat each cell alone, which is why they are called embarrassingly parallel, and that is the very property I went walking for.

So my reinvention is marching squares. Reinventing it without the priors, though, I arrived at a few things differently, and testing it showed me a few more.

What came out different #

No table. The priors enumerate cases and look up segments. The walk has no table: it lists the crossings in order and pairs them, and all sixteen cases, the two saddles among them, fall out of the one rule. A rule that short ought to carry over to any convex cell, a hexagon say, without a new table. It does. My tools walked hexagons over the same ground with no change but the list of corners, and named each crossing by its edge’s lesser corner, as on squares.

Contour lines in dark brown on cream paper over a faint honeycomb of small hexagons: the same rings around hills and hollows and winding bands as the square figure, every fourth line heavier.
Figure 2. The same ground and levels on 5,984 hexagons, each drawn alone from its six corners. Every one of the 7,111 crossings on a shared edge ends exactly two segments, one from each hexagon, at exactly the same point.

The saddle, from the walk. When the two high corners are diagonal, a tile has four crossings, and two ways to join them. The heightmap does not say which; the surface between four corners could go either way.

 nw ●───×───○ ne     apart: north to west, around nw,
    │       │               and east to south, around se.
    ×       ×        joined: north to east, around ne,
    │       │               and west to south, around sw.
 sw ○───×───● se     ● above the level, ○ below, × a crossing

The clockwise walk always keeps the high corners apart, and lets the low ground run through the saddle. My tools checked that on 13,419 random saddles. The priors resolve a saddle with arithmetic: the mean of the four corners stands for the center of the cell, or the asymptotic decider of Nielson and Hamann (1991) asks where the smooth surface through the four corners has its saddle. In 2026 I wrote that my rule needs no sample from the middle of the tile, but neither do theirs: they compute the center from the same four corners. What the walk avoids is the arithmetic. It decides from the four labels alone, as a fixed table does, and the price is that it agrees with the decider in only about half of all saddles. It draws the low ground connected and the hills apart, so contouring the map upside down would draw different saddles. Beside marching squares deciding by the mean, the walk draws different lines in 466 of 918 saddles on twenty maps, and the same lines everywhere else.

Two copies of the same patch of contour map side by side, brown lines on cream over a faint square grid, nearly identical. In four shaded squares the lines pair up differently through the square.
Figure 2. My walk, left, and marching squares deciding saddles by the mean, right, on the same 12 by 8 tiles at the same scale. In the four shaded tiles the mean is above the level: marching squares joins the high ground through the saddle, and the walk keeps it apart. No other tile differs.
Walking the other way around gives the same pairing, only with the segments reversed, so the same rule would settle a face shared by two cubes the same way from both sides, which the first marching cubes table did not.

Seams come from the edges. I had credited the walk with settling saddles in a way that lets tiles meet. It does, but so would any rule. Whether a level crosses an edge, and where, depends only on that edge’s two corners, so two tiles that share an edge always agree on its crossings, and a saddle only decides how they join inside one tile.

The canonical edge. The tiles join cleanly on one condition I did not anticipate in my sketch: both tiles must interpolate a shared edge from the same corner. Walking clockwise, the tile above an edge walks it east and the tile below walks it west. If each interpolates along its own walk, floating point puts their crossings as much as 1.4 × 10−14ths of a cell apart: 159 of 8,357 crossings disagree on that map. No one could see that in a drawing, but it breaks any join that matches end points exactly, which is the whole point of having no global pass. Interpolating every edge from its top left corner mends it: the same two numbers in the same order give the same bits.

Here too I met a prior. Paul Bourke suggests ordering an edge’s ends by position and interpolating from the lesser, as a fix for small cracks in surfaces, which is the same rule. What the reinvention adds is the measurement: the failure counted, and the fix checked, every inner crossing on thirty-one maps ending exactly two segments at exactly one point.

A deterministic visit. It did not occur to me to visit the corners in a shuffled order, but it was the purview of my myrmidon robotic assistant to fully explore the problem, and it found that the shuffle, which is how separate machines might visit them, is superfluous. A deterministic visit of the edges has the desired distributed property: a tile reads only its own four corners and writes only its own segments, so the tiles can be drawn in rows, in parallel, or on separate machines, and give the same lines. What makes that true is that both tiles compute each shared edge the same way, from one fixed corner, which is a property of the edge, not of the order. Interpolating in each tile’s own order is just as deterministic, and still cracks.

Joined by name. Each crossing is named by integers: its edge’s lesser corner, whether the edge is horizontal, and the level. Two tiles name a shared crossing alike without consulting each other, so segments from separate machines can be stitched by name, with no floating-point comparison. The priors share crossings through a cache of vertices, which wants the neighbors in one process.

Lines with a direction. Each segment runs from where the walk goes up to where it comes down, so the high ground is always on the same hand and the segments chain into directed lines, ready for labels, hachures or filled bands. The table and CONREC draw segments without a direction.

Small choices. A corner exactly on a level counts as low, the same in both tiles, where CONREC names the cases of a corner on the level and draws along the edge. Each pair of crossings is joined by one straight chord, as in marching squares, where CONREC bends a line through four triangles around the cell’s center.

From peaks to tiles. My 2020 sketch marched down from each peak, which is nearer the old programs that follow a contour line from cell to cell. The tested form, said the other way around, handles each tile alone.

What the priors have #

The priors have things my walk lacks: saddles true to the smooth surface, the same lines for a map turned upside down, and filled bands between levels. None of these matters for drawing lines at one level of detail, which is what I wanted, and is slightly cheaper without one extra division to find the average elevation.

The same tile draws the contours in runes under the rivers of Terminal Rivers, its sibling: each terminal cell is a tile, and a segment becomes a light or heavy weight on the two edges it touches. The code and its tests are in terminal-rivers-5799e64.zip (3.0 MB, commit 5799e64), described in docs/contours.md inside it.


First published on Patreon on August 31, 2020, as the third post of Terminal Rivers, and rewritten in November 2026, knowing its priors.

Sources #