Chapter 19: Quest for Visual Realism

19.4 Noise functions and Fractals

Perlin Noise Function Vase

Ken Perlin received a B.A. in theoretical mathematics from Harvard University in 1979 and his Ph.D. in Computer Science from New York University in 1986. Perlin started his graphics career as the System Architect for computer generated animation at MAGI (Mathematical Applications Group, Inc.) in Elmsford, NY. While at MAGI he worked on the movie TRON and began thinking about what would be his noise functions and how they could be used to efficiently create textures for use in complex images. Between 1984 and 1987 Perlin was Head of Software Development at R/Greenberg Associates in New York. He then became a professor in the Media Research Laboratory in the Department of Computer Science at New York University and served as the co-Director of the NYU Center for Advanced Technology. According to his bio on the NYU site, he has served on the Board of Directors of the New York chapter of ACM/SIGGRAPH, and on the Board of Directors of the New York Software Industry Association. His research interests include graphics, animation, and multimedia. In 2002 he received the NYC Mayor’s award for excellence in Science and Technology and the Sokol award for outstanding Science faculty at NYU. In 1991 he received a Presidential Young Investigator Award from the National Science Foundation.

Perlin Noise Functions

In 1997 Perlin won an Academy Award for Technical Achievement from the Academy of Motion Picture Arts and Sciences for his noise and turbulence procedural texturing techniques, which are widely used in feature films and television. 

As Perlin said in a lecture at the Game Developers Conference HardCore seminars titled Making Noise [1] in 1999,

“The first thing I did in 1983 was to create a primitive space-filling signal that would give an impression of randomness. It needed to have variation that looked random, and yet it needed to be controllable, so it could be used to design various looks. I set about designing a primitive that would be “random” but with all its visual features roughly the same size (no high or low spatial frequencies).

Perlin Noise Functions

I ended up developing a simple pseudo-random “noise” function that fills all of three dimensional space (a slice of the 3D is shown here). In order to make it controllable, the important thing is that all the apparently random variations be the same size and roughly isotropic. Ideally, you want to be able to do arbitrary translations and rotations without changing its appearance too much.”

Perlin modified his noise functions so that he could make naturally looking textures using controllable mathematical expressions, which he integrated into shaders. He later expanded the noise to generate 3D models, a process he dubbed Hypertexture in a 1989 paper. A tutorial about Perlin noise, with code, can be found on the scratchapixel.com tutorial site.

Benoit Mandelbrot

Benoit Mandelbrot is largely responsible for the present interest in fractal geometry, which has found its way into the fibre of computer graphics. He showed how fractals can occur in many different places in both mathematics and elsewhere in nature. In 1958, after a stint at the Institute for Advanced Study, he came to the United States permanently and began his long standing collaboration with IBM as an IBM Fellow at their Thomas J. Watson Research Laboratory in Yorktown Heights.

The IBM Watson laboratory provided Mandelbrot the opportunity to research many different concepts and approaches to looking at nature, in his words “an opportunity which no university post could have given me.” After retiring from IBM, became a professor at Yale University, where he received tenure and served as the Sterling Professor of Mathematical Sciences.

Fractals

He had been introduced at an early age to the mathematical concepts of the mathematicians Gaston Julia and his rival Pierre Fatou, whose contributions to the mathematics discipline were important but pretty much forgotten because of their rivalry until Mandelbrot revived a discussion of them. Mandelbrot had been working in other areas of scientific concepts, not in math, until he started rethinking about some areas of geometry and how they could provide a lens for visualizing science. This interest in geometric concepts brought him back to some of the ideas of Julia, in particular the one unifying aspect of certain geometries that was the concept of self-similarity. In the mid-1970s he coined the word “fractal” as a label for the underlying objects, since he observed that they had fractional dimensions.

Fractals

A fractal is a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole. Fractals are generally self-similar and independent of scale, that is they have similar properties at all levels of magnification or across all times. Just as the sphere is a concept that unites physical objects that can be described in terms of that shape, so fractals are a concept that unites plants, clouds, mountains, turbulence, and coastlines, that do not correspond to simple geometric shapes.

According to Mandelbrot,

“I coined fractal from the Latin adjective fractus. The corresponding Latin verb frangere means “to break” or to create irregular fragments. It is therefore sensible – and how appropriate for our needs – that, in addition to “fragmented” (as in fraction or refraction), fractus should also mean “irregular,” both meanings being preserved in fragment.”
(The Fractal Geometry of Nature, page 4.)

He gives a mathematical definition of a fractal as a set for which the Hausdorff-Besicovich dimension strictly exceeds the topological dimension.

With the aid of computer graphics, Mandelbrot was able to show how Julia’s work is a source of some of the most beautiful fractals known today. To do this he had to develop not only new mathematical ideas, but also he had to develop some of the first computer programs to print graphics. An example fractal is the Mandelbrot set (others include the Lyapunov fractal, Julia set, Cantor set, Sierpinski carpet and triangle, Peano curve and the Koch snowflake).

To graph the Mandelbrot set a test determines if a given number in the complex number domain is inside the set or outside the set. The test is based on the equation Z = Z2 + C where C represents a constant number, meaning that it does not change during the testing process. Z starts out as zero, but it changes as the equation is repeatedly iterated. With each iteration a new Z is created that is equal to the old Z squared plus the constant C.

The actual value of Z as it changes is not of interest per se, only its magnitude. As the equation is iterated, the magnitude of Z changes and will either stay equal to or below 2 forever (and will be part of the Mandelbrot set), or it will eventually surpass 2 (and will be excluded from the set). To create the visual representation a color is assigned to a number if it is not part of the Mandelbrot set. The actual color value is determined by how many iterations it took for the number to surpass 2.

Mandelbrot’s work was first described in his book Les Objets Fractals, Forn, Hasard et Dimension (1975) and later in The Fractal Geometry of Nature (1982).

http://en.wikipedia.org/wiki/Fractal

Loren Carpenter was employed at Boeing in Seattle when he decided he wanted to pursue a career in the evolving graphics film production industry. As an engineer at Boeing, Carpenter worked on problems related to the creation of high-quality renderings of free-form surfaces. He was also responsible for the development of algorithms for the use of fractal geometry as a tool for creating complex scenes for graphic display.

Scene from Vol Libre

In 1980 Carpenter used the fractal concept to create mountains for his film Vol Libre, which generated widespread interest in the possibilities that this approach promised. His technical contributions, along with the seminal work with fractals, resulted in a position with Lucasfilm’s Computer Division in 1981 (see the sidebar at the end of this section). He recreated the fractal mountains used in Vol Libre as part of the Genesis Demo for Star Trek II: The Wrath of Khan. Another of his contributions, the
A-buffer hidden surface algorithm, was central to the systems used by many production companies to create images for television and motion pictures.

He is the author of numerous fundamental papers in computer image synthesis and display algorithms. His research contributions include motion blur, fractal rendering, scan-line patch rendering, the A-buffer, distributed ray tracing and many other algorithmic approaches to image making. He holds several patents both personally and through Pixar, and his technical awards include the third SIGGRAPH Technical Achievement Award in 1985.

In 1986, when Lucasfilm’s Computer Division spun off to form Pixar, Loren became Chief Scientist for the company. In 1993, Loren received a Scientific and Technical Academy Award for his fundamental contributions to the motion picture industry through the invention and development of the RenderMan image synthesis software system. RenderMan has been used by many computer-generated films, including use by Lucasfilm’s Industrial Light and Magic to render the dinosaurs in Jurassic Park.

Cinematrix Wand

Carpenter also patented an interactive entertainment system which, through the use of simple retroreflectors, allows large audiences to play a variety of games together either as competing teams or unified toward a common goal, such as flying a plane. Enthusiastic audiences have shown that many types of people find this new method of communicating fun and exciting. Concurrently with his leadership of Pixar, Loren and his wife Rachel founded Cinematrix to explore the intersection of computers and art. Cinematrix’s Interactive Entertainment Systems division is focusing on the development of an interactive audience participation technology that enables thousands of people to simultaneously communicate with a computer, making possible an entire new class of human-computer interaction.

Reflectors used by audience to control motion

http://www.cinematrix.com/

Other people involved in using fractals as a basis for their work in image-making include Richard Voss, Ken Musgrave, Michael Barnsley, Melvin Prueitt (and high school and college students all over the world!)

Loren Carpenter, Rob Cook and Ed Catmull – And the Oscar Goes to… (IEEE Spectrum, April 2001)

Movie 19.12 Vol Libre


https://vimeo.com/5810737
1980 film by Loren Carpenter, created while he was at Boeing, and shown to attendees of the 1980 SIGGRAPH conference

The following account is from the book Droidmaker- George Lucas and the Digital Revolution, by Michael Rubin.

Fournier gave his talk on fractal math, and Loren gave his talk on all the different algorithms there were for generating fractals, and how some were better than others for making lightning bolts or boundaries. “All pretty technical stuff,” recalled Carpenter. “Then I showed the film.”

He stood before the thousand engineers crammed into the conference hall, all of whom had seen the image on the cover of the conference proceedings, many of whom had a hunch something cool was going to happen. He introduced his little film that would demonstrate that these algorithms were real. The hall darkened. And the Beatles began.

Vol Libre soared over rocky mountains with snowy peaks, banking and diving like a glider. It was utterly realistic, certainly more so than anything ever before created by a computer. After a minute there was a small interlude demonstrating some surrealistic floating objects, spheres with lightning bolts electrifying their insides. And then it ended with a climatic zooming flight through the landscape, finally coming to rest on a tiny teapot, Martin Newell’s infamous creation, sitting on the mountainside.

The audience erupted. The entire hall was on their feet and hollering. They wanted to see it again. “There had never been anything like it,” recalled Ed Catmull. Loren was beaming.

“There was strategy in this,” said Loren, “because I knew that Ed and Alvy were going to be in the front row of the room when I was giving this talk.” Everyone at SIGGRAPH knew about Ed and Alvy and the aggregation at Lucasfilm. They were already rock stars. Ed and Alvy walked up to Loren Carpenter after the film and asked if he could start in October.
(Available as an eBook from the iTunes store)

Ken Perlin, An image synthesizer, SIGGRAPH 1985, pp. 287 – 296.

Ken Perlin and Eric Hoffert, Hypertexture, SIGGRAPH 1989, pp. 253 – 262.

Mandelbrot, B. Fractals: Form, Chance and Dimension, W. H. Freeman and Company, 1977, xviii + 265 pp.

Mandelbrot, B. The Fractal Geometry of Nature, W. H. Freeman and Company, 1982, xii + 461 + xvi pp. (twenty-two reprints by 2005)

Mandelbrot, B. Fractals and Chaos: The Mandelbrot Set and Beyond, New York NY: Springer, 2004, xii + 308 pp.

Lane, J., L. Carpenter, T. Whitted, and J. Blinn, “Scan Line Methods for Displaying Parametrically Defined Surfaces,” CACM, 23(1), January 1980.

Gallery 19.3 Fractal Images


  1. This site is currently offline, but can be found in web archive at https://web.archive.org/web/20160303232627/http://www.noisemachine.com/talk1/

License