Non-Photorealistic Computer Graphics Library

Penrose Tiling

Author(s): Andrew Glassner.
Article: IEEE Computer Graphics and Applications, Vol. 18, No. 4, pp. 78--86, July/August, 1998.
[BibTeX]

Abstract:
Theme and variation are part of nature. Birdwatchers identify the species of a bird by its distinctive markings, even though the specific colors and shapes vary from one bird to the next. Every thunderclap sounds roughly like thunder, but each one is different. And of course snowflakes are beloved for the hexagonal symmetry they all share, as well as the delicate patterns unique to each one. In the May/June 1998 issue of IEEE CG&A I discussed the topic of aperiodic tiling for the plane. This technique helps us create patterns with lots of theme and variation, like the leaves on a tree. I’ll continue discussing the subject, so let’s first briefly summarize the main ideas from last time. The basic approach is to take a bunch of 2D shapes and impose rules on how they can connect, like the pieces of a jigsaw puzzle. Suppose that you have an infi- nite supply of these shapes, or tiles, and you cover the plane with them, out to infinity in all directions. You might be able to find a region of the pattern that you could pick up and use as a rubber stamp, and by stamping it out an infinite number of times (without rotating or scaling it), fill the plane with the identical design that you started with. So in essence you’ve reduced the original set of pieces and their interlocking rules to just many translated copies of a single, larger piece. If you can do this, then the overall pattern—and the set of tiles used to make it— are periodic. If you can’t find such a single, big piece that replicates the pattern by translation, the pattern is called nonperiodic. Many tiles can create both periodic and nonperiodic patterns, depending on how they’re laid down. If you happen to have a set of tiles that can only make nonperiodic patterns, and you can prove that’s the case, then you have an aperiodic set of tiles. The quest for aperiodic tiles has gone on for several decades. The first set discovered involved 26,000 tiles. In the last issue I discussed two far smaller sets of aperiodic tiles, named after their creators. These Robinson and Ammann tiles are based on squares, which make them very convenient for computer graphics applications like texture mapping and sampling. Here I’ll look at perhaps the most famous set of aperiodic tiles, discovered by Roger Penrose. Actually, Penrose found two distinct sets of aperiodic tiles, one called “kites and darts” and the other called “rhombs.” Each set is made of only two tiles. Let’s look at the kites and darts first.