“Escherization” by Kaplan and Salesin

This paper introduces and presents a solution to the “Escherization” problem: given a closed figure in the plane, find a new closed figure that is similar to the original and tiles the plane. Our solution works by using a simulated annealer to optimize over a parameterization of the “isohedral” tilings, a class of tilings that us flexible enough to encompass nearly all of Escher’s own tilings, and yet simple enough to be encoded and explored by a computer. We also describe a representation for isohedral tilings that allows for highly interactive viewing and rendering. We demonstrate the use of these tools—along with several additional techniques for adding decorations to tilings—with a variety of original ornamental designs.

1. Howard Alexander. The computer/plotter and the 17 ornamental design types. Proceedings of SIGGRAPH’75, pages 160-167, 1975.
2. E.M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell. An efficiently computable metric for comparing polygonal shapes. PAMI(13), pages 209-216, 1991.
3. Thaddeus Beier and Shawn Neely. Feature-based image metamorphosis. Proceedings of SIGGRAPH’92, pages 35-42, 1992.
4. William W. Chow. Automatic generation of interlocking shapes. Computer Graphics and Image Processing, 9:333-353, 1979.
5. William W. Chow. Interlocking shapes in art and engineering. Computer Aided Design, 12:29-34, 1980.
6. Andrew Crompton. Grotesque geometry, http://dspace, dial .pipex. com/crompton/Home, shtml.
7. Douglas J. Dunham. Creating hyperbolic escher patterns. In H.S.M. Coxeter et al., editor, M.C. Escher: Art and Science, pages 241-247. Elsevier Science Publishers B.V., 1986.
8. Andrew Glassner. Frieze groups. IEEE Computer Graphics and Applications, 16(3):78-83, May 1996.
9. Andrew Glassner. Andrew glassner’s notebook: Aperiodic tiling. IEEE Computer Graphics & Applications, 18(3):83-90, May- June 1998. ISSN 0272- 1716.
10. Andrew Glassner. Andrew glassner’s notebook: Penrose tiling. IEEE Computer Graphics & Applications, 18(4), July – August 1998. ISSN 0272-1716.
11. Branko Grfinbaum and G. C. Shephard. Tilings and Patterns. W. H. Freeman, 1987.
12. GTK–. http ://gtkmm. sourceforge, net.
13. Douglas Hofstadter. Metamagical Themas.” Questing for the Essence of Mind and Pattern. Bantam Books, 1986.
14. Daniel H. Huson and Olaf Delgado Friedrichs. Reptiles. ftp-//ftp. uni – biele feld. de/pub/math/t i i ing/rept i les/.
15. Hans Van Lemmen. Tiles.” 1000 Years of Architectural Decoration. Harry N. Abrams, Inc., 1993.
16. Raph Levien. libart, http://www, levien, com/libart/.
17. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical recipes in c: The art of scientific computing (2nd ed.). 1992. ISBN 0-521-43108-5. Held in Cambridge.
18. Doris Schattschneider. M.C. Escher: Visions of Symmetry. W.H. Freeman, 1990.
19. The GIMP toolkit, http ://www. gtk. org.
20. M.C. Escher (tran. Karin Ford). Escher on Escher: Exploring the Infinite. Henry N. Abrams, Inc., 1989.
21. Michael T. Wong, Douglas E. Zongker, and David H. Salesin. Computergenerated floral ornament. Proceedings ofSIGGRAPIt’98, pages 423-434, 1998.