Escherization

Escher was able to discover such tilings through a combination of natural ability and sheer determination. Can we automate the discovery of tilings by recognizable motifs? More formally, we pose the Escherization problem:

Given a shape S, find a new shape T such that:

1. T is as close as possible to S; and
2. Copies of T fit together to form a tiling of the plane.

We have developed an algorithm that can produce reasonable solutions to the Escherization problem. It is based on three large components:

• A parameterized space of tilings. We develop a parameterization of the space of isohedral tilings, a family of tilings that can express the designs Escher created. Every possible tile shape boils down to a sequence of real numbers. An interactive tool lets us modify these numbers in a natural way (corresponding to Escher manipulating drawings by hand). More importantly, we can direct the computer to search through possible sequences of numbers, trying to find good tilings by brute force.
• A comparison function for shapes. We can dial up a collection of tile shapes using the parameterization above. We need to know how well each of these tiles approximates the goal shape provided by the user. We use a metric from the computer vision literature that efficiently finds the L² distance between two polygons. Our objective then becomes to locate the particular tile shape that compares most favourably to the goal shape.
• An optimization algorithm. We need a meaningful strategy for sorting through the large shape of possible tile shapes for the best one (the one that's closest to the goal shape). We use a simulated annealing algorithm from Numerical Recipes. When suitably tuned, it tends to find good tile shapes without getting stuck in objectionable local minima.

Here are some images produced using Escherization. Click on each one for a full-size version.

A Plague of Frogs	Dogs; Dogs Everywhere
Tea-ssellation	Tux-ture Mapping
Twisted Sisters	Wiener Dog Art

Dihedral Escherization

Escher also created a number of dihedral tilings: designs featuring two different shapes. He was fond of these designs, since with more than one shape it was possible to tell a story, to have the shapes complement each other somehow.

The Escherization problem can be adapted in an obvious way to two goal shapes. We can also extend the space of tilings by including in the parameterization a path that splits an isohedral tile shape into two pieces. We compare the two pieces to the goal shapes and run the optimization as before, attempting to minimize the maximum of the two comparisons.

Gödel, Bach (Braided): An Eternal Escherization	Funky Chickens
The Owl and the Pussycat	Pen/Rose Tiling
Rembrandt and Mrs. van Rijn	Strange 'Tractors

Dihedral Escherization can also be exploited to create designs in the style of Escher's Sky and Water. We need to restrict the search to a narrower class of possible tiling types (what Dress calls “Heaven and Hell Patterns”). Once the desired tiling has been discovered the rest of the process is fairly easy, since we already have an association between a realistic, user-supplied goal shape and an abstract, more geometric tile shape. We just need to morph between those two extremes. Here's one example, based on Rembrandt and Mrs. van Rijn above.

Aperiodic Escherization

The Penrose tilings P2 (kites and darts) and P3 (thin and thick rhombs) can also be parameterized and fed to the Escherization system. It's much harder to discover satisfying results, because of the idiosyncratic shapes of the Penrose tiles. It's exciting to be able to produce these aperiodic pictures – Penrose and Escher were friends, but sadly Escher passed away before Penrose discovered P2 and P3. Penrose has asked what sorts of designs Escher would have been able to create from these tilings.

A Walk in the Park	Busby Berkeley Chickens
The Pentalateral Commission

You might enjoy playing with the edges of Penrose tiles to see whether you can produce recognizable shapes. I've created a Java applet that lets you do so interactively.

Non-Euclidean Escherization

Escher made four wonderful Circle Limit patterns, designs based on non-Euclidean geometry. Escher didn't have the mathematical background to manipulate hyperbolic patterns symbolically, but he certainly had the intuition necessary to create pictures of them.

Our Escherization algorithm cannot easily be translated into non-Euclidean geometry, for deep reasons having to do with the notion of shape, as used in the shape comparison metric. However, for some isohedral tiling types it is possible to transfer the output of Escherization from the Euclidean plane to the hyperbolic plane or to the surface of a sphere. The process is a kind of non-linear warp of a piece of the Escherized tiling.

Circle Limit V
Hyperbolic Teapots I	Hyperbolic Teapots II
Spheres on a Teapot, Teapots on a Sphere

Papers

• Escherization. SIGGRAPH 2000.
• Computer Graphics and Geometric Ornamental Design. PhD thesis, 2002. See especially Chapter 4.
• Dihedral Escherization. GI 2004.

Software

isohedral.ih (last updated: May 8th, 2002)

This file contains specifications for the representation and drawing of the 81 isohedral tilings realizable by unmarked tiles. Among other things, it provides the incidence symbol, a simple colouring, and a set of rules for deriving aspect transform matrices.

geo.py and params.py

These two files together provide a script for navigating the tiling vertex parameterizations of the isohedral tiling types. params.py contains a function for each unique parameterization, and can be used as a source from which to build your own library for parameterizing legal isohedral tiling polygons.

I have also made a Java applet that allows you to explore the space of Penrose tile shapes interactively. It's a fun way to play with this rather mysterious tiling. Most of the effort related to aperiodic tilings seems to be related to their combinatorial properties, without considering the actual shapes that can be produced. You can try the applet here.