January 2001

BEHAVIORAL ANIMATION
by Ismail Ziauddin  

Introduction
In the design of computer animation algorithms, key-frame based forward kinematics, inverse kinematics, and physically based methods are the most popular. The physically based methods are developed to achieve a degree of realism in addition to reducing the work an animator has to do to build a series of frames. Among many approaches taken for physically based methods, including those from computer simulation and robotics, I describe here core algorithms for behavior based animation, that is a combination of constraints formulation, with those of robotics for actuator forces, and a simple yet very effective integration scheme. The basic actions of move, chase, their rotational counter parts, and align to dynamic objects are described. Complex animation with differing effects can be achieved by varying various parameters, by moving intermediate target positions on parametric curves and by building behaviors based on basic actions. A method of constraining various parts of objects allows construction of articulated objects. It is possible to constrain any or all six Degrees of Freedom (DOFs) at a joint, and apply actions to articulated objects.

An integration scheme is described that produces better results than Euler’s numeric technique. In other numeric techniques like Runge-kutta method, additional data structures are required to store the state of system before and after each time derivative calculation. These are used when no closed form soultion is available. The scheme described here applies to each object separately, that may offer additional advantages. This author has seen these algorithms in reference [3] before, though described in animation context, but not in the context of behavior based animation. Additionally their handling of the rotational case is different. A very elegant and symmetric method of rotational integration that is directly derived from physical laws emerges once we do away storing rotations in Quaternion or Matrix, and store them simply in Euler angles.

Integration
Consider differential equation for distance traveled derived from Newton’s second law of motion.

Equation 1

That is

Equation 2

Since
Equation 3

Equation 4

Substituting (4) into (2) gives

Equation 5

The counterparts of above equations for rotational motion are
Equation 6

Equation 7

Where

R = current rotation matrix

w = angular velocity

J =  moment of inertia of body

t = torque acting on the body

ea = 3 vector of Euler angles

* = Matrix vector multiplication

Reference [1, 7] gives derivations of these equations 6 and 7.
At every time step dt, first new velocity at time (t+dt) is calculated from 4. Then new position x(t+dt) is calculated from 5. Finally, velocity v(t) is updated with new velocity v(t+dt) and similarly for rotational motion

Listing 1 gives a sample implementation of this integration scheme.

Euler angles are used to store orientation that is a 3 vector. The first element is rotation by x-axis, second is rotation by y-axis and third is rotation by z-axis. Having a 3 vector for orientation simplifies calculations for rotations. The rotation matrix, or quaternion can be derived from euler angles easily when required, for example, a quaternion may be required to be sent to graphics pipeline for output, or to transform a point to world coordinate system.

Expressions like I = RJR(transpose) can be computed directly from elements of two matrices, instead of actually invoking calls to matrix multiplication twice, transpose calculation and matrix equality. The moment of inertia matrix and its inverse can be stored with each object and calculated once in the beginning.

With similar optimizing techniques, this integration scheme gives fast performance.

Forces
In a physically based animation system, forces are applied to objects to animate them. There may be system wide forces acting on all objects like gravity or viscous drags. There may also be specific forces and torques acting on objects to move them in a desired way.

It is very difficult to determine initial conditions and subsequent forces to be applied to arrive at desired motions. It is an active research subject. An actuator generating a force or torque proportional to differences of positions and velocities of source and target is called a proportional derivative controller.

An actuator force to be applied to an object can be obtained from equation 2 if x(t+dt) is considered as target position xt.

Equation 8

Where:

m = Mass

xt = target position

xs = source or current position

vs = velocity of source object

The target can be a moving object with a velocity vt then
Equation 9

Force for a period of one time step dt can be calculated from equation 8 or 9, then integrating by equations 4 and 5 will yield the new position xt of source position xs exactly in time dt, since two sets of equations (4,5) and 9 are derived from the same basic equations.

The rotational counterparts to equations 8 and 9 are
Equation 10

Equation 11

Equation 12

These provide basis for actions for moveto (a fixed target position), chase (catch up with a moving target), and similarly turnto (to a fixed angle), turnchase (turn to a rotating object). By combining transition and rotational components, an object can be aligned to a fixed object in space, or to a moving and rotating object.

An action can be applied for a period greater than a single time step. At every time step a new intermediate target position is computed. For moveto and turnto actions where final target is fixed, these intermediate target positions can be on any parametric curve. The parameter u can be computed from total time of action and time elapsed. This parameter u allows calculation of intermediate target point. For chase and turnchase actions, one can do the only linear interpolation between current position of the source and target.

When constraints as described later in this article are active in the system, displacements are introduced to satisfy constraints; hence, actions applied by above equations do not achieve exact results. Two parameters alpha and beta are introduced to vary the effect of actions as described by following equations.

Equation 13

Equation 14

Equation 15

Equation 16

To stop an object at time t, clear its force and velocity counters, or torque and angular velocity counters for rotational motion.

Listings 2 provide sample implementations for actions

Constraints
Combining various parts that are smaller objects of different shapes and sizes forms an articulated object. The concept of constraint is that point p1 on object o1 is attached to point p2 on object o2 such that these two objects do not separate at these points under all applied forces and torques. Other types of simpler constraints are that a point p1 on object o1 is constrained to a fixed point in space and an object remains in a fixed oriented state. A point is constrained on a parametric curve so that it remains attached to nearest point on curve under applied forces.

An object can have six DOFs, three for translation and three for rotation. It is possible to constrain any or all of three DOFs of each type.

We follow the displacement constraints method as described in [3].

Equation 17

Equation 18

Equation 19

Equation 20

Where

G = center of mass

J = moment of inertia

m = mass

P = the point of attachment

P’ = point P after rotation

* = vector cross product

The translation dx1 and dx2 are to be applied after applying small rotations by dR1 and dR2..

To constrain a point on object to a fixed point in space, let mass m2 and moment of inertia matrix J2 of fixed point tend to infinity. These will make dx2 and dR2 zero. In other words, point P1 is moved back to fixed point to which it is constrained by exactly the same amount of displacement, and rotated back to fixed orientation by exactly the amount of rotation.

To constrain any of three DOFs of each type, store an indication for each type of constraint, in addition to constraint value for that DOF. Then change only those components of three axes that have the indication set to true.

These small rotations and translations are directly added to current orientation and position of respective objects. These displacements are applied after integration is done in the simulation loop, and routines satisfying constraints need to be called in loop until either all constraints are satisfied or a fixed number of iteration is reached. Usually a small number of iterations suffice.

This constrain technique is geometric, because no constraint forces or torques are calculated. Integration will have to be done again, possibly in a loop, if constrain forces and torques are calculated.

Conclusions
Among many physically based methods described in literature, the two most popular are one reduced coordinate method of Featherstone whose excellent reference is [4], and second of Lagrange multiplier method described in [5, 6, 7].

The constrain method allows only point-to-point constraints that suffice to build articulated objects, and is gemetric to achieve simplicity and performance. More complex behaviours can be built from basic actions described here.

Calculation of Moment of Inertia of any type of object is difficult. An algorithm for any type of polygonal object is described in [4]. It is also possible to manually create values of this matrix in three diagonal elements that need not be exact, that additionally gives extra flexibility to create rotations with different effects.

Implementation:

Listing 1:

Listing 2

// COM() returns position of center of mass in World co-od sys
// _off is the point specified in body co-ordinate system on source object to move to target// Xformed(p) returns p transformed to world co-ordianate system// LinearInterpolate(a,b,u) = a + u(b-a), ntar = new intermidiate target position// get(u) returns elapsed time fraction of total time t of action, Lvel() == Linear velocity
VECTOR3                ntar = LinearInterpolate(_objs->COM(),
                 _objt->COM() - ( _objs->XFormed(_off)-_objs->COM() ), getu(dt));

REAL tmp2 = (2.0*_objs->Mass())/dt;

// compute f = (xt - xs)*a*2m/dt2 + (vt-vs)*b*2m/dt
_objs->ForceExt() += ((ntar - _objs->COM()) * tmp2*_a/dt +
             (_objt->LVel() - _objs->LVel()) * tmp2*_b);

// Ts is current orientation
const VECTOR3& Ts = _objs->EulerAngles();

// _target is the final orientation and ntar is intermidiate orientation to turn to
// instead of Linearinterpolation, apply any parametric curve interpolation with suitable get(u)

VECTOR3 ntar = LinearInterpolate(Ts, _target, getu(dt));

// _J = R * mi * RT where R is current rotation matrix and mi is initial moment of inertia of object
_objs->MI(_J);

// compute correction due to angular momentum, Avel() is current angular velocity
// * operator multiplies a matrix by a row vector on left, or a column vector on right, to produce another vector
// vec * vec produces cross product vector
VECTOR3 a1 = (_J * _objs->AVel()) * _objs->AVel();
_J *= 2.0/dt;

// compute T = (2a/dt2) * J * (wt - ws) - (2b/dt) * J * ws - a1
_objs->TorqueExt() += ( (_J * (ntar-Ts) * _a / dt) -
                  (_J * _objs->AVel()) * _b - a1);

Listing 3

References:

[1] Herber Goldstein: Classical Mechanics, Addison Wesley, 1980

[2] John David Funge: AI for Games and Animation, A Cognitive Modelling Approach, A K Peters, 1999

[3]. A. Lamouret, M.P. Gascuel & J.D. Gascuel,: Combining Physically-based Simulation of Colliding Objects with Trajectory Control, The Journal of Visualization and Computer Animation, 6, pp 71-90, march 1995 , http://w3imagis.imag.fr/Membres/Marie-Paule.Cani/publis.html/

[4] Brian mirtich: Impulse-based Dynamic Simulation of Rigid Body Systems, Ph.D. thesis, University of California, Berkeley, December, 1996 http://www.merl.com/people/mirtich/papers/thesis/thesis.html

[5] Andew Witkin, Michael Gleicher, Will Welch: Interactive Dynamics. 1990, http://www.cs.cmu.edu/~aw/gallery.html

[6] D. Baraff: Linear-time dynamics using Lagrange multipliers. SIGGRAPH 1996, http://www.cs.cmu.edu/~baraff/papers/index.html/

[7] Andrew Witkin, David Baraff: Physically based modelling, Principles and practice, SIGGRAPH 1997 Course notes.

GIGnews is a publication of GIGnews.com, Inc.
"Get In the Game" is a registered trademark used with permission.
© 1999- 2005 GIGnews.com, Inc.
Legal