Precomputing Stipple Levels

The method presented in Section 3 can produce excellent stipple drawings given enough time for algorithm (1) to converge. Clearly a faster algorithm is needed to compute stipple drawings at interactive rates. We can accomplish this, albeit at a cost in quality, by precomputing sets of stipples and stitching them together at runtime.

Stipple Levels

We will call the result of stippling an image of constant tone $t$ the $t$ stipple level, $0 \leq t \leq 1$. To generate the $t$ stipple level, we simply use the method of Section 3 with $\rho=1$ and $\frac{1-t}{N}$ stipples, where $N$ is the number of stipples required in a pure black image⁴. Figure 11 shows nine stipple levels from black to white of a distribution of 1000 stipples, each differing by 125 stipples. Typically we would generate a greater number of levels, say 256. We discretise the normally continuous range of tones achievable into a limited number of fixed stipple distributions.

Figure 11: Nine discrete stipple levels with a maximum stipple count of 1000, differing by 125 stipples. The radii of the centre stipple level has been calibrated to represent a 50% gray.

Fast Stipplings

Using the precomputed stipple levels, we can quickly stipple an image using the following algorithm:

Algorithm 2 looks at the value of each pixel, determines which stipple level is appropriate, and copies all the stipples that fall inside the area covered by the pixel to the output. Since the input image is processed in scan-line order, we sort the stipples in a particular level into bins that cover a single row of pixels, and then sort the stipples in each bin from low $x$ values to high. Given a particular pixel and a particular level this allows us to quickly find the appropriate stipples.

Conceptually, we split the image into a number of regions to be represented by the same stipple level, then stipple each region individually and recompose the stippled regions into a final drawing. The algorithm is quite fast, but is limited by the amount of memory which must be scanned to produce a stipple drawing. Table 1 shows approximate timings on the system described in Section 3.2 for a simple animation loop. The animation in this case was rendered by OpenGL and read back from its buffers, illustrating the flexibility of using images as input. While increasing the numbers of stipples rendered does have a negative effect on the speed, the greatest factor is the image resolution.

Table 1: Frames per second at various numbers of stipples and resolutions

	5000	10000	20000	40000
$100\times100$	350	300	200	150
$300\times300$	150	120	100	80
$600\times600$	60	45	40	35
$900\times900$	20	20	20	18

Figure 12 compares the results of the fast algorithm to the high-quality algorithm. On the left are the fast stipple drawings of a black-to-white ramp and a lit sphere and on the right are the high-quality versions. Note the many voids and overlapping stipples on the left which should not exist. They are the result of two regions of the image with different values getting stippled using two different stipple levels. The stipple levels cannot merge smoothly since they have different densities of stipples. The result is a non-smooth pattern where there should be one.

Figure 12: A black-to-white ramp and a lit sphere stippled with the fast algorithm of Section 4.2 on the left and the high-quality algorithm of Section 3 on the right.

In addition, what can not be seen from Figure 12 is the temporal discontinuities that arise when the method is used to stipple an animation. In areas of the image where the tonal value is changing quickly, the pixels get stippled by many different stipple levels in a short time. Even if great care is taken to minimize the differences between one stipple level and the next, the rate at which the pixels change cause them to "shimmer." These problems are minimized by using greater numbers of smaller stipples in the animation.

Footnotes

... image⁴

We can actually set $\rho$ to any constant value at all, since equation (1) is insensitive to scalings of $\rho$.