Escherization

ABSTRACT

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.

REFERENCES

• 1: Howard Alexander, The computer/plotter and the 17 ornamental design types, Proceedings of the 2nd annual conference on Computer graphics and interactive techniques, p.160-167, June 25-27, 1975, Bowling Green, Ohio [doi>10.1145/563732.1138362]
• 2: Esther M. Arkin , L. Paul Chew , Daniel P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.209-216, March 1991 [doi>10.1109/34.75509]
• 3: Thaddeus Beier , Shawn Neely, Feature-based image metamorphosis, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.35-42, July 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, Aperiodic Tiling, IEEE Computer Graphics and Applications, v.18 n.3, p.83-90, May 1998 [doi>10.1109/38.674976]
• 10: Andrew Glassner, Penrose Tiling, IEEE Computer Graphics and Applications, v.18 n.4, p.78-86, July 1998 [doi>10.1109/38.689670]
• 11: Branko Grünbaum , G C Shephard, Tilings and patterns, W. H. Freeman & Co., New York, NY, 1986
• 12: GTK--. http ://gtkmm. sourceforge, net.
• 13: Douglas R. Hofstadter, Metamagical Themas: Questing for the Essence of Mind and Pattern, Bantam Books, Inc., New York, NY, 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 , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 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 , David H. Salesin, Computer-generated floral ornament, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.423-434, July 1998 [doi>10.1145/280814.280948]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

  J. Computer Applications
  J.5 ARTS AND HUMANITIES
      Subjects: Fine arts
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
Escher, morphing, optimization, simulated annealing, tesselations, tilings