1. Introduction 1
1.2. Character Animation by Computer 2
1.3. Traditional Character Animation 2
1.3.2. Principles of Character Animation 3
1.3.3. Limitations 4
1.4.2. Totally Computer-Generated Animation 6
2.1.2 Model Control 5
2.2.2 Homogeneous Vectors 6
2.2.3 Homogeneous Transforms 7
2.2.4 Hierarchy 8
2.2.5 Transformation Hierarchies 8
2.2.6 Directed Acyclic Graphs 8
2.2.7 Attribute Inheritance 9
2.2.8 Copying 9
2.3.2 Scripting vs. Interactive Systems 11
2.3.3 Key Frame Animation 12
2.3.4 Spline Interpolation 12
2.3.5 Time Parameterization 14
2.3.6 Applications 14
2.3.7 Multi-Track Animation 15
2.4.2 Skeletons 16
2.4.3 Joints 17
2.4.4 Links 17
2.4.5 Forward Kinematics 17
2.4.6 Rotoscoping 18
2.4.7 Inverse Kinematics 18
2.4.8 Key Joint Angle Interpolation 21
2.4.9 Other Techniques 22
2.5.2 Triangular Meshes 23
2.5.3 Polygonal Shape Interpolation 23
2.5.4 Spline Surfaces 24
2.5.5 Implicit Surfaces 25
2.5.6 Superquadrics 26
2.5.7 Soft Objects 26
2.5.8 Global Deformations 27
2.5.9 FFDs 28
2.6.2 Construction vs. Animation 30
2.6.3 Deformation at Joints 31
2.6.4 Spline Surface Animation 31
2.6.5 Hierarchical B-Splines 31
2.6.6 Blobbies 32
3.1.2. Physics 34
3.1.3. Numerical Programming 35
3.1.4. Computer Graphics 36
3.2.2. Kinematics 37
3.2.3. Newton's Laws: Dynamics 37
3.2.4. Conservation Laws 38
3.3.2. Newtonian Differential Equation 41
3.4.2. Modeling External Forces 42
3.4.3. Constraint Techniques 42
3.4.4. Penalty Constraints 43
3.4.5. Dynamic Constraints 43
3.4.6. Reaction Constraints 43
3.4.7. Augmented Lagrangian Constraints 43
3.4.8. Space-Time Constraints 44
3.5.2. Initial value problems 45
3.5.3. Boundary value problems 46
3.6.2. Create a Higher-Level Model 48
3.6.3. Representation as a Force Differential Equation 48
3.6.4. Different Types of Physically Based Models 48
3.7.2. Free Particle Force Laws 50
3.7.3. Mass-Spring Systems 51
3.9. Rigid Body Mechanics 52
3.9.2. Moment of Inertia Matrix 53
3.9.3. Multiple Rigid Body Systems 53
3.10.2. Snakes and Worms 55
3.10.3. The Critter System 55
3.10.4. Layered Elastic Facial Animation 56
3.10.5. Other Physically-Based Models 57
4.1.2. Skin Deformation 60
4.1.3. Elastic Simulation 60
4.1.4. Interactive Environment 60
4.1.5. Limitations 61
4.1.6. Construction and Animation 61
4.3. A Character Animation Pipeline 63
4.4. A Hybrid Model 64
4.5. The Elastic Surface Layer Model 65
4.5.2. Fat and Connective Tissue Layers 66
4.5.3. Muscle Layer 67
4.5.4. Skeleton Layer 67
4.6.2. Environmental Forces 70
4.6.3. Spring Constraint Forces 71
4.6.4. Reaction Constraint Forces 72
4.6.5. Discretization And Solution 75
4.7.2. Dynamic Effects 79
5.2. Implementing The Elastic Surface Layer Model 82
5.3. User Environment 82
5.4. Constructing a Character 83
5.4.2. Adding Muscles 85
5.4.3. Attaching the Skin Surface 86
5.4.4. Activating Reaction Constraints 86
5.4.5. Binding Surface Points to the Skeleton 86
5.4.6. Sculpting the Fat Layer 87
5.4.7. Animation 87
5.4.8. Interpolation of Key Postures 87
5.4.9. Increasing the Surface Resolution 87
5.4.10. Timing Statistics 88
5.5.2. Event-Driven Model 89
5.5.3. Representing Events 90
5.5.4. Event Handlers and Messages 90
5.5.5. Distribution of Events 90
5.6.2. Widgets 93
5.6.3. Direct Manipulation 94
5.6.4. Mouse-Based Events 94
5.6.5. Transform Events 94
5.6.6. Transform Event Response 95
5.7.2. System Overview 96
5.7.3. IPC Event Message Protocol 97
5.7.4. File Format 97
5.7.5. Memory Management 98
5.7.6. Modeling Classes 98
5.7.7. Maintaining Internal Consistency 99
5.7.8. Event Handling 100
5.7.9. Drawing 101
5.7.10. Motion Control 101
5.7.11. Attribute Inheritance 102
5.7.12. Inside-Outside Tests 102
5.7.13. Picking 103
7. Bibliography 107
Traditional character animation is a highly-developed art form,
but it has several creative and economic limitations. Computer animation
techniques have had great success in other aspects of commercial animation,
but have only recently begun to make inroads into the area of character
animation. Nonetheless, 3D character animation by computer has the potential
to be a flexible and creative medium of expression. This thesis will present
the current state of the art and a solution to some of its current limitations
in the form of a new type of 3D animated character model and an experimental
animation system.
1.1. Animation
The term animation literally means bringing to life. With the development of the motion picture camera, the term has come, in this century, to denote an entire communication and artistic medium. The final result is always the same: an animated film or video presenting an illusion of life, or at least of the natural or physical world. The techniques by which this result can be achieved are varied, ranging from paper cut-outs to clay figures, but the most common and perhaps most highly developed technique of all is the animated cartoon or drawing. Not only does the drawn or painted image provide the greatest flexibility and expressiveness, but it also can call upon thousands of years of artistic tradition in the development of what is still a very new aesthetic idiom.
Starting with Windsor McCay, and perhaps perfected at the Disney Studio in the first half of this century, artists have been able to devote their skills to creating animated characters, be they animals, humans or (normally) inanimate objects, which appear to live and breath, even though they are nothing more than a succession of static drawings. The medium provides an extremely creative environment for the animator: he usually specializes in drawing a particular character, and is able to experiment with and research every detailed aspect of its behavior. In this way he can make the character an artistic extension of his own personality, providing a rich medium for individual artistic expression.
This situation is unlikely to fundamentally change in the near future, despite the wave of new technology now coming into the animation industry, and hand-drawn character animation will doubtless always remain an important animation technique. Nonetheless, there are disadvantages to hand-drawn character animation, and therefore alternative techniques have been developed. For example, the drawn image is an inherently two-dimensional medium, and a great deal of burden is placed on the animator to consistently render a three-dimensional character in two dimensions. The technique of stop-motion or clay animation has been around for as long as hand drawn animation, and it allows the animator to work with a three-dimensional model, letting the camera handle the rendering. Stop-motion animation has its own limits too, particularly in its degree of expressiveness and its physical complexity.
It is therefore not unexpected that the computer, which is becoming increasingly useful in other aspects of the animation process, should have the potential to provide a new technique for character animation. Computer animation of certain types of inanimate objects, for example, is already quite standard in the industry, and computerized paint systems are rapidly making traditional ink-and-paint work obsolete. Character animation, however, is a much more subtle and difficult subject than any of these, and despite more than a decade of research, commercial character animation systems remain rather limited.
I believe, nonetheless, that computer-generated character animation, using three-dimensional character models, holds great promise and will eventually rival traditional techniques not only in speed and economy of production, but also in expressive power. In this dissertation, I argue why I believe this to be so, present my own three-dimensional character model as a solution to some of the problems of computer character animation, and present the software system I have built to implement it.
1.2. Character Animation by Computer
Computer generated character animation remains an open research subject. While many other aspects of commercial animation have developed well-established computerized techniques, character animation is still, for the most part, the domain of the traditional animator drawing by hand or the stop motion animator working with plastic or clay models. In the two-dimensional realm, computerized ink and paint, morphing and image processing have become standard tools. In the three-dimensional area, computer animation of backgrounds and rigid bodies are common techniques. Making deformable, anthropomorphic characters on the computer that have the appeal and subtlety of hand-drawn characters, however, is a much more difficult problem. This dissertation will discuss 3D character animation, which represents one approach to the problem of animating characters by computer.
1.3. Traditional Character Animation
Some writers (e.g. [Solomon 83, 87]) feel that the first fully developed animated character ever created was Gertie the Dinosaur. Produced in 1914 by the cartoon strip artist Windsor McCay, it consisted of over 5,000 ink drawings on paper, with background scenes retraced by an assistant. The smooth motion and distinct personality of the dinosaur displayed the most essential quality of character animation: appeal. Used in the animator's sense of the word, this means the ability to suspend disbelief and to elicit an emotional response from the audience.
Most animation historians agree, however, that it was the Disney studio in the 1930s that brought the production techniques and aesthetics of character animation to its perfected form. Not only did Disney develop most of the production methods associated with commercial animated film production, but he also placed an emphasis on artistic quality and sophistication which has set a standard for character animation ever since. This is the standard against which any character animation by computer must be judged.
1.3.1. Traditional Animation Production Process
Disney attacked the immensely complicated and labor-intensive animation production process by breaking tasks down into a rigid hierarchy and developing a standard production procedure consisting of many stages [Solomon 83]. This series of production steps might be termed, in modern computer graphics parlance, an animation pipeline.
First, a story or screenplay is written and documented down to a scene-by-scene level using a storyboard. This storyboard is basically a cartoon strip with a rough drawing of each shot in the entire film. From the finished storyboard and dialog, a voice track is then recorded and exposure sheets are made from it giving the exact timings of the action to the sound track. The storyboard and exposure sheets are then handed out to the background artists and to the key animators. The background artists paint the static scenes over which the action will take place.
The key animators draw in pencil the characters in their key or extreme positions according to the exposure sheets. This job is considered by many to be the most challenging and creative one in the entire animation process. It is the job of the key animators to create the basic personality of the character and fit its motion into the rigid timing constraints of the storyboard and exposure sheets. These key-frame drawings, together with exact timing information, are then given to the assistant animators or inbetweeners. These artists fill in the missing frames by interpolating between the key frame drawings. The completed pencil-drawn frames are then filmed and viewed to check the animation for any mistakes or artistic problems. This preliminary film is called the pencil test.
Once the drawings have passed the pencil test, they are sent to the clean-up artists, who trace them onto a new sheet of paper with a single clean outline to replace the rough sketches and construction lines of the animators. These cleaned-up drawings are transferred to sheets of clear acetate, which are called cels. This transfer was done originally by hand tracing the cleaned-up drawing directly onto the cels in ink, using a brush or pen. Later this was done mechanically using a photocopy process directly onto the acetate. The cels are then colored in by painting the reverse side with acrylic paints, resulting in finished cels.
These cels are then sent to the camera operator, who layers them on top of the backgrounds created by the background artist and photographs them in succession. This stage can become quite elaborate with multiple layers of cels and multi-plane cameras to simulate a kind of perspective. The processed film is then edited together to form the final film master.
1.3.2. Principles of Character Animation
The Animators of the Disney studio did not just develop a production process. They also developed a stylistic idiom for the new art-form of animation. Some of the essence of this style can summed up in a list of general principles of character animation which were presented for the computer graphics community by John Lasseter [Lasseter 87, 89]:
Timing -- Spacing actions to define the weight and size of objects and the personality of characters.
Anticipation -- The preparation for an action.
Staging -- Presenting an idea so that it is unmistakably clear.
Follow Through and Overlapping Action -- The termination of an action and establishing its relationship to the next action.
Straight Ahead Action and Pose-To-Pose Action -- The two contrasting approaches to the creation of movement.
Slow In and Out -- The spacing of the inbetween frames to achieve subtlety of timing and movement.
Arcs -- The visual path of action for natural movement.
Exaggeration --- Accentuating the essence of an idea via the design and the action.
Secondary Action -- The action of an object resulting from another action.
Appeal -- Creating a design or an action that the audience enjoys watching.
Character animation styles themselves varied considerably, forming a spectrum from pure caricature on the one hand (e.g. anthropomorphizing inanimate objects such as trees or cars), through natural-looking but non-the-less talking animals, to realistic portrayal of the moving human form. The first important example of this style of human animation was Snow White in the movie Snow White and the Seven Dwarfs, and it is notable that Disney was forced to base many of her movements on live-action footage to make it convincing enough for his standards.
1.3.3. Limitations
A natural question to ask is: why does this traditional animation process need to be computerized? There is a legitimate concern that the computer will remove much of the creative aspects of the process. The answer, in my opinion, is that there are several important limitations of the traditional process. These limitations are not only economic, but also creative. First of all, the sheer amount of labor required in the traditional process can be economically prohibitive: good animated films are simply not getting made because they are too expensive. One attempt to deal with this problem is to export the labor-intensive portions to low-wage countries. Computerization could therefore be a way of increasing the efficiency of animation workers and making animation production more globally competitive. Secondly, the slow turn-around time and large number of hands through which a simple animated sequence must pass make it difficult for a creative animator to get the kind of immediate feedback necessary for a truly iterative artistic process. The computer therefore presents the possibility for the animator to immediately see the finished results of his work. By reducing the number of people required, more individual creativity becomes possible. With the computer, it may even become possible for a single person to create an entire feature film by himself. This alone could bring about a significant stylistic change in the medium.
Studying the traditional animation production process is important for the development of new computer animation techniques for two reasons. First of all, the computer techniques can be very similar to the traditional ones and in fact are often modeled after the traditional ones. Computer graphics modeling is always searching for metaphors to make the abstractions of the subject more accessible and the traditional techniques provide just such metaphors. Secondly, it seems fairly certain that the introduction of computer techniques to the commercial animation industry will continue to be more an evolutionary than revolutionary process. Although there is already a niche within the industry for totally computer generated animation, computerization of the mainstream animation production process has taken, and will continue to take, the form of a step-by-step encroachment onto its various stages, normally replacing the most tedious and least creative ones first.
1.4. Computer Animation
1.4.1. Computerizing Traditional Animation
To take a look at just how much computer techniques have already taken hold in the industry, let's start with a non-computer technology that immediately replaced one stage in the traditional process in the 1960s: xerography. This eliminated the need for hand-tracing drawings to cels. Later, in the 1970s, video pencil-test systems speeded up the feedback loop to the animator and all but eliminated the need to shoot pencil tests on film.
By the nineteen eighties, two computer graphics techniques became well enough established and understood that they could start to be applied to the traditional animation process. First, two-dimensional image processing and frame-buffer techniques became of sufficient quality that drawings or even live-action film could be digitized, manipulated on the computer, and then output directly to film. This presented the possibility that the latter stages of the animation process, such as ink-and-paint and camera work, could be computerized. Secondly, the ability of the computer to render and animate rigid polygonal bodies from any camera angle became well-established. This offered the potential for certain types of static backgrounds, such as architecture, to be completely generated on the computer, as well as certain types of foreground objects such as cars, spaceships, etc. These could either be output as pen-plotted line drawings for photographing on a traditional animation camera stand, or composited directly with digitized drawing on a computer paint system.
With the release of Disney's Beauty and the Beast, we can see that at the beginning of the nineteen nineties both of these aspects of computerization have become accepted. This was the first Disney animated film to be colored in an entirely paintless system. All line drawings were inked in by hand and then digitized, into the computer paint system. From that point on, all coloring, compositing of images, and image-processing effects were done on the computer and then output directly to film. In addition, several background scenes, for example the ballroom interior, were done completely using a 3D computer animation system.
1.4.2. Totally Computer-Generated Animation
So far, we have been talking about an evolutionary approach to computerization of the animation industry. There is another, more revolutionary approach to computer animation: the completely computer-generated animated film. The idea here is to work completely within the creative limits of the computer as a medium, and perhaps to generate a new kind of aesthetic in the process. This sort of computer animated film has existed since the 1970s, especially in the areas of experimental animation, with such pioneers as Larry Cuba and the kind of work fostered by the National Film Board of Canada.
Initially, these films would take advantage of what the computer could do best, focusing on geometrical shapes and simple two-dimensional shape interpolation and inbetweening techniques. Commercially, the completely computer-generated film (or video) achieved its fame and seemed to find its niche with the notorious "flying logo" sequences on television. This took advantage of something that 3D computer animation could do very well: rigid body and camera motion. It has, in fact, achieved its own sort of aesthetic based on the grace and smoothness of large glittering objects in motion.
Totally computer generated 3D animation entered the field of Disney-type character animation with short films such as Pixar's Luxo Jr. and The Adventures of Andr and Wally Bee, which were animated by a traditionally-trained animator, John Lasseter [Lasseter 87]. Luxo Jr. used an articulated figure of rigid objects to animate a Luxo lamp, demonstrating that, by using the stylistic principles of traditional animation, it is possible to make a photo-realistic, rigid object come to life and be appealing. At the other end of the spectrum of realism, the film Rendevouz Montral demonstrated 3D character animation. in the form of realistic human animation using synthetic actors [Thalmann 87], while a more caricatured type of human animation was displayed in the film Tony de Peltrie [Bergeron 86].
The state-of-the-art in 3D character animation by computer is now perhaps embodied in a subsequent Lasseter film for Pixar, which won an academy award, called Tin Toy. This film featured a somewhat successful attempt to animate a human baby with deformable skin. As a result of its success, this film serves to highlight not only the successes of 3D character animation to date, but also its limitations.
1.5. Summary of Thesis
This thesis will review these successes and limitations in a survey of the current state of the art in 3D character animation. It will also present some of the latest modeling and animation techniques, in particular, interactive 3D graphics and physically-based modeling. It will then go on to identify some of the specific problems with current 3D character animation and how these can be approached through the use of layered elastic models, which utilize physically-based modeling techniques. An original layered elastic model, the elastic surface layer model, will then be presented, followed by a description of its implementation using the LEMAN animation system which was designed and programmed by the author.