Phoenix

Phoenix: 16000 Stipples

Stippling is the creation of a pattern simulating shading by using small dots. Such a pattern may occur in nature and these effects are frequently emulated by artists[1]. Adrian Secord first outlined a method of algorithmically generating the stippling pattern in his 2002 NPAR paper entitled “Weighted Voronoi Stippling”. The application presented below is an independent implementation of the ideas of the NPAR paper. This was originally done as a university assignment for Professor Craig S. Kaplan, but has since been fine tuned, sped up, corrected, and generally speaking changed beyond recognition. For a more technical take on this tool, please refer to the implementation details.

Downloads

Documentation

Full documentation for the command line arguments is available in the command line options section below.

Klaymen

“Klaymen” by ~LuigiL

Klaymen: Original

This image has multiple tones as a result of the interplay between the shadows and highlights on the character’s body.

Vase

Vase: Original

Fairy Eyes

Fairy Eyes: Original

A “Black and White” image with varying tone values and sharp details in some areas (the woman’s hair).

Implementation Details

The Stippling program is a command line utility that outputs an SVG file with the stippled rendition of an input PNG image using a set number of stipple points. The program is an implementation of the ideas found in Adrian Secord’s paper. The program follows the same general algorithm outlined in Secord’s paper. That is, the program first generates a set of initial stipple points using rejection sampling, followed by Lloyd’s Method to evenly space out the stipple points. However, instead of using the approximation technique used by Woo et al, this implementation computes a precise geometric Voronoi diagram using a slightly modified version of Fortune’s algorithm provided by O’Sullivan. The program then calculates the centroids of the Voronoi cells using a variably spaced numerical integration over the area of the Voronoi tile. In addition, the program uses the centroid computation to compute a variable radius size for each of the stipple points.

Varied Stipple Sizes

To create varied stipple sizes that preserve tonal qualities, the following algorithm is used: Calculate the area A of the Voronoi cell, while taking into account the colour density of the cell as well (so darker cells have a larger area than lighter cells). Then, using A, calculate the radius of a circle that would fit into that area. Essentially, the program finds the volume under the density map for any given cell using a very simple Gaussian numerical integration. This creates stipple dots that preserve tone.

Cell Centroid Area Calculations

A Voronoi tile with its intensity map

Figure 1: Example of a Voronoi Tile with Intensity Map.

To calculate the area of a cell, the following technique was used:

  • Compute the bounds of the Voronoi cell and construct n clip lines such that points that fall outside the Voronoi cell are clipped. Figure 1 shows a graphical representation of such a Voronoi Tile.
  • Perform a Gaussian numerical integration over the Voronoi Tile using the clipped version of the intensity map of the image as input.

Optimizations

The computation of the centroid area is embarrassingly parallel since each centroid area can be computed independently of the others. The program parallelizes the workload rather simply by using OpenMP for the centroid cell computation.

Command Line Options

All options for the utility take two forms, the long form and the alias form. Both variants, along with the functionality of the parameter are detailed below. If a parameter takes an argument, it is noted in the tables as well.

Required Options

Parameter Shortform Alias Takes argument Description
--input-file -I ✓ The input file. Must be a PNG image.
--output-file -O ✓ The name of the file to output.

NOTE: These two parameters are positional, meaning that as long as --input-file comes before --output-file on the command line, the argument names can be dropped.

Example

voronoi input.png output.svg: Using the PNG image input.png create an SVG image output.svg with the Stippled render.

Basic Options

Parameter Shortform Alias Takes argument Description
--stipples -s ✓ The number of stipple points to render. Generally speaking, the larger the number of stipples, the more detailed the resulting output image, at the expense of longer render times. Defaults to 4000.
--colour-output -c ✗ If this parameter is present, the output render will be in colour. Defaults to OFF (That is, rendered output will be in black and white).

Example

voronoi -s 18000 -c input.png output.svg: Using the PNG image input.png create a colour SVG image output.svg with 18000 stipple points.

Advanced Options

Parameter Shortform Alias Takes argument Description
--threshold -t ✓ The cut-off point for the convergence of the stippled output. The unit of this value is the averaged displacement of all stipple points after an iteration of Lloyd’s method. That is, if the averaged displacement is lower than this value, then the rendering process has finished. After each iteration of the rendering process, the expectation is that the stipple points have moved closer to their ideal spot. Generally speaking, the lower this value, the less noisy the rendering will be (a desirable quality) at the expense of longer render times. As a rule of thumb, the more stipple points there are, the lower this value should be, but lots of fiddling is necessary to get an ideal outcome. Defaults to 0.1.
--no-overlap -n ✗ Guarantees that stipple points will not overlap each other at the expense of some tone preservation. Defaults to OFF.
--fixed-radius -f ✗ The radius of all stipple points will be equal regardless of the intensity of the input image. Defaults to OFF.
--sizing-factor -z ✓ The radius of each stipple point will be multiplied by this factor. Use this parameter to control the tone preservation quality of the output image. Defaults to 1.0.
--subpixels -p ✓ Controls the tile size of centroid computations. Theoretically, higher values produce more faithful tone preservation at the expense of rendering speed, but real world outcomes are highly variable. Defaults to 5.
--log -l ✗ Determines whether the utility will produce an output log or not. If there is a problem with the utility, the output log may prove useful in diagnosing the problem. Defaults to OFF.