CS798: Lectures

Lecture 1: NPR and art

I will cover two topics: Notes:

Lecture 2: Strokes

This lecture is assembled from the following papers: Most or all of the papers are available from the ACM digital library, or from the home pages of the authors.

I also recommend Aaron Hertzmann's stroke-based rendering tutorial. It gathers together most of the work mentioned above and tries to cast it within a common optimization framework. It also takes a broader view of stroke-based rendering that incorporates stippling, vector field visualization, and pen-and-ink drawing.

Finally, following our discussion on painterly animation, Guillaume offers two examples: Frederic Back's The Man Who Planted Trees, animated by hand, and Umesh Shukla's Still I Rise, animated using off-the-shelf software. To these I will add a pointer to an animation I've mentioned a couple of times, Alexander Petrov's The Old Man and the Sea. There's also the music video for Frou Frou's The Dumbing Down of Love (is there a link to the video anywhere?). Anyone want to produce a short animation for their final project?

Lecture 3: Halftoning

Details about thresholding, ordered dithering and error diffusion dithering can be found in many graphics textbooks, including the course text. I also showed two non-standard examples of dithering: ASCII art (courtesy of AA-Project), and the art of Ken Knowlton.

The material on screening and stippling came from the following papers. Most of it is also described in the textbook, though the last paper doesn't appear there.

Lecture 4: Natural (and unnatural) media

I survey some of the work that has gone into simulating (or faking) natural artistic media. We proceed in a rough order of increasingly accurate simulations, also trying to group by technique.

Lecture 5: Optimization

I slow down a bit and look at specific algorithmic techniques in more detail. In this lecture, I focus on optimization and its usefulness in NPR. Optimization is a powerful technique for NPR, where frequently we can't generate the picture we want directly, but we can evaluate pictures to decide how well they fit an aesthetic goal.

I describe some simple approaches to optimization -- the downhill simplex method that appears in Numerical Recipes, and a deterministic perturbation-based approach that moves randomly through a configuration space. I then explain the idea of simulated annealing and present annealing-based versions of the two algorithms above.

As a demonstration of optimization in NPR, I present Agrawala and Stolte's SIGGRAPH 2001 paper Rendering Effective Route Maps. It uses several stages of optimization, each based on perturbation-based simulated annealing. Note that Kaplan and Salesin's 2000 Escherization paper uses the downhill simplex simulated annealing algorithm from Numerical Recipes.

Lecture 6: Object-space silhouettes

The computation of silhouettes from 3D models is perhaps the largest and most coherent body of work in NPR. I devote a number of class periods to this one topic. I break the presentation down roughly along these lines: More information about object-based (and image-based) silhouettes can also be found in SIGGRAPH 1999 course notes by Aaron Hertzmann.

Lecture 7: NPR lighting models

A discussion of two nonstandard lighting models that are used in NPR. The first is toon shaders, which are widely used in film and games. The technique has been known for a while, and is described for example in the NPAR 2000 paper Stylized Rendering Techniques For Scalable Real-Time 3D Animation by Lake et al. The other is the Tone-based shading illustration model developed by Gooch et al. See the Gooch and Gooch textbook for more details.

Lecture 8: Image-based NPR

I show how some NPR algorithms can be implemented simply by manipulation of pixel data, assuming that a rich set of buffers (beyond just R, G, and B) have been provided. I cover the seminal SIGGRAPH 1990 Comprehensible Rendering paper by Saito and Takahashi, the Piranesi system used commonly in architecture, and Curtis's Loose and Sketchy Animation technique. Curtis gives more details about his technique in the course notes of the SIGGRAPH 1999 NPR course. I also tie in image-based silhouette algorithms, as presented in Hertzmann's silhouette tutorial.

Lecture 9: Nontraditional perspective

Like shape, lighting and texturing, the camera is a participant in the expression of photorealism, and is therefore also subject to stylization in the creation of NPR. I discuss some of the reasons for altering the behaviour of the camera and the effects that can be achieved. I then survey some of the NPR research that has been carried out on the subject. For an excellent reference on this subject, and many examples, see the "Non-linear Drawing Systems" section of Frédo Durand's Depiction course.

In the most general case, every point in the image plane has its own camera. Of course, the result of such a setup would almost certainly be chaos; we have enough trouble positioning a single camera to achieve the best composition and artistry! So the goal is to provide high-level controls that paint camera parameters in broad strokes across the canvas.

Here are the specific papers I covered:

Lecture 10: Introduction to ornament

I introduce the topic of ornamental design, which will make up the remainder of the course. I attempt to give some guidelines that identify ornament and distinguish it from art. I talk about historical aspects of ornament and reasons why we feel compelled to decorate surfaces with patterns. Finally, I discuss some aspects of the psychology of ornament and our preference for symmetry in decoration. Most of this material is summarized in the introductory chapter of my PhD thesis. Some of the best places to look for further examples and discussion are: Ideally, this lecture would also include some discussion on the relationship between art and information theory. I need more references on this subject...

Lecture 11: Symmetry theory

I begin to give some of the mathematical theory needed to study ornament, most importantly symmetry theory. After a brief informal discussion of symmetry, I move to formal definitions. I define symmetry in general, and then narrow the focus to the specific case of the Euclidean plane, where I discuss the various kinds of isometries. I then define symmetry groups, orbits, and fundamental regions. Finally, I define discrete groups. I then use this infrastructure to talk about the various discrete symmetry groups in the Euclidean plane: the cyclic and dihedral groups, the frieze groups, and the wallpaper groups.

There are plenty of resources, both online and in print, to help understand symmetry groups and explore symmetric patterns. Here are some pointers.

Lecture 12: Tiling theory

Tilings have been part of human culture for millennia, but it is only in the last hundred or so years that systematic mathematical tools have been developed to analyze them. I introduce some of the formal definitions and facts about tilings. All of these concepts can be found in Grünbaum and Shephard's Tilings and Patterns. I list the ones that figure into the lecture.

Lecture 13: Celtic knotwork

I cover two construction methods for Celtic knotwork. The first was described by Peter Cromwell in the January 1993 issue of Mathematical Intelligencer. It is based on modifications to an underlying plaitwork; Cromwell attributes the technique to J. Romily Allen. The second technique is based on connecting midpoints of tiling edges in an arbitrary edge-to-edge tiling. A tutorial by Christian Mercat is on the web (English translation assisted by Steve Abbott).

I then describe some specific bits of research into the structure and rendering of knotwork.

Lecture 14: Islamic star patterns

At this point my lecture notes break down a little bit, mostly because I'm too familiar with the topic! I discuss the construction of Islamic star patterns. Rather than surveying the different techniques that have been developed, I give a straightforward presentation of the material in Chapter 3 of my dissertation. I even mostly reuse slides from my doctoral defense. What follows is a list of topics covered.

Lecture 15: M.C. Escher

As with the previous lecture, I mostly reuse material from my dissertation and defense. Here, I discuss Escher's influence on the worlds of mathematics and ornament, and show some Escher-related work in computer graphics by me and others. I talk mostly about Escherization (monohedral, dihedral, sky-and-water, aperiodic). I also mention non-Euclidean Escher's work with non-Euclidean geometry, including his print Snakes. I show two results related to Escher's Print Gallery: Escher and the Droste effect by Lenstra et al., and the photographic version (including Lenstra himself!) by Henry Segerman. I think I also showed the remarkable Lego renditions of Escher prints by Andrew Lipson.

Lecture 16: Wrap up

I tie up loose ends. First, I mention by name the topics that didn't get the attention they deserved during the term: I finished the course with a discussion about what people liked and didn't like, and how the course might be improved for next time. I still welcome feedback!
Craig S. Kaplan Last updated: