Sunday, 16 September 2007

Skeletal Animation and Ragdoll Physics using ODE and MilkShape3D


I haven't got around to working with skeletal animation or ragdolls before, though I am aware of how the theory works and I am familiar with how it could be implemented using the Open Dynamics Engine.

In addition, when working with 3D models, I have always used Quake 1 .MDL, Quake 2 .MD2 and Quake 3 Arena .MD3 files. These formats use "mesh deformation" or "frame-by-frame" animation techniques which make them unsuitable for ragdoll work.

For those of you who are not familiar with the terms "mesh deformation" or "skeletal animation" I offer this explanation:

Mesh Deformation

In "Mesh Deformation", a model is animated in the same way as a flip-book. A flip-book animation of a running stick figure would consist of, for example, 5 different drawings of the stick figure, each one with it's arms and legs in slightly different positions, so that when the drawings are cycled through quickly it appears that the figure is moving. This is why "mesh deformation" is also known as "frame by frame" animation - a 3D model which uses this technique would actually consist of several slightly different models (in the same way that the stick-figure consists of several slightly different drawings) but only one of these models would be shown at a time (in the same way that only one stick-figure drawing would be visible at any precise moment). The model would cycle through these separate frames of animation much like a 3D film, creating the illusion of movement.

This basic technique has a slight problem, though - if the frames of animation change too slowly then the model will appear to be moving jerkily, as the user is able to make out each frame individually, rather than see the overall "effect" of the frames as they change. A perfect example of this is in the original Quake 1 game, where monsters move in a rather jerky fashion no matter how high-end your computer is in terms of graphics power.

There are two solutions to this:

The most obvious approach is to simply use more frames of animation, more rapidly. This means that, for example, the running stick-figure now has 10 frames of animation rather than 5. This allows the artist to create "in between" animation frames for the animation so that the movement of their stick-figure looks more fluid. This technique can be used for both flip-book animations and 3D meshes. However, this approach not only requires the artist to do a lot more work but a (drawing/model) with 10 frames of animation will require twice as much (paper/computer memory and disc-drive space) than one with only 5.

The alternative, used in Quakes 2 and 3, is to use "linear interpolation" (also known as "lerping"). This essentially means that, if a game engine should show animation frame #1 at time=30 seconds and animation frame #2 at time=34 seconds and the current time is 32 seconds, the game will work out a new position for every vertex in the model, exactly halfway between the positions specified by animation frame #1 and animation frame #2. The artist is only required to create a few "key frames" for the model's animation and the grunt work of creating "in-between" animation frames is handled automatically by the game engine. Even better, as this work is done "on the fly", the model will not only transition smoothly between frames 1 and 2, but frames 4 and 9, 7 and 3 or anything else - useful in games, where you may want to go from a running animation to a death animation, a running animation to a shooting animation or a running animtion to a crouching animation. This is the same technique used by Adobe Flash for animating shapes, although Flash refers to it as "tweening" (as it is used to do the inbe-tweening of key-frames).

Skeletal animation.

"Skeletal" (also "jointed" or "boned") animation is a truly distinct concept from that of mesh deformation.

First, a series of "joints" is created. A joint consists of a unique joint ID (such as a number or a name string), a parent ID (similar to the above, but instead of referring to itself it refers to the unique ID of another joint), an XYZ position in 3D space and an angle (probably stored as a quaternion or a matrix).

If a joint does not have a parent - for example, joints may be numbered starting from 1 and the parent ID of the joint is set to zero - then it is completely independant of external influences and it can be positioned or rotated however it wants to be. If the joint does have a parent joint then it's position and angle will be influenced by the position and angle of that parent; It can be referred to as a "child" joint. An imaginary straight line, connecting a parent joint to a child joint, is called a "bone" and a collection of bones forms a "skeleton".

To illustrate, imagine that you have one "parent joint" positioned at your shoulder and another "child joint" positioned at your elbow. When your shoulder joint is rotated, your elbow joint is moved - but when you rotate your elbow joint, your shoulder joint does not change position. Now imagine that your enitre body is "jointed" in this way. Every joint in your body can be represented as either a parent joint, influencing others, or a child joint, being influenced. Some joints may even be both - your elbow may be the child of your shoulder but it is also the parent of your wrist. Additionally, parent joints may have multiple children - for example, one wrist influences five fingers.

Now that we understand how joints can influence each other, we can go on to explain how models can use jointed techniques in animation. Once an artist has created a skeleton for a character, they can create polygons around the bones as "flesh". Every vertex in the model is then mapped to a joint, so that, when the joint moves or rotates, the vertices will move along with it (in much the same way that a child joint will move along with a parent joint).

The result is a model with a skeleton that acts in a similar manner to that of a human. The model can be loaded into a computer game and the physics engine will be able to simulate forces acting upon the model's skeleton in the same way that forces such as gravity influence our own skeletons in reality. Combine this with collision detection and it becomes a "ragdoll" of the kind seen many recent video games.

More recently, the idea of using a system of "weights" to provide more realistic skeletal animation has become popular. However, this is not an area into which I have done much research as of yet.

"Tagged" Animation

To be completely fair, Quake 3 .MD3 meshes do allow a basic form of "jointed" animation (in addition to the legacy frame-by-frame technique which they have inherited from the earlier MDL/MD2 formats).

Each player model in Quake 3 consists of 4 parts: A "head" model, an "upper body" model, a "legs" models and a "weapon" model. These are stored as separate .MD3 files, each of them containing a list of "tags". A "tag" is simply an XYZ position, an angle stored as a 3x3 matrix and a name string (which is used as a unique identifier). This makes them almost, but not quite, the same thing as joints, as they do not have "parent tags" - each tag is influenced by nothing but itself. To connect the head model to the upper body, both the head and the upper body files will contain a "neck" tag. When the models are loaded, the head mesh is repositioned so that it's "neck" tag has the same position and orientation as that of the torso "neck" tag.

There are disadvantages of this approach:
  • As I have already mentioned, tags cannot have parents and so skeletons and bones cannot be formed.
  • Models must be scattered across several files rather than grouped into a single, self-contained one.
  • Triangles cannot use any vertices which are stored in seperate files. This means that each mesh file will appear to be physically unconnected with it's fellows.
It is worth noting that id Software (the creators of the Quake series) were originally going to use skeletal animation for .MD3 meshes, storing animation sequences in separate .MD4 files. However, this was never finished and both the .MD4 file format and Quake 3 skeletal code remain incomplete (this is why Quake 4 meshes are called "MD5" - to prevent confusion with the half-finished MD4 skeleton specification).

The Project.

My current project aims to allow any skeletal mesh formation to be loaded into my physics engine and be treated as a ragdoll. Unfortunately, models stored in Quake .MDL, Quake 2 .MD2 and Quake 3 .MD3 format do not contain any skeleton data and are thus unsuitable for ragdoll models, meaning that I cannot re-use my old mesh loading code. Instead, I have opted to use the MilkShape3D binary ".ms3d" format. It is a very simple format and yet it contains all the information needed to generate a ragdoll and render it.

At time of writing, I have finished creating a simple .ms3d loading API written in C (which loads almost everything aside from the joint animation data, which is not needed as I only require the joint's positions and parent data) and I am writing a simple test application using ODE, OpenGL and SDL.

As I am not a skilled modeller, I have decided to borrow the "Angelyss" model from OpenArena and create a skeleton for it rather than create a whole new character from scratch. So far, I have imported the .MD3 file and created a skeleton but have not yet finished assigning vertices to joints. Click here to see the image.


Lulli said...

Good words.

marco75 said...

Very interesting explanation, thank you!