1 Tools & Requirements
The following libraries were used in the implementation of this program:
This program requires an OpenGL capable graphics card newer than an ATI Radeon AIW 8500DV.
- GLUT: OpenGL Utility Tools
- Magick++: ImageMagick C++ bindings
- algebra.hpp: CS488 Point, Vector & Matrix data structures
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
- 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:
This algorithm ensures that all points generated are unique, and that more points exist in dark places
than in light.
- 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
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:
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.
- 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
5 Basic Results
Basic functionality was tested using a simple gradient.
To test the full functionality of the stipple program, and its extensions a single image will be used
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.
||Uniform Stipple Size
||Scaled Stipple Size
||Uniform Stipple Size (10000 dots, r=3, tol=0.5)
||Scaled Stipple Size (10000 dots, r=3, tol=0.5)
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:
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.
- 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
- Draw a line centered at D, in direction V, with length L.
- If drawing only a dotted outline, draw dots at D.
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.
Sketching can be combined with stippling to generate possibly interesting combinations.
Below, the results of combining:
|Level 2 Sketched Lines
||Level 4 Sketched Lines
||Level 2 Sketched Dots
||Level 4 Sketched Dots
|Level 2 Sketched Lines + Stippling
||Level 2 Sketched Dots + Stippling
Lion Statue (Stippled with Selective Colouring)
Statue of Child (Stippled and Inverted)
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.
Jelly! (Stippled, Invered, Coloured & Sketched)
Church Front (Stippled, Selectively Coloured and Sketched)
This is my chosen final scene.
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
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
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.
My final image, "Church Front" combines stippling, selective colouring, scaled stipples, and
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.
- Weighted Voronoi Stippling: Adrian Secord
- Insight into Images: Terry S. Yoo
- Stockxchng: www.sxc.hu (royalty free photography)