Stipple Art Generator

Look closely at the shading in an old anatomy plate and it falls apart into dots. Nothing on the page is gray. There is black ink, white paper, and the distance from one dot to the next.

That is stippling: small dots of one color, set closer together where the subject is dark and further apart where it is light. Adrian Secord, whose 2002 paper taught computers to do it well, put the difficulty in a phrase. The dots must be placed evenly yet randomly, so that the eye sees tone and never a pattern. Doing that by hand, he noted, is why a stipple drawing often takes weeks.

“Evenly” is the word that matters, more than “randomly” and more than the number of dots. Thousands of dots scattered by chance look like dirt. The same dots, each nudged clear of its neighbors, look like a photograph.

One ink, many grays

Printing has always had this problem. A press either lays ink down or it does not, so every gray has to be faked. Craig Kaplan and Robert Bosch describe halftoning as reproducing a continuous-tone image with only two colors, the white paper and the black ink, by distributing points of ink so that from a distance the eye is fooled into seeing shades of gray. Engravers reached the same answer by hand. Stipple engraving creates tone in a print by spreading a pattern of dots of various sizes and densities across the plate, gouged out with a burin or bitten by acid.

Stipple effects appear beside ordinary line work as early as Giulio Campagnola, who was born around 1482 and died around 1515. In 1757 Jean-Charles Francois engraved three plates directly on copper in the dotted crayon manner, and William Wynne Ryland, who had worked with him, took the manner to Britain. There stipple competed with mezzotint as a way to print tone. It lacked the rich depth of mezzotint, but far more impressions could be taken from one plate.

Scientific illustrators took up the pen version for an equally practical reason. On Secord’s account, drawn from textbooks of scientific illustration, stippling came into use when printing pictures in books was new and difficult. Halftone reproduction was of highly variable quality and drawings were often drastically resized; ordinary drawings suffered from that treatment while stipple drawings kept their character. It asks a printer for dots of a single color, which made it cheap. It also suits smooth, rounded objects without sharp edges, which is why it is often used in medical and archaeological texts.

Why random dots look wrong

Suppose a machine took over those weeks of work. The obvious method is to throw darts: drop each dot at random, with dark parts of the picture more likely to be hit. It fails, instructively.

Random points clump. Some land almost on top of one another and others leave bare patches, and the eye reads those accidents as a texture the photograph never had. Robert Ulichney gave the fault a name in 1988, in a study of how to render pictures on devices that show only black and white. Patterns of white noise, he wrote, carry energy at very low frequencies, and that gives them a grainy appearance. What he called blue noise keeps the irregular, uncorrelated structure and loses the low-frequency grain.

In plain terms, blue noise is randomness with manners. Robert Bridson’s example is the easiest to picture: a pattern in which all the points are at least some set distance apart. A grid would pass that test too, but a grid has rows, and rows are a pattern in their own right. Blue noise has neither rows nor clumps.

The tool shows the difference in a single number. Take the built-in ball with 5,000 dots on a sheet 200 mm wide, switch Relaxation to fixed rounds and set the rounds to zero. Those are the raw darts, thrown by a seeded generator of the xorshift kind George Marsaglia described, so one arrangement number always gives the same throw. The typical gap between a dot and its nearest neighbor reads 0.82 mm, barely more than the 0.7 mm dots themselves, and the dark side of the ball is a mass of merged blots. Now choose “Until it settles”. After 37 rounds the same dots show a typical gap of 1.57 mm.

Letting the dots push each other apart

The repair is called Lloyd’s method, and it is easier to watch than to prove. Give every dot a territory: all the places on the sheet that are nearer to it than to any other dot. The map of those territories is a Voronoi diagram. Now move each dot to the center of its own territory, draw the map again, and repeat. Secord states the method in three lines.

Why does that even things out? A dot that is crowded on one side owns a lopsided territory. Most of it lies on the open side, so its center is over there, and the dot drifts away from the crowd. A dot with room all around is already central and stays put. The steps shrink as the layout settles.

Plain relaxation would spread the dots evenly over the whole sheet and wipe the picture out. An earlier method by Deussen and colleagues relaxed the dots without regard to the image, and Secord reports that it blurred boundaries unless an artist fenced regions off by hand. His change was to weight the center. Define darkness as one minus the brightness of the image, then move each dot to the center of mass of its territory, with the darkness as the mass. Dark regions, as he put it, appear to attract more points, while every dot still keeps its distance. Density follows the photograph, spacing stays even, and edges hold.

The tool does this on a working copy of about 1.44 million pixels. It finds every pixel’s nearest dot exactly, with a method Pedro Felzenszwalb and Daniel Huttenlocher published for distance transforms. It stops by a test Secord suggests, when the average distance the dots move in a round becomes tiny against their own spacing. The makers of StippleGen, a free program built on his paper, say a drawing starts to look reasonably good after around 40 generations; the ball took 37. Secord’s own runs of 5,000 dots finished in under a minute, and his 40,000-dot drawings took about 20 minutes, on a 1000 MHz Pentium III.

One line through every dot

Dots are slow work for a machine that draws, because the pen must lift, travel and drop for each one. In 2004 Science News reported on a way around that, found by Robert Bosch and his student Adrianne Herman at Oberlin College. Treat the dots as cities and ask for a route that visits each exactly once, which is the traveling salesman problem. Then draw the route instead of the dots. Where the cities are dense the line folds back on itself and reads as dark; where they are sparse it wanders across white paper. One of their likenesses of the Mona Lisa used 27,486 cities.

Kaplan and Bosch later explained why Secord’s dots suit the trick. Their first, grid-based dots sat at haphazard distances, which put short, jagged edges into the tour. Relaxed dots give a line that looks tidier and more organized, and fewer cities are needed for the same quality. They add a pleasing fact about the ideal answer: the shortest possible tour is a simple closed polygon, so it never crosses itself.

Nobody computes the shortest tour through thousands of points, because the problem is intractable. The working recipe is to always go to the nearest dot not yet visited, which David Johnson and Lyle McGeoch measured at about 24 to 26 percent longer than a proven lower bound. Then apply 2-opt: delete two edges of the route and reconnect the two pieces the other way around, keeping the change whenever the route gets shorter. Removing a crossing always shortens a route, so the line untangles itself. In their tests 2-opt finished about 5 percent above the bound.

How far can the idea be pushed? In February 2009 Bosch posted a Mona Lisa of 100,000 cities as an open challenge, and later instances run to 200,000. The best tour found, by Yuichi Nagata that March, has a length of 5,757,191, and the best proven lower bound is 5,757,084. The gap is 107 units, or 0.0019 percent.

From the screen to a pen or a laser

A drawing meant for a machine needs real units. The tool asks for the width of the sheet in millimeters and writes every file to that scale: an SVG whose width is given in millimeters, so that its internal units are millimeters too, a DXF of the same path, and a list of dot centers and radii. For the settled ball the path is 10.36 m long. A pen plotter such as the AxiDraw holds pens up to 16 mm in diameter and is driven from SVG files, which makes the line version of the ball one unbroken stroke.

The dot version costs more than its length suggests. Evil Mad Scientist Laboratories, who sell the Egg-Bot, report that a well tuned machine plots about four stipples per second, so that a portrait in 2,000 dots can take as little as ten minutes. At that rate 5,000 dots need about 21 minutes and 30,000 more than two hours. The same makers call a single path even nicer than stipples as a toolpath, and say theirs plots in a couple of minutes.

Pen width is the other decision, and the typical gap settles it. With a gap of 1.57 mm, a 0.7 mm dot leaves most of the paper between neighbors white, while a pen as wide as the gap would turn the dark side of the ball into a solid patch. At 30,000 dots the same sheet has a typical gap of 0.62 mm, so either the pen must be finer or the sheet larger. Secord admitted that he set his own dot radius by a method he called rational yet ad hoc.

A laser changes the vocabulary but not the logic. Laser software treats a picture and a path differently: an image is engraved by sweeping from side to side and switching the beam to make dots, while a vector such as an SVG or DXF path is followed along its length. For a scan, resolution is a matter of line spacing, since dots per inch is 25.4 divided by the line interval in millimeters. An inch is 25.4 mm, so the tool’s 2,048-pixel PNG of a 200 mm sheet works out to 260 dots per inch.

What the method cannot do should be said plainly. It cannot show detail finer than the gap between its dots, which for 5,000 dots on a 200 mm sheet is a millimeter or two. It has no idea what the picture shows, so a pale gray background gets dots as faithfully as a cheek does. Kaplan and Bosch had to round a range of bright grays up to pure white to keep their backgrounds empty, and the tool does the same for the lightest 2 percent of the tonal range. The route is a good one, not the shortest. And dots carry tone, never color.

What it does well is the part that used to take weeks. Every dot keeps clear of its neighbors, the crowd as a whole follows the light, and a machine holding one pen can carry the result to paper.