Keywords: computer animation, dynamic simulation, robotics, articulated body dynamics. 

Abstract
There is a certain demand in the industry to create more and more complex games, featuring convincing representations of real and imaginary scenes and creatures. Physically based modeling is one direct way to address this problem. Since scientific accuracy is not as essential for games as artistic content and gameplay "flow", what kind of advantages does physical modeling have compared, for example, with key-frame animation?  

Perhaps, the most important factor is that properly implemented physical simulation gives "accuracy in the details", which is difficult to achieve using other methods. Yes, motion capture will be realistic per se, but it may be prohibitively expensive and is not very flexible or adoptive. Besides, games frequently involve situations, which are not closely related to reality. Motion capture would be impossible for animation of, for example, a velociraptor charging on the prehistoric plains. Meanwhile, physical laws were the same millions of years ago and, probably, the same throughout the universe.

Robust physical simulation may serve as a keystone in the implementation of "actor-in-the-box" concepts, where autonomous actors, augmented with adaptive behavior mechanisms, populate virtual words of various kinds. Quick game design may be feasible with this approach.

The mathematics developed by industrial robotics simulation work are finding applications in computer graphics for the realistic animation of virtual creatures. In particular, the forward dynamics algorithms, which compute the motion of articulated bodies given the joint torque and external force inputs, offer a reasonably complete physical model for animation. There are two important approaches to the solution of the forward dynamics problem. The reduced or generalized coordinate approach (Featherstone, Brandl, Lilly, Orin, Lathrop) uses structural recursion to solve the problem in a reduced coordinate space such as the space of joint angles. The maximal coordinate approach (Baraff) uses Lagrange multipliers to solve a constraint system in the 6 degree of freedom motion space. Both methods yield O(n) algorithms. The structurally recursive method is the most efficient in floating point operations but the Lagrange multiplier approach may offer better memory access locality and cache performance.  

This paper provides a tutorial base for the physics involved in the structurally recursive algorithm and then describes a modular set of objects for constructing an articulated body and simulating its dynamics. We deal with a set of rigid bodies connected by joints. In the simple case, where there are no closed loops of connected bodies, the algorithm is quite simple. The Brandl algorithm for the case with closed loops is also discussed and is considerably more complex. We discuss issues related to numerical integration, integrator drift, and performance optimizations, in particular tuning the underlying linear algebra and matrix package and grouping matrix storage for efficient memory access on Intel platforms. 

Joint torques as a function of time must be specified in order to synthesize articulated body motions such as walking or running. These values are generated by dynamic controllers. Real life creatures use their muscles to control their motion. In its original form, the Featherstone algorithm had spatial forces and torques as inputs, and joint accelerations as outputs and thus required a controller to generate the inputs. Inverse dynamic methods enable computation of torques, based on known accelerations. In a hybrid dynamics method, which we describe here, some joints have their acceleration (or velocity) predefined, while for others it has to be computed. Thus makes it possible, for example, to specify leg motions during walking and then to compute the dynamic motion of the whole creature.  

Our implementation is based on the fact, that the Featherstone algorithm establishes a linear dependency between accelerations and forces (due to Newton's second law a = f/m). As a result, it is possible to compute acceleration in the system as a linear combination of unknown values (torques and spatial forces). After that, we may compute these unknown values by solving a system of linear equations using controller generated accelerations. The rank of this system is equal to the number of unknown variables (related to the controllers) and considerably smaller, then rank of the system used in the Lagrange multiplier method (6 * <number of joints>). This approach also has nice implications for the numerical stability of the equations of motion, because it enables the controller to influence the motion of the body as a whole, without delays. 

The presentation will go with "Physically based animation" demo, as it was shown in Intel's booth on Siggraph-98.

Earlier version of this work may be found at CGDC site as

http://www.cgdc.com/1998/vault/wcd00506.doc

http://www.cgdc.com/1998/vault/wcd00505.ppt

http://www.cgdc.com/1998/vault/wcd0010c.avi

It did not consider inverse dynamics and hybrid methods in great details though, which we are planing to do for GraphiCon’98.

E-mail:
Alexander.Reshetov@intel.com
Michael.J.Shantz@intel.com