Paul Bourke has a nice simple algorithm for doing contours[1] using local information. The page has a nice explanation of the algorithm, and lists a number of ports in various languages. I decided to try my hand at porting it into my platform of choice: XQuery.

Given a set of 3D points sampled at a set of x and y coordinates and a set of z levels, the contour consists of edges labelled with the appropriate z level. The edges are based on the mesh of triangles created from the boundaries and diagonals of rectangles involving adjacent x and y values. The algorithm decides which edge to draw by comparing the z values of the triangle corners with each level in turn. Depending on how many vertices lie below, at, or above the contour level, an appropriate edge is drawn for that case (or none, if appropriate).

The algorithm proceeds by drawing edges of intersection between the triangle and the plane of the contour level.

It's pretty clear that if all the points are above the contour level, there is no intersection of the plane of triangle with the contour plane, so no edge is drawn. It's also pretty clear that if only two of the points of the triangle are at contour level, then an edge between them is part of the contour. Similarly, if only one point is at contour level but the others straddle the contour then an edge from the point at contour level to some intermediate point between the others should be drawn. And so it goes for all the cases:

  • When two vertices are at the contour level and the other above or below it, the edge is the edge between the two points at contour level.
  • When one vertex is below the contour level, one at it, and one above it, the edge runs from the vertex at contour level to a point on the opposite edge.
  • When two vertices are below the contour level and one above it, or vice verse, the edge runs across the triangle from edge to edge parallel to the edge entirely above or below the contour level.
  • When one point is at contour level and the others are both above it or below it, no edge is drawn.
  • When all points are above the contour level, or all are below it, no edge is drawn.
  • When all points are at the contour level, no good decision can be made, so no edge is drawn.

The specific points along the triangle boundary to use is calculated based on the relative heights (z values) of the points. The last case (everything at contour height) can be problematic and can arise quite easily for me because most points are quantized to canvas space (integer coordinates). The fix to this is to add small epsilon values to contour levels to avoid equality with the z values of the points.

Here's a sample set of contours based on a depth field based on signed distance from the union and intersection of a set of random ellipses. Even though the contours are drawn as a set of edges, with all edges at the same contour level drawn with the same colour, you get a strong sense of continuity of the lines, except at corners where the contour turns. Setting stroke-linecap to round fixes that (right image). You do still get a strong sense of mesh, however, because of the sharp turns. More on that in a moment.

There are two key dimensions that control how the contours come out: the number of contour levels and the granularity of the mesh. Both of the images below have the same number of contour levels (30). The image on the left, however, was created with a mesh granularity more than twice that of the image on the right. That is to say, it was created with using a much lower density of sample points within the overall depth field to create the contours. The effect of higher granularity is to have less intricate mapping of the details of the depth field, a coarser mapping with wider separations between the contour lines.

There is an interplay between contour density and line width. Variation in both is nice, but without overlap. I achieve variable widths and densities by dividing the width of the canvas by the number of contour levels times the desired contour density and using that as an upper limit for the stroke widths. Actual stroke width is chosen using a truncated Zipf distribution.

The rendering where all edges at the same level are coloured with the same colour makes sense for contours as contours. For artistic purposes, however, we may want different colouring schemes. For example, we might want to colour contour lines with a colour gradient.

Well! That stitched appearance may be artistically interesting in its own right, but to reclaim the sense of continuity, we'll need to do something else. We'll need to put edges at a particular contour level in order in a single path.

The algorithm works by starting with a seed edge and gradually extending it at both end. Since edges may be drawn in either direction, the added edge may need to be reoriented. An edge is chosen to extend an existing path if one of its endpoints falls within some epsilon of the end of the path. Once an edge is used it is removed from the pool. When no valid edge is found, we start over with a new seed edge, continuing until the pool of unused edges is empty. The key here is the choice of epsilon. A conservative choice is one that just accommodates floating point errors. A more radical choice is one that can allow us to span gaps caused by flat triangles at contour level (all points at contour: no edges added because there is no good local choice). The downside with the radical choice is that it is easy to create cross-linkages where none should exist.

The brute force algorithm works fine, although it can be slow for large contour fields because we end up computing distances between each pair of points for every edge at a given contour level over and over. It can be improved by organizing the edges for each level into a quad tree to reduce the number of edges that need to be considered for any point.

Once we generate full paths for each contour, a gradient colouring looks less ragged:

We can also calculate splines on the paths to smooth them out a little bit at this point. It can also be interesting to add a little wobble to the edges before splining them. Here is a dense contour field rendered as quite wobbly splines first as a wider path in a gradient of pinks and reds overlain with narrower path in a rainbow gradient.

Wilder rendering choices are possible. In these images, the contours are not rendered directly at all. On the left, dots of various colours are scattered normal to the edges using an exponential distribution for the dots. On the right, random circles are placed along the contours.

The final piece to the puzzle, from an artistic point of view is: how should we construct the depth field? We've already seen the contours from the signed distance fields of random unions and intersections of ellipses. Signed distance fields from other curves can be interesting too.

Here we have a circle with rays coming from it, a modulated torus knot, and a tilted and projected dodecahedron./p>

Space-filling curves can be interesting too, although care needs to be taken to select a scaling for the curve compatible with the contour sampling granularity. Here we have a Gosper quad curve, a dragon curve, a Koch snowflake, and a pentaplex.

The possibilities are endless. A distance field can be computed for letter forms:

Or we can take a different slant entirely. These images were created by taking samples from photographs (the Vatican on the left, the Temple of Kukulcan at Chichen Itza on the right) and use number calculated from those colour samples to form the contours. For the Vatican I used a linear combination of the colour coordinates in the XYZ colour space. For the pyramid I used just the X coordinate.

References and Notes