We begin our study of character animation by examining the skeleton, the underlying foundation of the digital character, upon which body, motion, and personality are built.

A character’s *skeleton* is a pose-able framework of
bones connected by articulated joints, arranged in a tree data structure. The
skeleton itself is generally not rendered, but instead can be used as an
invisible armature to position and orient render-able geometry such as a
character’s skin, as we will see in later chapters.

The *joints* allow relative movement within the
skeleton, and they are represented mathematically by 4x4 linear transformation
matrices. By combining the rotations, translations, scales, and shears possible
with these matrices, a variety of joint types can be constructed, including
hinges, ball-and-socket joints, sliding joints, and various other custom types.
In practice, however, many character skeletons can be set up using only simple
rotational joints, as they can adequately model the joints of most real
animals.

Every joint has one or more *degrees of freedom *(DOFs),
which define its possible range of motion. For example, an elbow joint has one
rotational DOF as it can only rotate along a single axis, while a shoulder
joint has three DOFs, as it can rotate along three perpendicular axes. Individual
joints usually have between one and six DOFs, but all together, a detailed
character may have more than a hundred DOFs in the entire skeleton. Specifying
values for these DOFs poses the skeleton, and changing these values over time
results in movement, and is the essence of the animation process.

Given a set of specified DOF values, a *joint local matrix*
can be constructed for each joint. These matrices define the position and
orientation of each joint relative to the joint above it in the tree hierarchy.
The local matrices can then be used to compute the *world space matrices *for
all of the joints using the process of *forward kinematics*. These world
space matrices are what ultimately place the virtual character into the world,
and can be used for skinning, rendering, collision detection, or other
purposes.

In many ways, a digital character’s skeleton is analogous to the skeleton of a real animal. Real world animals with true bones are called vertebrates, and this group includes humans, mammals, reptiles, fish, and birds. The use of a virtual skeleton to animate these creatures makes perfect sense, but digital bones don’t necessarily have to correspond to actual bones. In addition to animating rigid movement, they can be used to animate facial expressions, soft tissues such as muscles and fat, mechanical parts such as wheels, or even clothing. Skeletons can be used to animate humans, aliens, robots, plants, cartoon characters, insects, vehicles, furniture, and more.

[Image: critters with skeletons]

In this chapter, we will examine the internal workings of the virtual skeleton. [Section 2.1] discusses the details of forward kinematics and how it is applied to skeletons, starting with a brief review of some 3D geometry and linear algebra topics. [Section 2.2] presents a variety of specific joint types that can be used in a character, as well as the matrix construction needed for these joints. [Section 2.3] introduces the concept of a pose and [section 2.4] presents some implementation details on skeletons and their implications on real time performance.

The term *kinematics* refers to the mathematical
description of motion without considering the underlying physical forces.
Kinematics deals primarily with positions, velocities, accelerations, and their
rotational counterparts: orientation, angular velocity, and angular
acceleration. In this chapter, we are simply considered with computing static
poses for skeletons and so we will limit our analysis mainly to positions and
orientations.

The skeleton itself is usually treated as a purely kinematic
structure. Higher-level systems may animate the skeleton with physical forces
if desired, but those dynamic systems are typically layered on top of an
underlying kinematic framework. We will examine *dynamics*, or the study
of physically based motion later in [chapter 12], but for now, we will
concentrate on the kinematics of the skeleton.

Two useful kinematic analysis tools are *forward
kinematics* and *inverse kinematics*. Within the scope of character
animation, forward kinematics refers to the process of computing world space
joint matrices based on specified DOF values, whereas inverse kinematics refers
to the opposite problem of computing a set of DOF values that position a joint
at a desired world space goal. Both forward and inverse kinematics are used in
other fields such as robotics and mechanical engineering, and there is
extensive literature available on the subject. We study forward kinematics here
and will examine inverse kinematics later in [chapter 10].

This section presents a review of some basic linear algebra
and is intended mainly as an introduction to the notation and standards used
throughout this book. It is not intended as a complete introduction to the
subject, however, as there are numerous good books on linear algebra and
introductory computer graphics [MOLL99], [BUSS], [LINEAR], [

Before delving deeper into the subject of character animation, we must first make a few basic definitions about coordinate systems. Throughout the book, we will use a three dimensional, right handed coordinate system by convention, meaning that the z-axis is the positive cross product of the x- and y-axes, with x pointing to the right, y pointing up, and z pointing to the viewer.

Figure [x]: Right-handed coordinate system

Because the positive z-axis points outward, the viewer therefore looks in the –z direction. To be consistent with this coordinate system methodology, a character in a ‘default’ orientation would be aligned with the viewer, and would therefore look in the –z direction as well. Lights, cameras, vehicles, and other objects that get positioned with matrices will all be assumed to be facing down the –z axis in their default orientation.

[Image: camera, character, light, & vehicle facing in –z direction]

Historically, different software and hardware rendering systems have disagreed upon the choice of coordinate systems and many different standards exist. The use of a right-handed system with the positive z-axis facing the viewer is probably the most widely accepted of these standards within the computer graphics industry and so it will be used here. In any case, it is always possible to change from one representation to another with one additional transformation (see [appendix A] for more details).

A vector **v** in 3D space has three individual scalar
components representing its coordinates along the x-, y-, and z-axes.

_{}

Vectors typically represent either a position or a
direction, but they can also be used for more abstract constructs. The *magnitude*
of a vector is a scalar representing the Euclidean length and can be computed
as:

_{}

If we are only interested in the direction that a vector is
pointing and not its magnitude, it is often more computationally convenient if
the length of the vector is exactly 1. We define a *normalize* operation
which returns a unit length vector as follows:

_{}

Most of the vectors we will use in this book represent some 3-dimensional geometric property, but they are not strictly limited to being 3D.

It is common practice in computer graphics to perform vector computations using 4D homogeneous space. Doing so allows various different operations (such as rotations and translations) to be combined into a single methodology. For details on homogeneous space, consult an introductory graphics text such as [MOLL99], [BUSS] or review [appendix A].

[more: homogeneous space]

_{}

The 4x4 homogeneous matrix is a useful tool in computer graphics due to its ability to represent both the position and orientation of an object in space. Matrices can transform geometric data from one space to another and they are used extensively throughout character animation for a variety of purposes. To be consistent with most graphics texts, we choose to define the matrices with the translation along the bottom row, instead of along the right column as in many engineering texts. The right hand column is mainly used for viewing projections and is rarely needed for character animation. In almost every 4x4 matrix used in this book, the right hand column will contain three 0’s starting from the top and a 1 at the bottom. Matrices will generally take the following format:

_{}

where **a**, **b**, and **c** are the three basis
vectors defining the orientation of the matrix and **d** is the position.
Usually, the three basis vectors will be of unit length and will be
perpendicular to each other, making the matrix *orthonormal* or *rigid*,
but this is not a strict requirement and some matrices may break that
convention.

Figure [x]: Basis
vectors **a**, **b**, **c**, and position **d** of matrix **M**

[more: image: equal sized axes, illustrate ‘d’ better]

A vector is transformed by a matrix in the following manner:

_{}

where **v**’ is the resulting transformed vector and (.)
is the vector dot product. If **v** is a vertex in an object’s local
coordinate system and **M** is a matrix placing the object in world space,
then **v**’ will be the vertex’s location in world space. The inverse of
this transformation is written as:

_{}

where **M**-1 is the *matrix inverse* of **M**.
If **M** is a matrix that transforms from local to world space, then **M**-1
will transform from world space to local space.

[more: matrix concatenation]

For more information on matrix operations and linear algebra, see [appendix A] or [MOLL99][BUSS].

In 3D graphics and animation, we define a fixed coordinate
system called the *world coordinate system* or simply *world space*,
in which all objects, characters, effects, cameras, lights and other entities
are ultimately placed. The terms *global coordinate system* and *global
space* are also commonly used and mean exactly the same thing, but for
consistency, we will stick with the use of the word *world* rather than *global*.

Individual objects are typically defined in their own *local
space* and make use of 4x4 matrices to transform to world space.

In a typical interactive graphics application, many
different objects will need to co-exist in world space. Some of these objects
are simple rigid objects, like a chair, for example. To manipulate the position
and orientation of a simple object like this, we could use a single 4x4 matrix
to transform the chair’s vertices from its local space to world space. This
matrix is called the chair’s *world matrix*, as it positions the chair
into the world.

A more complex object, such as a character, will have many
moving parts, and so will require many matrices. In order to render the
character in the world and perform other operations such as collision detection,
we need to know the world space matrices of all of the joints in the
character’s skeleton. It is difficult and unintuitive to specify character
joint matrices directly in world space, and so skeletons are built up of a
hierarchy of local transformations, each defined relative to the one above it.
The joint matrices are defined in this *local space* and are converted to
world space by the process of forward kinematics, described below.

To render a view of the 3D world, we place a virtual camera
with a matrix called a *camera matrix*. The space representing what the
camera sees is called *view space* and objects are transformed into this
space by the *view matrix*,* *which is the inverse of the camera
matrix.

The topology of a skeleton is an *open directed graph*,
or *tree *(also called a *hierarchy*). One joint is selected as the *root
*and the other joints are connected up in hierarchical fashion.

To keep the definition of a skeleton simple, we will restrict them to being open trees without any closed loops. This restriction doesn’t really prevent kinematic loops in the final animated character, as we will learn about in [chapter 10].

The nodes in the tree represent the joints of the skeleton.
They could just as easily represent the bones, and in fact, there is little
difference between the concept of a bone and a joint, as the motion of a
particular bone is the same as the motion of the joint controlling it. In this
book, the two will be treated as the same thing, i.e., we may occasionally
refer to a joint such as the shoulder in the exact same way we would refer to
the bone directly manipulated by that joint (in this case, the upper arm or *humerus
*bone). For consistency, we will usually describe things in terms of joints
unless the situation specifically warrants the use of bones.

Figure [x] shows an example skeleton for a simple robot character. The hierarchical structure of the same skeleton is shown in figure [x], with the root located at the top of the figure.

Figure [x]: Simple character skeleton

Figure [x]: Hierarchical graph of skeleton joints

The choice of which node to make the root is somewhat arbitrary, but it is usually convenient to select something near the center of the character. A common choice on animals is somewhere in the spine, so that both the pelvis and torso can be attached underneath in the tree.

The root can be treated as a special joint that capable of unrestricted rotational and translational movement. In most characters, all other joints would have restrictions on their motion.

A node directly above another in the tree is that node’s *parent*.
All nodes will have exactly one parent except for the root node, which has
none. A node directly below another in the tree is that node’s *child*,
and a node may have zero or more children. Child nodes inherit transformations
from their parent nodes, so that if an elbow is rotated, for example, all of
the joints in the hand will follow correctly. Nodes at the same level under a
common parent are called *siblings*.

Figure [x]: Node hierarchical relationships

A child of a child, (etc.) is called a *descendant* and
a parent of a parent (etc.) is called an *ancestor*. Nodes with no
children are called *leaf nodes* and nodes with children are called *interior
nodes*.

It is said that a joint down in the tree *inherits* its
transformation from its ancestors, that is, its own transformation builds on
the ones that came above it. This concept can also be applied to other
properties, such as rendering materials, or other visual properties, but we
will not consider any of these other types of inheritance here.

The inheritance of the linear transformation information is handled through the process of forward kinematics and relies specifically on matrix concatenation, which is discussed in [section 2.1.3].

An alternative view of the skeleton hierarchy is presented in [figure x]. It contains essentially the same information as the view in [figure x], but it is rearranged to list the joints in a linear fashion. Accessing joints as a linear array can be convenient in many situations, and if a design calls for it, it is easy for both tree and array representations to coexist.

- Root
- Torso
- Neck
- Head
- ShoulderL
- ElbowL
- WristL
- ShoulderR
- ElbowR
- WristR
- Pelvis
- HipL
- KneeL
- AnkleL
- HipR
- KneeR
- AnkleR

Figure [x]: linear representation of character hierarchy

To compute world space joint matrices, we will need to
perform a *depth-first tree traversal*
of the skeleton. A depth-first traversal starts at the root node and traverses
down through each of the children. When a child node is visited, each of its
children are then traversed. Only when all of a node’s children have been
visited does control return to the parent node. In this way, all nodes are
visited once. When a node is visited, an arbitrary operation can be performed,
in the case of a skeleton, it will be forward kinematics computations.

Figure [x]: Depth first tree traversal order

The linearized hierarchy presented in [figure x] lists the
nodes of the skeleton in the same order that they would be accessed in a
depth-first traversal. One can see in this representation that before any
particular node in the tree is reached, all of its ancestors will have been
traversed already. This ensures that the necessary information about the node’s
parent will be computed already. It is also possible to traverse the hierarchy
in a *breadth-first* traversal, but
this is generally a bit worse on caching performance, and won’t be discussed in
this book.

A movable joint has one or more degrees of freedom, but typically they won’t have more than three. A free rigid body has 6 DOFs (3 to describe its position and 3 more to describe its rotation), but there isn’t really any reason why a joint couldn’t have 6 or even more DOFs. The root joint of a skeleton can be treated as a 6-DOF joint in most cases, unless the skeleton is somehow constrained to a fixed coordinate system.

The term ‘degree of freedom’ is a general term that includes not only joint angles, but also joint translations, scales, or any other types of motion a joint may allow. In the next few chapters, we will see how the concept of a DOF can be extended further to include any other property we may wish to animate.

As DOFs can represent different types of quantities, it is important to keep track of the units used. For example, a rotational DOF could use degrees, radians, or any other arbitrary unit, as long as it is used consistently. Throughout the book, we will assume that rotational DOFs use radians and translational DOFs use meters.

A joint must take the input DOF values and use them to
generate a *joint local matrix*. This matrix is a 4x4 homogeneous
transformation matrix that defines the joint’s current position and orientation
relative to its parent joint. Different types of joints will use different
methods for generating this matrix. We will examine several common joint types
and their corresponding local matrices in [section 2.2] later in this chapter.

Joints will typically have a fixed *offset* position in
the parent node’s space, which acts as a pivot point for the joint movement.
The pivot point of an elbow, for example, stays at a fixed location relative to
the shoulder joint, as the shoulder joint itself moves about. For flexibility,
we treat this offset as a general 3D vector, **r** and will use it for all
joint types. To handle this offset mathematically, we add the offset vector **r**
to the bottom row when we construct the joint local matrix. A joint local
matrix **L **that does nothing other than apply this constant offset would
be written as:

_{}

For a 1-DOF rotational joint that pivots about the x-axis by an angle [theta], the matrix would be:

_{}

[Figure x] illustrates a rotational joint with a fixed offset. Joint local matrices for other joint types are discussed in [section 2.2].

[Image: rotational joint with fixed offset]

Some 3D animation systems allow a full fixed transformation to apply to the joint instead of just a positional offset. The use of a full transformation means that we must apply a matrix multiplication to compute the complete joint local matrix instead of simply adding a translation to the bottom line. The purpose of this full transformation is to allow joints to rotate or translate around arbitrary axes, but as we will see throughout [section 2.2], there are other straightforward ways to achieve this. Still, a full fixed orientation change can be supported for individual joints if desired. We will avoid this extra matrix, however, as we prefer other means for achieving the same results.

Joint DOFs can have limits on their range of movement. For example, the human elbow can bend to about +150 degrees (about 2.1 radians) and hyperextend back as much as –10 degrees (about -.17 radians). Limits should be able to be set on a DOF-by-DOF basis. In practice, it is common to have minimum and maximum limits for each DOF that can be enabled or disabled independently.

[Image: joint limits]

For most joints, the DOF values are completely independent
and can easily be *clamped* to within legal limits on an individual basis.
It may, sometimes, be desirable to describe joint limits with a more geometric
or general-purpose method. This is especially true for quaternion rotational
joints where joint limits can’t be implemented by simple clamping. We will
examine geometric joint limits in more detail in [section 2.2.2].

[more: clean up]

Concatenating the local matrices to make the world space
matrices is straightforward and makes use of matrix algebra and the very useful
properties of 4x4 homogeneous matrices. To compute all of the world space
matrices for a skeleton, we begin at the root and perform a depth-first tree
traversal. For each joint visited in the traversal, we compute its world space
matrix **W**joint by multiplying its local matrix **L**joint by its
parent’s world space matrix **W**parent:

_{}

The root node has no parent, and so **W**parent is just
the identity matrix, which causes its world space matrix to be equal to its
joint local matrix.

Many modern CPU and graphics processors are equipped with vector floating point units that are designed specifically to handle 4x4 matrix concatenation and similar computations. Taking advantage of features like these should result in significant performance gains.

The end result of the forward kinematics process for a skeleton is a set of world space matrices- one for each joint. If we assume, for now, that the character is posed by some higher level system and its joint DOF values are all specified, then the two main computational steps needed per joint to compute the world space matrices are:

- Generate joint local matrix
- Concatenate joint local matrix to compute world space matrix

There are a variety of different local matrix constructions depending on the types of joints used, but the matrix concatenation phase where the world space matrices are computed is simple and consistent.

[more: elaborate on algorithm]

In this section, we examine several different joint types and present formulas for constructing their joint local matrices.

In realistic characters, most or all joints will be rotational. Both 1-DOF and 3-DOF rotational joints are common, and 2-DOF joints are used occasionally as well.

Perhaps the most useful joint type in computer character
animation is the 1-DOF rotational joint, sometimes called a *hinge joint*.
Elbows and knees are good examples of hinge joints. Multiple 1-DOF hinge joints
can be combined together to construct 2- or 3-DOF joints if desired, but those
joints can also be treated as unique types.

The hinge joint can be specified to rotate about any axis. Most often, animation systems allow users to create joints that rotate about the local x, y, or z axes, but it is also possible to define joints that rotate about any arbitrary axis. By definition, a positive rotation about an axis will cause an object to rotate counterclockwise when viewed from the direction that the axis is pointing.

A general 1-DOF rotational joint is illustrated in [figure x].

[Figure x]: 1-DOF hinge joint

To formulate the complete joint local matrix for an x-axis
rotational joint, we add in the positional offset vector **r** to the bottom
line of the matrix to get:

_{}

Similarly, the joint local matrix for a hinge joint that rotates about the positive y-axis is:

_{}

and for rotation about the positive z-axis:

_{}

It is often desirable to allow hinge joints to rotate about
an arbitrary axis. Given an arbitrary unit vector **a** defining the desired
axis of rotation, the formula for the joint local matrix becomes:

_{}

where _{}=_{} and _{}=_{}.

2-DOF rotational joints can be found in some places such as
the wrist, the clavicle-sternum joint, and the first joint in the thumb. A *universal
joint *in an automobile drive shaft is another example, and indeed, 2-DOF
rotational joints are sometimes referred to as universal joints.

2-DOF rotational joints can be constructed as a combination of two sequential rotations about different axes. Usually, two principle axes are chosen such as xy, xz, or yz, but one could create a 2-DOF joint out of any two arbitrary axes if desired.

Joint local matrix formulas for xy, xz, and yz joints are presented below:

_{}

_{}

_{}

where _{}=_{}, _{}=_{}, etc.

It should be noted that a 2-DOF joint could simply be constructed by connecting together two 1-DOF joints, or even by using a 3-DOF joint and just setting one of the DOFs to zero. Either of these options is of course possible, however, it is likely that if 2-DOF joints are required, supporting them explicitly would be slightly faster at the expense of some minor additional code complexity.

3-DOF rotational joints are found in important joints in the
body such as the *ball-and-socket* joints of the hips and shoulders. As
mentioned earlier, it is possible to construct a 3-DOF rotational joint out of
3 independent 1-DOF joints, but it is still worth considering a 3-DOF joint as
a unique type.

[Image: 3-DOF joint]

With matrix algebra, multiplication is not commutative, that
is **AB** is not equal to **BA**. This means that attention must be paid
to the order that rotations are performed in multiple DOF rotational joints.
Often, commercial animation packages allow the user to specify an arbitrary
rotation order for each joint (such as xyz, xzy, yxz…). Sometimes, this extra
flexibility is useful in interactive applications as well.

_{}

_{}

_{}

_{}

_{}

_{}

where _{}=_{}, _{}=_{}, etc.

[more: rotation order, Euler angles, problems, multiple representations, gimbal lock…]

Rotational joints can also be implemented with quaternions. A quaternion is a mathematical construct that can represent an arbitrary 3D orientation without some of the complications that Euler angles are prone to.

Quaternions were first introduced by William Hamilton in 1843 and further developed by Arthur Cayley, Josiah Gibbs and others. They have more recently become a popular method in computer graphics for handling orientations since their introduction to the graphics literature in [SHOE85], and have been an active research topic in modern graphics, physics, engineering and mathematics.

A quaternion is a vector in 4D space that can be used to define a 3D rigid body orientation:

_{}

Usually, they are constrained to be of unit length, and we will apply this constraint to all quaternions used in this book.

_{}

A quaternion can be thought of as a rotation about an
arbitrary axis. Any orientation can be represented by a single rotation around
some unit length axis **a** by some angle *theta*, and quaternions are
related to this axis and angle by the following formula:

_{}

The formula for the joint local matrix of a quaternion joint is:

_{}

A brief introduction to quaternions is provided in [appendix A] and quaternion interpolation is discussed in [chapter 6]. For more information about quaternion mathematics and its uses, see [KUIP99], [BUSS], and [SHOE85].

Because the 4 variables in the quaternion don’t correspond to intuitive geometric values, it is not practical to implement quaternion joint limits by just clamping the 4 variables to some pre-defined range, as with joint limits for other DOF types. This makes it necessary to take a more geometric approach to defining the joint limits for quaternion joints, which can actually be more powerful and general purpose than the simple DOF clamping approach.

[more: cone joint limits]

Although quaternions are certainly a powerful way to store and manipulate arbitrary orientations, they are not necessarily a total replacement for the more traditional Euler angle approach. Clearly, for 1-DOF rotational joints, a single axis rotation matrix would be faster and simpler than using a quaternion, and so a general purpose skeleton system should be prepared to support a variety of joint types and configurations. If multiple joint types were allowed, then it wouldn’t be very difficult for an animation system to support both Euler angle joints and quaternion joints, selectable on a joint-by-joint basis. It may even be desirable to allow rotational joints to be handled as quaternions in certain situations and as Euler angles in others. For the purposes of this book, however, we will just consider a quaternion joint as a unique joint type.

Quaternions tend to be particularly useful when there is a need to support interpolation between arbitrary orientations without suffering from gimbal lock and the order dependent problems we find with Euler angles. The human shoulder is a good example of a joint that often needs to interpolate between widely varying orientations. However, there are occasions when the less sophisticated Euler interpolation scheme actually works better and may even look more natural. The human hip might make a good example of this. Even though the hip is a ball-and-socket joint like the shoulder, it has a more limited range of motion, making it less prone to Euler interpolation problems. The important point is that there isn’t one method that works best in all situations. The following chart is provided to compare some of the relevant issues between the two:

## Quaternions |
## Euler Angles |

Handle arbitrary interpolations well |
Don’t handle arbitrary interpolation well |

One consistent representation |
12 (or even more) possible representations |

Joint limits require custom handling |
Joint limits very simple |

4 interrelated variables, which may require special handling by higher level animation code |
3 totally independent variables |

Interpolation computations are slower |
Interpolation computation is fast |

Conversion to matrix format is very fast |
Conversion to matrix format requires 3 sin() and 3 cos() functions (or table lookups) |

May require occasional renormalization |
No normalization required |

Both quaternions and Euler angles have their place in computer animation, and so it helps to study and understand the properties of both schemes.

Translational joints are not as common in computer character animation as rotational joints, but they still are important to consider. Generally, real-life creatures don’t have translational joints but mechanical creatures such as robots or other animated mechanisms may contain them.

[Image: translational joint]

Like rotational joints, translational joints can be
specified to translate along any axis. Translational joints with a single
degree of freedom are called *prismatic *joints. A shock absorber for a
car’s suspension system is a good example of a prismatic joint. A general
definition of a prismatic joint would consist of a fixed offset vector **r** and a unit vector **a**
representing the axis of translation, and the joint local matrix for a
translation DOF value *t* would be constructed like this:

_{}

Translational joints require very little computation and
obviously, in cases where **a** is a principle axis this math reduces even
further.

It is also possible to make 2-DOF and 3-DOF translational
joints. For example, the joint local matrix for a 3-DOF translational joint
that takes a translation vector **t** and has a fixed offset **r** would
be:

_{}

Sometimes it may be desirable to create joints that combine
several different types of motion under the control of relatively few DOFs. We
will define these as *compound joints*, which can include any linear
transformations we may choose to use for joints. We will briefly look at three examples:
6-DOF joints, screw joints, and curve joints, but one could create their own
compound joints by creating a function that takes a set of DOFs and generates a
linear transformation using any rules desired.

A free rigid body has 6 DOFs and can be constructed from the rotational and translational joint types already discussed. However, because 6-DOF joints are common, both for rigid objects, and for the root node of articulated objects, it may be convenient to define a single joint type that incorporates all the necessary DOFs. To do this, one can use any of the 3-DOF rotational joint types defined (including the quaternion joint) and combine it with the 3-DOF translational joint type. Treating a 6-DOF joint as a single joint will reduce the matrix computations in the kinematics process. An example of a 6-DOF joint local matrix that uses the xyz Euler rotation order would be:

_{}

Another example of a compound joint is a screw joint, which
combines a rotation and a translation. These two operations are not independent
however, and are controlled by a single degree of freedom, in a way similar to
the motion of a screw. The translation along the x-axis is related to the
rotation angle [theta] by a simple scalar *rate*:

_{}

The joint local matrix for a screw joint rotating and translating about the positive x-axis would be:

_{}

It is left to the reader to construct other screw matrices.

[Image: screw joint]

Another example of compound joint type could be a translation along a curve. It combines translation in two or three dimensions, but they are grouped under a single degree of freedom.

[Image: curve constraint]

A formula for generating the joint local matrix for a curve constraint joint could work like this:

_{}

where *c*(*u*) is some function that returns the
3D position of the curve at parameter *u*.

All of these examples of compound joints ultimately generate linear transformations, and so they are compatible with our definition of a joint. Like the other joint types, they take a small number of input DOF values and use them to generate a local joint matrix.

A train car going along a winding train track can be thought of as another elaboration on the curve joint concept. Even though the train car may actually translate and rotate in all three dimensions as it moves along the track, it is still constrained to a single degree of freedom and can be represented as a 1-DOF compound joint.

Rotations and translations are examples of *orthonormal*
or *rigid* transformations. A rigid transformation can move an object but
it does not distort the shape in any way. Although less commonly used, it is
possible to create joints out of *non-rigid* linear transformations such
as scales and shears. Non-rigid transformations can come in handy when one is
trying to construct and animate cartoon characters that may deform in ways that
a real character would not.

Non-rigid matrices can be treated in the exact same way as rigid matrices in many situations, but there are a few cases where additional considerations must be made.

[more: clean up]

When geometry is transformed by a non-rigid matrix, the normals can no longer be transformed by the upper 3x3 portion of the matrix, as with a rigid transformation. An illustration of this problem is shown in [figure x].

Figure [x]: Object is subjected to a non-uniform scale showing that the transformed normals are no longer perpendicular to the surface

To properly transform a normal through with a non-rigid 3x3
matrix **W**, we must use the inverse transpose of **W**:

_{}

Explicitly computing **W**-1T per joint can be expensive
due to the full matrix inversion required.**W**-1T can be usually computed
much cheaper if it is computed as part of the forward kinematics process. If
one is willing to store a copy of **W**-1T per joint, then it can be
computed as

_{}

This involves construction of an inverse joint local matrix **L**-1
and a matrix multiplication. If these are only going to be used for
transforming normals, they only need to be 3x3 matrices.

In most cases the construction of **L**-1 is
straightforward. Rotational and translational joints simply negate the joint
angles or translations used in the construction of **L**, and scale matrices
can replace a scale value *s* with 1/*s*.

[more: details of L-1 construction]

[more: 3x3 vs. 4x4, fast inversion]

Adding these extra steps to the forward kinematics algorithm and storing an additional matrix per joint are two of the costs that must be paid when one wants to support non-rigid matrices properly. Supporting non-rigid joint transformations puts additional costs and complexities on the system that will also be further apparent when we examine skinning in [chapter 3] and inverse kinematics in [chapter 10].

There are a variety of ways to create scale matrices. Scales
may be along 1, 2, or 3 axes. The joint local matrix for a uniform scale that
affects all axes equally by a factor *s* is:

_{}

For scaling along only the x-axis:

_{}

And for scaling independently along all three axes:

_{}

It is sometimes desirable to have scales that preserve the
overall volume of an object. This can be a simple way to achieve a stretching
effect and can be a useful joint type to have on cartoon style characters. A
volume preserving joint that scales along the x-axis by a factor *sx* is:

_{}

Different variations of these scale matrices can be formulated for different axes.

[more: scale joints]

[Image: scale]

Shears are another type of non-rigid linear transformation that can be used for interesting cartoon-like character effects and simple shape distortions. A shear is a transformation with the following format:

_{}

[more: shear]

[Image: shear]

Typically in computer character animation, joints are limited only to doing linear transformations (such as rotations, translations, scales, and shears). This is usually to keep things simple and fast and to be able to take advantage of built in matrix support on modern CPUs. It is possible, however, to allow joints to do nonlinear transformations, such as bends, twists, or any other local or global deformations. In this book, we choose to treat these nonlinear functions as skinning operations that do not affect the underlying skeleton, and deal with them in [chapter 3].

There are two main computational parts to the skeletal forward kinematics system: local joint matrix construction, and world matrix concatenation. There are several subtle details that must be worked out in the implementation of a skeleton framework that will have impact on the system’s flexibility, performance, and memory usage. We will look at some of those details here.

A very simple humanoid skeleton model might contain around 20 joints. A more complex model with articulated fingers and other details might have up to 50, 100 or even more joints. Applications with a wide variety of different characters or a large number of similar characters will definitely have to consider memory and performance issues relating to the number of active joints in the world.

Many modern CPUs and graphics processors have considerable hardware support for floating point vector and matrix routines. Skeleton kinematics algorithms can typically be implemented very efficiently on modern systems in very few clock cycles, and so making the most of available vector processing should definitely pay off when performance is critical.

For software matrix math implementations, it may be perfectly acceptable to use 3x4 matrices instead of 4x4. We can just assume that the right hand column is always [0,0,0,1]T, and implement the matrix algebra routines accordingly. Generally, character animation systems can get away with using 3x4 matrices throughout for everything except for final view projection. Using 3x4 matrices can save a significant amount of computations in matrix operations. For example, multiplying two 4x4 matrices requires 64 multiplies and 48 adds, while multiplying two 3x4 matrices only requires 36 multiplies and 27 adds.

One issue to consider is how matrices are stored per joint. A simple implementation might just store one local matrix and one world matrix for every joint in a character. But is it really necessary to allocate permanent storage space for this data or can these be created only when needed? Often, the local matrix is only needed for a short time and can be very temporary. On modern vector CPUs, the local joint matrix might only need to exist in vector registers. Local matrix construction may involve different types of operations depending on the joint type (rotational, translational…), but for the more common rotational joints, the matrix construction involves a few sin() and cos() functions and possibly several multiplications and additions.

Unlike the temporary local matrices, world space matrices are usually needed for a bit longer. Usually, an application would at least need all of the world matrices for a single character to exist at one time, to be used for skinning and rendering, however, for very simple applications that don’t use skinning, the need to retain world matrices can be eliminated by the use of a matrix stack. More commonly, however, the application might require all world space matrices for all active characters to exist at the same time to be used for collision detection or other environment interactions. The software engineer will have to make the appropriate tradeoffs between memory usage, performance, flexibility, and code complexity.

It should be noted that for some applications, additional
performance may be gained by directly transforming the skeleton into *view
space*, the space defined relative to the camera viewing the world. This may
be effective for some situations, but not always in others which may require
objects to be placed in a consistent world space for collision detection, AI,
or other purposes. Also, in applications that involve multiple camera views of
the same character, it is better to transform everything to a common world
space before transforming to individual camera spaces.

The simplicity of the forward kinematics algorithm means
that it can be coded in very few cycles per joint on modern graphics hardware.
In this situation, the overhead for calling an actual recursive function per
joint can start to add up. This can be worse if a virtual function call is
issued per joint to support multiple joint types. If function call overhead
becomes a measurable bottleneck in the forward kinematics implementation, it
can be eliminated entirely in most cases. The forward kinematics algorithm exhibits
a property called *tail recursion*, which means that it does all of a
joint’s processing before moving onto its children and therefore doesn’t
actually require a local variable stack. The entire forward kinematics for a
skeleton can therefore be computed within a single small function. Support for
a wide variety of joints and other options can complicate this and in these
situations, one may have to exchange some performance for flexibility.

[more: array processing]

An important area where memory can be saved is in the
separation of constant and variable data. Constant data is data that does not
change, while variable data may actively change over time. In skeletal terms,
constant data might include data relating to joint offsets, joint types, joint
limits, while variable data would include the DOF values and global matrices.
While it is tempting to store all of this joint data in a single class, it may
be advisable to separate them to allow for character types to be *instanced*
or shared among many active characters. Again, the software engineer must be
aware of these issues in order to make informed decisions about the
implementation.

The skeleton itself is usually not drawn in an animation; it is an invisible structure that exists for the convenience of the animators. Still, no interactive character animation system would be complete without some method of visualizing the actual skeleton, for debugging purposes if nothing else. Supporting the ability to turn off the characters skin and display the underlying skeleton can be very helpful to people using the system. The bones of the skeleton can be drawn as simple lines, boxes, cylinders, or any other geometric representation desired. It is also useful to draw the three vectors forming the basis of each joint matrix as well. Additional useful features include drawing data specific to each different joint type, such as joint axes or joint limits.

[more: Skeleton files]

[more: single joint type vs. derived joitns]

A C++ pseudocode algorithm for computing the forward kinematics for a skeleton is presented below. It is a recursive function that first generates the local matrix for a joint, and then concatenates it with its parent’s matrix to compute the joint’s world matrix. It then proceeds to recursively call the same function on all of its children, thus transforming the entire skeleton. The ComputeLocalMatrix() function could use any of the techniques presented in [section 2.2] to generate a local matrix.

Joint::ComputeWorldMatrix(Matrix44 parentMtx) {

Matrix44 localMtx=ComputeLocalMatrix();

WorldMtx= localMtx * parentMtx;

for i = 1 to NumChildJoints {

ChildJoint[i].ComputeWorldMatrix(WorldMtx)

}

}

The process is started by calling ComputeWorldMatrix() on the root joint and passing in the identity matrix as the parent.

RootJoint.ComputeWorldMatrix(IdentityMtx)

[more: pseudocode]

In this chapter, we examined the mathematics of the underlying kinematic framework for the virtual character, the skeleton. Skeletons in character animation are typically built from a hierarchy of rigid bones connected by articulated joints. Each joint has one or more degrees of freedom (DOFs), which describe its articulation. These DOF values are set by higher-level systems that pose the skeleton, and animation is the process of changing the DOF values over time.

The skeleton system uses the process of forward kinematics to take these specified DOF values and compute the final world space matrices of the joints, which can then be used for skinning, collision detection, or other purposes.

The forward kinematics computational process involves a depth-first traversal through the skeleton hierarchy. For each bone traversed, the two main computations that need to take place are construction of the joint local matrix and then computation of the joint world matrix by concatenating the local matrix with the parent’s world matrix. Many options exist for generating local matrices for different joint types.

Some real time animation applications may do just fine limiting their characters to simple 1-DOF rotational joints and can implement the entire skeleton kinematics system in a few lines of code. Other systems may require more generality and may need to support a wider variety of joint types and other options. If the system needs to support non-rigid transformations such as scales and shears, additional complexities must be dealt with, both in the skeleton layer and in higher-level systems that use it such as inverse kinematics and skinning.

As the skeleton is an essential foundation for the animated character, the remaining chapters in this book will build upon the basic framework that the skeleton provides. In the next chapter, we will see how to attach a deformable skin to the skeleton.