Introduction

Stippling as a technique came into existence to give artists control over the half-toning processes used when printing images in books was a new and difficult task [6]. The technique consists of carefully placing many small dots of ink on paper to approximate different tones. Stipples are placed closer together to form dark regions and further apart to form lighter regions. The stipples must be placed evenly yet randomly so that the human eye does not see spurious patterns that are not a part of the intended impression. The stipples may vary in size and occasionally shape to convey subtle details.

The original advantage of stippling was its ease of reproduction. The half-toning used to print images in books was of highly variable quality and often drawings were drastically resized to meet space requirements. While normal drawings suffered from such treatment stipple drawings retained their attributes more faithfully. In addition, printing a stippled drawing requires only the ability to produce dots of a single colour, making it an inexpensive technique [12].

However, stippling has significant artistic merit independent of its utility. The stipples can represent fine detail and texture with little cost in complexity. Stippling is particularly good at clearly representing smooth, rounded objects without sharp edges and so is often used in medical and archaeological texts.

We wish to generate stipple drawings from images with as little user input as possible. The goal is to develop a tool which can generate high-quality stipple drawings from any source whatsoever, which implies that we use images as input and not 3D models. While this limits the amount of information we have to work with, it allows us a greater variety of input sources. For example, a user could start from a scanned pencil sketch, a photograph, the output of a 3D interactive application, frames of an animation, etc.

One of the features of a good stipple drawing is that the stipples are well-spaced, that is, the stipples do not clump together, leave uneven voids, or form unwanted patterns. The artist achieves this by carefully placing each stipple onto the page, explaining why stipple drawings often take weeks to create by hand.

Central to our approach is the use of centroidal Voronoi diagrams to produce good distributions of points, as explained in Section 2.1. These distributions can be pre-computed for various different constant tonal values and accessed at run-time to generate stipple drawings rapidly, as covered in Section 4. Alternatively, the input image can be used directly as a weighting function to create a distribution of points that approximate its tones. This method produces images of higher quality but takes more processing time, as explained in Section 3.

Related Work

Our iterative method is a direct descendent of the one described in Deussen et. al. [1]. Their method generates stipple drawings by first placing stipples roughly using a dithering algorithm on the input image and then relaxing them using Lloyd's algorithm until they are well-spaced. Lloyd's algorithm was first introduced to computer graphics by McCool and Fiume in [7] for the generation of sampling point sets. Lloyd's algorithm and the resulting centroidal Voronoi diagrams are explained in section 2.2. However, Deussen et. al.'s relaxation step does not take into account the underlying image, resulting in a blurring of image boundaries. The blurring occurs because the relaxation process attempts to space out closely-packed stipples and compress widely-spaced stipples. Since their tool was designed for interactive use with an artist, they solved this problem by having the user confine sets of stipples to fixed regions, which are aligned to important image boundaries. Since the stipples are not allowed to cross the region boundaries during relaxation, the most important edges are preserved. We wish to find an algorithm that will maintain image boundaries without human interaction.

Hausner [3] uses an approach similar to our iterative technique outlined in Section 3 for aligning the rectangular tiles of a decorative mosaic. Their approach differs significantly from ours in that they must align the tiles' orientation in addition to their position. However, edges that are to be preserved by the algorithm must be entered separately by the user. This makes the algorithm less suitable for a non-interactive application.