CS 791 Lecture notes

Lecture 1: Introduction to ornament

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

Notes:

• A lot of the content of the lecture appears in the first few sections of my PhD thesis. See, in particular, my attempt to (loosely) define ornament and explain why it's different from art. I also said a bit about the history (and prehistory) of ornamental traditions, the turn towards modernism in the 20th century, and new opportunties for a revitalization of "ornamentalism" with the benefit of computer technology.
• My thoughts on the human compulsion to create ornament have evolved since 2002. My thesis focuses primarily on an explanation drawn from psychoaesthetics (the study of the neurophysiological basis for our appreciation of art).
• There are plenty of philosophical theories that attempt to explain our love of ornament. The idea of "Horror Vacui" (expressed optimistically by Gombrich as "Amor Infiniti") is an old one. It might also be argued that ornamentation gives a sense of human-level scale to monumental structures, helping them be less overwhelming to our perceptual systems.
• Another explanation might lie with Gestalt psychology. This theory explains how we see the world in terms of perceptual grouping mechanisms, and the aesthetic pleasure we find when we successfully group elements together. Ornamental patterns might be seen to provide a hook for those grouping mechanisms to be applied.

  A good graphics-oriented introduction to this topic is Frédo Durand's 2002 SIGGRAPH course.

• As always, I strongly encouraged everyone to listen to streaming versions of Ramachandran's 2003 Reith lectures, particularly "The Artful Brain" and "Purple Numbers and Sharp Cheese".
• Since the time of my thesis, I have tried to cast the question of our response to ornament in terms of information theory. I haven't found much published on the relationship between art and information theory (there's probably an opportunity to do some new writing here), but this essay by Jim Bumgardner has many overlaps with some of my thinking on the subject. His essay attempts to account for information in an image based on a Shannon-style measurement; I find that the more recent idea of Kolmogorov complexity provides a more suitable metaphor for thinking about art and information theory.
• In the lecture I hypothesized (as did Jim Bumgardner in his essay) that there might be an "informational sweet spot" in art and ornament. Too little information in a visual stimulus might not hold one's attention; on the other hand, too much information might be dismissed as noise. As Gombrich says, "Delight lies somewhere between boredom and confusion". We might also find some relevant ideas in Frances Hutcheson's notion of "uniformity amidst variety" (from Inquiry into the Original of Our Ideas of Beauty and Virtue, published in 1725!).
• I couldn't leave this lecture without also saying something about neurology. We're hard-wired to detect symmetry (particularly bilateral mirror symmetry), and it's natural to conclude that we'd get some sort of positive aesthetic feedback from symmetric stimuli.

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.

• The simplest halftoning algorithm is thresholding: set a colour to black or white depending on whether its luminance is below or above some threshold. This produces pretty bad results. Note that while it's natural to set the threshold to 50% grey, you can do marginally better to choose the threshold so that half the image pixels are white and half are black.

  In adaptive thresholding, a threshold for each pixel is computed as the mean tone of the pixels in a neighbourhood around it. This algorithm is good at factoring out broad changes in tone, but still not very artistic.

  I mentioned in passing that my former student Jie Xu and I created an artistic thresholding algorithm designed for non-photorealistic illustration.

• Thresholding gives poor results because a single pixel can't make a very good tone reproduction decision in isolation. We can do better by converting pixels in NxN blocks. We can then define M=N²+1 matrices of black and white pixels, and convert blocks of NxN pixels from the source image by subdividing the luminance range into M corresponding intervals. This is called ordered dithering. Dithering produces a lot of structured artifacts, which Strothotte and Schlechtweg claim can be harnessed for NPR. You can tradeoff between image detail and tone reproduction by varying the size of the blocks.
• When dithering, every decision to turn a pixel black or white introduces some approximation error (unless the source image tone is pure black or white!). We can attempt to account for that error by passing it on to nearby pixels that have not yet been processed. When processing a pixel, we calculate the approximation error after having set it to black or white, and divide that error among the pixel's unprocessed neighbours. This technique is known as error diffusion dithering, and it produces far fewer artifacts than ordered dithering. The Floyd-Steinberg algorithm is by far the most well known error diffusion algorithm, but the question of how best to distribute error is still an active area of research.
• Conceptually, screening is a bit like using an arbitrary greyscale image in the place of the dither matrices in ordered dithering. When placed atop an image, the greyscale screen is treated as a spatially varying threshold used to convert individual source pixels. A good screen will tend to contain a uniform distribution of threshold values in any region of the plane (this obviously becomes impossible for small regions). Screens are practical for artistic purposes, since they offer a lot more control over the pattern used for halftoning.

  You can visualize the screening process using height fields: draw the source image as an inverted black height field and the screen as a white height field. When drawn on top of each other, the screen height field will only allow black pixels to be shown that are locally darker than the screen at that point. In class I showed a demo that worked in exactly this way, using the OpenGL depth buffer to perform screening.

  Victor Ostromoukhov has two excellent papers on artistic uses of screening. In Digital Facial Engraving (Ostromoukhov, SIGGRAPH 1999), he develops an algebra of screens based on patterns of lines that simulate copperplate engraving, and warps them to create engraved portraits. In Artistic Screening (Ostromoukhov and Hersch, SIGGRAPH 1995), he and Roger Hersch show to achieve fine-grained control over screen shapes by allowing a designer to "keyframe" a screen at a small set of grey levels and interpolating between those levels to achieve continuous tone reproduction.

• Stippling also involves the placement of black marks on a white background, but the marks are no longer constrained to a pixel grid. It's an important illustration technique in the sciences, useful for its ability to convey shape, tone and texture simultaneously in black and white.

  I first talked about Floating Points: A Method for Computing Stipple Drawings (Deussen et al., Eurographics 2000). They create an initial stipple distribution within a region using dithering, then relax the distribution into one that is more evenly spaced using Lloyd's method (which will figure into many techniques in the first part of this course). They offer a variety of clever brush-like tools for modifying the positions and attributes of the resulting stipples.

  Weighted Voronoi Stippling (Secord, NPAR 2002) is a refinement of the previous technique that requires no user intervention. The stippling algorithm uses a weighted variant of Lloyd's method in which stipples relax into a distribution that is evenly spaced but also denser where a source image is darker, and sparser where it is lighter. I really like Secord's paper. It produces attractive results in a natural way. Weighted Voronoi Stippling is the subject of the first assignment in this course.

  We might ask whether computer-generated stippling patterns resemble hand-drawn patterns, and whether that matters. More generally, non-photorealistic rendering is lacking a tradition of evaluation of results. That's obviously difficult when the algorithms are created in the pursuit of art, but surely the field can offer something better than "I looked at the results and I liked them". In the context of stippling, there have been a few attempts to study human-generated stippling patterns and the difference between hand-drawn and computer-generated art. In Non-Photorealistic Rendering in Context: An Observational Study (Isenberg et al., NPAR 2006), they report on a user study in which they had participants look at both kinds of images and sort them into piles based on criteria of their choosing. In a series of papers Isenberg and his collaborators used statistical measures to quantify differences between hand-drawn and computer-generated stipple patterns, and attempted to create stippled images the mimic the style of specific human stipplers.

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:

• Use elements to approximate the shapes of regions in the plane
• Approximate the tone or colour of some source image
• Minimize the gaps (and eliminate overlaps)
• Make the "grout" as even as possible
• Construct a true tilings (no gaps, no overlaps)
• Find suitable orientations of elements
• Find suitable deformations of elements

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?

• Beyond Stippling—Methods for Distributing Objects on the Plane (Hiller, Hellwig and Deussen, Eurographics 2003) presents a stippling-like element distribution technique similar to Weighted Voronoi Stippling. Voronoi diagrams generalize naturally from point generators to arbitrary geometry. Now, the geometric algorithms for computing non-point Voronoi diagrams are very complicated. Fortunately, the discrete version based on GPU computation is just as easy. This observation leads to a natural extension of Lloyd's method to area-based primitives, produced a CAVD (Centroidal Area Voronoi Diagram).

  Non-trivial elements have non-trivial orientation. The authors suggest orienting elements relative to a user-supplied vector field, or orienting each element relative to the estimated orientation of its enclosing Voronoi region.

• Animosaics (Smith, Liu and Klein, SCA 2005) is similar to the paper above. They suggest generating an orientation field for elements based on container boundaries, to make sure that elements align themselves well to represent container shapes. Each element can have a set of "equivalent orientations" that can all be tried to find a best fit. They also adapt the algorithm to animated packings (hence the name). They describe several techniques for pushing elements around to represent container motion between frames. The results are fairly convincing, given the fundamentally discrete nature of the problem.
• Most recently, A spectral approach to NPR packing (Dalal et al., NPAR 2006) offer a relaxation algorithm that isn't based on centroids, but on creating even grout. They define a measurement of "unevenness" based on a least-squares measurement of the distance from the element boundary to the boundary of its Voronoi region. It turns out that the element translation that minimized this measurement can be computed efficiently using the FFT (sexy!). The extra performance lets the authors explore natural ideas such as optimizing over a large set of possible element orientations, and some special packing effects.
• One sub-area of NPR packing is the question of how to simulate traditional Roman mosaics. An early attempt is Simulating Decorative Mosaics (Hausner, SIGGRAPH 2001). The idea is clever: run Lloyd's method using the Manhattan (L¹) metric instead of the usual Euclidean (L²) metric. This change is easily accomplished on the GPU by rendering square-based pyramids instead of circular cones. This variant on Lloyd's method will tend to converge to Voronoi cells that are squarish instead of hexagonal, and which can then be filled with mosaic tiles. The pyramids can be rotated to produce a layout of oriented mosaic tiles.

  There have been a few recent papers that have applied a more careful understanding of real mosaic construction in their simulations. In Rendering Traditional Mosaics (Elber and Wolberg, The Visual Computer 2003), the authors place mosaic tiles in channels defined by offset curves, leading to much more even grout. In A Novel Technique for Opus Vermiculatum Mosaic Rendering (Battiato et al., WSCG 2006), the offset curves are only computed in the foreground, and oriented tiles are laid atop a regular grid in the background (a traditional technique known as opus vermiculatum). They also trim tiles that overlap offset curves or other tiles.

• I wrapped up the lecture with a few odds and ends. I direct you to Jigsaw Image Mosaics (Kim and Pellacini, SIGGRAPH 2002), 3D Collage: Expressive Non-Realistic Modeling (Gal et al., NPAR 2007), and Calligraphic Packing (Xu and Kaplan, GI 2007).

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.

• In Computer-Generated Floral Ornament (Wong, Zongker and Salesin, SIGGRAPH 1998), the authors present a technique for creating stylized floral arrangements in a container region of the plane, in the style of designers such as William Morris. The system consumes space in an initially empty container by repeatedly searching for large, empty regions and allowing placed elements on the boundary of those regions to apply a growth rule to extend into them.
• In the past decade there has been a new set of research papers that explore procedural element arrangement by example. In the world of images, texture synthesis includes many well-known techniques for generating a large patch of pixels from a small samples in a way that preserves the sample's statistical properties. Can such an example-based approach be extended to geometry?

  Stroke pattern analysis and synthesis (Barla et al., Eurographics 2006) studies the problem of example-based geometric texture synthesis. Given an arbitrary set of vector strokes, they first "cluster" the strokes into disjoint elements (a flower, for example, might comprise a handful of strokes). Then, they construct a Delauney triangulation of element centres. This triangulation can now act like the raster grid in image-based texture synthesis. They place elements from the source pattern at the vertices of any new triangulation by finding suitable neighbourhoods in the source from which to copy. This technique works well for patterns made from large numbers of small, evenly-spaced elements.

• The more recent paper An example-based procedural system for element arrangement (Ijiri et al., Eurographics 2008) combines ideas from the previously mentioned papers from Wong, Zongker and Salesin and Barla et al. They also build a statistical model of element arrangement based on Delauney triangulation. However, instead of generating a new triangulation from scratch and copying elements onto its vertices, they "grow" the new triangulation neighbourhood by neighbourhood by copying neighbourhoods from the example input. This gives them finer-grained control over a wider range of regularity, including completely regular input textures. They also include some tricks to control element rotation and to constrain the result to a container region.
• One paper not covered in class, but still probably worth a look, is Appearance-guided synthesis of element arrangements by example (Hutut et al., NPAR 2009). They perform a more sophisticated analysis of the source texture, based on results from computer vision.

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.

• The text that parallels my in-class presentation most closely must perforce be my textbook. Chapter 3 covers introductory symmetry theory.
• An older and slightly different presentation appears in Chapter 2 of my PhD thesis.
• If you'd like a gentle introduction to symmetry theory from an elementary perspective, I recommend Farmer's Groups and symmetry: a guide to discovering mathematics. A more recent text that starts from scratch and can take you to whatever depth you want is The symmetries of things by Conway, Burgiel and Goodman-Strauss. This book presents a comprehensive theory of symmetry (and, to some extent, tilings), in terms of orbifolds. This is a much more topological and less algebraic view of symmetry which appears quite naturally to one's geometric intuition.
• Symmetries of Culture by Washburn and Crowe is a classic book that demonstrates the use of symmetric design by cultures all over the world. The mathematical background in that book is useful as well. It provides handy flowchart-based algorithms for classifying patterns according to their symmetry groups, and the appendices contain excellent proofs of some of the core facts needed in establishing the classification.
• Victor Ostromoukhov's paper Mathematical tools for computer-generated ornamental patterns (RIDT 1998) provides a solid infrastructure for using many of the properties of symmetric designs in the context of computer graphics.
• A simple, classic program for playing with planar symmetry is Kali, originally created by The Geometry Center. It lets you draw patterns of coloured lines, and replicates the lines according to a finite or wallpaper symmetry group. More fully featured is Tess, by Pedagoguery Software.
• I also briefly covered extended forms of symmetry, most importantly counterchange symmetry and coloured symmetry. I discuss these topics briefly in my book. You might also find more information in Grünbaum and Shephard's Tilings and Patterns (W.H. Freeman, 1987). Symmetry in Science and Art by Shubnikov and Koptsik (Plenum Press, 1974) contains a very detailed discussion of symmetry in many forms and spaces.

Lecture 6: Celtic knotwork

This lecture discussed Celtic art, with a focus on knotwork and the paper by Cromwell connecting Celtic friezes with two-sided symmetry groups.

• I began with some historical examples from classic sources such as the Book of Kells and the Lindisfarne Gospels. Several of those sources (which seem to be hard to find) are reproduced by Jones in Grammar of Ornament, but based on Bain's grumbling, perhaps they should be taken with a grain of salt ("The above two examples show gross travesties of Pictish art in publications that have been the chief sources of information available to students and others in the libraries of the universities and art colleges of the civilised world, for the past fifty years.") I'm not aware of any particularly good online resources for Celtic design, though I did recently discover a complete reproduction of the Lindisfarne Gospels.
• I went through the most popular knotwork construction technique, based on J. Romilly Allen's "modified plaitwork" approach. This approach was refined by George Bain and later by his son Iain Bain. Many good examples appear in George Bain's Celtic art: the methods of construction (Dover, 1973). The book is fun to read -- Bain grumbles often about the mistakes in previous reproductions of Celtic art (see the quote above).
• The primary inspiration for the lecture was Celtic knotwork: mathematical art by Peter Cromwell (The Mathematical Intelligencer 15(1):36-47). The paper introduces Romilly Allen's method, and discusses some of the mathematical properties of Celtic friezes, most importantly which of the two-sided frieze groups can (and do) arise naturally. (The two-sided frieze groups are more-or-less the equivalent of the counterchange frieze groups mentioned in the symmetry lecture.) The paper's results can be used as a prescription for an algorithm to design Celtic friezes belonging to any legal two-sided frieze group.
• Mercat's method can be seen as a generalization of the grid-based approaches used above to an arbitrarily planar map. The notion of break markers carries over naturally; the trickier part is getting the strands to look good when you move away from fixed grids of squares. This web page is quite popular and has been translated into several languages.
• Andrew Glassner wrote three columns for IEEE Computer Graphics & Applications. (September 1999, November 1999, January 2000). The first of these is a recapitulation and implementation of Bain's work, and provides more than enough details to complete the assignment, including suggested curves for tiles. The second discusses a technique analogous to Mercat's. The third (which, annoyingly, doesn't seem to be accessible online) muses about possible extensions of the notion of Celtic knotwork to 3D.
• Matthew Kaplan (no relation) has also done some research on Celtic knotwork. Computer generated Celtic design (Kaplan and Cohen, EGSR 2003) uses Mercat's method to produce novel knots and decorates those knots with zoomorphs (stylized animal forms). A later paper, Pattern oriented remeshing for Celtic decoration (Kaplan, Praun and Cohen, Pacific Graphics 2004) tries to construct Celtic knots over 3D meshes. (Compare this with my more recent paper Semiregular patterns on surfaces (Kaplan, NPAR 2009), which is capable of creating many of the same designs with lower distortion.
• I briefly covered Cameron Browne's paper Font Decoration and Automatic Mesh Fitting (RIDT 1998), which filled arbitrary letterforms with knotwork. Some additional images appear here.
• I closed by mentioning briefly other forms of Celtic art, namely spiral designs and key patterns. From a computer graphics point of view, there's lots of research that can be done in these areas. For key patterns, I'll mention Iain Bain's book Celtic Key Patterns (Constable, 1993), which also reproduces some earlier work by J. Romilly Allen. Doug Dunham also has a short paper about hyperbolic key patterns. Finally, there's a reproduced page from a Celtic manuscript on display in the bottom floor of the CEIT building.

Lecture 7: Introduction to tiling theory

Tiling theory is a beautiful branch of mathematics, but one whose technical details you are unlikely to encounter unless you seek them out. It combines the elegance and intuition of geometry with complex results from algebra and analysis, and offers a wide range of simply stated but deep open problems. How fortunate that you chose to take this course!

This introductory lecture on the subject comes more or less verbatim from Chapter 2 of my book. You might also find some useful text in Chapter 2 of my thesis. Needless to say, the true bible of tiling theory (and, indeed, one of the most wonderful math textbooks I have ever encountered) is Tilings and Patterns, by Grünbaum and Shephard. Amazon still lists this book as coming back into print on April 15th of 2010. Buy a copy as soon as it's available. You won't regret it.

Lecture 8: Polygonal tilings

Most of tiling theory can be understood in terms of tilings by polygons, and many interesting classifications become possible when we restrict out attention to polygons of specific types. This lecture develops the language needed to talk about polygonal tilings, and presents several well known families: the regular, Archimedean (semi-regular) and Laves tilings. That material is all in Chapter 4 of my book. I also briefly mention tilings that include star polygons and non-edge-to-edge tilings by regular polygons of several distinct sizes. These two topics are very promising for their decorative possibilities. See Chapter 2 of Grünbaum and Shephard for details.

Lecture 9: Islamic star patterns

Islamic art is one of the world's great ornamental traditions. This lecture introduces Islamic art in general, and the mathematics of Islamic star patterns in particular. We don't have a great deal of information on how these patterns were originally constructed, but there are a few scattered hints, such as the Topkapi Scroll. And of course, we have lots of sophisticated modern mathematical techniques to draw from.

I introduce E.H. Hankin's "polygons-in-contact" technique, in which a polygonal tiling is chosen and rays are grown at a fixed contact angle out from the midpoint of every edge. The rays are cut off when they encounter other rays. Clearly, regular polygons will develop star-shaped motifs. The trick is to generalize the process to other polygon tiles. I describe one approach in Islamic star patterns from polygons in contact. That paper also discusses a couple of extra tricks to handle stars with extra layers of geometry and two-point patterns.

Where do the tilings come from? To construct interesting star patterns, we start with tilings containing many regular polygons as tiles. These tilings are described in Islamic star patterns in absolute geometry. That paper generalizes the construction process to Euclidean and non-Euclidean geometry in a way that's beyond the scope of the lecture.

In many star patterns, we find a recurring geometrical figure called a rosette. I discuss two approaches to constructing rosettes. The first is to develop an explicit construction for them inside regular polygons. I discuss A.J. (Tony) Lee's construction method from his 1987 paper Islamic star patterns. The other approach is to use the polygons in contact method, but rely on the underlying tiling to produce rosettes as a by-product. This is discussed in the polygons in contact paper mentioned above.

I conclude by mentioned some of the great work that has been done on the subject of Islamic star patterns.

• In Grünbaum and Shephard's Interlace patterns in Islamic and Moorish art (Leonardo, 1992), they explore what geometric properties of a pattern can be deduced from its restriction to a single fundamental region.
• A.K. Dewdney (briefly a professor here) considered the construction of star patterns by drawing line segments connecting symmetrically arranged points on a regular arrangement of circles. (See his book The Tinkertoy Computer for a reprint of the essay.) See also Dispot's software Arabeske Studio, which is based on Dewdney's method (or at least I believe it was initially).
• Jay Bonner is an architectural ornamentalist who has worked on some of the great monuments of Islamic art. He has produced some wonderful designs from unusual combinations of stars (see, for example, his design with 6, 7, 8 and 12-pointed stars. He has also created amazing multi-level designs.
• Jean-Marc Castéra has studied the Moroccan tradition of star pattern design extensively, particularly the fountains in cities such as Fez that feature a massive central star with as many as 96 points, surrounded by peripheral stars with local eightfold symmetry. See especially his book Arabesques: Decorative Art in Morocco.
• A few more references. When studying star patterns, it's helpful to grab a copy of Bourgoin's drawings, reprinted by Dover as Arabic Geometrical Pattern and Design. See also the lovely paintings by Achille-Constant-Théodore-Émile Prisse d'Avennes (!), collected in a couple of lovely books. There's also an excellent online photo collection by David Wade, and Brian Wichmann's site contains many computer illustrations of star patterns (and lots of other tilings besides).

Lecture 10: Isohedral tilings

I develop the theory of isohedral tilings, which are both highly expressive and capable of an efficient implementation. The lecture is taken more or less directly from Chapter 5 of my book. Lots more detail can be found in Tilings and Patterns, particularly Section 6.2, though you should also look through Sections 2.7 and 4.3 as background. I build up to a complete description of the shapes of isohedral prototiles, sufficient to implement a data structure that represents them.

As part of the lecture, I take a side trip through the world of anisohedral prototiles. These complex shapes admit periodic tilings of the plane, but none that are isohedral. A good resource for this subject is Paul Church's Master's thesis Snakes in the Plane. See also Joseph Myers's excellent page reporting the results of his exhaustive searches for polyominoes with interesting tiling properties.

Lecture 11: M.C. Escher

I take a tour through Escher's artistic legacy, with an emphasis on his tessellations and the development of his "layman's theory". The layman's theory is certainly interesting from a historical point of view, though today we can simply rely on the isohedral tilings, which subsume his theory.

Just about any Escher book will give you a rich source of beautiful pictures to look at. Schattschneider's book Visions of Symmetry (Harry N. Abrams, second edition, 2004) is the essential reference for Escher's tessellation drawings and his layman's theory. See also the comprehensive reference M.C. Escher: His Life and Complete Graphic Work by Bool et al. (Harry N. Abrams, 1992) and the more recent The Magic of M.C. Escher by Locker (Harry N. Abrams, 2000).

I then move on to discuss the Escherization algorithm and its successor, dihedral Escherization. Both techniques are described on a page about the project.

Lecture 12: Nonperiodic tilings

There are many wonderful mathematical and aesthetic possibilities to explore in the world of nonperiodic tilings. I begin by making clear the distinction between nonperiodic and aperiodic. In the former case, even if any individual tiling is complex, it might be composed from tiles that could easily be rearranged into a simpler (periodic) tiling. An aperiodic tiling is one whose tiles must necessarily admit only nonperiodic tilings. It wasn't known until the sixties that aperiodic tilings could even exist.

I start by showing some examples of spiral tilings, as presented in Section 9.5 of Tilings and Patterns. Voderberg's modified isosceles triangle admits many interesting spiral tilings, and also answers an old geometry question: can a shape be completely surrounded by two copies of itself? There are many other interesting spiral tilings to be found. See, for example, Paul Gailiunas's fun paper on the subject.

I then move on to overlay tilings. Overlay tilings are a method for creating new irregular arrangements of polygons by superimposing the duals of multiple tilings and then dualizing the superposition. A good reference on the subject is Zongker's paper Creation of overlay tilings through dualization Of regular networks (ISAMA 1999). See also the Stampfli paper cited in that paper.

The main event is substitution tilings and rep-tiles, discussed in detail in Section 6.1 of my book (see also Section 10.1 of Tilings and Patterns, though that book doesn't talk much about substitution tilings). There are a lot of open questions in this area, as well as ideas for computational techniques. A large collection of substitution tilings can be found in the Tilings Encyclopedia maintained by Harriss and Frettlöh. For a lot of mathematical discussion of substitution tilings, see the Primer by Natalie Priebe Frank, not to mention the many other lovely examples and papers on her home page. You'll also probably find good references and examples on Chaim Goodman-Strauss's home page (but I can't verify that because it's down right now).

---

Craig S. Kaplan

Last updated: