CS798: Lectures
Lecture 1: NPR and art
I will cover two topics:
 A look at some of the highlevel challenges faced by
NPR researchers
 An introduction to human perception of art and how it
can influence our approach to NPR
Notes:
 As a gentle introduction to issues of perception in art,
I recommend two books: Understanding Comics, by
Scott McCloud, and
Picture This by Molly
Bang. Neither will give you
a comprehensive theory of art, but both will raise your
level of sensitivity to the issues.
 Most of the artrelated material was drawn from a
SIGGRAPH 2002 course organized by Frédo Durand.
Note in particular the sections "Gestalt and composition"
and "Neurological theories of aesthetic".
These slides also contain pointers to many good references
on the subject.
 Guillaume also offers his slides on
Ramachandran's work and on
perceptual grouping and shape equivalence.
 V.S. Ramachandran has done a lot of very interesting work
on perception and cognition. I highly recommend the
Reith lectures
he gave last year for the BBC. Lecture 3, "The Artful Brain",
relates most strongly to the class, though I also went on a
bit about Lecture 4, "Purple Numbers and Sharp Cheese".
Imprint's web
page has links to the lectures and to the papers that
preceded them.
 Lee raised an interesting question about economic models
for computer art. Two artists working in a highly
electronic medium are Kenneth
A. Huff and Golan Levin.
They both produce work that require us to rethink the traditional
economy of art.
Lecture 2: Strokes
This lecture is assembled from the following papers:
 Paul Haeberli. Paint by numbers: abstract image representation.
SIGGRAPH 1990.
 Peter Litwinowicz. Processing images and video for an
impressionist effect. SIGGRAPH 1997.
 Aaron Hertzmann. Painterly rendering with curved brushstrokes
of multiple sizes. SIGGRAPH 1998.
 Aaron Hertzmann. Fast paint texture. NPAR 2002.
 Michio Siriashi and Yasushi Yamaguchi. An algorithm for
painterly rendering based on local source image approximation.
NPAR 2000.
 Bruce Gooch, Greg Coombe and Peter Shirley. Artistic vision:
painterly rendering using computer vision techniques.
NPAR 2002.
 Aaron Hertzmann. Paint by Relaxation. CGI 2001.
 Anthony Santella and Doug DeCarlo. Stylization and
abstraction of photographs. SIGGRPAH 2002.
 Aaron Hertzmann and Ken Perlin. Painterly rendering
for video and interaction. NPAR 2000.
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
strokebased
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 strokebased rendering that incorporates
stippling, vector field visualization, and penandink 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 offtheshelf 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 nonstandard examples of dithering:
ASCII art (courtesy of
AAProject),
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.
 Victor Ostromoukhov. Artistic Screening. SIGGRAPH 1995.
 Oliver Deussen, S. Hiller, C.W.A.M. van Overveld and
Thomas Strothotte.
Floating Points: A method for computing stipple drawings.
Eurographics 2000.
 Adrian Secord. Weighted Voronoi Stippling. NPAR 2002.
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.
 Steve Strassman. Hairy Brushes. SIGGRAPH 1986.
I also demonstrated Golan Levin's
applet
implementing hairy brushes. Spending some time on Golan's
web
page could be a good inspiration for your project.
 Victor Ostromoukhov. Digital Facial Engraving. SIGGRAPH 1999.
 Cassidy Curtis, Sean Anderson, Josh Seims, Kurt Fleischer and
David Salesin. ComputerGenerated Watercolor. SIGGRAPH 1997.
 William Baxter, Jeremy Wendt and Ming Lin. IMPaSTo: A Realistic,
Interactive Model for Paint. NPAR 2004.
 Mario Sousa and John Buchanan. Observational Model of Blenders
and Erasers in ComputerGenerated Pencil Rendering. GI 1999.
 Brian Wyvill, Kees van Overveld and Sheelagh Carpendale.
Visualizing Batik. NPAR 2004.
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 perturbationbased approach
that moves randomly through a configuration space. I then explain
the idea of simulated annealing and present annealingbased 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 perturbationbased simulated annealing. Note that
Kaplan and Salesin's 2000 Escherization paper uses the downhill
simplex simulated annealing algorithm from Numerical Recipes.
Lecture 6: Objectspace 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:
 The importance of silhouettes in depiction of shape.
 Kinds of features we care about, and their properties:
silhouettes, creases, boundary edges, cusps.
 The generic silhouette algorithm: identify all possible edges,
process them for visibility, render.
 Two silhouette edge identification algorithms: in a faceted mesh,
silhouettes are the edges separating front and back faces.
In a smooth mesh (one with vertex normals), they can be found
as line segments on mesh triangles.
 Identification of creases, either explicitly by the user
or by thresholding dihedral angle.
 Visibility for silhouette edges. Appel's Quantitative
Invisibility (more information can be found in the SIGGRAPH 1997
paper
Realtime Nonphotorealistic Rendering by Markosian et al.,
and in Chapter 2 of
Markosian's PhD thesis). Project and build a planar
subdivision. Imagebased approximation using an ID image
(see the NPAR 2000 paper Artistic Silhouettes: A Hybrid Approach by
Northrup and Markosian; the technique is passed on to
the SIGGRAPH papers in 2002 and 2003).
 Acceleration of silhouette detection. The edge buffer
(Sousa and Buchanan, NPAR 2000)
reduces total computation. Markosian's probabilistic
technique (see Realtime NPR again) reduces the number of faces that must be tested.
 "Exotic" silhouette detection, i.e. algorithms that are
a little harder to explain but that are elegant and efficient.
Hertzmann and Zorin's
dual space method, from SIGGRAPH 2000.
Gooch et al.'s Gauss maps (see the Gooch and Gooch NPR
textbook).
 One quick image space algorithm: Raskar and Cohen's
Image Precision
Silhouette Edges (from I3D 1999).
 Some recent advances. Temporal coherence of imagespace
stroke parameterization, as described in the SIGGRAPH 2003
paper Coherent Stylized Silhouettes. An extension to silhouettes
called
Suggestive Contours (also from SIGGRAPH 2003), which includes
edges that are silhouettes in nearby views.
 Stylization of silhouettes. Especially the various stylization
techniques collected in the SIGGRAPH 2002
WYSIWYG NPR
paper.
More information about objectbased (and imagebased) 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 RealTime 3D Animation by Lake et al. The other is the
Tonebased shading illustration model developed by Gooch et al.
See the Gooch and Gooch textbook for more details.
Lecture 8: Imagebased 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 imagebased 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
"Nonlinear 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 highlevel controls that paint camera
parameters in broad strokes across the canvas.
Here are the specific papers I covered:

Multiperspective Panoramas (Wood et al., SIGGRAPH 1997).
Create a single scene that embodies a continuous change in
camera parameters. Inspired by brilliant hand painting of
such panoramas in cel animation.

Artisitic Multiprojection Rendering (Agrawala et al.,
Eurographics Rendering Workshop 2000). Give each object
in a raytraced scene its own camera. Occlusion ordering
is controlled by a master camera and a set of constraints.
 Cubism and Cameras: Freeform Optics for Computer Graphics (Glassner, MSR tech report).
Explores a generalized cubist camera abstraction, where the
eye and view directions are represented by NURBS surfaces.
Lots of wonderful hand drawings of desired effects.

RYAN: Rendering your animation nonlinearly projected (Coleman and
Singh, NPAR 2004). Push the multiple perspectives offered by
cameras in the scene onto the scene itself by deforming the
geometry. Also explores the impact of the deformation on illumination.
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:
 E.H. Gombrich's The Sense of Order
 Owen Jones's The Grammar of Ornament
 Shubnikov and Koptsik's Symmetry in Science and Art
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.
 Most of the theory is given together with some examples
in Chapter 2 of
my PhD thesis.
 An excellent reference (as always) is Grünbaum and
Shephard's Tilings and Patterns.
 Again, Shubnikov and Koptsik's Symmetry in Science and
Art talks about many forms of symmetry and give lots
of excellent examples, some drawn from Jones's Grammar
of Ornament.
 A wonderful and very gentle introduction is David Farmer's
Groups and Symmetry: A Guide to Discovering Mathematics
.
 Washburn and Crowe's Symmetries of Culture is the
definitive treatise on the effect of place and time on the
use of symmetry. A great reference with lots of examples.
 David Joyce has a good web page about the
wallpaper
groups.

Kali is the classic online program for drawing pictures
within the discrete planar symmetry groups.
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.
 Abstract definition of a tiling of the plane.
 Normal tiling, which are a wellbehaved subset of all tilings,
more suitable for building ornamental patterns. Note that
normal tilings don't permit topologically degenerate tiles
(i.e., tiles with only two tiling vertices). Perhaps
for the purposed of ornament, the definition should be
relaxed slightly.
 Features of a tiling: tiling vertices, tiling edges, corners
and sides in a polygonal tiling, edgetoedge tilings.
 Regular uniform tilings. Vertex symbols as
notation for enumerating uniform tilings. Does the vertex
symbol uniquely determine the tiling? It's a tricky question.
 Monohedral, dihedral, khedral tilings. Prototiles.
 Symmetries of tilings. Periodic and nonperiodic tilings.
 The distinction between nonperiodic tilings and aperiodic tilings
(as given by Grübaum and Shephard). Penrose's aperiodic
sets P2 (kite and dart) and P3 (thin and thick
rhombs). A sketch of why these pairs of shapes only form aperiodic
tilings (based on the fact that in the limit, the ratio of
one shape to the other converges to an irrational number).
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
edgetoedge 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.
 In Cromwell's paper, he analyzes knotwork friezes in terms of
the 31 twosided frieze groups. He shows that only certain
groups can arise in knotwork, finds traditional examples, and
invents a few where none were found.
 In RIDT 1998, Cameron Browne had a paper about filling letterforms
with knotwork. His method is essentially an expression of Mercat's
tilebased construction, where he has an initial step that finds
a good tiling of the letterform by shapes that are close to squares
or equilateral triangles.
 Glassner wrote a series of three articles in IEEE CG&A about
knotwork. Among other things, he asks an interesting question:
what should knotwork look like in 3D? How should we represent
a 3D analogue of interlacing?
 In (Matthew) Kaplan and Cohen EGSR 2003 paper, they implement
Mercat's method and use it to create a bunch of designs. They
also work in some tools for incorporating zoomorphs (stylized
animal figures). One interesting feature is a relaxation algorithmmmm
for smoothing out curved strands in a pleasing way.
 I demonstrate Cromwell's method using Doug Zongker's excellent
Celtic Knot Thingy.
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.
 The key forms of Islamic ornament: calligraphy, stylized floral
designs, and star patterns (of course, there are others).
 Anatomy of a star pattern: planar maps and perfect crossings.
 Hankin's method (from E.H. Hankin's 1925 papers).
 Design elements: stars, rosettes, and extended rosettes.
 Template tilings.
 Star patterns in absolute geometry.
 CAD and star patterns.
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 Escherrelated
work in computer graphics by me and others. I talk mostly about
Escherization (monohedral, dihedral, skyandwater, aperiodic).
I also mention nonEuclidean Escher's work with nonEuclidean
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:
 Barb Meier's SIGGRAPH 1996 paper Painterly rendering
for animation
 Graftals, as covered in the SIGGRAPH 1999 "Dr. Seuss" paper
 Deussen and Strotthote's SIGGRAPH 2000 paper about illustration
of trees
 Image Analogies in SIGGRAPH 2001; I deliberately skipped
the topic of texture synthesis, although there is some
overlap with NPR.
 Mosaics: Hausner's SIGGRAPH 2001 paper and the SIGGRAPH 2002
Jigsaw Image Mosaics paper
 Floral ornament from SIGGRAPH 1997
 NonEuclidean geometry; I had hoped to have more time for
time subject, but it requires a number of lecture periods
to get it right.
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!