The Science of Fractal Images Heinz-Otto Peitgen Dietmar Saupe Editors The Science of Fractal Images Michael F. Barnsley Robert L. Devaney Benoit B. Mandelbrot Heinz-Otto Peitgen Dietmar Saupe Richard F. Voss With Contributions by Yuval Fisher Michael McGuire With 142 Illustrations in 277 Parts and 39 Color Plates Springer-Verlag New York Berlin Heidelberg London Paris Tokyo Heinz-Otto Peitgen Institut fUr Oynamische Systeme, Universitat Bremen, 0-2800 Bremen 33, Federal Republic of Germany, and Department of Mathematics, University of California, Santa Cruz, CA 95064, USA Oietmar Saupe Institut fUr Oynamische Systeme, Universitat Bremen, 0-2800 Bremen 33, Federal Republic of Germany The cover picture shows a fractal combining the two main topics of this book: deterministic and random fractals. The deterministic part is given in the form of the potential surface in a neighborhood of the Mandelbrot set. The sky is generated using random fractals. The image is produced by H. Jurgens, H.-O. Peitgen and D. Saupe. The back cover images are: Black Forest in Winter (top left, M. Bamsley, F. Jacquin, A. Malassenet, A. Sloan, L. Reuter); Distance estimates at boundary of Mandelbrot set (top right, H. Jurgens, H.-O. Peitgen, D. Saupe); Floating island of Gulliver's Travels (center left, R. Voss); Foggy fractally cratered landscape (center right, R. Voss); Fractal landscaping (bottom, B. Mandelbrot, K. Musgrave). Library of Congress Cataloging-in-Publication Data The Science of fractal images: edited by Heinz-Otto Peitgen and Dietmar Saupe ; contributions by Michael F. Bamsley ... let al.l. p. cm. Based on notes for the course Fractals-introduction, basics, and perspectives given by Michael F. Bamsley, and others, as part of the SIGGRAPH '87 (Anaheim, Calif.) course program. Bibliography: p. Includes index. I. Fractals. I. Peitgen, Heinz-Otto, 1945- II. Saupe, Dietmar, 1954- III. Bamsley, M. F. (Michael Fielding), 1946- QA614.86.S35 1988 5 I 6--dc 19 88-12683 ISBN-13: 978-1-4612-8349-2 e-ISBN-13: 978-1-4612-3784-6 001: 10.1007/978-1-4612-3784-6 © 1988 by Springer-Verlag New York Inc; the copyright of all artwork and images remains with the individual authors. Softcover reprint of the hardcover 1st edition 1988 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Verlag, 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc. in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. This book was prepared with IiITEX on Macintosh computers and reproduced by Springer-Verlag from camera-ready copy supplied by the editors. TEX is a trademark of the American Mathematical Society. Macintosh is a trademark of Applt; Computer, Inc. 9 8 765 Preface This book is based on notes for the course Fractals:lntroduction, Basics and Perspectives given by MichaelF. Barnsley, RobertL. Devaney, Heinz-Otto Peit gen, Dietmar Saupe and Richard F. Voss. The course was chaired by Heinz-Otto Peitgen and was part of the SIGGRAPH '87 (Anaheim, California) course pro gram. Though the five chapters of this book have emerged from those courses we have tried to make this book a coherent and uniformly styled presentation as much as possible. It is the first book which discusses fractals solely from the point of view of computer graphics. Though fundamental concepts and algo rithms are not introduced and discussed in mathematical rigor we have made a serious attempt to justify and motivate wherever it appeared to be desirable. Ba sic algorithms are typically presented in pseudo-code or a description so close to code that a reader who is familiar with elementary computer graphics should find no problem to get started. Mandelbrot's fractal geometry provides both a description and a mathemat ical model for many of the seemingly complex forms and patterns in nature and the sciences. Fractals have blossomed enormously in the past few years and have helped reconnect pure mathematics research with both natural sciences and computing. Computer graphics has played an essential role both in its de velopment and rapidly growing popularity. Conversely, fractal geometry now plays an important role in the rendering, modelling and animation of natural phenomena and fantastic shapes in computer graphics. We are proud and grateful that Benoit B. Mandelbrot agreed to write a de tailed foreword for our book. In these beautiful notes the Father of Fractals shares with us some of the computer graphical history of fractals. The five chapters of our book cover: • an introduction to the basic axioms of fractals and their applications in the natural sciences, • a survey of random fractals together with many pseudo codes for selected algorithms, • an introduction into fantastic fractals, such as the Mandelbrot set, Julia sets and various chaotic attractors, together with a detailed discussion of algorithms, • fractal modelling of real world objects. V Chapters 1 and 2 are devoted to random fractals. While Chapter 1 also gives an introduction to the basic concepts and the scientific potential of frac tals, Chapter 2 is essentially devoted to algorithms and their mathematical back ground. Chapters 3,4 and 5 deal with deterministic fractals and develop a dy namical systems point of view. The first part of Chapter 3 serves as an intro duction to Chapters 4 and 5, and also describes some links to the recent chaos theory. The Appendix of our book has four parts. In Appendix A Benoit B. Mandel brot contributes some of his brand new ideas to create random fractals which are directed towards the simulation of landscapes, including mountains and rivers. In Appendix B we present a collection of magnificent photographs created and introduced by Michael Mc Guire, who works in the tradition of Ansel Adams. The other two appendices were added at the last minute. In Appendix C Diet mar Saupe provides a short introduction to rewriting systems, which are used for the modelling of branching patterns of plants and the drawing of classic frac tal curves. These are topics which are otherwise not covered in this book but certainly have their place in the computer graphics of fractals. The final Appen dix D by Yuval Fisher from Cornell University shares with us the fundamentals of a new algorithm for the Mandelbrot set which is very efficient and therefore has potential to become popular for PC based experiments. Almost throughout the book we provide selected pseudo codes for the most fundamental algorithms being developed and discussed, some of them for be ginning and some others for advanced readers. These codes are intended to illustrate the methods and to help with a first implementation, therefore they are not optimized for speed. The center of the book displays 39 color plates which exemplify the potential of the algorithms discussed in the book. They are referred to in the text as Plate followed by a single number N. Color plate captions are found on the pages immediately preceding and following the color work. There we also describe the front and back cover images of the book. All black and white figures are listed as Figure N.M. Here N refers to the chapter number and M is a running number within the chapter. After our first publication in the Scientific American, August 1985, the Man delbrot set has become one of the brightest stars of amateur mathematics. Since then we have received numerous mailings from enthusiasts around the world. VI We have reproduced some of the most beautiful experiments (using MSetDEM( ) , see Chapter 4) on pages 20 and 306. These were suggested by David Brooks and Daniel N. Kalikow, Framingham, Massachusetts. Bremen, March 1988 Heinz-Otto Peitgen and Dietmar Saupe Acknowledgements Michael F. Barnsley acknowledges collaboration with Laurie Reuter and Alan D. Sloan, both from Georgia Institute of Technology. Robert L. Devaney thanks Chris Frazier from the University of Bremen for putting his black and white figures in final form. Chris Frazier also produced Figures 0.2, 5.1, 5.2 and 5.17. Heinz-Otto Peitgen acknowledges collaboration with Hartmut Jurgens and Diet mar Saupe, University of Bremen, and thanks Chris Frazier for some of the black and white images. Dietmar Saupe thanks Richard F. Voss for sharing his expertise on random fractals. Besides the authors several people contributed to the color plates of this book, which is gratefully acknowledged. A detailed list of credits is given in the Color Plate Section. Michael F. Bamsley Robert L. Devaney Yuval Fisher Benoit B. Mandelbrot Michael McGuire Heinz-Otto Peitgen Dietmar Saupe Richard F. Voss VII Michael F. Barnsley. *1946 in Folkestone (England). Ph. D. in Theoretical Chemistry, University of Wisconsin (Madison) 1972. Professor of Mathematics, Georgia Institute of Technology, Atlanta, since 1983. Formerly at University of Wisconsin (Madison), University of Bradford (England), Centre d'Etudes Nucleaires de Saclay (Paris). Founding officer of Iterated Systems, Inc. Robert L. Devaney. * 1948 in Lawrence, Mass. (USA). Ph. D. at the University of California, Berkeley, 1973. Professor of Mathematics, Boston University 1980. Formerly at Northwestern University and Tufts University. Research in terests: complex dynamics, Hamiltonian systems. M.F. Barnsley R.L. Devaney Yuval Fisher. *1962 in Israel. 1984 B.S. in Mathematics and Physics, University of California, Irvine. 1986 M.S. in Computer Science, Cornell University. 1988 Ph. D. in Mathematics (expected), Cornell University. Benoit B. Mandelbrot. *1924 in Warsaw (Poland). Moved to Paris in 1936, to USA in 1958. Diploma 1947, Ecole Poly technique, D. Sc. 1952, Paris, Dr. Sc. (h. c.) Syracuse, Laurentian, Boston, SUNY. 1974 I.B.M. Fellow at Thomas 1. Watson Research Center and 1987 Abraham Robinson Adjunct Professor of Mathematical Science, Yale University. Barnard Medal 1985,. Franklin Medal 1986. Member of the American Academy of Arts and Sciences and of the U.S. National Academy of Sciences. Y. Fisher B.B. Mandelbrot Michael McGuire. *1945 in Ballarat, Victoria (Australia). Ph. D. in Physics, University of Washington (Seattle), 1974. He has worked in the field of atomic frequency standards at the University of Mainz, Germany, NASA, Goddard Space Flight Center, and Hewlett Packard Laboratories. Heinz-Otto Peitgen. * 1945 in Bruch (Germany). Dr. rer. nat. 1973, Habilitation 1976, both from the University of Bonn. Research on nonlinear analysis and dynamical systems. 1977 Professor of Mathematics at the University of Bremen and since 1985 also Professor of Mathematics at the University of California at Santa Cruz. Visiting Professor in Belgium, Italy, Mexico and USA. M. McGuire H.-O. Peitgen Dietmar Saupe. *1954 in Bremen (Germany). Dr. rer. nat. 1982 at the University of Bremen. Visiting Assistant Professor of Mathematics at the University of California, Santa Cruz, 1985-87 and since 1987 at the University of Bremen. There he is a researcher at the Dynamical Systems Graphics Laboratory. Research interests: mathematical computer graphics and experimental mathematics. Richard F. Voss. * 1948 in St. Paul, Minnesota (USA). 1970 B. S. in Physics from M.LT. 1975 Ph. D. in Physics from U. C. Berkeley. 1975-present: Re search Staff Member at the LB.M. Thomas 1. Watson Research Laboratory in Yorktown Heights, NY. Research in condensed matter physics. D. Saupe R.F. Voss VIII Contents Preface V Foreword: People and events behind the "Science of Fractal Images" 1 Benoit B.Mandelbrot 0.1 The prehistory of some fractals-to-be: Poincare, Fricke, Klein and Escher . . . . . . . . . . . . . . 2 0.2 Fractals at IBM. . . . . . . . . . . 5 0.3 The fractal mountains by R.E Voss . 6 0.4 Old films . . . . . . . . . . . . . . 8 0.5 Star Trek II . . . . . . . . . . . . . 8 0.6 Midpoint displacement in Greek geometry: The Archimedes construction for the parabola . 11 0.7 Fractal clouds ......................... 12 0.8 Fractal trees .... . . . . . . . . . . . . . . . . . . . . .. 13 0.9 Iteration, yesterday's dry mathematics and today's weird and wonderful new fractal shapes, and the "Geometry Supercom- puter Project" . . . . . . . . . . . . . . . . . . . . . . 14 0.10 Devaney, Bamsley and the Bremen "Beauty of Fractals" . 17 1 Fractals in nature: From characterization to simulation 21 Richard F.Voss 1.1 Visual introduction to fractals: Coastlines, mountains and clouds 22 1.1.1 Mathematical monsters: The fractal heritage . . . . 25 1.1.2 Fractals and self-similarity . . . . . . . . . . . . . 25 1.1.3 An early monster: The von Koch snowflake curve . 26 1.1.4 Self-similarity and dimension 28 1.1.5 Statistical self-similarity . . 30 1.1.6 Mandelbrot landscapes . . . . 30 1.1.7 Fractally distributed craters . 31 1.1.8 Fractal planet: Brownian motion on a sphere 33 1.1.9 Fractal flakes and clouds . . . . . . . . . . . 33 1.2 Fractals in nature: A brief survey from aggregation to music. 35 1.2.1 Fractals at large scales . . . . . . . . . . . 36 1.2.2 Fractals at small scales: Condensing matter 36 IX 1.2.3 Scaling randomness in time: -jp-noises 39 1.2.4 Fractal music. . . . . . . . . . . . . . 40 1.3 Mathematical models: Fractional Brownian motion 42 1.3.1 Self-affinity ....... . . . . . . . . . 44 1.3.2 Zerosets . . . . . . . . . . . . . . . . . . 45 1.3.3 Self-affinity in higher dimensions: Mandelbrot land- scapes and clouds .... . . . . . . . . . . . . . .. 45 1.3.4 Spectral densities for fBm and the spectral exponent f3 47 1.4 Algorithms: Approximating fBm on a finite grid . 47 1.4.1 Brownian motion as independent cuts 48 1.4.2 Fast Fourier Transform filtering 49 1.4.3 Random midpoint displacement . . . 51 1.4.4 Successive random additions. . . . . 54 1.4.5 Weierstrass-Mandelbrot random fractal function. 55 1.5 Laputa: A concluding tale . . . . . 57 1.6 Mathematical details and formalism . . . . 58 1.6.1 Fractional Brownian motion . . . . 58 1.6.2 Exact and statistical self-similarity . 59 1.6.3 Measuring the fractal dimension D . 61 1.6.4 Self-affinity ..... . . . . . . . 62 1.6.5 The relation of D to H for self-affine fractional Brow- nian motion . . . . . . . . . 63 1.6.6 Trails of fBm. . . . . . . . . . . . . . . . . . . . . . 64 1.6.7 Self-affinity in E dimensions . . . . . . . . . . . . . . 64 1.6.8 Spectral densities for fBm and the spectral exponent f3 65 1.6.9 Measuring fractal dimensions: Mandelbrot measures 66 1.6.10 Lacunarity . . . . . . . . . . . . . . . . . . . 67 ¥ t: 1.6.11 Random cuts with H Campbell's theorem 69 1.6.12 FFT filtering in 2 and 3 dimensions ..... . 69 2 Algorithms for random fractals 71 Dietmar Saupe 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . 71 2.2 First case study: One-dimensional Brownian motion . 74 2.2.1 Definitions.............. 74 2.2.2 Integrating white noise . . . . . . . . . 75 2.2.3 Generating Gaussian random numbers . 76 2.2.4 Random midpoint displacement method 78 2.2.5 Independent jumps . . . . . . . . . . . 80 2.3 Fractional Brownian motion: Approximation by spatial methods 82 2.3.1 Definitions........... 82 2.3.2 Midpoint displacement methods 84 2.3.3 Displacing interpolated points . 87 x