CS 791 Assignment 1: Stippling

Due date: Monday, January 25th, 2010


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.


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.

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.

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:

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.
Craig S. Kaplan Last updated: