Stippled Drawings

CS 798
Assignment 2

Lesley Northam

1 Tools & Requirements

The following libraries were used in the implementation of this program:
  • GLUT: OpenGL Utility Tools
  • Magick++: ImageMagick C++ bindings
  • algebra.hpp: CS488 Point, Vector & Matrix data structures
This program requires an OpenGL capable graphics card newer than an ATI Radeon AIW 8500DV.

2 User Interface

The program is called "stipple". Running the program starts up an OpenGL window.

To run the program:

stipple [in out #dots tol scaled? maxr invert? sketch? #lines maxl minl #colours dots? RGB coloured? RGB eTol


where:

  • in: input image file, in any format that ImageMagick supports
  • out: name of output svg file
  • #dots: number of points in scene
  • tol: maximum average dot movement to allow before convergence
  • scaled? 0 for no, 1 for yes, to use scaled radii for dots
  • maxr: maximum radius of stipples
  • invert?: 0 for no, 1 for yes, to draw white dots on black page
  • sketch?: 0 for no, 1 for yes, to draw sketch lines or dots on diagram
  • #lines: number of lines to sketch with
  • maxl: maximum line length
  • minl: minimum line length
  • dots?: 0 for no, 1 for yes, to sketch with dots instead of lines
  • RGB: RGB colour in format RRRGGGBBB, eg: 123195246 or 129003045, used for main dot colour
  • coloured?: 0 for no, 1 for yes, to draw some dots within eTol of RGB value in given colour
  • RGB: RGB colour in format RRRGGGBBB, colour used for selective dots
  • eTol: allowed tolerance between original and new colour

3 Initial Point Generation

Initial points are generated using a probability-based method as follows:
  • create a random point (x,y)
  • generate a random number z between 0 and 99
  • find the grayscale colour of pixel (x,y) in original image, let it be C
  • convert C so that it lies between 0 and 99
  • if z less than C AND (x,y) is unique, point is valid, use it
  • repeat until all points generated
This algorithm ensures that all points generated are unique, and that more points exist in dark places than in light.

4 Generating and Computing the Weighted Centroid Voronoi Diagram

The voronoi diagram is created by drawing a cone at each point generated in section 3. To discover regions in the voronoi diagram (and thus compute their centroid), each cone must have a unique colour. So, at point generation time a unique colour is assigned to each point. The unique colours are generated by:
  • for each red value there are 255 values of green
  • a random blue value is added to each red/green combo
  • the colour is stored as RRRGGGBBB, which is a unique key
Now that each region has a unique colour, the framebuffer can be analyzed and the pixels sorted into regions. Then, after the framebuffer has been completely analyzed the centroids are computed as in Secord's paper. To determine convergence, the average centroid movement is compared to the user input tolerance.

5 Basic Results

Basic functionality was tested using a simple gradient.
Original Gradient Uniform Stipple Size Scaled Stipple Size
To test the full functionality of the stipple program, and its extensions a single image will be used for reference. This image (of two vases), is not necessarily a good image choice for all modes but is capable of illustrating the basic ideas. Below, results from using the basic algorithm.
Original Image Uniform Stipple Size (10000 dots, r=3, tol=0.5) Scaled Stipple Size (10000 dots, r=3, tol=0.5)

6 Extensions

Pen and ink stippled drawings are not limited to just black ink in the real world. Artists may decide to draw the entire scene in a different colour (eg. blue for an ocean scene), or may even choose to some sections of a scene in a unique colour (perhaps to emphasize something). These two ideas will be implemented as minor extensions.

Ink drawing, while typically done on white or pale coloured pages can be done on dark pages with pale ink. For example, fine white dots (possibly paint, or print making ink) on a black velevet canvas. This idea will also be implemented (and is called inversion).

The first image below draws dots using a user input colour. The second image has multiple dot colours. The pale blue/green dots are coloured as such because the colour in the underlying image (at those points) is within the user specified tolerance of the dot colour. Note that the vases do not have any significant colours, so this feature does not have much of an impact.

The third image shows the effects of inversion, where dots are drawn in brighter areas instead of darker areas. This feature can be useful for rendering darker images whose subject is pale (such as marble statues). Note that the vases are pale as is the background, so inversion (while it technically works) does not have a pleasing output.

Coloured (10000, r=3, t=0.5) Partial Coloured (10000, r=3, t=0.5) Inverted (10000, r=3, t=0.5)

Before drawing a scene many artists sketch the general shape and highlights out in a rough fashion. Architechtural drawings, and even some comic books can also exhibit this sketched appearance. Even some stippled drawings may keep sketch lines (or dotted lines) to help differentiate textures, structures, etc.

If I could mathematically describe this sketching method, it would be "a sequence of evenly spaced, non-uniform length tangent lines".

To implement tangent outlines:

  • Using the user input colour level C, limit input image to C colours (this will allow the user to choose the amount of detail they wish to have sketched).
  • Compute the edges of colour-limited image.
  • Place user specified N dots along edge diagram, but only in brighest areas (above 90%).
  • Compute the weighted centroid voronoi diagram of the edge dots, allow it to relax (this will space out the points along the edges in a neat fashion).
  • Blur the edge diagram to allow details to blur together.
  • For each dot D, compute the "detail" at this point ("detail" is the average pixel colour within range R of D. Range R can be parameterized. The range forms a box around D of height 2R.).
  • Let MD be the maximum detail found from the step above.
  • For each dot D, find the gradient from the grayscale input image (use central differencing to compute).
  • Find V, the normal to the gradient at point D.
  • Compute the "detail" d, at D, and let L = MAXLENGTH * ( 1 - ( d / MD ) ) be the length of the line. (This sets the length L of the line to be shorter in areas with more details, and longer in areas of less detail.)
  • Draw a line centered at D, in direction V, with length L.
  • If drawing only a dotted outline, draw dots at D.
Below, results of sketching the vase image with lines and dots using two different colour levels. Note that this image is not a good choice for this algorithm as the vases are too similar in colour to the background.

Note the random lines and dots present in areas where there should be nothing. This was an error in the algorithm that was later corrected. Another interesting note, length of lines in the following images was selected at random. But areas with lots of details, or finer curves should be drawn with shorter lines. This was an improvement that was made for the final images.

Level 2 Sketched Lines Level 4 Sketched Lines Level 2 Sketched Dots Level 4 Sketched Dots
Sketching can be combined with stippling to generate possibly interesting combinations. Below, the results of combining:
Level 2 Sketched Lines + Stippling Level 2 Sketched Dots + Stippling

7 Results


Gear (Stippled)
Original Image


Lion Statue (Stippled with Selective Colouring)
Original Image


Statue of Child (Stippled and Inverted)
Original Image

Vase of Roses (Stippled and Selectively Coloured)
On the left, drawn with few dots and on the right many dots for a "silk screened" feel.
Original Image


Vase (Sketched)
Original Image


Bench (Sketched)
Original Image


Building (Sketched)
Original Image


Steeple (Sketched)
Original Image


Jelly! (Stippled, Invered, Coloured & Sketched)
Original Image


Church Front (Stippled, Selectively Coloured and Sketched)
This is my chosen final scene.
Original Image

8 Comments & Future Work

I find that the stippling algorithm, while it technically works is too mechanical (too perfect). Dots are perfectly shaped, there is no bleeding, there are no ink blots, no smudges and the dots are perfectly spaced. To improve this, simple randomizations could be added (eg. randomize the dot shape, allow ink to bleed, jitter dot positions slightly, etc).

However in its "as-is" form, I find the algorithm represents some forms of print-making very closely. Specifically, wood block, etching and silk screening. The "Jelly!" image above illustrates how the stippling algorithm (combined with my extensions) can replicate print-making media.

Not all images work well for sketching. Images with large gradients, shadows and highlights produce extra lines that may be undesired. This is a result of the edge detection algorithm (ImageMagick's standard algorithm combined with the user-specified detail level (which restricts image to a given number of colours for better detail finding)). Images that work well are buildings, single objects on non-busy backgrounds and those images with few highlight/shadowed areas.

Whenever there are small features (say a small dot of a texture) in a large expanse of nothing -- very messy lines are created in star-like patterns. This is because there is not enough detail in the nearby area to force the strokes to be small. (Observe the star patterns present in the Chruch Front image above). Occasionaly these patterns may be desirable, but not always. To fix this problem, evaluation of curvature in nearby areas could be taken into account when setting line length. Creating interesting sketches is a matter of image choice and finding the best line length. Below are two examples where the sketching does not work well. The first, is a picture of grapes outlined with the original (random line length algorithm). Notice that in areas where there are "pinches", large star patterns are visible. Now that detail is considered for line length, the sketch of grapes could be improved. However the smooth internal gradients make it difficult to sketch internal grape structure.

The second image is a carving on a cathedral. There are no large smooth gradient sections, but the detail of the image is great, and the line length chosen is too long. Too much detail results in very messy sketches such as this.

Sketched Grapes (Original Image) Sketched Carving (Original Image)

My final image, "Church Front" combines stippling, selective colouring, scaled stipples, and sketching. I find that this image, resembles those found in comic books (one could almost build up a story to fit the "panel"). An interesting thing to note about this image, if it had been sketched alone the 3D surfaces would not have been evident. Stippling in this image also helps us differentiate the sky from other surfaces. By adding stippling, you can depict the 3D shape (eg. the facade of the church doors). I'm very happy with this final image.

References

  • Weighted Voronoi Stippling: Adrian Secord
  • Insight into Images: Terry S. Yoo
  • Stockxchng: www.sxc.hu (royalty free photography)