Computational Stippling: Can Machines Do as Well as Humans?—Wolfram Blog

Stippling is a kind of drawing style using only points to mimic lines, edges, and grayscale. The entire drawing consists only of dots on a white background. The density of the points gives the impression of grayscale shading. Back in 1510, stippling was first invented as an engraving technique, and then became popular in many fields because it requires just one color of ink. Here is a photo of a fine example taken from an exhibition of lithography and copperplate art (the Centenary of European Engraving Exhibition held at the Hubei Museum of Art in March 2015; in case you’re curious, here is the museum’s official page in English). The art piece is a lithographic print. From a view of one meter away, it shows remarkable detail and appears realistic. However, looking at it from a much closer distance, you can see it’s made up of hundreds of thousands of handcrafted stipples, with the original marble stone giving it even more texture. From my point of view, this artistic stippling method is like a simulation of variable solidity using small dotted patterns, like a really dense dot matrix printer, except these patterns are handmade. It is fascinating looking at lithographs, observing how a macro reality emerges from uncountable random dots: the mirror reflection on the floor, the soft sense of the cloths, and the mottling on the building engraved by history. (Photos were taken from the same exhibition.) As a technique invented five hundred years ago, stippling has become popular in so many fields way beyond its original intention because of its simplicity. It was once the standard for technical illustrations, especially in math and mechanics books. Even today, many people are interested in it. Experts from different domains are still using stippling in daily work. Typical stippling almost always uses one or two colors. Actually, one can create all sorts of textures and tones without introducing artifacts—one cannot achieve both with techniques like hatching or line drawing—just by varying the density and distribution of the dots. That makes stippling an excellent choice when archaeologists, geologists, and biologists are doing fieldwork and want to record things they find immediately. They don’t want to travel along with heavy painting gear; a single pen is good enough for stippling. Even in modern days, compared to photography, stippling still holds some advantages despite requiring a large amount of time. For example, the author can mark and emphasize any features he or she wants right on the drawing; thus, the technique is an important skill—one that is still being taught and researched today. Here to support my point, I made these dinnertime paper-napkin stipplings (if they look like a complete disaster to you, please forgive me, as I’m not an expert and they only took about five minutes): It is also very interesting to note that stippling is such a natural way to distribute dense points that the strategy is actually adopted by many living things, like this one in my dish: In the computer age, there is a special computer graphics domain called non-photorealistic rendering. Stippling is one of its basic artistic painting styles, and can be used as the foundation of many other synthetic styles, such as mosaic, stained glass, hatching, etc. Back to the art side. Stippling shows interesting connections with Divisionism and Pointillism, which both belong to Neo-Impressionism. In popular art, people are still attracted to this ancient art. There are even stipple tattoos on Pinterest. You can watch people doing it with stunning effect. Perhaps you can even learn stippling yourself on the internet. Needless to say, stippling as a handcrafted art really requires lots of patience. The manual process is time consuming. Moreover, it takes a lot of practice to become skillful. After trying so hard on the napkin without satisfaction, I had a closer look at the masterpieces. I noticed that the points in the drawings seem random but are actually ordered, a bit like the structure seen in a quasicrystal: In the above comparison, the left figure corresponds to randomly distributed points, while the right figure corresponds to a distribution like those found in stippling drawings. Obviously, they are very different from each other. It turns out when using points to approximate grayscale shading, a random set of points with uniform distribution is usually not good enough. To illustrate that, both images in the comparison below have 63,024 points sampled from the same distribution with the same contrast. If we think of the original grayscale image as a two-dimensional distribution, the local density of the two resulting images are the same for any corresponding position. Therefore, the contrast of the two images must be the same as well, which can be illustrated by resizing them to a small enough scale so the detail of the points won’t distract our eyes. Nevertheless, the one on the right is a good stippling (or, as it’s usually called, well spaced), while the one on the left has too many unwanted small artifacts—clumps and voids that do not exist in the original image. Now it is not very hard to see that in the stippling graphics, the triangle formed with any three points nearest to each other is nearly equilateral. This turns out to be the essential property of a “good” stippling. Given that unique micro scale character, I couldn’t help wondering: is it possible to generate a stippling drawing from any image programmatically? The answer is yes—as I have just shown one of the results from my generator, and which I will describe in detail in the rest of this blog. Actually, there are not only lots of papers on this topic, but also well-made applications. Back to the first comparison example. In order to quantitatively reveal the “well-spaced” property, I draw the DelaunayMesh of the points and observe them: With the meshes, I can confirm my equilateral triangle conjecture numerically by graphing the distribution of the interior angles of the cells in the meshes: Recalling the duality between a Delaunay mesh and a Voronoi mesh, and with the help of lots of academic papers, I eventually inferred that my equilateral Delaunay mesh corresponds to the so-called centroidal Voronoi diagram (CVD). Indeed, the CVD is the de facto method for computer-generated stippling. Moreover, there is a dedicated algorithm for it due to Lloyd: 1. Generate n random points inside the region of interest 2. Generate the Voronoi diagram of the n points 3. Find the centroid (i.e. center of mass) of each Voronoi cell 4. Use the n centroids as the resulting points 5. If satisfied, stop; otherwise, return to step 1 Here the key steps are the Voronoi diagram generation and the centroid finding. The former is a perfect match for the bounded version of the built-in function VoronoiMesh. The latter, as the Voronoi cells for a closed region are always closed convex polygons, has a simple formula that I’d like to briefly describe as follows for completeness. If you’re not into math, it can be skipped safely without harming the joy of stippling! Now suppose I have a cell defined by n vertices ordered clockwise (or counterclockwise) {P1=(x1, y1), P2=(x2, y2),… Pn=(xn, yn)}; then its centroid C can be determined as: As a test, we generate 2,500 uniformly distributed random points in a square region [-1,1]×[-1,1]: Its Voronoi diagram is: Lloyd’s algorithm can be expressed as the following findCentroid function: Here, just to illustrate the principle of the algorithm, and to make things simpler to understand by ensuring that the code structure is similar to the weighted centroidal Voronoi diagram (which I will describe later), I have defined my own findCentroid function. Note that for uniform cases, there is the much more efficient built-in function, MeshCellCentroid: Each Polygon from the Voronoi mesh can be extracted with MeshPrimitives[...,2], which then should be piped to the findCentroid to complete one iteration: Now we’re ready to animate the first 50 iteration results to give a rough illustration of the CVD: There are various ways to show the difference between the point distributions before and after the process: For example, I can use NearestNeighborGraph to illustrate their connectivity, which will highlight the unwanted voids in the former case: Alternatively, as was shown earlier, I can compare the statistics of the interior angles. After Lloyd’s algorithm, the mesh angles are much nearer to 60°: Finally, to give another intuitive impression on the “well-spaced” property from a different point of view, I’d like to compare the discrete Fourier transform of the initial points with the one of the refined points: