CS 791 Lecture notes

These are notes and additional references that complete and augment the material presented in class. Note that the material is organized by "lecture topic" and not "class period".

Lecture 1: Introduction to ornament

I began the course with some general administrivia. All that information is spread around these web pages.

In previous grad courses, I've moved between the extremes of a "traditional" presentation of NPR techniques, and a more mathematical course on symmetry, patterns and tilings. This time around, the pendulum has swung in the mathematical direction. My aim to to begin with a few weeks of geometrically-oriented NPR techniques, and then move into symmetry and tilings. It might be possible to characterize the course broadly as "techniques for creating pleasing arrangements of small elements".


Lecture 2: Halftoning

Halftoning refers to a collection of algorithms that span traditional and non-photorealistic rendering. The original goal of halftoning was to approximate continuous tones on devices that can only support discrete tones (i.e., white dots on a black screen or black marks on a white page). While these algorithms matter less now for display devices (mind you, new display technologies tend to start out in black and white, e-ink being a contemporary example), they're still very important for printing. The ultimate reference for halftoning is Ulichney's book Digital Halftoning (MIT Press, 1987); see also his 2000 survey. The Strothotte and Schlechtweg textbook also contains a good deal of information about halftoning, with an eye towards adapting the algorithms to non-photorealistic rendering.

Lecture 3: NPR Packing

NPR Packing is the name I use to refer to a collection of techniques for assembling a layout of small elements in the plane, satisfying a set of geometric constraints. (I don't know how universal the name "NPR Packing" is, but others certainly use it too.) Mathematically, a packing is any arrangement of shapes in the plane that don't overlap (that is, all pairwise intersections are sets of zero area). We'll see packings again briefly when we talk about tiling theory.

Here's a high-level set of possible constraints you might want to satisfy:

Now at the outset, this is impossible. From theoretical computer science, we know that it's NP-hard to know whether a packing exists. From a pragmatic point of view, we're certainly not going to let that stop us! We're more concerned with aesthetics anyway, and are willing to relax the problem or construct sub-optimal solutions.

Photomosaics can be seen as being a kind of packing problem, but not really related to this course. The geometric constraints are trivial; the difficulties lie in rapid searching of a database of source imagery. Of course, the element-based halftoning methods of the previous lecture, such as stippling, are also packing processes. What else is possible?

Lecture 4: Procedural object distribution

This lecture might be considered as an addendum to the previous one: additional algorithms for covering the plane with graphic elements. I decided to separate out this topic because it seems to be developing its own independent momentum, and it's a promising area for future research.

I had a hard time nailing down exactly what I consider this topic to be, and why it's distinct from the previous one. My general feeling is that here we have a small set of distinct geometric primitives, together with a means of placing primitives in the plane in an arrangement that is not necessarily even. Whereas the packing techniques seem to be about achieving a tight overall packing of elements, here we're more concerned about local similarity of neighbourhoods relative to some specified growth rules or an exmaple.

Lecture 5: Introduction to symmetry theory

In this lecture, I begin with an informal view of symmetry, building up to a precise definition and an enumeration of the discrete symmetry groups in the plane.

Rather than write a set of detailed notes here, I'll include a list of useful references, many of which are available online.