Procedural Animation

Below is a recent research paper I’ve done on procedural animation over the duration of one month in between classes. I take no credit for the ideas presented, as they are not original. To be more precise it is a paper better served as reference notes for future work in the area.

Introduction

Next generation games are becoming more demanding of large behavior sets, and therefore more animations per character. This trend is primarily noticeable through third person action adventure games such as Naughty Dog’s Uncharted, and Rockstar’s Grand Theft Auto 4. This demand is easily the prime reason for increased budgets when creating a next-gen video game [11]. Art assets are numerous and motion capture is often very expansive, especially so for startup studios. Thanks largely in part to systems like Natural Motion’s Euphoria, and Will Wright’s Spore; the industry has turned towards procedural animations.
Animation Systems

There are various forms of animation systems available. These range from simple free-bodies, morphing, articulated animations, and skin-bone animation [00]. This paper will focus on implementing a skin-bone animation, and analyze the restrictions and limitations of such a system.

Skin bone animation combines hierarchical joints that stem from the root (usually being the pelvis area), and associate sets of vertices to a single or multiple bones as is the case with smoothed skin animation.

In order to implement a hierarchical system, each node usually contains a several degrees of freedom, a quaternion to represent rotation, and a vector to represent translation. By distributing the matrix in such a form we cut back from the rather redundant <0, 0, 0, 1> vector for the last row or column in the matrix. Each joint is in reference to its parent, and the root note is respectively in global space. Due to this incoherency, the vertices will need to be translated into world space. This process is often referred to as flattening the hierarchy.

Below is a list of common structures that I will reference in the coming paragraphs. This will also give you a good sense of the architecture [10].

Transform
class transform_t
{
public:
transform_t();
quaternion rotation;
vector3<float> position;
};
A spatial transform structure is a good way to represent joints inside a skeleton structure and similarly we can include the bone information inside this same structure. It’s important to begin to get a good grasp over the required data, over a static composition.

Bone
class bone_t
{
public:
enum
{
X_ROTATION =1<<0,
Y_ROTATION =1<<1,
Z_ROTATION =1<<2
};
bone_t();
float dof[6];
float distance;
int parent;
int options;
};
The bone primarily represents the edges for the skeleton. This one way to go about your architecture and in reality there are many. In this example we specify in the options bit field which degree of freedom we’ll use. Based on that, we can also use the enum declared above to specify which dof (degrees of freedom) we’d like to access. The stored value of a dof is a pair of minimum and maximum values in radians for that joint. Where distance, is the offset along Z-axis. Finally the parent points us towards the index of our parent bone

Animation Sequence
class sequence_t
{
public:
sequence_t();
float fps;
int index;
int numframes;
};
Sequences act very much like mini-players in our architecture where we reference the time, in this case our fps, the index into our frames list which has a reference to a complete pose, and the number of frames to play for.

Our final structure would be a skeleton or a character class that encapsulates all of the above, and handles the hierarchy flattening, updating, rendering, and the animation. In the next section we will discuss motion graphs and talk and how modern games procedurally generate it’s animation from limited budgets.

Motion Graphs
Procedural animations can be classified into three forms. The most common in triple A titles is the parametric approach, which we’ll focus on here. This method is a combination of motion graphs and blending functions. Another approach is often presented by Ken Perlin [03] on his website, where walk cycles, butterfly wings, and other forms of movement are defined by math functions. Spore to some surprise is the former of the two, and the animation system is actually defined backwards where the mesh defines the bone structure and not the other way around. Finally a we have the Euphoria approach which combines rag doll physics system with an animation system and some clever AI to create its own set of procedural animations [11][13].

Taking into consideration only the parametric approaches, data is usually represented through either move trees or motion graphs. The former involves a designer to specify the exact transitions from one animation to another, and usually is done with short clips of animation. Although this process is considerably simpler than motion graphs it is also proportionally more expansive. Each time a new clip of animation is needed, the studio must reserve time for professional actors and/or stunt men to produce, and so these are usually all done in one go and often times don’t come out perfect. At the current state of the industry it is safe to assume that this is the most used approach.

Motion graphs help define transitions from one animation into another where smooth, seamless set of actions can be generated on the fly. This technique to my knowledge was pioneered or made popular by Lucas Kovar [09]. We begin with a corpus of motion capture data. Someone than edits the footage and associates each set of frames with labels. Labels simply act as human-legible strings that define the motion, such as “jump”, “walk”, “kick”, or “ballet”. I will not attempt to recreate Kovar’s work in this paper since his paper on motion graphs is largely distributed over the internet and is cited at the end of the paper. Instead I will help draw an understanding and familiarity with the algorithms involved.

After the motion capture data is recorded and labeled, we begin by generating an error function based of point clouds [16]. For each frame we compute the average distance of from frame i to frame j. From this data we can now generate our error function. See figure above. Next we compute the minima, which are simply points with the highest probability for transitions. Since this error function is based off point clouds, we are now less focusing primarily on the mesh as opposed to the bones which may lead to miss-interpretation. Such as certain rotations, like those in the wrist are sometimes less significant than those of the waist. After our minima is calculated we use those points to build the nodes of our animation and create transitions into other minima via blending functions (see blending below). Next we prune our graph against; dead ends – nodes with no children, sinks – nodes that contain one or only a few children but have many connections pointing towards them. And finally we want to prune our data against nodes that take in one type of label but who’s children do not share the same label for n depth. This final prune helps avoid a character from transition into awkward states in order to reach his goal; like going from “boxing” into “ballet”.

After the graph is properly generated we can utilize A* with heuristics to generate walk paths for our animations. For more on this, again, please reference Kovar’s work.

Blending
Real time animation in video games is evolving beyond cut-scenes and the fidelity involves balancing responsive controls towards smooth animations. We will consider blending techniques from linear interpolation to the more advanced approaches such as discussed by Leslie Ikemoto from the University of Berkley in her paper on Quick Transitions with Cached Multi-Way Blends [02].

Interpolation through functions is the most common form of transitioning from frame to frame of animation. Linear interpolation is the simplest way to handle translation without the seeing obscure artifacts. When handling rotation, by using a quaternion we can avoid scaling artifacts that can arise when using matrices. Spherical interpolation, commonly referred to as slerp is performed on the quaternions [06].

Breezier functions are often also good function to use, since it quite simply the interpolation of A onto B and C onto D and than AB onto CD. For further research on blending, and more particularly motion graph blends, I recommend reading Leslie’s paper on Multi-Way blends, where multiple samples are taken and an average motion is assumed.

Sliding Foot Syndrome

A very common problem when it comes to procedural animations, is the uncanny foot sliding, that creates unrealistic locomotion. This is often due to interpolation blending, that can creates unrealistic forward kinematics, particularly in the feet, since our eyes are so in tune to picking up such subtleties in human motion, the common solution is to perform an inverse kinematics algorithm onto the feet, and essentially clamp them to the ground.

To perform IK, we begin at the end-effectors [07] of the bones, in this case the feet nodes, and then perform the following steps:

1. Given a target point, we perform attempt to rotate our joint towards the target and perform a distance check from the tip of our bone to the target.

2. If we can’t reach the target based on the allowed degree’s of freedom we, begin a recursive process of moving down our hierarchy and readjusting our angles to achieve the maximum possible distance.

This algorithm will not guarantee realistic motion, and weights are often used to prefer one joint to another. Another approach is to split up the geometry into multiple parts, such as the body, arms, and legs. This allows for some optimization, particularly in a system that utilizes instancing. It also avoid obscure postures.

Remember that sometimes reaching the target is not possible, and this should be accounted for, since it may produce artifacts [10].
Creating Intelligence: Behavior Tree Design and Implementation
Due to higher expectations and level of interaction of AI agents, current-gen titles need to be both goal oriented and quick to make changes. The solution has grown to be hierarchical logic. These include HFSM (hierarchical Finite State Machine), HTN (hierarchical task network planner), and hierarchical scripting. Each given advantages and disadvantages, one new technique has emerged that was largely adopted by Damian Isla Halo 2 to be more precise. Behavior trees are the best compromise for the previous three techniques.

A behavior tree, is a tree that defines animations, sounds, into actions and conditions, that make up a task node. A task node can either succeed or fail. Before moving on, I’ll quickly define a composite. A composite can be considered children nodes from a task. These are not leaf nodes usually, but are broken down into two types. Sequencers, and selectors. A sequence is a condition in which case all child nodes must be successful to return true, and selectors return true if any of the children return true. As Alex Champandard points out, these are simply the AND/OR logic that most people are quite familiar with. Sequences and selectors are usually added onto basic state machine by a designer (usually through some sort of GUI). Similarly this has application into scripting. The final piece that makes behavior trees extremely powerful are filters that can be applied between nodes. These filters utilize the decorator design pattern, and can attempt to prune the hierarchy based off specific criteria. Creating multiples of such filters, a behavior tree specific design patterns will begin to immerge. Examples of which are timers, loops, counters, and so on. To learn more about behavior trees, I highly recommend AIGameDev.com, and Alex’s three part video tutorial on the subject.

To relate the topic back to procedural animation, a good approach is to split up the motion graph queries from the higher level logic. Which can be better handled through a separate data structure. Let’s consider a dog that’s currently eating a bowl of dog cereal, but is suddenly attacked. This would involve several very specific animations before going straight into his bark animation. The dog would first stop eating, look around, after he finds his target, glare at it, and begin to growl.

Work Cited
[00] Lecture notes from Real Time Animation by Shawn Stafford. FullSail University.

[01] Learning to Move Autonomously in a Hostile World, Leslie Ikemoto, University of California at Berkeley. http://www.animate-me.com/~leslie/papers/moveAutonomous.pdf

[02] Quick Transitions with Cached Multi-way Blends, Leslie Ikemoto, University of California at Berkeley. http://www.animate-me.com/~leslie/papers/i3d2007.pdf

[03] Ken Perlin’s Experiments on Procedural Animation, http://www.mrl.nyu.edu/~perlin/

[04] Inverse Kinematics by Hugo Elias, http://freespace.virgin.net/hugo.elias/models/m_ik.htm

[05] Inverse Kinematics – Improved Meathods by Hugo Elias, http://freespace.virgin.net/hugo.elias/models/m_ik2.htm

[06] The Matrix and Quaternion FAQ, http://web.archive.org/web/20041029003853/http:/www.j3d.org/matrix_faq/matrfaq_latest.html#Q47

[07] Physics Based Animation by Erleben, Sporring, Henriksen, Dohlmann.

[08] Inverse Kinematics Using Jacobians, http://diegopark.googlepages.com/computergraphics

[09] Motion Graphs by Lucas Kovar, University of Wisconsin Maddison. http://www.cs.wisc.edu/graphics/Papers/Gleicher/Mocap/mograph.pdf

[10] Inverse Kinematics for Humanoid Skeleton Tutorial by Jonathan Kreuzer. http://www.3dkingdoms.com/ik.htm#ikappen

[11] Planting Spores of Procedural Animation? by Dave Mark. http://aigamedev.com/discussion/planting-the-spores-of-procedural-animation

[12] The Crysis of Integrating Next-Gen Animations and AI, by Alex J. Champandard. http://aigamedev.com/reviews/crysis-animation-integration

[13] 9 Tips for Creating Rich Behaviors on a Low Animation Budget, by Alex J. Champandard. http://aigamedev.com/animation/budget-rich-behaviors

[14] The Backbone of AI Behaviors: Movement and Animation, by Alex J. Champandard. http://aigamedev.com/tutorials/backbone-behaviors-movement-animation

[15] Behavior Trees for Next-Gen AI, by Alex J. Champandard (3 parts). http://aigamedev.com/videos/behavior-trees-part1

[16] Point Cloud, Wikipedia (2008). http://en.wikipedia.org/wiki/Point_cloud