CS 791 Assignment 1: Stippling

Due date: Monday, January 25th, 2010

Summary

Specification

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.

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 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.

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

• 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!