Russell Turner1 and Enrico Gobbetti2

All of these limitations can be potentially overcome by using the computer as a creative tool for the character animator. The most advanced approach is to model the character directly in three dimensions as an articulated figure. Animation can then be accomplished by evolving the model's joint angles over time using a variety of techniques such as forward and inverse kinematics1,2, forward and inverse dynamics3,4,5,6, procedural modeling7, motion capture8,9, and spacetime constraints10. Many commercial software systems (e.g. Alias/Wavefront, Softimage) and several in-house software systems (notably, Pixar's Marionette) allow the interactive creation and animation of 3D articulated characters. However, at least two major problems still prevent 3D character animation from being fully accepted by the animation community as a genuinely superior alternative to traditional animation. First is the difficulty of building good 3D character models that allow natural looking deformation of the skin surface as well as high-level animator control. Second is the lack of intuitive and powerful user interfaces that take full advantage of the animator's real-world artistic technique.

The ideal 3D character model should provide a good compromise between high-level animator control and physically realistic behavior. One approach to this is to allow the animator to directly control the joint motion of the articulated figure through animating its joint angles, while the skin deformation is calculated automatically in a natural-looking way according to some small, intuitive set of skin behavior parameters. A variety of geometric modeling methods have been proposed for representing deformable animated characters, such as standard polygonal surface meshes, free-form deformations11,12, implicit surfaces such as soft objects13, 14 and parametric surfaces such as tensor product splines or hierarchical B-splines15, 16. These purely geometric techniques are straightforward, provide ease of control and rapid computation but they have little relation to the physical reality of a flesh and blood creature, and therefore tend to lack realism. In particular, they tend to represent characters either as geometric surfaces, or as uniform solids, both of which ignore the complex internal structure of human or animal anatomy and are unable to provide dynamic deformation effects that are the hallmark of high-quality traditional animation. These kinds of effects are referred to by animators as squash-and-stretch, in which volume is conserved as a character undergoes deformation, and follow-through which describes the deformation caused by inertia when a character decelerates2.

Physics-based deformable models17, are derived from the elastic and viscous properties of continuous media and therefore can produce very realistic looking simulations of deformable materials. Like all physics-based models, however, they are usually difficult to control, so to be useful to animators they must be constrained properly18,19. Because they represent continuous media as large numbers of discrete nodal elements, elastic models can also be very CPU-intensive, especially when simulating solids using three-dimensional lattices. However, elastic surfaces, simulated as two-dimensional lattices, require fewer numbers of discrete nodes to produce visually interesting results and therefore are not as demanding of CPU time. It is now possible, using high-end workstations, to simulate a reasonably complex surface of a several hundred mass points at interactive rates.

The goal of this paper is to describe a working system that addresses both the modeling and simulation aspects of creating and animating characters on the computer. The system is based on earlier versions20, 20, 22 to which we have added an improved character model, a completely new equation solver and performance evaluation. The system, called LEMAN (Layered Elastic Model ANimation system), uses a highly interactive direct manipulation user interface and a hybrid character model that combines an elastic simulation of skin deformation together with standard techniques for animating the articulated skeleton. For the remainder of this paper we will present the different aspects of LEMAN and demonstrate how it can be used to construct and animate simple characters as well as some limited forms of human animation. First, we give an overview of the layered approach to character modeling. Second, we discuss our elastic surface layer model and the techniques we use for physical simulation and for the numerical solution of the equations. Then, we present our 3D user interface and illustrate the construction of a simple character. Finally, we discuss the results obtained and provide a view of future work.

For designing animated characters, a common approach taken by artists and traditional animators is to work in layers. First a stick figure is drawn, representing the skeleton, followed by rounded forms to represent the flesh, followed by the finished outline, representing the skin23. This same sort of approach is taken in clay animation, where plasticene is wrapped around a metal armature.

It is not surprising that the first computer animated characters should also be constructed in layers. The film Tony De Peltrie used combinations of digitized facial expressions to deform a polygonal surface24. Implicit surfaces, called soft objects or blobbies, surrounding a stick figure skeleton have been used to create deformable characters13. Forsey used hierarchical B-splines with control points attached to a skeleton for modeling animals and human joints25. Shen combines these two approaches, wrapping NURBS surfaces around an internal layer of implicit surfaces16.

Layered elastic models add physics-based elastic components to some or all of the layers to improve realism. We use the term elastic to distiguish them from other deformable models that are not based on simulation of elastically-deformable materials. A simple example of this type of approach is Pacific Data Images' Goop system, in which a mass and spring with damping are attached to each vertex of a polygonal model26. Moving the model causes the vertex points to oscillate, causing a jello-like effect. However, the surface points are not attached to each other, so the skin has no surface-like physical behavior.

A more sophisticated examples of layered elastic construction for animated characters is found in the Critter system27 in which a network of connected springs and masses is used to create a control point lattice for free-form deformations of the geometric surface. Some of the control points are bound to links of the underlying skeleton so that, when the skeleton is animated, the unattached mass points are influenced to move through the spring lattice. In this way, a physical simulation controls a solid deformation. Although the mass-spring lattice allows for shape control over the muscle deformation and a technique for bending at the joints, the skin is still fundamentally a geometric surface model, not a model of a physical skin. Similarly, a model for articulated figures is proposed by Gascuel and colleagues in which the control points for an interpolating spline surface are bound to a rigid bone layer by springs28.

The finite element method is used by Gourret et al29, who describe a human hand modeled as a volume element mesh surrounding bones, and Chen et al.30, who have developed a biomechanically-based model of muscles on bone. These approaches focus more on obtaining realistic simulations, while being computationally too expensive to be effectively used for interactive character animation.

A sophisticated example of a layered elastic model is used by Terzopoulos and colleagues to implement facial animation31, 32. In this model, an elastic solid simulation, consisting of a mass-spring lattice of depth three, is attached to a human skull model and deformed by muscles which take the form of force constraints between the skin surface and the underlying bone. The springs are biphasic to emulate the non-linear behavior of real skin, and volume preserving constraints simulate the effects of incompressible fatty tissue.

Many of these techniques are now becoming available in commercial character animation systems such as the Dynamation system of Alias/Wavefront's Maya product, which implements soft-body dynamics for characters using simulated damped springs attached to skin surface control points33.

The skin layer is at the starting point for the elastic surface layer model and is the only layer that is purely physics-based, using a simplified physical model of a continuous elastic surface17.

We have therefore chosen to represent the muscle layer, as well as the underlying bone layer, by deformable geometrical solid surfaces which the skin may not penetrate. Geometric constraints are used to force the skin outside of the muscle layer surface, but leave it free to slide along the surface until it finds an energy minimum. Since, in the worst case, every point on the surface must be tested for penetration, it is important that the muscle geometric models allow for quick inside/outside tests. For this we use spheres and implicit surfaces such as super quadrics which have a simple inside/outside function, together with global deformation functions34, 35. The muscle shapes are attached as links to the skeleton joints so that they move as rigid components of an articulated figure. The flexing and bending of muscles is simulated by animating the parameters of the global deformations, either directly using key-frame interpolation, or by tying them to the joint angle values of the joints. While this is a rather simplistic model of muscle, more sophisticated physics-based or procedural models can easily be substituted, provided that they have an efficient inside/outside test algorithm, while leaving the bone layer as simple rigid bodies.

where t is the simulation time, r(t) = (r1(t)T ... rP(t)T)T is the P-dimensional vector of mass point positions at time t, v(t) is the vector of mass point velocities at time t, M is the PxP-dimensional constant diagonal inertia matrix, f(r(t), v(t)) is the vector of forces applied to mass points at time t, gk(r) is the inside-outside function the implicit surface representing muscle j. Note that r, v and f are P-dimensional vectors containing 3-dimensional vector elements.

To determine the elastic forces, the deformable surface is modeled as a three-dimensional function of a two-dimensional material coordinate system, referred to as the u-coordinate system. The total elastic energy of the surface can then be represented by a scalar-valued functional . The elastic force at each point on the surface is represented by the variational36 derivative . The fact that this local quantity depends on a functional of the entire surface is the reason this kind of elastic model is non-linear. Note that this is an equation in force per u-coordinate area, or force density.

The choice of functional, , is determined by the elastic properties of the surface and choosing a good model of these properties can influence ease of solution as well as the quality of the simulated behavior. We use the elastic model proposed by Terzopoulos (see reference17 for full details of the elastic force model).

Following Terzopoulos17 we discretize equation (1a) using finite differences, into an MxN rectangular mesh such that the M and N dimensions correspond to the u1 and u2 local coordinates respectively. We then obtain the approximation

where is the difference vector from the fixed point to the skin surface point, is the difference between the fixed point velocity and the skin surface point velocity, j is the initial length of the spring, ks is the spring constant and kd is the damping coefficient. By tuning the parameters of the springs (ks , kd and l(0)ij), the animator can fine-tune the behavior of the skin. High values of ks , for example, result in skin that clings tightly to the skeleton, while low values result in loose, floppy skin that hangs down below the skeleton under the influence of gravity. Adjusting the values of kd controls how fast the skin follow-through dies down.

where g is the acceleration of gravity in the appropriate direction and g is a global damping factor.

During simulation, the skin must be maintained outside the bone and muscle layers at all times. Instead of modeling non-penetration through reaction or constraint forces18, 19, we model this behavior using a two-step process, first evolving the unconstrained ODE (1a) for a small timestep before directly correcting the state of the system to enforce possibly violated constraints (1b). The constraint resolution technique is detailed in the Section on numerical integration.

Constraints are defined by the implicit inside-outside functions gk(r) that determine the shape of the muscles (currently spheres or superquadrics with local and global deformations34, 35). To speed-up the inside-outside tests, the mesh surface is traversed hierarchically using a quadtree scheme in which a lower-resolution subset of the surface points is selected initially for the inside-outside tests, from which a higher-resolution subset is determined according to a distance threshold. To model fat thickness at a point we actually apply the constraints to the corresponding point on the inside of the fat layer

While implicit techniques are generally more stable and permit bigger stepsizes, the time spent in the construction and solution of linear systems of equations is too big, at least in our implementation, to meet the high simulation rate criterion. Among the explicit techniques, we have obtained the best results with the second-order Verlet method37, 38, modified to take into account velocity-dependent forces39 The method is explicit and self-starting, evolving the state of the system from a time t to a time t+h starting from initial conditions (rt,vt) according to the following procedure:

where v(scale) is a scaling vector used to normalize errors, e(v) is a user defined tolerance for the estimation of velocities, and the "*" operator performs componentwise multiplication. To provide the user with control on both absolute and relative error, v(scale) is defined as:

where v(threshold) defines the maximum magnitude of a velocity component after which error control switches from absolute to relative40. Since small adaptive timesteps are used, the fixed point iteration (10c)-(10g) for the velocity estimation converges very rapidly. Because rt+h/2 remains constant during the iteration, only velocity-dependent forces have to be recomputed at each step.

To control the stepsize, we estimate the accuracy of the solution rt+h by comparing it with the alternate solution given by embedded lower-order formulas40. In case of the Verlet method, the embedded formula is simply the explicit Euler method:

where r(*)t+h is the unknown exact position vector at t+h, and the scaling vector r(scale) is determined from rt and the user-defined parameter r(threshold) by the same technique used for v(scale). The next stepsize h1 can then be determined by

where e(r)) denotes the user-specified desired accuracy. If D is smaller than e(r) the step is accepted and h1 is used for the next step, otherwise the step is rejected and the smaller stepsize h1 is used to repeat it40.

After a step has been accepted, the system has to enforce all constraints in (1b) that have been violated. This is done by directly moving any points inside the muscle shapes to the surface, and by adjusting the velocities to simulate an inelastic collision. For each point (i,j) violating a constraint gk, we thus compute the new state of the system by

where rijunconstrainedt+h and vijunconstrainedt+h are the position and velocity computed during the integration step, lg and —gk are the distance and the unit gradient to the constraint surface evaluated at rijunconstrainedt+h, vij//t+h and vij^t+h are the parallel and perpendicular component of the velocity with respect to the constraint gradient, and rijconstrainedt+h and vijconstrainedt+h are the corrected position and velocity components.

To control the error introduced during constraint resolution, we limit the magnitude of the correction of each position component to be smaller than a user specified threshold e(c). If the threshold is exceeded, the step is rejected and a new step with stepsize hc < h is attempted. hc is determined by a standard root bracketing procedure so that gk(rij(t+hc)) ³ 0 for all constraints violated at time t+h. The process is similar to the collision resolution techniques used in rigid-body simulation systems41. Alternative techniques to enforce non-penentration are reaction18 or Lagrangian constraints42 However, reaction constraints, while having computational costs similar to the technique outlined here, have the important drawback that violated constraints require multiple timesteps to be resolved. Lagrangian constraints solve this problem, but are more expensive to compute, requiring the computation of constraint Jacobians and the solution of a linear system.

Character construction is an important creative aspect of physics-based layered character animation since so much of the character's animated behavior is determined by its structure. We therefore focus our efforts on improving the user-interface for this task, which, given the structure of the layered model, is mainly concerned with providing effective ways to perform the following operations21:

It is only recently that techniques for interaction with synthetic worlds have tried to go beyond straightforward interpretation of physical device data43. By contrast, recent research in the 3D interaction field has focused on exploring responsive 3D interfaces with better affordances, functional fidelity and mental appeal44, 45, 46. This research, while dramatically improving the expressive power of desktop computers to accomplish 3D tasks, has not taken advantage of the latest developments of virtual reality technology to increase the bandwidth and fidelity of man-machine communication. In most cases, the interaction tools reside in 3D space, but are operated with the 2D mouse and presented to users using a conventional perspective view on a workstation monitor.

One of our goals for the animation system was to augment the 3D workstation desktop user-interface to create a restricted, but high-quality form of virtual reality, one that would give a compelling sense of immersion within the confines of the desktop world, but would at the same time be expressive and ergonomic enough for people to use for extended periods of time to do practical work. Recent research on "fishtank VR"47 and on projection-based systems48 has started to focus on these techniques.

In the LEMAN system, a six degree-of-freedom head-tracker and CrystalEyes shutter glasses are used to produce stereo images that dynamically follow the user head motion. We have used both Polhemus Fastrak magnetic and Logitech ultrasonic sensors to track the head and 3D mouse motion. As in49, the left and right viewing frusta are recomputed at each frame from the physical position of the viewer's eyes and the physical position of the display surface. Each of the frusta is a truncated pyramid with apex at the eye position and edges passing through the corners of the rendering viewport. The position of the left and right eyes are computed from offsets from the tracked head-position, while the position of the display surface in tracker coordinates is determined by a calibration step that has to be re-executed only when the screen monitor or the tracker reference frame are moved. Our current calibration procedure simply consists of measuring the position of the four corners of the workstation monitor with the 3D mouse. Thanks to the registration between virtual and physical coordinates, 3D virtual objects can be made to appear at a fixed location in physical space which the user may view from different angles by moving his head. The combination of physically accurate perspective, stereo viewing, and motion parallax provide a compelling illusion of the existence of the simulated 3D objects.

Thanks to head-tracking, camera motion can take advantage of simultaneous position and velocity control, and a single control mode has characteristics which are at the same time appropriate for close inspection, exploration, and navigation50. In our system, the Spaceball incrementally controls a virtual vehicle, and tracked head and right hand positions are interpreted local to that vehicle. Relying on an incremental device such as the Spaceball for vehicle control reduces the user's fatigue, as opposed to solutions based on absolute devices such as those presented in reference50, since the left hand can rest on the Spaceball support and only very small finger movements are necessary for motion control.

The different components of an animated character are created, connected and manipulated using virtual tools which are encapsulations of a physical appearance and a behavior43, 51. Since tools are manipulated with the right hand using absolute input, the user can have the visual impression of touching the virtual objects that are close to him. These virtual tools are in some ways 3D analogs of the types of interactive tools found in typical 2D drawing programs (e.g. select, resize, create-circle, spray-paint). However, since they are inherently three-dimensional, they are capable of performing more sophisticated 3D spatial tasks, and are often more intuitive for 3D operations than their two-dimensional counterparts since they correspond more closely to a real-world tool. Like a 2D drawing program, the various tools are arranged in a toolbar from which the current tool may be selected using the 3D mouse. Once selected, a copy of the tool is displayed at the current position of the 3D mouse, representing a 3D cursor. A visible "wand" extends a few centimeters out from the cursor and is used for picking objects and specifying positions in space, and a button on the 3D mouse allows picking and dragging operations. The large number of degrees of freedom and direct-manipulation capabilities of these virtual tools allow complex interactive operations, which might otherwise require several 2D widgets and 2D mouse, to be performed naturally with a single virtual tool.

To give users the impression of manipulating real objects, it is important that the lag between their movements and the effects in the synthetic world be as small as possible. This is obtained in LEMAN by decoupling the simulation and tracking activities22. At each frame, the following actions are taken:

Since the motion tracker is sampled at a much higher rate than the frame rate of the application (60 Hz vs. 10 Hz), and since on our machine (an SGI Onyx RE2) computing the simulation is more expensive in time than rendering the character, reading tracker values twice per frame (once before computing the application behavior and once just before rendering the frame) allows the reduction of the most important lags, i.e. those of the objects directly associated with the physical position of the user. The perceived hand and head motion lag is determined by the rendering time and does not depend on the simulation time. This lag reduction technique is similar to just-in-time-synchronization52 with a priority given to the user's position as in DIVER53.

With LEMAN, the animator can build up a three-dimensional character model from scratch, adjusting parameters and moving it interactively throughout the process to test its appearance and behavior. Once the character is constructed, it can be saved to a file for future use. The main operations involved in character creation have been implemented so as to take advantage of head-tracked stereo-viewing and a two-handed direct-manipulation interface. The hand-eye coordination made possible by the registration between virtual and physical space which allows a variety of complex 3D tasks necessary for constructing 3D animated characters to be performed more easily and more rapidly than is possible using traditional interactive techniques. The following sections describe the main steps involved in the creation of a 3D characters, contrasting our user-interface with traditional desktop approaches such as those used in our previous work20, 21. The pictures presented in the following sections were taken by tracking the position of the camera using the Logitech ultrasonic head tracker. MPEG video files presenting live video clips can also be viewed at the following web address: http://www.crs4.it/~gobbetti/group_homepage/contents/projects/ongoing/leman/index.html. Figure 6 shows a user in the process of constructing a character.

In a direct manipulation user environment, it is usually easier to build both muscle and skeleton layers simultaneously, since the geometric link shapes provide something tangible to manipulate. Articulated figures are constructed by selecting one of the shape creation tools (e.g. sphere, superellipse) and selecting a point in space causing a new joint be created at that location. Dragging the tool, by holding the 3D mouse button down while changing its position and orientation, changes the size and shape of the muscle associated with the joint. For example, drag-translating the tip of the sphere creation tool wand will vary the radius of the sphere, while drag-rotating the superellipse creation tool will vary its curvature parameters. The direct correspondence between the physical location of the hand tracker and the effect on the manipulated objects gives invaluable help when creating the character, since the size of the character's muscles and the position of the joints are controlled directly in the physical space (Figure 7). Traditional user-interfaces such as the one used in reference21 offer only indirect control over these parameters.

In order to check that the articulated figure has been properly constructed, the user must be able to move the skeleton into various postures easily. This is done in the LEMAN system using the inverse kinematics tool, which implements a standard technique used in computer-based character animation that allows the posture of a kinematic chain (e.g. arm, leg, spine) to be specified by moving the end joint of the chain, known as the end-effector. To change the posture of the character's skeleton, the user simply selects the end-effector joint with the inverse kinematics tool and drags it to the desired new position. The entire kinematic chain up to the nearest branching point in the skeleton hierarchy will then follow the motion of the end-effector1. This movement can be either a translation, a rotation or both. This differential vector is then multiplied by the inverse Jacobian of the kinematic chain to determine the corresponding differential joint angle values, which are added to the current joint angles54. This process is repeated for each event at interactive speeds so that the user has the impression of directly manipulating the skeleton by moving a particular joint. This can easily be replaced with a more sophisticated method when desired. The direct correspondence between physical and virtual locations allows for a direct control in space of the end-effector movement, while the control offered by a non head-tracked application can only be approximate. The behavior of the character can thus be tested more effectively. Figure 8 shows the inverse kinematics positioning of a character's body.

The final character shape may be sculpted to a fair degree by locally adjusting the thickness of the fat layer. Since the fat thickness is a single parameter associated with each point on the skin surface, it can be controlled very naturally using the "liposuction" tool, which increases or decreases the fat thickness of the skin in a Gaussian distribution around the selected point on the skin surface (Figure 10). The implementation of fat thickness is described in detail in20. This tool is analogous in some ways to a spray-can tool in a 2D paint program in that the longer the user holds down the mouse button, the more fat is injected into the skin. The orientation of the tool along its main axis differentiates between injection or removal of fat: a clockwise rotation with respect to the initial orientation injects fat, while a counter-clockwise rotation removes it. Figure 11 shows the final character, which was created in only a few minutes. Texture-maps have been added using a conventional user-interface.

Once the character has been constructed and all of its physical parameters defined, it may be animated simply by animating the skeleton. The motion of the skeleton provides the input forces which drive the skin surface. There exists a variety of dynamic and kinematic techniques for animating articulated figures. We have chosen a key-frame animation technique in which a series of key postures is specified and a smooth skeletal motion is interpolated between them1. The key postures are specified interactively using the inverse kinematics manipulator described in the previous section. Although the interpolated skeletal motion is a purely kinematic one, the resulting dynamic motion of the skin is physically simulated, resulting in a richer form of automatic inbetweening. For example, a perfectly cyclical skeletal motion such as a walk sequence will not necessarily result in a perfectly cyclical skin motion, but rather will vary somewhat from cycle to cycle, depending on the time constants of the elastic surface.

Once a desired posture has been found, the user can store its joint angles as a key posture. A series of key postures can then be used to interpolate a smooth motion, using interpolating splines on the joint angles55.

To animate the figure, the user positions the skeleton into a sequence of key postures, either without the elastic surface, or with the simulation running at a low surface resolution for interactive speed. A smooth motion can then be created by interpolating the joint angles using an interpolating spline55. This motion sequence can be played back in real time, to check the animation, or in (usually non-real) simulated time to calculate an animation sequence at high surface resolution.. To give an idea of what the final animation sequence will look like, the simulation can be turned off and then the skeleton motion sequence can be played back at full-speed. To get an accurate impression of the skin dynamics, the simulation can be turned back on while the skeleton motion is played back in simulation time. Key postures can be edited by selecting the particular key and repositioning the skeleton interactively.

LEMAN has been implemented in C on Silicon Graphics workstation. Figures 13, 14, and 15 show some of the characters that have been created so far with the system. Our current implementation makes it possible to work at interactive rates with characters of sufficient complexity. Table 1 summarizes the performance obtained with our system on a Silicon graphics Onyx RE2. Three different explicit solvers were used to integrate the differential equations of motion: a fixed timestep first-order Euler solver, the adaptive second-order Verlet solver described in Section 4.2, and an adaptive second-order Runge-Kutta solver40. For each of the solvers, performance has been measured with the high-resolution versions of the three characters presented in figures 13 to 15. The Verlet solver performs consistently better, enabling high-resolution simulations to run at 1/8 to 1/28 of real-time. Simpler versions of the same characters with skin meshes of 256 mass points are interactively animated at 1/2 to 1/7 of real-time, and may thus be effectively used for behavior testing and during animation design.