Computer Graphics and Geometric Ornamental Design
Craig S. Kaplan: Computer Graphics and Geometric Ornamental Design. Ph.D. Thesis, University of Washington, 2002.
Throughout history, geometric patterns have formed an important part of art and ornamental design. Today we have unprecedented ability to understand ornamental styles of the past, to recreate tradi- tional designs, and to innovate with new interpretations of old styles and with new styles altogether. The power to further the study and practice of ornament stems from three sources. We have new mathematical tools: a modern conception of geometry that enables us to describe with precision what designers of the past could only hint at. We have new algorithmic tools: computers and the abstract mathematical processing they enable allow us to perform calculations that were intractable in previous generations. Finally, we have technological tools: manufacturing devices that can turn a synthetic description provided by a computer into a real-world artifact. Taken together, these three sets of tools provide new opportunities for the application of computers to the analysis and creation of ornament. In this dissertation, I present my research in the area of computer-generated geometric art and ornament. I focus on two projects in particular. First I develop a collection of tools and methods for producing traditional Islamic star patterns. Then I examine the tesselations of M. C. Escher, developing an “Escherization” algorithm that can derive novel Escher-like tesselations of the plane from arbitrary user-supplied shapes. Throughout, I show how modern mathematics, algorithms, and technology can be applied to the study of these ornamental styles.
 Jan Abas. A hyperbolic mural. http://www.bangor.ac.uk/~mas009/ppic7.html. 404
 Syed Jan Abas and Amer Shaker Salman. Symmetries of Islamic Geometrical Patterns. World Scientific, 1995.
 Steve Abbott. Steve Abbott’s computer drawn Celtic knotwork. http://www.abbott.demon.co.uk/knots.html. 404
 Maneesh Agrawala and Chris Stolte. Rendering effective route maps: Improving usability through generalization. Proceedings of SIGGRAPH 2001, pages 241–250, 2001.
 Nina Amenta and Mark Phillips. Kali. http://www.geom.umn.edu/java/Kali/. 404
 E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell. An efficiently computable metric for comparing polygonal shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13:209–216, 1991.
 George Bain. The Methods of Construction of Celtic Art. Dover, 1973.
 Thaddeus Beier and Shawn Neely. Feature-based image metamorphosis. Proceedings of SIGGRAPH’92, pages 35–42, 1992.
 John Berglund. Anisohedral tilings page. http://www.angelfire.com/mn3/anisohedral/
 John Berglund. Is there a k-anisohedral tile for k ≥ 5? American Mathematical Monthly, 100:585–588, 1993.
 Jinny Beyer. Designing Tesselations: The Secrets of Interlocking Patterns. Contemporary Books, 1999.  Jay Bonner. Geodazzlers. http://www.dstoys.com/GD.html. 404
 Jay Francis Bonner. Islamic Geometric Patterns: Their Historical Development and Tradi- tional Methods of Derivation. Unpublished, 2000.
 Roberto Bonola. Non-Euclidean Geometry. Dover Publications, 1955.201
 F. H. Bool, J. R. Kist, J. L. Locher, and F. Wierda. M. C. Escher: His Life and Complete Graphic Work. Harry N. Abrams, Inc., 1992.
 J. Bourgoin. Arabic Geometrical Pattern and Design. Dover Publications, 1973.
 Cameron Browne. Font decoration by automatic mesh fitting. In R.D. Hersch, J. Andr, and H. Brown, editors, Electronic Publishing, Artistic Imaging, and Digital Typography, pages 23–43. Springer Verlag, 1998.
 Paul Burchard, Daeron Meyer, and Eugenio Durand. Quasitiler. http://www.geom.umn.edu/apps/quasitiler/.
 Jean-Marc Cast ́era. Arabesques: Decorative Art in Morocco. ACR Edition, 1999.
 Jean-Marc Cast ́era. Zellijs, muqarnas and quasicrystals. In Nathaniel Friedman and Javiar Barrallo, editors, ISAMA 99 Proceedings, pages 99–104, 1999.
 William W. Chow. Automatic generation of interlocking shapes. Computer Graphics and Image Processing, 9:333–353, 1979.
 Archibald Christie. Traditional Methods of Pattern Designing. Oxford University Press, 1929.
 Alain Connes. Noncommutative Geometry. Academic Press, San Diego, 1994.
 H. S. M. Coxeter. Coloured symmetry. In H. S. M. Coxeter et al., editor, M.C. Escher: Art and Science, pages 15–33. Elsevier Science Publishers B.V., 1986.
 H. S. M. Coxeter. Non-Euclidean Geometry. Mathematical Association of America, sixth edition, 1998.
 H. S. M. Coxeter and W. O. J. Moser. Generators and Relations for Discrete Groups. Springer-Verlag, 1980.
 Keith Critchlow. Islamic Patterns: An Analytical and Cosmological Approach. Thames and Hudson, 1976.
 Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy. Unsolved Problems in Geometry. Springer-Verlag, 1991.
 Peter R. Cromwell. Celtic knotwork: Mathematical art. The Mathematical Intelligencer, 15(1):36–47, 1993.202
 L. Danzer, B. Gr ̈unbaum, and G. C. Shephard. Can all tiles of a tiling have five-fold symme- try? American Mathematical Monthly, 89:568–585, 1982.
 Prisse d’Avennes. Arabic Art. L’Aventurine, 2001.
 Doug DeCarlo and Anthony Santella. Stylization and abstraction of photographs. Proceed- ings of SIGGRAPH 2002, pages 769–776, 2002.
 Olaf Delgado, Daniel Huson, and Elizaveta Zamorzaeva. The classification of 2-isohedral tilings of the plane. Geometricae Dedicata, 42:43–117, 1992.
 Olaf Delgado-Friedrichs. Data structures and algorithms for tilings. To be published in Theoretical Computer Science.
 Tony DeRose, Michael Kass, and Tien Truong. Subdivision surfaces in character anima- tion. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques (SIGGRAPH’98), pages 85–94. ACM Press, 1998.
 A.K. Dewdney. The Tinkertoy Computer and Other Machinations, pages 222–230. W. H. Freeman, 1993.
 Robert Dixon. Two conformal mappings. In Michele Emmer, editor, The Visual Mind: Art and Mathematics, pages 45–48. MIT Press, 1993.
 Andreas W. M. Dress. The 37 combinatorial types of regular “Heaven and Hell” patterns in the euclidean plane. In H. S. M. Coxeter et al., editor, M.C. Escher: Art and Science, pages 35–45. Elsevier Science Publishers B.V., 1986.
 Douglas Dunham. Hyperbolic symmetry. Computers and Mathematics with Applications, 12B(1/2):139–153, 1986.
 Douglas Dunham. Artistic patterns in hyperbolic geometry. In Reza Sarhangi, editor, Bridges 1999 Proceedings, pages 139–149, 1999.
 Douglas Dunham. Hyperbolic Islamic patterns — a beginning. In Reza Sarhangi, editor, Bridges 2001 Proceedings, pages 247–254, 2001.
 Douglas Dunham, John Lindgren, and David Witte. Creating repeating hyperbolic patterns. Computer Graphics (Proc. SIGGRAPH), pages 215–223, 1981.
 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.203
 David S. Ebert, F. Kenton Musgrave, Darwyn Peachey, Ken Perlin, and Steven Worley. Tex- turing and Modeling. AP Professional, 1998.
 David Eppstein. The geometry junkyard: Penrose tiling. http://www.ics.uci.edu/~eppstein/junkyard/penrose.html.
 David B. A. Epstein, J .W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston. Word Processing in Groups. Jones and Bartlett, 1992.
 Bruno Ernst. The Magic Mirror of M. C. Escher. Ballantine Books, New York, 1976.
 George A. Escher. M.C. escher at work. In H. S. M. Coxeter et al., editor, M.C. Escher: Art and Science, pages 1–8. Elsevier Science Publishers B.V., 1986.
 M. C. Escher. Escher on Escher: Exploring the Infinite. Henry N. Abrams, Inc., 1989. Translated by Karin Ford.
 Richard L. Faber. Foundations of Eucliedean And Non-Euclidean Geometry. Marcel Dekker, Inc., 1993.
 Michael Field and Martin Golubitsky. Symmetry in Chaos. Oxford University Press, 1992.
 Franc ̧ois Dispot. Arabeske home page. http://www.wozzeck.net/arabeske/index.html.
 The gimp. http://www.gimp.org/.
 Andrew Glassner. Andrew Glassner’s notebook: Aperiodic tiling. IEEE Computer Graphics & Applications, 18(3):83–90, may–jun 1998. ISSN 0272-1716.
 Andrew Glassner. Andrew Glassner’s notebook: Penrose tiling. IEEE Computer Graphics & Applications, 18(4), jul–aug 1998. ISSN 0272-1716.
 Andrew Glassner. Andrew Glassner’s notebook: Celtic knots, part II. IEEE Computer Graph- ics & Applications, 19(6):82–86, nov–dec 1999. ISSN 0272-1716.
 Andrew Glassner. Andrew Glassner’s notebook: Celtic knotwork, part I. IEEE Computer Graphics & Applications, 19(5):78–84, sep–oct 1999. ISSN 0272-1716.
 Andrew Glassner. Andrew Glassner’s notebook: Celtic knots, part III. IEEE Computer Graphics & Applications, 20(1):70–75, jan–feb 2000. ISSN 0272-1716.
 Solomon W. Golomb. Polyominoes: Puzzles, Patterns, Problems and Packings. Princeton University Press, second edition, 1994.204
 E. H. Gombrich. The Sense of Order: A Study in the Psychology of Decorative Art. Phaidon Press Limited, second edition, 1998.
 Chaim Goodman-Strauss. A small set of aperiodic tiles. European Journal of Combinatorics, 20:375–384, 1999.
 Marvin J. Greenberg. Euclidean and Non-Euclidean Geometries: Development and History. W. H. Freeman and Company, third edition, 1993.
 Bathsheba Grossman. Bathsheba Grossman – sculpting geometry. http://www.bathsheba.com/.
 Branko Gr ̈unbaum. The emperor’s new clothes: Full regalia, G string, or nothing? Mathematical Intelligencer, 6(4):47–53, 1984.
 Branko Gr ̈unbaum. Periodic ornamentation of the fabric plane: Lessons from Peruvian fab- rics. Symmetry, 1(1):45–68, 1990.
 Branko Gr ̈unbaum. Levels of orderliness: Global and local symmetry. In I. Hargittai and T. C. Laurent, editors, Symmetry 2000, pages 51–61. Portland Press, London, 2002.
 Branko Gr ̈unbaum and G. C. Shephard. Spherical tilings with transitivity properties. In Chan- dler Davis, Branko Gr ̈unbaum, and F. A. Sherk, editors, The Geometric Vein: The Coxeter Festschrift, pages 65–94. Springer-Verlag, New York, 1982.
 Branko Gr ̈unbaum and G. C. Shephard. Tilings and Patterns. W. H. Freeman, 1987.
 Branko Gr ̈unbaum and G. C. Shephard. Interlace patterns in Islamic and Moorish art. Leonardo, 25:331–339, 1992.
 E. H. Hankin. The Drawing of Geometric Patterns in Saracenic Art, volume 15 of Memoirs of the Archaeological Society of India. Government of India, 1925.
 E. Hanbury Hankin. Examples of methods of drawing geometrical arabesque patterns. The Mathematical Gazette, pages 371–373, May 1925.
 E. Hanbury Hankin. Some difficult Saracenic designs II. The Mathematical Gazette, pages 165–168, July 1934.
 E. Hanbury Hankin. Some difficult Saracenic designs III. The Mathematical Gazette, pages 318–319, December 1936.
 Istv ́an Hargittai and Magdolna Hargittai. Symmetry through the Eyes of a Chemist. Plenum Press, New York, second edition, 1995.205
 George W. Hart. Conway notation for polyhedra. http://www.georgehart.com/virtual-polyhedra/conway_notation.html.
 George W. Hart. Geometric sculpture. http://www.georgehart.com/sculpture/sculpture.html.
 George W. Hart. Uniform polyhedra. http://www.georgehart.com/virtual-polyhedra/uniform-info.html.
 Barbara Hausmann, Britta Slopianka, and Hans-Peter Seidel. Exploring plane hyperbolic ge- ometry. In Hans-Christian Hege and Konrad Polthier, editors, Visualization and Mathematics, pages 21–36. Springer, 1997.
 H. Heesch. Aufbau der ebene aus kongruenten bereichen. Nachrichten von der Gesellschaft der Wissenschaften zu G ̈ottingen, pages 115–117, 1935. John Berglund provides an online English translation at http://www.angelfire.com/mn3/anisohedral/heesch35.html.
 H. Heesch and O. Kienzle. Flachenschluss. Springer–Verlag, 1963.
 Richard E. Hodel. An Introduction to Mathematical Logic. PWS Publishing Company, 1995.
 Paul Hoffman. The Man Who Loved Only Numbers. Hyperion, New York, 1998.
 Douglas Hofstadter. Metamagical Themas: Questing for the Essence of Mind and Pattern. Bantam Books, 1986.
 Alan Holden. Shapes, Space, and Symmetry. Dover Publications, Inc., 1991.
 Edmund S. Howe. Effects of partial symmetry, exposure time, and backward masking on judged goodness and reproduction of visual patterns. Quarterly Journal of Experimental Psychology, 32:27–55, 1980.
 Daniel H. Huson. The generation and classification of tile-k-transitive tilings of the euclidean plane, the sphere, and the hyperbolic plane. Geometriae Dedicata, 47:269–296, 1993.
 Pedagoguery Software Inc. Tess. http://www.peda.com/tess/Welcome.html.
 Washington Irving. The Alhambra. Macmillan and co., 1931.
 Drew Ivans. The origin and meaning of Celtic knotwork. http://www.craytech.com/drew/knotwork/knotwork-meaning.html 404
 Robert Jensen and Patricia Conway. Ornamentalism: the New Decorativeness in Artchitec- ture & Design. Clarkson N. Potter, Inc., 1982.
 Owen Jones. The Grammar of Ornament. Studio Editions, 1986.
 Craig S. Kaplan. isohedral.ih. http://www.cs.washington.edu/homes/csk/tile/escherization.html => http://www.cgl.uwaterloo.ca/~csk/projects/escherization/
 Craig S. Kaplan. Computer generated islamic star patterns. In Reza Sarhangi, editor, Bridges 2000 Proceedings, 2000.
 Craig S. Kaplan. Computer generated islamic star patterns. Visual Mathematics, 2(3), 2000. http://members.tripod.com/vismath4/kaplan/index.html
 Craig S. Kaplan and George W. Hart. Symmetrohedra: Polyhedra from symmetric placement of regular polygons. In Reza Sarhangi, editor, Bridges 2001 Proceedings, 2001.
 Craig S. Kaplan and David H. Salesin. Escherization. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques (SIGGRAPH 2000), pages 499– 510. ACM Press/Addison-Wesley Publishing Co., 2000.
 David C. Kay. College Geometry. Holt, Rinehart and Winston, Inc., 1969.
 Haresh Lalvani. Pattern regeneration: A focus on Islamic jalis and mosaics. In Jan Pieper and George Michell, editors, The Impulse to Adorn, pages 123–136. Marg Publications, 1982.
 A.J. Lee. Islamic star patterns. Muqarnas, 4:182–197, 1995.
 Raph Levien. libart. http://www.levien.com/libart/
 Silvio Levy. Automatic generation of hyperbolic tilings. In Michele Emmer, editor, The Visual Mind: Art and Mathematics, pages 165–170. MIT Press, 1993.
 Michael Leyton. A Generative Theory of Shape, volume 2145 of Lecture Notes in Computer Science. Springer, 2001.
 Ming Li and Paul Vit ́anyi. An Introduction to Kolmogorov Complexity and its Applications. Graduate texts in Computer Science. Springer-Verlag, Inc., New York, second edition, 1997.
 Stanley B. Lippman and Jos ́ee Lajoie. C++ Primer. Addison-Wesley, third edition, 1998.
 J. L. Locher. The Magic of M. C. Escher. Harry N. Abrams, Inc., 2000. Designed by Erik Th ́e.207
 P. Locher and C. Nodine. The perceptual value of symmetry. Computers and Mathematics With Applications, 17(4–6):475–484, 1989.
 Z. Luˇci ́c and E. Moln ́ar. Fundamental domains for planar discontinuous groups and uniform tilings. Geometriae Dedicata, 40:125–143, 1991.
 Wilhelm Magnus, Abraham Karrass, and Donald Solitar. Combinatorial group theory: pre- sentations of groups in terms of generators and relations. Dover Publications, 1976.
 George E. Martin. The Foundations of Geometry and the Non-Euclidean Plane. Intext Edu- cational Publishers, 1975.
 Scott McCloud. Understanding Comics. HarperCollins, 1993.
 Christian Mercat. Celtic knotwork, the ultimate tutorial. http://www.entrelacs.net/en.index.html
 Kevin Mitchell. Semi-regular tilings of the plane. http://people.hws.edu/mitchell/tilings/Part1.html
 Anders Pape Møller and John P. Swaddle. The biological importance of imperfect symmetry. In Asymmetry, Developmental Stability and Evolution, chapter W1. Oxford University Press, 1997. Available online from http://www.oup.co.uk/isbn/0-19-854894-X
 E. N. Mortenson and W. A. Barrett. Intelligent scissors for image composition. Proceedings of SIGGRAPH 1995, pages 191–198, 1995.
 Joseph Myers. Polyomino, polyhex, and polyiamond tiling. http://www.srcf.ucam.org/~jsm28/tiling/
 G ̈ulru Necipoˇglu. The Topkapı Scroll — Geometry and Ornament in Islamic Architecture. The Getty Center for the History of Art and the Humanities, 1995.
 John Allen Paulos. Mathematics and Humor. The University of Chicago Press, 1980.
 Roger Penrose. Escher and the visual representation of mathematical ideas. In H. S. M. Cox- eter et al., editor, M.C. Escher: Art and Science, pages 143–157. Elsevier Science Publishers B.V., 1986.
 Ivars Peterson. The Mathematical Tourist: Snapshots of Modern Mathematics. W. H. Free- man and Company, New York, 1988.
 William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, second edition, 1992. ISBN 0-521-43108-5. Held in Cambridge.208
 A. Racinet. The Encyclopedia of Ornament. Studio Editions, 1988.
 J. F. Rigby. Butterflies and snakes. In H. S. M. Coxeter et al., editor, M.C. Escher: Art and Science, pages 211–220. Elsevier Science Publishers B.V., 1986.
 Doris Schattschneider. Escher’s classification system for his colored periodic drawings. In H. S. M. Coxeter et al., editor, M.C. Escher: Art and Science, pages 82–96. Elsevier Science Publishers B.V., 1986.
 Doris Schattschneider. M.C. Escher: Visions of Symmetry. W.H. Freeman, 1990.
 P. J. Schneider. An algorithm for automatically fitting digitized curves. In Graphics Gems, pages 612–626. Academic Press, Boston, 1990.
 G. C. Shephard. What Escher might have done. In H. S. M. Coxeter et al., editor, M.C. Es- cher: Art and Science, pages 111–122. Elsevier Science Publishers B.V., 1986.
 A. V. Shubnikov and V. A. Koptsik. Symmetry in Science and Art. Plenum Press, 1974.
 Peter Stampfli. New quasiperiodic lattices from the grid method. In Istv ́an Hargittai, editor, Quasicrystals, Networks and Molecules of Fivefold Symmetry, chapter 12, pages 201–221. VCH Publishers, 1990.
 Desmond Stewart. The Alhambra. Newsweek, 1974.
 Ian Stewart. The Problems of Mathematics. Oxford University Press, 1987.
 Peter G. Szilagyi and John C. Baird. A quantitative approach to the study of visual symmetry. Perception & Psychophysics, 22(3):287–292, 1977.
 C. W. Tyler. The human expression of symmetry:Art and neuroscience. http://www.ski.org/CWTyler_lab/CWTyler/Art\%20Investigations/Symmetry/S%ymmetry.html 404
 Shinji Umeyama. Least-squares estimation of transformation parameters between two point patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(4):376–380, April 1991.
 David Wade. Pattern in Islamic Art. The Overlook Press, 1976.
 Dorothy K. Washburn and Donald W. Crowe. Symmetries of Culture. University of Wash- ington Press, 1992.
 Magnus J. Wenninger. Polyhedron Models. Cambridge University Press, 1971.209
 Hermann Weyl. Symmetry. Princeton Science Library, 1989.
 Stephen Wolfram. A New Kind of Science. Wolfram Media, Inc., 2002.
 Michael T. Wong, Douglas E. Zongker, and David H. Salesin. Computer–generated floral ornament. Proceedings of SIGGRAPH’98, pages 423–434, 1998.
 Jane Yen and Carlo S ́equin. Escher sphere construction kit. In Proceedings of the 2001 symposium on Interactive 3D graphics, pages 95–98. ACM Press, 2001.
 Douglas Zongker. Celtic knot thingy. http://www.cs.washington.edu/homes/dougz/hacks/knot/ 404
 Douglas Zongker. Creation of overlay tilings through dualization of regular networks. In Nathaniel Friedman and Javiar Barrallo, editors, ISAMA 99 Proceedings, pages 495–502, 1999.