CS 791 Assignment 1: Stippling
Due date: Monday, January 25th, 2010
Summary
You must implement the basic stippling algorithm from Adrian Secord's
paper
Weighted Voronoi Stippling. The algorithm relies on creating
an initial, mostly random distribution of stipple positions, and
refining that distribution using iterations of a weighted variation
of Lloyd's method. A sample stippled drawing from the paper is
shown above.
Specification
You should start by reading the paper. Concentrate on the first
few sections; you are not required to implement anything in Section 4
or beyond. You might also get some benefit from reading through the
relevant portions of Adrian's Master's thesis, Random marks on paper:
Non-photorealistic rendering with small primitives.
The next step is to construct an implementation of the algorithm
(see below for some notes regarding the implementation). At a
minimum, you are required to implement the following aspects of the paper.
- You should be able to read in an arbitrary raster image as
input, in colour or greyscale. If passed a colour image,
first convert it to greyscale.
- Construct an initial distribution of stipple locations in
the image plane. Just about any technique will work
here, but you'll converge on better results faster if you
use an approximation of importance sampling. Adrian uses
rejection sampling (generate random points, but don't add
a point if it's too close to an existing one). You could
experiment with stratified sampling or even some form of
dithering, but you should be able to control the number
of stipples you generate precisely.
- You must run the weighted Lloyd's method iteratively until
the amount of change in the stipple locations falls below
a threshold. Choose the method of measuring change and the
threshold appropriately.
- Use the hardware acceleration trick for rendering Voronoi
diagrams (see in particular the Hoff III reference in the
paper). Some of you may wish to experiment with precise
geometric computation of Voronoi diagrams. I'd like to see
that (it would be very interesting to compare performance),
but you'll probably want to start with the lower-risk OpenGL
method. Also, hacks like this one turn out to be of some
importance in NPR.
- Find a way of controlling radii for circular stipples to
improve tone reproduction. This isn't in the paper.
There might be details in Adrian's thesis, or you can
make up your own technique.
- You must be able to generate your output in a vector format:
Postscript, SVG, or PDF.
Next, you must implement at least one nontrivial extension to your
algorithm. This part of the assignment is open-ended, and there are
many possible extensions. Ideally, a "non-trivial" extension is one
that produces a noticeable, qualitative change to the drawings produced
by your system.
You should be able to show side-by-side images with
and without your extension and convince a stranger that your extension
is doing something.
(Some extensions are more about performance or
interactivity, in which the change must be demonstrated in other ways.)
What follows is a short list of suggestions for extensions. You are
free (indeed, encouraged) to dream up other ideas. If you're unsure
about your idea, or need more guidance, come talk to me.
- Move more of the algorithm to the GPU. You can probably do a
fair amount of the weighted summation on the GPU before
figuring out the new point locations on the CPU. Can the
entire algorithm be moved to the GPU?
- Experiment with exact computation of the Voronoi diagrams
on the CPU. I suspect that ultimately the hardware method
is faster and sufficiently reliable. But there's a tradeoff
here and it would be interesting to see the difference.
- Implement the postprocessing brushes described by Deussen et al.
in the Floating
Points paper.
- Experiment with stipples that aren't points. The technique adapts
readily to other shapes if you can figure out how to generalize
the cones used in the Voronoi diagram computation. See
the Animosaics paper by Smith et al. for ideas.
- Experiment with temporally coherent animations of stipples.
The Animosaics paper can work here too, as can their follow-up
paper
A spectral approach to NPR packing. If you want to be
very fancy you can even think about distributing stipples on
3D surfaces with density that adjusts to reflect changes in
shading.
- Look at other importance sampling methods for stippling. There
have been a few papers recently by Ostromoukhov and by Deussen
about sampling using Penrose tiles, polyominoes, and Wang tiles.
If you're really into computational geometry, it might be interesting
to develop a stippling algorithm based on the
linear-time
algorithm for generating Poisson distributions by
Dunbar and Humphreys.
- Generate coloured stipple drawings that approximate colour
images. This becomes especially interesting if different layers
of coloured dots overlap, since the overlap changes the ability
of lower layers to reproduce the tones their thought they were
reproducing. Things get even more interesting if the
stipples are partially transparent.
- Throw in my
TSP Art technique on top of the stipple locations.
Be sure to use the stipple radius estimate to control line width
locally.
- Use asymmetric stipples, so that you can see their directionality.
Then find a way to orient stipples to help them indicate
image gradients as well as tone.
This part of the assignment is not intended to be overwhelming; it's
just a way to get you thinking about what ideas might follow on from
the paper. Don't feel you have to wear your fingers down to nubs
trying to implement your extension. A proof of concept will suffice.
The final step is to produce stippled drawings using your program.
You can use any photographs you like; I recommend
Philip Greenspun's collection.
You should also take a look at the recently released
photographic
archives posted on Flickr by the Library of Congress (indeed,
Flickr in general is a great source of photographs).
What's important
is that your renderings should clearly demonstrate the features you
implemented.
What to submit
You need to produce a short write-up describing your implementation
and showcasing the illustrations you created. Your write-up can either
be a PDF document or a web page. Your submission should not contain
more than about three or four pages of text, though you're welcome
to make it longer by including lots of pictures. Some time before the
deadline, email me either a URL for your web-based write-up or a PDF.
You are free to structure your submission as you desire. But it should
at least include the following:
- Describe your implementation. What set of languages, tools,
and libraries did you use? What is the interface? If you
created an interactive user interface, include screen shots.
- If there are aspects of the paper that you didn't get working,
list them. If applicable, explain how you would need to modify
your program to complete the implementation.
- Describe your extension. Explain why you predicted your
extension would enhance the algorithm's output. Briefly
explain how you had to modify the core algorithm to accommodate
this extension. Comment on how successful you feel the
extension was.
- Include sample output. Always include the source image along
with the illustration. Use at least three different
source images. Good judgment matters: choose images that
clearly show your implementation's correctness, and that
make for artistic paintings.
If you include raster
pictures in a web page, be sure also to link to vector drawings (PDF,
SVG, or PS). If you're feeling bold you can embed SVG illustrations
directly in your web page; they should render very nicely in Firefox.
- At least one result must clearly demonstrate the
effect of your extension (if your extension can not be demonstrated
visually, you must find some other way to prove that it's working).
If possible, give a side-by-side comparison with and without
the extension running, highlighting its effect.
- One result must be your "official artifact", the one you want to
use to represent your submission as a whole (think of this as the
image that would go in the "teaser figure" common on the first
pages of graphics papers). It can be an additional image or
one of the ones above; just make sure it's clearly indicated.
Part of your mark will be based on the artistic merit of this result.
You're welcome to include other comments and observations on the paper,
the technique, and the underlying intents of this branch of NPR.
I'm also interested in ideas for future work.
By default, I'm not going to look at your source code. But I reserve
the right to request it as part of marking if it sounds from your
description like there's something worth taking a look at.
I also reserve the right to request a live demonstration; this
could be important if you create an especially nice interface or
a realtime version of the algorithm.
Implementation notes
You're free to construct your implementation in whatever way you
like, as long as it can produce the desired final renderings.
- Yes, I know that Adrian made his stippling software available
both as downloadable executables and as source code. Frankly,
trying to understand someone else's research prototype is
more trouble than it's worth. In any case, please don't
use his source code as a reference. You can try out his
executables if you really want, though I'd be happiest if
you worked from the published details.
- You could probably do the whole assignment in Java if you were
willing to use the Java bindings for OpenGL. I highly recommend
the JOGL library
for this.
- You need to read the contents of the frame buffer back into
main memory in order to analyize the Voronoi diagrams being
generated. See the function
glReadPixels
.
- The most appropriate way to render the Voronoi diagram is into
an offscreen buffer. After all, you don't need to see the
Voronoi diagram during the relaxation process (though it couldn't
hurt to get a look at it for debugging purposes). These days,
the best way to render offscreen is to use a Frame Buffer Object
(FBO). I was able to get up to speed on them by looking through a
couple of tutorials on the web. If you want to benefit from
my experience, here's some starter code
that creates an FBO.
- If you'd like to experiment with exact Voronoi diagrams, see
Shewchuck's
Triangle or CGAL.
I strongly discourage you from attempting to implement Voronoi
diagram construction yourself. It's difficult, and too much of a
digression from the main thread of the assignment.
- It's not too hard to generate SVG files or Postscript directly
if you know the formats (mind you, there's not too much to learn
if you want to generate a sequence of discs. Another suggestion
would be to use the Cairo
library here, since it will let you move seamlessly from
interactive viewing on the screen to vector output, all from the
same programmer API. Similar libraries exist for Java; see,
for example, Apache's SVG Generator, a drop-in replacement for
Graphics2D that diverts graphics to an SVG file.
- I'm happy to offer more ideas here, driven by requests for
help and suggestions from students who encountered successes.
Let me know!