A Critical History of Computer Graphics and Animation

As the CG discipline has matured, researchers have moved from trying to discover fundamental drawing and rendering techniques, and have looked to increasing the complexity, and in some respects, the realism of synthetic images. Hardware has helped in this quest, but the algorithms that are embedded in hardware were first (usually) written and tested in software, later migrating to hardware.

One of the keys to complex realistic images is to represent the laws of nature and the physical environment in such a way that they are reasonably accurate and consistent, yet approximated in such a way as to allow reasonable computation speeds. CG researchers have often resorted to "tricks" that fool the observer into believing that the physical laws are represented ... the proof, as some maintain, is in the believability of the image, not necessarily in the accuracy of the representation.

Some of the more important attempts at realistic image synthesis are covered below. Many of the researchers are leaders in the field, and many have won awards for their contributions to the discipline.

• Bill Reeves - Particle Systems
• Karl Sims - Particle systems and artificial life
• Craig Reynolds, Susan Amkraut- Flocking
• Physically-based modeling
  • Dave Haumann
  • James Hahn
  • Al Barr
  • Demetri Terzopoulos
  • Andrew Witkin
  • Michael Kass
  • David Baraff
• Ken Perlin - noise functions
• Benoit Mandelbrot - Fractals
• Loren Carpenter - Fractals and surface rendering
• Global illumination
  • Jim Kajiya
  • Radiosity
  • Ray-tracing
  • Photon Mapping
• Paul Debevec - Image Based Rendering
• Plant growth
  • Przemyslaw Prusinkiewicz
  • Michael Barnsley (Iterated Function Systems)
  • Midori Kitagawa
• Wayne Lytle - MIDI control of animation
• Chris Landreth - Character animation

Click on the images below to view a larger version (when available).

One of the problems with generating highly complex imagery of an organic nature is the ability to control motion, change of form, dynamics, and surface characteristics of the models in the scene. An early contribution to the solution of this problem was provided by Bill Reeves, in his seminal paper Particle Systems  - A Technique for Modeling a Class of Fuzzy Objects, presented at SIGGRAPH 82 and published in the April, 1983 ACM Transactions on Graphics.

Bill Reeves began his graphics career at the University of Waterloo and at the University of Toronto, where he received his B.S. in math and M.A. and Ph.D. in computer science. In 1980, Reeves joined the computer division of Lucasfilm as project leader of the systems group and a member of the computer graphics group. Several years into a career that focused Reeves on the field of animation, he invented the particle systems image synthesis technique that enabled the generation of very complex and detailed images.

From 1982 to 1986, he worked as project leader of the modeling and animation group at Lucasfilms. In 1986, Bill joined Pixar as head of Animation Research and Development. His film credits while at Lucasfilm, Ltd. and Pixar include: Star Trek II: The Wrath of Khan, Return of the Jedi, Young Sherlock Holmes, Luxo Jr. (1986 Academy Award nominee), Red's Dream, Tin Toy and Knickknack. In 1988, Bill received an Academy Award for Best Animated Short Film for his work as technical director on Tin Toy.

A particle system is used to describe techniques for modeling, rendering, and animation of dynamic objects. The system involves a collection of particles, each of which has attributes that directly or indirectly impact the behavior of the particle and/or its neighboring particles. The individual particles can be graphical primitives such as points or lines, but they can also be any geometric entity (birds, stones, snowflakes, water drops, etc.) The other characteristic of a particle system is a random element that controls the actions and characteristics of each particle (eg, position, velocity, color, transparency, etc.) The random element is stochastically controlled, meaning that the randomness has bounds, controlled variance, or some mode of distribution.

For the Star Trek scene, Reeves and his colleagues were trying to create a wall of fire spreading out from the point of impact of a projectile on a planetary surface. Every particle in Reeve's system was a single point in space and the wall of fire was represented by thousands of these individual points. Each particle had the following attributes:

• Position in 3D space
• Velocity (speed and direction)
• Color
• Lifetime (how long it is active)
• Age
• Shape
• Size
• Transparency

Each particle in the system is born (or generated), undergoes some dynamic changes, and dies. Particles in the system are generated semi-randomly within the bounds of some initial object. This space is termed the generation shape of the fuzzy object. Each of the partcle's attributes is given an initial value that may be fixed or may be determined by a stochastic process.

The particle undergoes dynamics, meaning the attributes of each of the particles may vary over time. That is, each of the particle attributes can be specified by a parametric equation with time as the parameter and they can be functions of both time and other particle attributes. Each particle has its age and lifetime. Age is the time that the particle has been active (measured in frames from its generation). Lifetime is the maximum amount of time that the particle can live. When the particle age matches it's lifetime it is destroyed. There may also be other criteria for terminating a particle before its lifetime bounds. For example

• If a particle moves out of the viewing area and will not reenter it, it can be killed.
• Particles that impact a "ground plane" burn out and can be killed.
• Some other related attribute reaches a bounding threshold. For example, if the particle color is so close to black or the background color that it will not contribute any color to the final image, it can be killed.

The Genesis Effect

Reeves also used the particle system approach to model bushes in the image Road to Pt. Reyes and trees in the movie The Adventures of Andre and Wally B. Each tree was created by using a particle system, and the position of a tree within the forest was also controlled by a particle system. The system can use a "trace" of the trajectory of each particle, and when it dies (eg, at the end of a branch) a leaf can be created.

The Adventures of Andre and Wally B

Karl Sims received a B.S. in Life Sciences from MIT in 1984. After working at Thinking Machines Corporation for a year he returned to MIT to study graphics and animation at the Media Laboratory and received an M.S. in Visual Studies in 1987. He then joined the production research team at Whitney/Demos Production in California, and later became co-founder and director of research for Hollywood based Optomystic. He worked at Thinking Machines Corporation as an artist-in-residence and was sometimes employed elsewhere as a part time consultant. He currently leads GenArts, Inc. in Cambridge, Massachusetts, which creates special effects software plugins for various packages used for the motion picture industry.

Sims became known for his particle system studies in his short films Excerpts from Leonardo's Deluge and Particle Dreams (1988). He won the Prix Ars Electronica Golden Nica award two years in a row, in 1991 for Panspermia, and in 1992 for Liquid Selves and Primordial Dance. He has also contributed greatly to the graphics world in the area of artificial evolution and virtual creatures. In 1998 he was awarded a prestigious Macarthur Foundation fellowship.

http://www.genarts.com/karl/

A variation of the particle system was used by Craig Reynolds to model the flocking and schooling behavior of birds and fish. In this particle system the particles are used to represent what Reynolds called "boids". In this case, each particle is an entire polygonal object rather than a graphical primitive, each particle has a local coordinate system, and there are a fixed number of particles that are not created or destroyed. The attributes which control the boids behavior is dependent on external as well as internal conditions, allowing a boid particle to react to what other particles are doing around it. Some characteristics of this system include:

• Collision avoidance - a boid is constrained from colliding with other boids or obstacles;
• Velocity matching - each boid attempts to go the same speed and direction as neighboring boids;
• Flock centering - each boid attempts to stay close to nearby flockmates.

According to Reynolds:

Typical computer animation models only the shape and physical properties of the characters, whereas behavioral or character-based animation seeks to model the behavior of the character. The goal is for such simulated characters to handle many of the details of their actions, and hence their motions. These behaviors include a whole range of activities from simple path planning to complex "emotional" interactions between characters. The construction of behavioral animation characters has attracted many researchers, but it is still a young field in which more work is needed.

Reynolds' 1986 computer model of coordinated animal motion was based on three dimensional computational geometry. The flocking model placed an individual "boid" in a flock, and determined the motion path using the steering behaviors that were based on the positions and velocities nearby flockmates:

• Separation: steer to avoid crowding local flockmates
• Alignment: steer towards the average heading of local flockmates
• Cohesion: steer to move toward the average position of local flockmates

Each boid has direct access to the whole scene's geometric description, but it needs to react only to flockmates within a certain small neighborhood around itself. The neighborhood is characterized by a distance (measured from the center of the boid) and an angle, measured from the boid's direction of flight. Flockmates outside the local neighborhood are ignored.

Reynolds produce a short film for the SIGGRAPH 87 electronic theatre called Stanley and Stella in: Breaking the Ice. to demonstrate the basic flocking and schooling algorithms in his system, which he calld BOIDS. The film was made in conjunction with Symbolics and Whitney/Demos Productions.

Stanley and Stella in Breaking the Ice

Reynolds flocking algorithm was not the first such algorithm. For the famous film Eurhythmy produced at Ohio State, Susan Amkraut implemented what she referred to as a "force-field" flocking algorithm. She describes her approach in an interview with later collaborator Paul Kaiser:

Yes, I'd started working on the problem of flocking. Whereas Michael's [Girard] project [at Ohio State] was to look at the human body in motion, mine was to take a mathematical algorithm and to see where it could lead. I'd begun by animating particles using force-fields in 3D. These force-fields would attract, or repel, or shape the movement of the particles. So, for example, I could have a sink that drew all the particles in, or a source they'd funnel out of, or even a spiral they'd fly around. I soon saw how this could lead to an elegant solution for flocking.

The problem posed by flocking is this: you have multiple creatures who don't want to run into each other, but also want to stay very close together -- and they have to avoid hitting any external obstacles as well. Algorithms had been developed in which a lead bird guided the flock. But real flocks behave in a more interesting fashion: they have no leader. So, neither did my algorithm, which worked like this. I put a little force-field around every bird, so that if any other bird got near, it was told to go away. And of course each bird had a corresponding attraction field, so that if the other bird got too far away, it was told to come closer. So every bird at every frame of the animation considers every force-field around it, and moves accordingly.

It's a difficult algorithm to work with because you can't tell where you are at any given point in time unless you know where you started and have computed all the way back up from there. My interest in this went beyond wanting to simulate actual flocks. I wanted to create a flock of birds all flying realistically as individuals, but flying collectively in patterns that could never happen in the real world.

Flocking sequence from Eurhythmy

http://www.red3d.com/cwr/boids/

Boids paper

As Reynolds points out on his web site, since 1987 there have been many other applications of the boids model in the realm of behavioral animation. The 1992 Tim Burton film Batman Returns was the first. It contained computer simulated bat swarms and penguin flocks which were created with modified versions of the original boids software developed at Symbolics. Andy Kopra (then at VIFX, which later merged with Rhythm & Hues) produced realistic imagery of bat swarms. Andrea Losch (then at Boss Films) and Paul Ashdown created animation of an "army" of penguins marching through the streets of Gotham City.

A similar approach was used to produce the famous Wildebeest stampede in the Disney movie The Lion King. According to the film notes at http://www.lionking.org/text/FilmNotes.html

For the pivotal scene in the film where Scar enacts his plan to do away with his royal relatives, Mufasa and Simba, directors Allers and Minkoff wanted to create something with the same visual impact as the dramatic events that were unfolding. The script called for thousands of stampeding wildebeests to pour over the hilltop into the gorge below. Feature Animation's CGI (Computer Generated Imagery) department was called upon to help pull off this amazing feat and to enhance the emotional impact of the scene. Five specially trained animators and technicians in this department spent over two years creating the impressive 2-1/2 minute sequence, which represents a new level of sophistication for the art form and a dramatic highlight for the film.

Starting with a 2-dimensional model sheet and some conventional hand-drawn rough animation, created by supervising animator Ruben Aquino, Johnston and his CGI team were able to generate 3-dimensional representations of a wildebeest inside the computer. Once this digitized computer version existed, the camera could be placed anywhere to allow different angles during the course of a scene.

"Since the scene called for a stampede, we had to come up with a way that our animators could control the behavior of herds of wildebeests without having them bump into each other," says Johnston. "We developed a simulation program that would allow us to designate leaders and followers within each group. We were also able to individualize and vary the movement of each animal within a group to give them a certain random quality. Effectively they could all be doing different things with the library of behavior including slow and fast gallops, various head tosses and even a few different kinds of leaps."

In the end, the hand-drawn animation of Simba and Mufasa was composited with the CGI wildebeest stampede and the film's other hand-drawn elements (backgrounds and effects). "The object is to make the wildebeests look like the other characters in the film," says Johnston. "We don't want them to stand out. We just want a dramatic effect."

Wildebeest stampede from The Lion King

The flocking algorithms developed by Reynolds and others have advanced significantly, and variations on the same approach have been used (coupled with new technologies such as motion capture) to generate crowds and large numbers of animated characters for motion pictures. In the movie Sharkslayers, large schools of fish are animated. There are armies in Star Wars, The Mummy, and Lord of the Rings, colonies of ants in Antz, insects in A Bug's Life, and passengers on the Titanic. Production companies such as PDI and ILM have developed their own approach to crowd control, and software packages like Houdini and Character Studio have included crowd animation components.

Several articles by Barbara Robertson of Computer Graphics World have dealt with crowd animation, including Crowd Control in the February, 1998 issue, Faces and Crowds in the July 1998 issue, A Bug's Eye View in the November 1998 issue, and more recently The Two Towers (February 2003)

Dynamics animation from the Mummy trailer

These approaches to defining environments and actions in the "physical world" defined by a computer graphics-based synthetic approach can be considered part of a collective family of algorithmic approaches called physically-based modeling. According to Demetri Terzopolous, one of the pioneers of this approach, in a SIGGRAPH '89 panel discussion:

Physically-based techniques facilitate the creation of models capable of automatically synthesizing complex shapes and realistic motions that were, until recently, attainable only by skilled animators, if at all. Physically-based modeling adds new levels of representation to graphics objects. In addition to geometry — forces, torques, velocities, accelerations, kinetic and potential energies, heat, and other physical quantities are used to control the creation and evolution of models. Simulated physical laws govern model behavior, and animators can guide their models using physically-based control systems. Physically-based models are responsive to one another and to the simulated physical worlds that they inhabit.

Centers of activity in the physically-based modeling and animation area included Ohio State (Dave Haumann, James Hahn, Michael Girard and John Chadwick), CalTech (Al Barr, Kurt Fleischer, Ronen Barzel, John Platt) Carnegie Mellon (Andrew Witkin and David Baraff) and Apple Computer (Gavin Miller, Michael Kass) and later at Pixar (Baraff, Witkin, Fleischer, Barzel and Kass).

Two early physically based modeling research experiments were done at Ohio State by Dave Haumann and James Hahn. Hahn's 1988 work created an animation system that gave the animator control over the simulation of dynamic interaction between rigid objects, taking into account physical characteristics of friction, mass, motion, elasticity and moments of inertia. His system effectively combined kinematics and dynamics in a computationally efficient method. Hahn went on to continue his research as the Director of The Institute for Computer Graphics at The George Washington University.

Haumann's work with physically-based simulations used simple mass-spring models, through which he could model bridge cables and tanzan vines. He added vector fields to simulate flags and curtains as well. These effects were shown in a 1988 movie that accompanied a paper in SIGGRAPH. His research was used by Chris Wedge in a 1989 movie produced at Ohio Stae called Balloon Guy. Haumann went to IBM, and experimented with effects for demonstrating the shattering of a physical object. He then experimented with time-varying vector fields, including vortices, sources, sinks and uniform fields for a movie that simulated leaves blowing in these fields. He then expanded his model of leaves, picked a leaf shape that floated nicely, and showed a movie illustrating his work. He is now at Pixar, where he worked on the Pixar short Geri's Game.

James Hahn - Ohio State - Ridgid Body Dynamics

David Haumann - Ohio State - Flexible Dynamics

Hahn, James. "Realistic Animation of Rigid Bodies,"Computer graphics, Proceedings SIGGRAPH '88, Association for Computing Machinery (ACM), Vol. 22, No. 4 (August 1988), pp. 299-308

Haumann, D., "Modeling the Physical Behavior of Flexible Objects", in Topics in Physically-Based Modeling, SIGGRAPH Tutorial 17 Notes, 1987.

Jakub Wejchert , David Haumann, Animation aerodynamics, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.19-22, July 1991

Al Barr advised several important researchers at the Graphics Group at Cal Tech. His sudents included Ronen Barzel (Pixar), John Platt (Microsoft), David Kirk (Nvidia), Kurt Fleischer (Pixar) and others. Together with Andrew Witkin, Barr coordinated several sessions related to physically-based modeling for the SIGGRAPH courses program (87-91), as well as panels and papers on the topic. The list of papers below shows the influence of the CalTech researchers on this area of graphics.

• Barr - "Dynamic Constraints: A New Paradigm for Computer Graphics Modeling," State of the Art in Image Synthesis, ACM Siggraph 1986
• "Elastically Deformable Models," with D. Terzopoulos, J. Platt and K. Fleischer, Computer Graphics(21), ACM Siggraph, 1987.
• "Energy Constraints on Parameterized Models," with A. Witkin and K. Fleischer, Computer Graphics(21), ACM Siggraph, 1987.
• Introduction to Physically Based Modeling, Course Notes, with A. Witkin, ACM Siggraph, 1990 and 1991
• Topics in Physically-based Modeling, Course Notes, ACM Siggraph, 1987, 1988 and 1989
• " Physically-Based Modeling: Past, Present, and Future," Panel Proceedings, D. Terzopoulis chair, ACM Siggraph, 1989
• "Constraint Methods for Flexible Models," with John Platt, Computer Graphics(22), 1988.
• "Teleological Modeling," Computer Graphics and the Sciences, ACM Siggraph, 1988.
• " A Modeling System Based on Dynamic Constraints," with R. Barzel, Computer Graphics(22), ACM Siggraph 1988.
• "Elastically Deformable Models," with D. Terzopoulos, J. Platt and K. Fleischer, Computer Graphics(21), ACM Siggraph, 1987.
• "Energy Constraints on Parameterized Models," with A. Witkin and K. Fleischer, Computer Graphics(21), ACM Siggraph, 1987.
• Ronen Barzel, A Structured Approach to Physically-Based Modeling, Ph.D. Thesis, California Institute of Technology, 1992
• Ronen Barzel, Controlling Rigid Bodies with Dynamic Constraints, Master's Thesis, Caltech-CS-TR-88-19, California Instiitute of Technology, 1988

Demetri Terzopoulos received his university education at McGill University (B.Eng. 1978, M.Eng. 1980) and MIT (PhD 1984). He does pioneering work in artificial life, an emerging field that cuts across computer science and biological science. He devises computer models of animal locomotion, perception, behavior, learning and intelligence. Terzopoulos and his students have created artificial fishes, virtual inhabitants of an underwater world simulated in a powerful computer. These autonomous, lifelike creatures swim, forage, eat and mate on their own. Terzopoulos has also done important work on human facial modeling. He has produced what is widely recognized as the most realistic biomechanical model of the human face to date. Expressive synthetic faces are useful in entertainment and human-computer interaction, but they can also play a role in planning reconstructive facial surgery, as well as in automated face recognition and teleconferencing systems. Terzopoulos is widely known as the inventor of deformable models, a family of shape modeling algorithms that have bridged the fields of computer vision and computer graphics and have opened up new avenues of research in medical imaging and computer-aided design.

ACM SIGGRAPH recognized Andrew Witkin for his pioneering work in bringing a physics-based approach to computer graphics with the 2001 Computer Graphics Achievement Award. Witkin's papers on active contours (snakes) and deformable models, variational modeling, scale-space filtering, space time constraints, and dynamic simulation are considered landmarks that have been inspirational to others and have shaped the field in such different areas as image analysis, surface modeling, and animation.

He received his Ph.D. at the Massachusetts Institute of Technology in the psychology department. In the early 80s, the vision and graphics research communities were largely disjoint. Witkin was one of the first to bridge the divide in a series of papers that included his 1987 prize winning paper "Constraints on Deformable Models: Recovering 3D Shape and Non-rigid Motion" and "Snakes: Active Contour Models" both co-authored with Michael Kass and Demetri Terzopoulos. These papers popularized the idea that computer vision techniques could provide interactive "power assists" to a human operator creating computer graphics models.

While still at Schlumberger, and subsequently as a professor at Carnegie Mellon University, Witkin has done notable work on the use of physically-based modeling techniques not only for animating rigid or deformable objects, but also as an interaction technique for a range of problems including constrained geometric modeling and camera control (with Michael Gleicher) and visualization of implicit surfaces (with Paul Heckbert). In 1992, with Michael Kass, Witkin won a Golden Nica from Ars Electronica for his use of physically based modeling of reaction-diffusion equations to synthesize organic looking textures. In 1988 Witkin, with Michael Kass, introduced the idea of using control theory in computer graphics with their "Spacetime Constraints" paper and showed that optimization could be used to direct physically-based character animation.

Recently, Witkin has become interested in the very difficult problem of clothing simulation. With David Baraff at Carnegie Mellon University, Witkin developed the clothing simulator which forms the basis of Maya Cloth, and which was used in the production of "Stuart Little," among other films. With David Baraff and Michael Kass at Pixar Animation Studios, Witkin developed the clothing and hair simulator used in the Pixar/Disney film "Monsters, Inc."

Stuart Little

Monsters Inc trailer

"Monsters Inc." marked Pixar's first extensive use of physical simulation in a feature film. Pixar animators directly controlled the movements of the characters' bodies and faces, but much of their hair and clothing movement was computed using simulations of Newtonian physics. Physical simulation allowed a degree of realism of motion that would not have been possible with traditional methods. Nonetheless, adding this type of simulation into the Pixar production pipeline sometimes caused surprising and amusing results. One of the key developments that allowed clothing simulation to go smoothly during the production was a set of algorithms for untangling simulated clothing when it was excessively tortured by the animators. The algorithms allowed the simulator to handle a range of non-physical situations like character interpenetrations without producing unpleasant visual artifacts.

Michael Kass is a Senior Scientist at Pixar Animation Studios. He received his B.A. from Princeton in 1982, his M.S. from M.I.T. in 1984, and his Ph. D. from Stanford in 1988. Dr. Kass has received numerous awards for his research on physically-based methods in computer graphics and computer vision including several conference best paper awards, the Prix Ars Electronica for the image "Reaction Diffusion Texture Buttons," and the Imagina Grand Prix for the animation "Splash Dance." Before joining Pixar in 1995, Dr. Kass held research positions at Schlumberger Palo Alto Research and Apple Computer.

Eric the Worm

Splashdance

David Baraff joined Pixar Animation Studios in 1998 as a SeniorAnimation Scientist in Pixar's research and development group. Prior to his arrival at Pixar, he was an Associate Professor of Robotics, and Computer Science at Carnegie Mellon University. Baraff received his Ph.D. in computer science from Cornell University in 1992, and his Bs.E. in computer science from the University of Pennsylvania in 1987. Before and during his graduate studies, he also worked at Bell Laboratories' Computer Technology Research Laboratory doing computer graphics research, including real-time 3D interactive animation and games. In 1992, he joined the faculty of Carnegie Mellon University. In 1995, he was named an ONR Young Investigator.

Jello on Stairs

Pandora's Chain - CalTech

Gavin Miller and Ned Greene

David Baraff

Ken Perlin is a Professor in the Media Research Laboratory in the Department of Computer Science at New York University and co-Director of the NYU Center for Advanced Technology. 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 1997 he 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. In 1991 he received a Presidential Young Investigator Award from the National Science Foundation.

Dr. Perlin received his Ph.D. in Computer Science from New York University in 1986, and a B.A. in theoretical mathematics from Harvard University in 1979. He was Head of Software Development at R/Greenberg Associates in New York, NY from 1984 through 1987. Prior to that, from 1979 to 1984, he was the System Architect for computer generated animation at Mathematical Applications Group, Inc., Elmsford, NY. TRON was the first movie for which his name got onto the credits. He has served on the Board of Directors of the New York chapter of ACM/SIGGRAPH, and currently serves on the Board of Directors of the New York Software Industry Association.

Perlin's noise function

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 he came to the United States permanently and began his long standing collaboration with IBM as an IBM Fellow at their laboratories in Yorktown Heights.

IBM presented Mandelbrot with an environment which allowed him to explore a wide variety of different ideas. He has spoken of how this freedom at IBM to choose the directions that he wanted to take in his research presented him with an opportunity which no university post could have given him. After retiring from IBM, he found similar opportunities at Yale University, where he is presently Sterling Professor of Mathematical Sciences.

He had been introduced at an early age to the mathematical concepts of the mathematician Julia. At the time it didn't seem clear to him that he wanted to be a mathematician, and he chose to pursue interests in many other areas of science. An interest in geometric concepts brought him back to some of the ideas of Julia. He realized that one unifying aspect of certain geometries 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.

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 fragents. 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 = Z**2 + C. C represents a constant number, meaning that it does not change during the testing process. Z starts out as zero, but it changes as we repeatedly iterate this equation. With each iteration we create a new Z 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). In the top image to the right, 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 in 1982.

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

Loren Carpenter was employed at Boeing in Seattle when he became determined to pursue a career in the evolving graphics film production industry. While at Boeing, he developed what are now-standard algorithms for rendering sculpted surfaces, and for the use of fractal geometry as a tool for creating complex scenes for graphic display.

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 revolutionary work with fractals, along with his other technical expertise, landed him a job with Lucasfilm's Computer Division in 1981. He recreated the fractal mountains used in Vol Libre as part of the Genesis Demo for Star Trek II: The Wrath of Khan. The sequence was so highly acclaimed that it was used in the next three Star Trek movies. Another of his contributions, the A-buffer hidden surface algorithm, was used in the sequence to create the first high-complexity anti-aliased images for motion picture animation.

Vol Libre

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, a title he still holds today. 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, many computer-generated films, including use by Lucasfilm's Industrial Light and Magic to render the dinosaurs in Jurassic Park.

Carpenter has patented a new 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. A variety of wildly 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.

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.

Frame from the film Vol Libre

Loren Carpenter, Rob Cook and Ed Catmull

And the Oscar Goes to...
(IEE Spectrum, April 2001)

http://www.cinematrix.com/

Another important component of complex and ralistic images is accurate lighting. Lighting is one of the most complicated of all computer graphics algorithms, and it is also one of the most critical for believable images. The lighting is what gives the surface detail that is keyed to the object's physical properties. The basis of most lighting approximation techniques is in estimating the amount of light energy being transmitted, reflected or absorbed at a given point on a surface. Almost every reasonable algorithm is derived from the rendering equation, a very important contribution to the field of computer graphics by James T. Kajiya of CalTech in 1986. Kajiya based his idea on the theory of radiative heat transfer.

The intensity of light that travels from point x' to point x assumes there are no surfaces between to deflect or scatter the light. I(x, x') is that energy of radiation per unit time per unit area of source dx' per unit area dx of the target. In many cases, computer graphicists do not deal with joules of energy when talking about intensity of light. Instead, more descriptive terms are used. White, for example, is considered a hot (or high intensity) color while deep blues, purples and very dark shades of grey are cool (or low intensity) colors. Once all calculations are done, the numerical value of I(x, x') is usually normalised to the range [0.0, 1.0].

The quanity g(x, x') represents the occlusion between point x' and point x. The value of g(x, x') is exactly zero if there is no straight line-of-sight from x' to x and vice versa. From a geometric standpoint this makes perfect sense. If the geometry of the scene is such that no light can travel between two points, then whatever illumination that x' provides cannot be absorbed and/or reflected at x. If there is, however, some mutual visibility between the two points, g(x, x') is equal to the inverse of r squared where r is the distance from x' to x (a common physics law).
 
The amount of energy emitted by a surface at point x' reaching a point x is measured in per unit time per unit area of source per unit area of target. This sounds very similar for the units of transport intensity I. The difference however, is that emittance is also a function of the distance between x' and x.
 
Surfaces are often illuminated indirectly. That is, some point x receives scattered light from point x' that originated from x''. The scattering term is a dimensionless quantity.

As one can conclude from the equation itself, evaluating the integrated intensity I for each point on a surface is a very expensive task. Kajiya, in the paper that introduced the rendering equation, also introduced a Monte Carlo method for approximating the equation. Other good approximations have since been introduced and are widely used, but the theory introduced by Kajiya has influenced the derivation of most alternative approaches. Also, much simplified equations for I(x, x') are typically substituted in the case of indoor lighting models.
 

Global illumination refers to a class of algorithms used in 3D computer graphics which, when determining the light falling on a surface, takes into account not only the light which has taken a path directly from a light source (local illumination), but also light which has undergone reflection from other surfaces in the world. This is the situation for most physical scenes that a graphics artist would be interested in simulating.

Images rendered using global illumination algorithms are often considered to be more photorealistic than images rendered using local illumination algorithms. However, they are also much slower and more computationally expensive to create as well. A common approach is to compute the global illumination of a scene and store that information along with the geometry. That stored data can then be used to generate images from different viewpoints within the scene (assuming no lights have been added or deleted).Radiosity, ray tracing, cone tracing and photon mapping are examples of global illumination algorithms.

Radiosity was introduced in 1984 by researchers at Cornell University (Cindy Goral, Ken Torrance,Don Greenberg and B. Battaile) in their paper Modeling the interaction of light between diffuse surfaces.

Like Kajiya's rendering equation, the radiosity method has its basis in the theory of thermal radiation, since radiosity relies on computing the amount of light energy transferred between two surfaces. In order to simplify the algorithm, the radiosity algorithm assumes that this amount is constant across the surfaces (perfect or ideal Lambertian surfaces); this means that to compute an accurate image, geometry in the scene description must be broken down into smaller areas, or patches, which can then be recombined for the final image.

The amount of light energy transfer can be computed by using the known reflectivity of the reflecting patch and the emission quantity of an "illuminating" patch, combined with what is called the form factor of the two patches. This dimensionless quantity is computed from the geometric orientation of the two patches, and can be thought of as the fraction of the total possible emitting area of the first patch which is covered by the second patch.

The form factor can be calculated in a number of ways. Early methods used a hemicube (an imaginary cube centered upon the first surface to which the second surface was projected, devised by Cohen and Greenberg in 1985) to approximate the form factor, which also solved the intervening patch problem. This is quite computationally expensive, because ideally form factors must be derived for every possible pair of patches, leading to a quadratic increase in computation with added geometry.

Radiosity movie (currently unavailable)

Ray tracing is one of the most popular methods used in 3D computer graphics to render an image. It works by tracing the path taken by a ray of light through the scene, and calculating reflection, refraction, or absorption of the ray whenever it intersects an object (or the background) in the scene.

For example, starting at a light source, trace a ray of light to a surface, which is transparent but refracts the light beam in a different direction while absorbing some of the spectrum (and altering the color). From this point, the beam is traced until it strikes another surface, which is not transparent. In this case the light undergoes both absorption (further changing the color) and reflection (changing the direction). Finally, from this second surface it is traced directly into the virtual camera, where its resulting color contributes to the final rendered image.

Ray tracing's popularity stems from its realism over other rendering methods; effects such as reflections and shadows, which are difficult to simulate in other algorithms, follow naturally from the ray tracing algorithm. The main drawback of ray tracing is that it can be an extremely slow process, due mainly to the large numbers of light rays which need to be traced, and the larger number of potentially complicated intersection calculations between light rays and geometry (the result of which may lead to the creation of new rays). Since very few of the potential rays of light emitted from light sources might end up reaching the camera, a common optimization is to trace hypothetical rays of light in the opposite direction. That is, a ray of light is traced starting from the camera into the scene, and back through interactions with geometry, to see if it ends up back at a light source. This is usually referred to as backwards ray tracing.

Nonetheless, since its first use as a graphics technique by Turner Whitted in 1980, much research has been done on acceleration schemes for ray tracing; many of these focus on speeding up the determination of whether a light ray has intersected an arbitrary piece of geometry in the scene, often by storing the geometric database in a spatially organised data structure. Ray tracing has also shown itself to be very versatile, and in the last decade ray tracing has been extended to global illumination rendering methods such as photon mapping and Metropolis light transport.

Photon mapping is a ray tracing technique used to realistically simulate the interaction of light with different objects. It was pioneered by Henrik Wann Jensen. Specifically, it is capable of simulating the refraction of light through a transparent substance, such as glass or water, diffuse inter-reflections between illuminated objects, and some of the effects caused by particulate matter such as smoke or water vapor.

In the context of the refraction of light through a transparent medium, the desired effects are called caustics. A caustic is a pattern of light that is focused on a surface after having had the original path of light rays bent by an intermediate surface.

With photon mapping (most often used in conjunction with ray tracing) light packets (photons) are sent out into the scene from the light source (reverse ray tracing) and whenever they intersect with a surface, the 3D coordinate of the intersection is stored in a cache (also called the photon map) along with the incoming direction and the energy of the photon. As each photon is bounced or refracted by intermediate surfaces, the energy gets absorbed until no more is left. We can then stop tracing the path of the photon. Often we stop tracing the path after a pre-defined number of bounces, in order to save time.

Also to save time, the direction of the outgoing rays is often constrained. Instead of simply sending out photons in random directions (a waste of time), we send them in the direction of a known object that we wish to use as a photon-manipulator to either focus or diffuse the light.

This is generally a pre-process and is carried out before the main rendering of the image. Often the photon map is stored for later use. Once the actual rendering is started, every intersection of an object by a ray is tested to see if it is within a certain range of one or more stored photons and if so, the energy of the photons is added to the energy calculated using a more common equation.

There are many refinements that can be made to the algorithm, like deciding where to send the photons, how many to send and in what pattern. This method can result in extremely realistic images if implemented correctly.

Radiosity grid geometry

http://graphics.ucsd.edu/~henrik/

Paul Debevec earned degrees in Math and Computer Engineering at the University of Michigan in 1992 and a Ph.D. in Computer Science at UC Berkeley in 1996. He began working in image-based rendering in 1991 by deriving a textured 3D model of a Chevette from photographs for an animation project. At Interval Research Corporation he contributed to Michael Naimark's Immersion '94 virtual exploration of the Banff National forest and collaborated with Golan Levin on Rouen Revisited, an interactive visualization of the Rouen Cathedral and Monet's related series of paintings. Debevec's Ph.D. thesis presented an interactive method for modeling architectural scenes from photographs and rendering these scenes using projective texture-mapping. With this he led the creation of a photorealistic model of the Berkeley campus for his 1997 film The Campanile Movie whose techniques were later used to create the virtual backgrounds for the "bullet time" shots in the 1999 Keanu Reeves film The Matrix.

Since his Ph.D. Debevec has worked on techniques for capturing real-world illumination and illuminating synthetic objects with real light, facilitating the realistic integration of real and computer generated imagery. His 1999 film Fiat Lux placed towering monoliths and gleaming spheres into a photorealistic reconstruction of St. Peter's Basilica, all illuminated by the light that was actually there. For real objects, Debevec led the development of the Light Stage, a device that allows objects and actors to be synthetically illuminated with any form of lighting. In May 2000 Debevec became the Executive Producer of Graphics Research at USC's Institute for Creative Technologies, where he directs research in virtual actors, virtual environments, and applying computer graphics to creative projects.

In 2001 Paul Debevec received ACM SIGGRAPH's first Significant New Researcher Award for his Creative and Innovative Work in the Field of Image-Based Modeling and Rendering, and in 2002 was named one of the world's top 100 young innovators by MIT's Technology Review Magazine.

(from Debevec's bio at http://www.debevec.org/)

Dr. Przemyslaw Prusinkiewicz's interest in computer graphics began in the late 1970s. By 1986 he originated a method for visualizing the structure and growth of plants based on L-systems, a mathematical theory of development of multicellular organisms introduced by the late Professor Aristid Lindenmayer. Prusinkiewicz, his students, and collaborators transformed L-systems into a powerful programming language for expressing plant models, and extended the range of phenomena that can be simulated. Specifically, parametric L-systems facilitate the construction of models by assigning attributes to their components. Differential L-systems make it possible to simulate plant growth in continuous time, which is essential to the animation of developmental processes. Environmentally-sensitive and open L-systems provide a framework for simulating the interactions between plants and their environment. The power of these concepts is demonstrated by the wide range of biological structures already modeled, from algae to wild flowers to gardens and stands of trees competing for light.

In addition to the important extensions of L-systems, Prusinkiewicz's research also includes studies of fundamental problems of morphogenesis - emergence of patterns and three dimensional forms in nature. This includes the modeling of spiral phyllotactic patterns in plants, and developmental patterns and forms of seashells.

As a result of the research on the extension of L-systems, plants can be modeled with unprecedented visual and behavioral fidelity to nature. Prusinkiewicz authored the book, The Algorithmic Beauty of Plants, demonstrating that plant models can be combined artistically into stunning and inspiring images. His website, Visual Models of Morphogenesis: A Guided Tour is a spectacular explanation of the techniques used to model organic shapes such as plants.

Developmental sequence of Mycelis muralis.
Copyright © 1987 P. Prusinkiewicz and J. Hanan.

The Garden of L.
Copyright © 1988 P. Prusinkiewicz, F.D. Fracchia, J. Hanan, and D. Fowler.

Topiary dinosaur.
R. Mech, P. Prusinkiewicz, and B. Wyvill.
Copyright © 1994 P. Prusinkiewicz.

Green coneflower.
Copyright © 1992 D. Fowler, P. Prusinkiewicz, and J. Battjes.

Table of cacti, including realistic models of the elongated Mammillaria spinosissima.
Copyright © 1992 D. Fowler, P. Prusinkiewicz, and J. Battjes.

http://www.cpsc.ucalgary.ca/Research/bmv/vmm-deluxe/TableOfContents.html

John Hutchinson demonstrated in 1981a branch of mathematics now known as Iterated Function Theory. Later in the decade Michael Barnsley, a leading researcher from Georgia Tech, wrote the popular book Fractals Everywhere. The book presents the mathematics of Iterated Functions Systems (IFS), and proves a result known as the Collage Theorem.

An IFS fractal, in the sense of Barnsley, is defined by a set of elementary geometric transformations which are called "linear" or "affine" by mathematicians. In the everyday language, they are a combination of

• translations
• rotations
• linear compressions along the vertical or horizontal axis, or both. The compression ratios along the two axes can be different.
• vertical or horizontal shears, such that a rectangle is transformed into a parallelogram through the sliding of a side along itself.

The only requirement is that the transformations must be contractive, i.e. the distance between two points must decrease (at least, not increase) in the transformation.The transformations to be implemented in the IFS set depend upon the figure to be redrawn. There is a magical precept that must be satisfied: if the target figure is transformed through the various transformations in the set, one must get exact parts of this figure, and superimposing all these parts must reconstruct the whole figure.

The Collage Theorem presented an intriguing possibility. If, in the forward direction, fractal mathematics is good for generating natural looking images, then, in the reverse direction, could it not serve to compress images? Going from a given image to an Iterated Function System that can generate the original (or at least closely resemble it), is known as the inverse problem. This problem remains unsolved.

Barnsley, however, armed with his Collage Theorem, thought he had it solved. He applied for and was granted a software patent and left academia to found Iterated Systems Incorporated (US patent 4,941,193. Alan Sloan is the co-grantee of the patent and co-founder of Iterated Systems.) Barnsley announced his success to the world in the January 1988 issue of BYTE magazine. This article did not address the inverse problem but it did exhibit several images purportedly compressed in excess of 10,000:1. Alas, it was not a breakthrough.

The images were given suggestive names such as "Black Forest" and "Monterey Coast" and "Bolivian Girl" but they were all manually constructed. Barnsley's patent has come to be derisively referred to as the "graduate student algorithm."

Barnsley introduced the theory of Iterated function systems (IFS): with a small set of affine transformations it is possible to generate every type of self-similar fractals. The most frequent examples in the book are ferns and Sierpinski triangles.
Based on IFS, Barnsley has a patent for an algorithm that compresses every picture to FIF: fractal image format.

Barnsley Fern

Graduate Student Algorithm:

• Acquire a graduate student.
• Give the student a picture.
• And a room with a graphics workstation.
• Lock the door.
• Wait until the student has reverse engineered the picture.
• Open the door.

Midori Kitagawa, an associate professor in the Department of Art and the Advanced Computing Center for the Arts and Design at Ohio State, developed the Branching Object Generation and Animation System (BOGAS) to create realistic models of trees, plants, blood vessels, nervous systems, underwater animals and even imaginary creatures. The system was designed to help scientists, botanists and artists visualize realistic branching objects, permitting them to generate the objects interactively and then to see how factors like gravity and sunlight affect growth.

I have never seen, but I know...

Above: Solar orbits

Wayne Lytle began his graphics career as a visualization staff member at the Cornell Theory Center. He received a Master's degree from Cornell in 1989 with his thesis titled A modular testbed for realistic image synthesis. His first full multi-instrument music animation "More Bells and Whistles" premiered in the Electronic Theater at SIGGRAPH 1990. It has since won awards and been shown in various contexts world-wide. In 1991 Lytle received an award from IBM for his early work in music animation. Lytle also contributed to the debate about standards for visual representation, which persists along with questions about numerical simulations. This was illustrated by an animation from the Cornell Theory Center by Lytle called The Dangers of Glitziness and Other Visualization Faux Pas, using fictitious software named "Viz-o-Matic." The video, shown in the Electronic Theater at SIGGRAPH 93, documents the enhancement and subsequent "glitz buffer overload" of a sparsely data-driven visualization trying to parade as a data-driven, thoughtfully rendered presentation.

The Dangers of Glitziness and Other Visualization Faux Pas
This is a Windows Media file and will downloaded to your computer.

In 1995, Lytle formed Animusic, a content creation company. Two of the more famous animations are Stick Figures and Pipe Dreams, shown at SIGGRAPH 2000 and 2001, respectively. The principle focus of Animusic is the production of 3D computer graphics music animation. Animusic uses proprietary motion generation software called MIDImotionTM. Without this software, animating instruments using traditional "keyframing" techniques would be prohibitively time-consuming, and inaccurate. By combining motion generated by approximately 12 algorithms (each with 10 to 50 parameters), the instrument animation is automatically generated with sub-frame accuracy. If the music is changed, the animation is regenerated effortlessly.

The technique differs significantly from reactive sound visualization technology, as made popular by music player plug-ins. Rather than reacting to sound with undulating shapes, the animation is correlated to the music at a note-for-note granularity, based on a non-real-time analysis pre-process. Animusic instruments generally appear to generate the music heard, rather than respond to it.

At any given instant, not only do they take into account the notes currently being played, but also notes recently played and those coming up soon. These factors are combined to derive "intelligent", natural-moving, self-playing instruments. And although the original instruments created for the"video album" are reminiscent of real instruments, the motion algorithms can be applied to arbitrary graphics models, including non-instrumental objects and abstract shapes.

After graduating from the University of Illinois with a specialty in mechanical engineering, Chris Landreth joined the North Carolina Supercomputing Center as a scientific visualization animator. He later became a Senior Animator at NCSC, where he produced his famous animation "Data Driven: The Story of Franz K."(1993) in which various artistic elements were mixed with sci vis procedures to create a compelling animation. In 1994, he went to Alias/Wavefront as a Senior Animator, where he produced "the end"(which won a number of awards in addition to an Academy Award nomination.) He has become known for his advanced character animations and scientific visualizations which explore unique ways of representing humanity and nature.

Other Landreth works include "The Listener" (1991), "Caustic Sky: A Portrait of Regional Acid Deposition" (1992), and "Bingo" (1998). Bingo is based on the short play "Disregard This Play" by Chicago's Neo-Futurist Theatre Company. The story deals with the age-old question: "What if a lie is told long enough and loud enough?" Bingo is the first animated short fully produced with Alias/Wavefront's animation software, Maya.

Bingo was originally conceived as an extensive in-house quality assurance project aimed at rigorously testing and demonstrating the technical capabilities of Maya.In his words, "This was in many ways a very unusual production. We were an ad-hoc production studio within a software development company. During this production, people who were programmers, testers and expert users became some of the most brilliant modelers, animators, technical directors and rendering artists I've ever seen in a production environment."

From the October, 1998 Wired Magazine (Amy Johns ):

Beta testers don't usually get much attention on Oscar night. But Chris Landreth - who was nominated for an Academy Award for his 1996 all-digital short The End - is not your usual guy. A senior animator at Alias|Wavefront, Landreth says his job is "to be a tyrant." Long before his company's Maya program hit top f/x houses, Landreth put it to the test, searching for bugs and demanding new features.

For this untrained artist and onetime mechanical engineer, working at Alias is a "Faustian deal." He pushes, prods, and tests products, and in exchange he gets company time to create his own animations. His latest tour de force, Bingo, is a disturbing short based on a play by Chicago's Neo-Futurists. The eerily lifelike effects - from the swing of a pigtail to the twitch of an eyebrow - exploit features Landreth wrested from coders during a year and a half of testing.

In the increasingly specialized CG industry, Landreth relishes his dual role: "I am able to be technical - to help design the software - and at the same time be an artist who tells a story with those tools."

   
Chris Landreth - from The End

from Bingo

from Bingo

Test for hair generation using A/W CompUHair

Scientific Visualization article by Landreth and Rheingold
http://www.cs.umbc.edu/~rheingan/pubs/perception.html

"Hair-Raising Effects"
from CGW October 1995 (hair simulation article)

"Read My Lips"
from CGW August 1997 (lip-synch article)