The Character Animation FAQ
===========================
Version 1.6 6th August 1998
----------------------------
This FAQ is maintained by "hexapod@netcom.com". Any additional suggestions
or related questions are welcome. Just send E-mail to the above address.
The latest copy of this FAQ can be found at the following web page:
ftp://ftp.netcom.com/pub/he/hexapod/index.html
http://www.glue.umd.edu/~rsrodger
Feel free to distribute or copy this FAQ as you please.
Questions
---------
CHARACTER ANIMATION
===================
INTRODUCTION
------------
Q1. What is character animation?
Q2. What are skeletons?
Q3. What are chains and anchors?
JOINTS
------
Q4. What are joints?
Q5. What are revolute joints?
Q6. What are prismatic joints?
Q7. What are helical joints?
Q8. What are cylindrical joints?
Q9. What are spherical joints?
Q10. What are planar joints?
SKELETONS
---------
Q11. How do I define a skeleton?
Q12. How do I move a skeleton?
Q13. How do I constrain a skeleton?
Q14. How do I evaluate a skeleton?
KEYFRAMING
----------
Q15. What are keyframes?
Q16. What is keyframe animation?
Q17. What is keyframe Interpolation?
Q18. What is motion capture?
Q19. What are state machines?
DIGITAL SKIN
------------
Q20. What is digital skin?
Q21. How do I define digital skin?
Q22. How do I evaluate digital skin?
Q23. How do I render digital skin?
INVERSE KINEMATICS
------------------
Q24. What are expressions?
Q25. What are inverse kinematics?
Q26. How do I implement an IK system?
RENDERING
---------
Q27. How do I render a skeleton as a set of lines?
Q28. How do I render a skeleton as a set of tetrahedrons?
Q29. How do I render a skeleton as a texture-mapped model?
COLLISION DETECTION
-------------------
Q30. How do I perform collision detection?
Q31. How do I perform intersection tests between coordinates and a plane?
Q32. How do I perform intersection tests between a line and a sphere?
Q33. How do I perform intersection tests between two spheres?
PARTICLE SYSTEMS
----------------
Q34. What are Flocks and Swarms ?
Q35. What is Facial Animation?
Q36. What is a good 3D mathematics library to build?
BIBLIOGRAPHY
------------
B1. Bibliography
Answers
-------
CHARACTER ANIMATION
===================
Introduction
------------
Q1. What is Character Animation?
---------------------------------
Character animation can be defined as the expression of emotion or
behaviour of a live or inanimate object through the use of motion.
A good guide to the artistic side of this topic is the book titled
"Disney's - The Art of Animation".
There are ten main ways of giving a character expressive behaviour.
These can be summarised briefly as follows:
o Squash and Stretch
The change in shape of a character when a part of its body moves eg.
head stretching and squashing as a character eats some food.
Or a character's stomach enlarging and shrinking as he pants after
running.
o Anticipation
The positioning of a character before he performs an act eg. making
his hand reach the sky before digging into his pocket.
o Staging
Positioning of the camera, so that the viewer can see what the
character is doing. This may also include selecting the correct
background scenery in order to get the message across eg. Standing
in front of a hot-dog stand while eating a hot-dog which flies across
the screen when bitten.
o Straight Ahead Action and Pose to Pose
Straight Ahead Action simply involves running one animation sequence
after another without any pre-planning of animation sequences.
Pose to Pose is exactly the opposite. All the animation sequences are
planned ahead of time. This allows the camera positions to be planned
so that everything is in proportion.
o Follow Through and Overlapping Action
This involves parts of a character to continue moving from a previous
animation sequence while the character starts a new sequence.
eg. A character comes to a sudden stop, while his coat-tails continue
moving forward.
o Slow In and Slow Out
Accelarating and deaccelarating the motion of a character between
animation sequences.
o Arcs
Modelling the motion of every part of a character's body as he moves.
eg. Making the head bob up and down as the character walks along
o Secondary Action
Adding other smaller movements to emphasise any animation sequence eg.
A character shaking his head after being hit by a falling object.
o Timing
The number of frames required to complete a single animation sequence.
o Exaggeration
Making the motion of a character more dramatic
o Solid Drawing
Making a character appear solid and 3-dimensional. Avoiding "twinning"
where two limbs of a character will have mirror symmetry.
o Appeal
Making a character attract the viewers attention. This includes getting
the colors right, avoiding clumsy shapes, awkward motion, and distorting
the shape of the character.
Other attributes can include the behaviour of the character and the
manner in which he/she speaks.
Q2. What are Skeletons?
------------------------
To represent the motion of a living creature such as a human, animal or
arthropod (insect), it is convenient to store the relationships between
each movable part of the creature eg. Head is attached to the neck,
left foot is attached to the lower left leg and so on.
Taking a cue from biology, each movable part is referred to as a bone,
the attachments between each bone are called joints and the entire
collection of bones is referred to as a skeleton.
The connections between individual bones are referred to as "joints".
For example, a basic mammal (without fingers or toes) would take around
20 bones:
+-----------------------------------------------------------+
| |
| o |
| | Head |
| Right.shoulder | Left.shoulder |
| o-------o-------o |
| Right.upperarm | |Upper- | Left.upperarm |
| | |back | |
| o | o |
| Right.lowerarm | | | Left.lowerarm |
| | oLower- | |
| o |back o |
| Right.hand | | | Left.hand |
| | |
| Right.butt | Left.butt |
| o--o--o |
| | | |
| | | |
| Right.upperleg | | Left.upperleg |
| | | |
| o o |
| | | |
| | | |
| Right.lowerleg | | Left.lowerleg |
| o o |
| Right.foot / / Left.foot |
| |
| |
+-----------------------------------------------------------+
A hand might be represented with 16 bones as follows:
+----------------------------------------------------------------+
| thumbend |
| o---- |
| / |
| thumbbase / o---o---o---- ringbase ringmid ringend |
| / | |
| / o----o----o---- indexbase indexmid indexend |
| o-------o-------o |
| lowerarm palm o---o---o--- midbase midmid midend |
| | |
| o--o--o--- littlebase littlemid littleend |
| |
| |
+----------------------------------------------------------------+
For an anatomically correct skeleton of a human, over 300 bones would
be required.
Q3. What are Chains and Anchors?
---------------------------------
"Chains" are a more generic name for skeletons. The latter term really
only makes sense when applied to living creatures. Other applications
for inverse kinematics include simulating flexible objects such as
ropes, string and ship anchor chains.
Each of these objects can be modelled using a set of single "bones" or
links.
Taking a cue from nautical terms, the "anchor" or "anchor point" is one
end of the chain which always has a fixed or known position - much like
a ships anchor limits the positions that a ship can be in.
+-------------------------+
| |
| +----+ |
| | | |
| o---+----+----o |
| \ O/ |
| +| | |
| o---------o| link1 |
| o |
| | |
| | link2 |
| o |
| | |
| | link3 |
| @ |
| Anchor |
| |
+-------------------------+
For animation purposes, each part of the chain has a single object
attached to it ie. a chain link.
JOINTS
------
Q4. What are joints?
---------------------
In the field of robotics (or cybernetics), six basic types of joint
have been defined. These can be summarised as follows:
+--------------------+--------+-----+
| Name | Symbol | DOF |
+--------------------+--------+-----+
| | | |
| Revolute joints | R | 1 |
+--------------------+--------+-----+
| | | |
| Prismatic joints | P | 1 |
+--------------------+--------+-----+
| | | |
| Helical joints | - | 1 |
+--------------------+--------+-----+
| | ~~ | |
| Cylindrical joints | RP RP | 2 |
+--------------------+--------+-----+
| | | |
| Spherical joints | 3R RRR | 3 |
+--------------------+--------+-----+
| | | |
| Planar joints | RRP | 3 |
+--------------------+--------+-----+
In the field of character animation, only three types of joint need
to be considered. These are the "revolute" and "prismatic" joints.
All other types can be based on these two.
The symbols "R" annd P" are used when describing combined rotation
and prismatic joints. The number of symbols liked together indicates
the number of degrees of freedom.
Q5. What are revolute joints?
------------------------------
Revolute joints are the most commonly used joint. The term "revolute"
comes from the fact that the endpoint of one bone rotates around the
endpoint of another.
Revolute joints are represented by the symbol R.
Because revolute joints only rotate in a single axis, they only have
one degree of freedom.
Three types of "revolute" joint exist:
+----------+ +----------+ +--------------+
|R1 | |R2 a | |R3 a |
| | | . | | . |
| | | . | | . |
| @ | | @ | | . |
| |B | | |B | | . |
| | | | | | | . |
| | | | | | | . B |
| ...o...a | | o | | o----@ |
| | | | | | | | |
| | | | | | | | |
| |A | | |A | | |A |
| | | | | | | | |
| ---O--- | | ---O--- | | ---O--- |
| | | | | |
+----------+ +----------+ +--------------+
R1 is the simplest of the three types - it is most comonly known as
the "simple hinge". Bone B rotates in an axis perpendicular to both
bone A. The far endpoint of bone B rotates in a circle centred on the
endpoint of bone B.
Examples in nature include the human knee and elbow joints.
R2 differs from R1 in that the rotation axis is parallel to both
bones B and A. The far endpoint of bone B cannot change location but
can rotate in place.
Examples in nature include the human wrist.
R3 is a variation on R2. While the rotation axis remains the same, bone
B has been repositioned so that it is perpendicular to bone A. This
allows for the far endpoint of bone B to rotate in a circle around the
endpoint of bone A.
Q6. What are prismatic joints?
-------------------------------
Prismatic joints are joint in which the motion of the bone is purely
translational. The name "prismatic" is derived from the implementation
of such joints in industry by using triangular bars (prisms) sliding
into a matching holder.
Prismatic joints are represented by the symbol P.
Because prismatic joints are constrained to move in a single axis,
only one degree of freedom exists.
+-----------+
|P . |
| . |
| . |
| @ |
| | |
| |B |
| | |
| +|+ |
| ||| |
| |o| |
| |.| |
| |.| |
| |.|A |
| o-o |
| |
+-----------+
Q7. What are helical joints?
-----------------------------
Helical joints combine a rotation motion with a matching translation.
The main industrial application is in the drive systems for lathes and
clamps.
As bone A rotates, bone B experiences a translational movement parallel
to axis of bone A.
Because the amount of translation is directly related to the amount of
rotation, only one degree of freedom exists.
As a consequence, helical joints are rarely used in the field of
robotics.
+-----------+
|H1 |
| |
| |
| @ |
| /A |
| \ |
| / |
| \ B |
| /o----@ |
| \ |
| / |
| \ |
| / |
| \ |
| o |
| |
+-----------+
Q8. What are cylindrical joints?
---------------------------------
Cylindrical joints combine an coaxial rotation (R3) along with a
translational movement. Since both movements are independent
of each other, two degrees of freedom exist.
Because cylindrical joints are a combination of rotation (R) and
translation (P), they are represented by the symbol RP.
~~
If both movements share the same axis, then the symbol RP is used.
The two types of cylindrical joint are as follows:
+-----------+ +-----------+
| | |~~ |
|RP . | |RP |
| . | | @.@ |
| . | | |.| |
| o | | |o| |
| | | | |||B |
| | | | ||| |
| ||| B | | ||| |
| ||o----@ | | ||| |
| ||| | | ||| |
| | | | o|o |
| A| | | | |
| | | | A| |
| o | | o |
| . | | . |
| . | | . |
| . | | . |
| | | |
+-----------+ +-----------+
Q9. What are spherical joints?
-------------------------------
Spherical joints implement the "ball-and-socket" concept of a joint,
where a ball is free to rotate in any direction while being held by
a socket.
Since the only way to prevent the ball from popping out of
the socket is to use a volume slightly larger than a hemisphere, this
restricts motion in two axii to less than 180 degrees.
However, the remaining third axis which is parallel to bone B is free
to move about unrestricted.
Because it is practically impossible to drive "ball-and-socket"
mechanisms in the real world, spherical motion is usually implemented
through the use of three revolute joints.
~~~
Thus, a spherical joint is represented by the symbol 3R or RRR
+------------+
|RRR |
| |
| ... |
| . . |
| o . |
| . \B . |
| . \ . |
| . @ . |
| . | . |
| . | . |
| .|. |
| | |
| A| |
| | |
| o |
| |
+------------+
Q10. What are planar joints?
----------------------------
Planar joints combine prismatic motion in two axii, along with rotation
in the axis perpendicular to the other two planes. This can be
visualised as the motion of a book held flat against a desk.
Thus, planar joints can be represented by the symbols RRP, RPR or PRR.
+------------+
|PRR |
| . |
| . |
| . |
| . |
| +---+ |
| | | |
| ..| |.. |
| | | |
| +---+ |
| . |
| . |
| . |
| |
+------------+
SKELETONS
=========
Q11. How do I define a skeleton?
--------------------------------
A skeleton can be defined as an array of bones. Each bone is defined
in terms of a length, a default direction vector, a name and the name
of the parent.
The parent of a bone is the bone which is attached to that bone and will
cause that bone to move if it moves. eg. If you turn your neck, your
head will also turn. If you bend your back, your neck and head will also
both move forwards.
The only bone which does not have a parent is the root node. It is not
really a bone in a physical sense but rather it is used as a convenient
way of moving the entire skeleton with a single translation or rotation.
So, for the example above, the list would be as follows:
Bone Parent Length Direction
---------------------------------------------------------
Root --- - - - -
Head Upperback 3 0 1 0
Upperback Lowerback 5 0 1 0
Lowerback Root 5 0 1 0
Left.shoulder Upperback 8 1 0 0
Left.upperarm Right.shoulder 3 0 -1 0
Left.lowerarm Right.upperarm 3 0 -1 0
Left.hand Right.lowerarm 2 0 -1 0
Right.shoulder Upperback 8 -1 0 0
Right.upperarm Right.shoulder 3 0 -1 0
Right.lowerarm Right.upperarm 3 0 -1 0
Right.hand Right.lowerarm 2 0 -1 0
Left.butt Root 3 1 0 0
Left.upperleg Left.butt 5 1 0 0
Left.lowerleg Left.upperleg 4 1 0 0
Left.foot Left.lowerleg 2 0 0 1
Right.butt Root 3 -1 0 0
Right.upperleg Right.butt 5 1 0 0
Right.lowerleg Right.upperleg 4 1 0 0
Right.foot Right.lowerleg 2 0 0 1
-------------------------------------------------------
Q12. How do I move a skeleton?
------------------------------
Since each bone has a direction vector and a length, it is possible
to use rotation matrices to transform each bone to a new position.
Generation of the rotation matrix can be performed by the mathematical
concatenation the XYZ rotation matrices or by using quaternions.
For most applications, translating the position of each bone will not be
needed. However, for special effects such as a body being dismembered,
translation operations can be used.
Other uses may be for the barrel of a gun which can recoil after
launching a round of ammunition.
For other special effects such as pair of extra arms sprouting out of
nowhere, it can be convenient to set the bone lengths to zero.
The lengths can then be gradually incremented until they are at
full length. This is one way of modelling the growth of a tree.
Q13. How do I constrain a skeleton?
-----------------------------------
With the skeleton defined above, there is no way of determining
whether a particular configuration of joints rotations is valid or
not. For example, the rotation data may have come from external input
such as a trackball or motion capture sensors.
In order to ensure that the skeleton is always in a valid position,
constraints are placed onto the position of each joint.
The simplest way to implement a constraint based system is to place
maximum and minimum limits on each rotation and translation axis.
For example you can twist your thigh sideways around +/- 45 degrees.
For the model this would correspond to minimum/maximum rotations in
the Y-axis. Since you cannot detach your leg without some difficulty,
the constraints for translation are all zero.
In this case, these would be defined as follows:
#name rotation min max translation min max
------------------------------------------------------------------
Left.upperleg 0 -45 0 0 45 0 0 0 0 0 0 0
However, this method requires that the user has to consider and
visualise the limits of rotation for each joint in the skeleton.
A more sophisticated method is to classify each type of joint according
to the type of motion expected. A considerable amount of research in
this area has been performed in the field of robotics.
Q14. How do I evaluate a skeleton?
----------------------------------
This is fairly easy to perform. Every bone has the following set of
local information:
Start-point - The end attached to the parent
End-point - The end where children are attached
Relative matrix - Matrix generated from local rotation/translation values
Absolute matrix - Matrix generated from local matrix and parent matrix
The first stage performed is to evaluate the root node. This will
involve setting the start-point, end-point and the "relative" (R)
matrix. Since this is the root node, the "absolute" (A) matrix is
identical to this.
The second stage involves the generation of the A-matrix for each
bone in the model. For each bone in the model, the following steps
are performed:
[1] The parent bone is determined. Only if this bone has already
been evaluated, can the following steps can be performed. The
ID of the parent bone can be represented either by a name-tag
or by an index value.
[2] The end-point of the parent bone is used as the start-point of
the current bone.
[3] The R-matrix is calculated (if this has not already been done).
[4] The R-matrix is combined with the parent's A-matrix to
generate a new A-matrix.
[5] The direction vector is combined with the A-matrix to determine
the current orientation of the bone.
[6] The current orientation of the bone is added to the start-point
in order to generate the end-point.
This process is repeated until all bones have been evaluated.
Once every bone in the skeleton has been evaluated, the next stage is to
transform all geometry (polygons, lines, particle systems etc...)
associated with each bone.
For each piece of geometry, the associated bone is identified, and the
following steps are performed:
For each piece of geometry, the A-matrix is used to rotate the
coordinates then they are translated by the start-point of the bone.
KEYFRAMING
==========
Q15. What are keyframes?
------------------------
As mentioned above, each bone in a skeleton can be assigned a particular
orientation. In order to represent a particular pose (eg. a single frame
in a walk cycle), it is necessary to store the rotation/translation values
for every bone. There are several ways of specifying the keyframe data.
One way is to store the rotations and translations as vectors eg.
#rotate Left.upperleg 0 10 0
#translate Left.upperleg 0 0.3 0
#length Left.upperleg 3
This method saves space, however it requires the rotation matrix to be
calculated every time, plus a translation operation.
Another way is to evaluate and combine the rotation and translation
operations into a single 4x4 matrix.
#matrix Left.upperleg
1 0 0 0
0 1 0 0.3
0 0 0 0
0 0 0 1
This method avoids having to calculate the rotation matrix every time,
but it does require the storage of sixteen data values instead of six.
Q16. What is keyframe animation?
--------------------------------
In a method similar to pencil drawn flip-books, keyframe animation
gives the appearance of motion through the continuous presentation
of different positions of a character.
For example, a simple walk cycle may require 8 keyframes. The first
four frames will have the left leg and right arm swinging forward
and backwards to rest, then the last four frames will be when the
right leg and left arm swing forward, and the cycle will continue
from the beginning again.
Q17. What is keyframe interpolation?
------------------------------------
Unless there are a large number of keyframes, any motion using
keyframe animation will appear jerky. For example, assuming a
screen is being updated at 60 frames/second and a character takes
1 second to complete one walk cycle, then this animation will
require 60 frames of animation.
However, there may not be memory space for 60 frames of animation
(especially for game console systems), so that only 30 or even 15
frames can be stored.
The solution to this problem is to perform keyframe interpolation.
As the name suggests, keyframe interpolation attempts to generate new
frames by interpolating values between two existing frames.
To implement this, each keyframe must store the XYZ rotations and
translations of every bone, regardless of whether it has moved or not.
The simplest method of interpolation is "linear interpolation". Here,
the individual values of two frames are combined using a weighting
function ie.
Pnew = Pold[frame] * (1.0-frac) + Pold[frame+1] * frac;
where Pnew is the new value,
Pold[frame] is the position for the current frame,
Pold[frame+1] is the position for the next frame,
and frac is the fraction of time between the two frames
This calculation would be performed for each field in the XYZ rotation,
translation and scaling data.
More complex motion paths can also be specified - for example, three
or more frames can be used to implement B-spline interpolation.
If the frames are not at consecutive intervals of time, Non-Uniform
Rational B-splines can be used.
Even more complex methods can use quaternions to interpolate between
the actual R-matrices.
Q18. What is motion capture?
----------------------------
There are two ways of generating keyframe data. One way is to get an
animator, a suitable animation package, and get the animator to add
the keyframe data to the model.
For simple actions or for conveying action with exaggerated emotion,
this is the most efficient way to go.
However, for animation which requires a large amount of movement (say
dancers on a stage), then motion capture can be used. There are two
main methods of motion capture, magnetic and optical.
In magnetic motion capture systems, a large coil magnet is placed at the
centre of the stage, magnetic sensors are attached to the actor's body
and readings are collected by the motion capture software to be
converted into keyframe data.
This method has the advantage of generating accurate data, however
the disadvantages are that the actors are tethered by cables, are
limited by the operating range of the magnetic coil. There is also the
problem of callibrating and finding a non-metallic environment. Also,
the data may require a large amount of signal processing in order to
smooth out any any background noise that may appear (eg. A/C power
transformers).
In order for this type of motion capture to operate successfully, there
must not be any metallic objects (eg. iron girders, power-cables, tables)
within the operating range of the system. The most suitable environments
are either aircraft hangers large warehouses or a farm field.
In optical motion capture systems, a large number of reflective light
markers are placed on the actor's body. Using the reflection of studio
lights, a video camera will capture these reflections, pass the video
data to a software package capable of converting the screen coordinates
into three dimensional keyframe data.
The advantage of this system is that actors are not tethered to any
location, so long as they remain within visual range of the camera. The
only disadvantage are that a user may have to callibrate the software
in order to determine what exactly each point of light represents.
Q19. What are state machines?
-----------------------------
When used with character animation, state machines are a way of managing
sequences of keyframe animation such that all animation remains smooth
and continuous ie. there are no occasions where the character "jumps"
from pose to pose.
For example, a character in an adventure game may have the following
actions modelled by keyframe animation:
o Stationary (STAT)
o Start to walk (STWK)
o Come to stop (CSTP)
o Walk (WALK)
o Turn left (TLFT)
o Turn right (TRGT)
o Jump (JUMP)
o Fly (FLY)
o Land (LAND)
o Crouch (CRCH)
o Stand up (STUP)
In this game, the character can only jump, turn left or right when
walking. Also, the character can only fly after jumping and may only
stand up after crouching. Landing is only possible after flying.
During game development, without the use of state machines will lead to
more and more code hacking in order to add new states (eg. run, fire,
pick-up etc...)
The solution is to use a state machine. First of all, all the possible
states are drawn as boxes. Then these boxes are joined together by
arrows which indicate the moves that are possibl.
Each arrow defines a particular input event that occurs eg. control
pad buttons pressed, monster-player collision etc...
+----+
+------------<---------|CSTP|<--------------------+
| +----+ |
| ^ |
| | |
| +----+ +----+ +----+ |
+->|STAT|---->-----+-->|STWK|-----+----->|WALK|->-+
| +----+ | +----+ ^ +----+ |
| | | |
^ +----+ | | +----+ |
+<-|TLFT|----<-----+ |--<---|TLFT|<--+
| +----+ | | +----+ |
| v | |
| +----+ | | +----+ |
|<-|TRGT|----<-----+ +--<---|TRGT|<--+
| +----+ | +----+ |
| | |
| +----+ +----+ | +----+ +----+ +----+ |
+--|STUP|<--|CRCH|<+-|LAND|<--|FLY |<----|JUMP|<--+
+----+ +----+ +----+ +----+ +----+
This information can then be converted into a state table. This defines
the current states as a column and the events as a row. Each entry
defines the new state given the current state and incoming event. ie.
+-------+-------------------------------+----------------+
| | Input event | |
|Current+---------+------+-------+------+ |
|state | FORWARD | LEFT | RIGHT | STOP | |
+-------+---------+------+-------+------+----------------+
| | | |
| STAT | STWK TLFG TRGT STAT | |
| STWK | WALK WALK WALK CSTP | |
| WALK | WALK TLFG TRGT CSTP | |
| CSTP | STAT STAT STAT STAT | |
| TLFT | TLFT TLFT TLFT CSTP | New states |
| TRGT | TRGT TLFT TRGY CSTP | |
| JUMP | FLY FLY FLY FLY | |
| FLY | LAND LAND LAND LAND | |
| LAND | CRCH CRCH CRCH CRCH | |
| CRCH | STUP STUP STUP STUP | |
| STUP | STAT STAT STAT STAT | |
+-------+-------------------------------+----------------+
An optional feature is to have an output action associated with each
state change eg. scheduling an audio scream if a player is killed, a
coin being collected if a player-object collision is detected.
DIGITAL SKIN
============
Q20. What is digital skin?
--------------------------
Until recently, most character animation has been performed using
simple geometry primitives eg. boxes, cylinders, spheres or NURBS
patches, each of which would contain their own unique list of
polygons and vertices.
In this simple polgon model of a head, neck and torso, it can be seen
that the character's neck extends into both the head and torso.
Using Gouraud or flat-polygon shading with Z-buffering or polygon
sorting, this is acceptable, since whenever the head is moved, the
head will always appear attached to both the head and torso.
Using individual polygon parts
+----------------------------------------------------+
| |
| +-----+ |
| | | Head |
| | +-+ | /- Seams -\ |
| +-|-|-+ | | |
| | | Neck v v |
| +-----|-|-----+ UpperArm Hand |
| | | | |/---------\/--------\/----\ |
| | +-+ /| /\ /\ \ |
| | \| \/ \/ / |
| | Torso |\---------/\--------/\----/ |
| LowerArm |
| |
+----------------------------------------------------+
However, when texture-mapping is used, the textures on the neck will
appear to sink into both the head and torso. Also, there is the problem
of seams appearing between the different body parts whenever the
character moves around.
The solution is to use a technique known as digital skin. In the model
above, each body part would be defined as a list of vertices and polygons.
With digital skin, each body part still retains its own list of vertices.
However, there is now a single global list of polygons. Polygons can now
be defined which share vertices between different body parts (These are
referred to as "glue" polygons. The following figure demonstrates this:
+----------------------------------------------------+
| |
| +-----+ Glue |
| | | Head Polygons |
| | | /- -\ |
| +-+-+-+ | | |
| | | Neck v v |
| +-----+-+-----+ UpperArm Hand |
| | +-+-------+--+------+--+----\ |
| | | | | | | | \ |
| | | | | | | | / |
| | Torso +-+-------+--+------+--+----/ |
| | |^ ^ ^ |
| | | | |
| Glue polygons |
| |
+----------------------------------------------------+
As the character moves a body part (say, twists an arm), then the "glue"
polygons will stretch and contract between the two parts and give the
appearance of skin.
A more sophisticated use of digital skin is to make muscles appear to
bulge whenever a joint is bent.
Q21. How do I define Digital Skin?
----------------------------------
Models which use digital skin are still defined in terms of polygons
and vertices. However, as mentioned before, there is only a single
polygon list, rather than individual lists for each bone in the skeleton.
Vertices are defined in terms of XYZ coordinates.
Polygons are defined in terms of their vertices (typically vertex ID's)
and any other data eg. texture vertex ID's, outward normals
Q22. How do I evaluate Digital Skin?
------------------------------------
For most purposes, the only calculations required will be to calculate
the new locations of each vertex based on the rotation matrix of the
current bone.
However, in order to implement more realistic effects such as bulging
muscles, then it quite possible to use Expressions to determine the
new position of a vertex.
The method works as follows:
[1] The rotation angle of the selected joint is read.
[2] This value is translated using a cubic equation to determine
the scale factor for the vertex.
[3] This scale vactor is then used to adjust the position of the
selected vertices.
Q23. How do I render digital skin?
----------------------------------
The digital skin can be rendered as any other type of polygon surface,
mesh or NURBS Patch, and so no special calculations are required.
INVERSE KINEMATICS
==================
Q24. What are Expressions?
--------------------------
In many animation scenes, it is often required that one or more 3D
models are synchronised in the way they move. For example, consider
the animation of a car gearbox with 15 or more gears. Using keyframes,
this would require the animator to calculate and specify the position
of all 15 gears per frame.
Apart from running the risk of getting some of the calculations wrong,
this also wastes time and memory space.
An alternative method is to use arithmetic expressions (or "expressions"
for short) to evaluate the movement of each gear. This method requires
that arithmetic relationships between two moving objects are defined.
Arithmetic expressions can include variables, constant values (eg. PI),
trigonometric functions (eg. sin cos tan sqrt log exp ...)
In the following model, A and B are two gears, each with radius
Ra and Rb. C is a rack which moves up and down according to B
(similar to car steering).
+------------------------------+
| |
| A | | Y |
| --- B | | | |
| / \/-\|C| | |
| | o ||o|| | | |
| \ /\-/| | /---- X |
| --- | | / |
| / Z |
| | Ra||Rb| |
| |
+------------------------------+
Gear A is rotating at 10 degrees/frame. Gear B intersects Gear A.
So the expressions for this system would be:
-----------------------------------------------------------
radius_a = 10 # Define constants
radius_b = 8
pi = 3.14159265
gear_a.rotate_z = frameid # Get frame ID
# Calculate position of gear B
gear_b.rotate_z = -(radius_a / radius_b) * gear_a.rotate_z
rack_c.trans_y = -gear_b.rotate_z * 2 * pi
-----------------------------------------------------------
Q25. What are Inverse Kinematics?
---------------------------------
In the examples given above, it has always been assumed that the
rotation angles and translation vectors for each bone are already
known and only the end-points and rotation matrices for each bone
have to be calculated.
With inverse kinematics (or IK for short), only a limited set of
endpoints and translation values are known, along with the set of
constraints defining the freedom of movement of the skeleton. Other
constraints that are known include the motion paths for each joint.
For example, with motion capture, sensors will provide continuous
data which will be interpolated into NURBS curves. For any instant
of time, these will be translated into the endpoints of each bone
in the skeleton. From these values, direction vectors can be
generated for each bone.
Once the direction vectors are known, rotation matrices for vertex
data can be determined. These can then be used to transform the
geometry of the model.
Q26. How do I implement an IK system?
-------------------------------------
With IK systems, the goal is to determine the values of all unknown
variables in the skeleton. As mentioned before, each bone data
structure contains several pieces of data:
+-----------------------+----------+---------------+
| Name | Acronym | C flag |
+-----------------------+----------+---------------+
| Euler rotation angles | RA | IK_ANGLES |
| Rotation matrix | RM | IK_MATRIX |
| Start Point | SP | IK_START |
| End Points | EP | IK_END |
| Translation | TR | |
| Direction vector | DIR | |
| Length | LEN | |
| ID of parent bone | | |
| Flag list | | |
+-----------------------+----------+---------------+
The flag list contains a set of bit-values associated with each of the
first four parameters (RA), (RM), (SP) and (EP). For each value which
is known the appropriate flag bit is set.
Since each of these values are related mathematically, data can be
propagated both forwards and backwards.
If the end-point of a parent bone is known, then the start-point of any
child-bone is also known. This is forward propagation.
Similarly, if the start-point of a child bone is known, then the
end-point of the parent is also known. This is backward propagation.
If the start-point of the parent bone is known, and the end-point of
the child bone is known, the location of the intermediate joint
(end-point of the parent or start-point of the child) can also be
determined.
Altogether, there are around 12+ rules which can be used to propagate
data both backwards and forwards. These are as follows:
+------+---------+-----------------+-----------------------------+--------+
|Rule | Unknown | Parent bone | Current bone | Path |
| # | var. | PSP | PRM | PEP | TR | SP | RA | RM | EP | Vec PV |
+------+---------+-----+-----+-----+-----+-----+-----+-----+-----+--------+
| 1 * | SP | /// | ... | ### | ### | ??? | ... | ... | ... | ... |
| 2 | TR | /// | ... | ### | ??? | ### | ... | ... | ... | ... |
| 3 % | EP | ... | ... | ??? | ### | ### | ... | ... | ... | ... |
| 4 * | RM | ... | ### | ... | ... | ... | ### | ??? | ... | ... |
| 5 | RA | ... | ### | ... | ... | ... | ??? | ### | ... | ... |
| 6 | PRM | ... | ??? | ... | ... | ... | ### | ### | ... | ... |
| 7 * | EP | ... | ... | ... | ... | ### | ... | ### | ??? | ... |
| 8 % | RM | ... | ### | ... | ... | ### | ... | ??? | ### | ... |
| 9 | SP | ... | ... | ... | ... | ??? | ... | ### | ### | ... |
| 10 | EP | ... | ... | ... | ... | ### | ... | ... | ??? | ### |
| 11 | PEP | ### | ... | ??? | ... | ... | ... | ... | ... | ### |
| 12 % | PEP | ### | ... | ??? | ... | ... | ... | ... | ### | ... |
+------+---------+-----+-----+-----+-----+-----+-----+-----+-----+--------+
... - Not needed
/// - Need not be known in certain cases
### - Known variable
??? - Unknown variable
* - Standard character animation
% - Can be used to implement motion capture
It should be noted that Expressions can also be used by IK systems. In
this case, the left hand side of the equation would be regarded as the
unknown variable and any variables on the right hand side as known
variables.
The operation of the IK system is fairly straightforward, and can be
defined by the following sequence of actions:
--------------------------------------------------------------
For each animation_frame do
Mark all variables as unknown
Set known variables and bit-flags
Set progress_made flag
While unknown_variables_exist and progress_made do
Clear progress_made flag
For each bone do
For each rule do
If LHS variable is unknown and
all RHS variables are known then
Evaluate_rule( rule, bone )
Mark variable as known
set progress_made flag
Endif
Endfor
Endfor
Endwhile /* unknown_variables_exist */
Endfor /* animation_frame */
--------------------------------------------------------------
In certain situations, it may be impossible to find the values of some
unknown variables. To detect this situation, it is necessary to maintain
a progress made flag, which is set whenever the value of an unknown
variable is determined. If no unknown variables can be determined then
execution of the main loop is terminated, and the IK system returns the
values of those variables which could be determined.
Each of the above rules can be implemented using simple vector and matrix
mathematics. A list of rules using the 3D API is as follows:
-------------------------------------
Rule #
1. v3_sub( SP, PEP, TR )
2. v3_sub( TR, SP, PEP )
3. v3_sub( PEP, SP, TR )
4. m3_rotatexyz( m1, RA )
m3_mult( RM, PRM, m1 )
5. m3_transpose( m1, PRM )
m3_mult ( m2, m1, RM )
m3_toeuler( m2, RA )
6. m3_rotatexyz( m1, RA )
m3_transpose( m2, m1 )
m3_mult( PRM, RM, m1 )
7. m3_multvector( RM, v1, DIR, 1 )
v3_scalef( v1, v1, LEN )
v3_add( EP, v1, SP )
8. findmatrix( RM, SP, EP )
m3_toeuler( RM, RA )
9. m3_multvector( MR, v1, DIR, 1 )
v3_scalef( v1, v1, LEN )
v3_sub( SP, EP, v1 )
10. v3_sub( v1, PATHMAX, PATHMIN )
v3_normalise( v1, v1 )
v3_scale( v1, v1, LEN )
v3_add( EP, SP, v1 )
11. intersect sphere with line
12. intersect sphere with sphere
-------------------------------------
findmatrix - Function to determine the rotation matrix between the
direction vector and the new position of a bone
m3_multvector( PRM, v1, DIR )
v3_sub( v2, PEP, SP )
v3_normalise( v2, v2 )
v3_cross( v3, v1, v2 )
v3_norm( v3, v3 )
lrot = v3_dot( v1, v2 )
lrot = acos( lrot ) * RADIANS
m3_fromquat( RM, v3, lrot );
m3_transpose( m1, RM )
m3_mult( m1, RM, PRM )
m3_copy( RM, m2 )
RENDERING
=========
Q27. How do I render a skeleton as a set of lines?
--------------------------------------------------
This is simplest and quickest way of rendering a skeleton.
It is achieved simply by drawing a line from the start point to the
end point of each bone.
Joints can be highlighted by drawing circles at each joint.
Q28. How do I render a skeleton as a set of tetrahedrons?
---------------------------------------------------------
While drawing a skeleton as a series of lines is fast, it does not
provide a clear view of the way in which each limb is moving.
An alternative way is to represent each bone as an elongated
tetrahedron. The base of the tetrahedron is placed at the start of
the bone. The elongated end of the tetrahedron is positioned at the
end of the bone.
The coordinates of the tetrahedron can be stored as a single 4x4 matrix
and scaled according to the dimensions of the bone.
A unit tetrahedron has the following coordinates:
| 0.000 0.353553 -0.176776 -0.176776 |
| 0.000 0.000000 0.306186 -3.306186 |
| 1.000 0.000000 -0.000000 0.000000 |
with one end-point stored at (0,0,1). This coordinate will be scaled
according to the length of the bone.
To ensure that the tetrahedron rotates along with the model, each bone
has an initial direction vector.
Since the tetrahedron has a direction vector of ( 0,0,1 ), the base
rotation matrix is derived from the matrix which rotates the direction
vector of the tetrahedron to the direction vector of the bone.
As the bone is rotated through keyframe animation or inverse kinematics
the current rotation matrix of the bone is multiplied with the base
rotation matrix. Applying this matrix to the vertices of the tetrahedron.
The resulting set of vertices are used to render the tetrahedron.
The tetrahedron can be rendered in wireframe, shaded or even texture
mapped modes.
Q29. How do I render a skeleton as a texture mapped model?
----------------------------------------------------------
See Q23. Rendering digital skin
COLLISION DETECTION
===================
Q30. How do I perform Collision Detection?
------------------------------------------
This really depends on what kind of objects are colliding. For example,
you may be attempting to determine whether a missile has collided with a
character or whether the player has attempted to walk through a wall
or has set off a trip-wire.
The most commonly used collision detection methods are as follows:
o Coordinate/Plane intersection test
used for: trip-wire tests, character/wall collision, door activation
o Sphere/Sphere intersection test
used for: object pickup, character/character collision
o Parametric line/Sphere intersection test
used for: missile trajectory hits
Q31. How do I perform intersection tests between coordinates and a plane?
-------------------------------------------------------------------------
For flat objects such as trip-fires or doors, plane-collision tests
can be performed.
A plane is defined by the equation:
P = A.x + B.y + C.z + D
where the constants A,B,C and D define the equation of the plane and
(x,y,z) is a coordinate in Euclidean space.
This calculation can also be considered to be a dot product between
two homogenous coordinates.
All points in front of the plane will generate positive value.
All points behind the plane will generate negative values.
All points which lie exactly on the plane will generate a value of zero.
As a player or object moves around in world space, the current position
is saved and the new position is calculated.
For each new position, the new value of the plane equation is calculated.
If the result changes sign, then a collision has occured.
The point of intersection can be determined by the algorithm:
ro = P . oldpos
rn = P . newpos
Then the point of intersection is given by:
ro rn
Pi = --------- Po + ---------- Pn
(rn - ro) (rn - ro )
This can be rearranged to give:
ro.Po + rn.Pn
Pi = -------------
(rn - ro)
where Po is the first point,
Pn is the second point,
ro is the evaluated plane equation for Po
rn is the evaluated plane equation for Pn and
Pi is the interpolated point
Q32. How do I perform intersection tests between a line and a sphere?
---------------------------------------------------------------------
For all cases, it is convenient to define a bounding sphere for the
character. This allows for a simple distance check to determine
whether a collision is likely to happen or not.
The equation can be defined as follows:
2 2 2 2
V = (Xp - Xm) + (Yp - Ym) + (Zp - Zm) - R
where (Xp,Yp,Zp) are the coordinates of the player,
(Xm,Ym,Zm) are the coordinates of the missile and
R is the radius of the boundary sphere
If V is less than zero, a "hit" has occurred, otherwise it is a "miss".
If the missile is travelling so fast, as to appear instantaneous eg. high
velocity rifle, then you are better off performing a line-sphere
intersection test. In this case the trajectory of the missile is
determined by a line equation:
Pt = Ps + t . Pd
Where Pt is the location of the missile at time t
Ps is the initial location of the missile and
t is the time
This is substituted into the sphere equation above:
2 2 2 2
V = (Xp - Xm) + (Yp - Ym) + (Zp - Zm) - R
Evaluating out, this forms a quadratic equation with the terms:
2
A.t + B.t + C = 0
with the values of P, Q and R:
A = Pdx + Pdy + Pdz
B = -2.Xp.Pdx - 2.Yp.Pdy - 2.Zp.Pdz - 2.Psx.Pdx - 2.Psy.Pdy - 2.Psz.Pdz
2 2 2 2
C = Xp + Yp + Zp - 2.Xp.Psx - 2.Yp.Psy - 2.Zp.Psz - R
The roots of this quadratic equation define the values of the
parametric variable t where the line intersects the sphere.
The number of roots can be determined by calculated the "discriminant"
D where:
2
D = B - 4AC
If D is less than zero, no roots exist.
If D is equal to zero, then one root exists.
IF D is greater than zero, then two roots exist.
Q33. How do I perform intersection tests between two spheres?
-------------------------------------------------------------
Given two spheres with Radii Ra and Rb and center points Pa and Pb, then
the following test can be performed:
D = | Pb - Pa | - Ra - Rb
where D is the resulting test value.
If D is less than zero, the spheres intersect
If D is equal to zero, then the spheres just touch each other.
If D is greater than zero, then the spheres do not intersect.
The plane of intersection can be calculated as follows:
The outward normal is the normalised direction vector of Pa to Pb.
-------
Pn = Pb - Pa
This is equivalent to the values of A, B and C in the standard plane
equation.
The point of intersection is derived by:
Ra
Pi = Pa + ------- . N
(Ra+Rb)
The constant term of the plane equation can be evaluated by taking the
negative dot product ie.
D = -N.Pi
PARTICLE SYSTEMS
================
Q34. What are Flocks and Swarms?
--------------------------------
When animating animals, birds and insects, it is often required that
two or more creatures are required to interact with each other. For
example, a flock of geese will typically form a ^ formation when
flying South or a swarm of bees will fly in a cluster towards a
specific target.
This behaviour can be modelled by a special kind of particle system
(often referred to as Flocks). With traditional particle systems the
motion of each particle is governed solely by the laws of Physics eg.
gravity, velocity, wind, air-friction etc... No decision making ability
is given to individual particles.
Flocks attempt to give the particle system the appearance of cognitive
thought, by allowing each particle to make decisions based on its
position in the environment and relative to other particles.
Certain constraints can be applied to the system. These include speed
limits on velocity and accelaration. They may even include contraining
the amount of angular vision on a particle ie. modelling the inability
to see directly behind itself. This is required for modelling geese and
insects. (Out of scientific curiosity, it is noted that Rabbits have 360
degree vision).
Usually, each particle will also be assigned a preferred distance from
other particle. This is implemented using spherical force fields.
For each particle, the distance to every other particle is determined
using simple geometry. This value is then scaled using the inverse-square
law and used to determine the resulting acceleration vector. These vectors
are accumulated and used to move the particle. A maximum distance limit
is usually set to discount particles that are far away.
If two particles are closed together, they will attempt to move apart. If
they are too far away, they will attempt to move together.
To implement line-of-sight, the angular direction or direction vector is
also determined. Using a suitable acceptance function eg. dot product or
maximum/minimum limits, the visibility of other particles can be determined.
If "out of sight", then these particles are ignored.
To allow closer particles to obscure other further-away particles, only
the nearest 3 or more particles need be considered to generate the
acceleration vector.
Particle may also be required to interect with an environment. In that
case, collision detection and force fields may be implemented as
described in 19].
Q35. What is Facial Animation?
------------------------------
In the same way that Character Animation attempts to give life to
inanimate objects, character animation attempts to bring to life a
model of a face or an object which resembles a face.
For example, the front of a car can be made to look like a face; the
headlights are it's eyes, and the radiator is it's mouth.
Another example is a stero system; the large speakers to each side are
it's eyes and the buttons at the bottom are it's teeth/mouth.
One way to implement facial animation is to model the way muscles move.
With any living creature, movement of the skin surface is generated by
movement of muscles underneath.
Each patch of skin can be stretched by at least one or more muscles.
However, while each muscle can only pull in one direction when it
contracts, two or more muscles may be combined simultaneously to
generate a new stretch direction.
To represent this system using 3D mathematics, patches of skin are
represented by 3D vertices, rendered either using NURBS or polygons.
Each muscle is represented as a weighting factor from 0.0 (relaxed) to
1.0 (fully contracted).
Every vertex which is attached to that muscle has a cubic spline function
weighted to model the way in which the skin is stretched. When the muscle
contracts, the verex is displaced in a particular direction path.
Since the polygonal geometry remains the same, the face produces a
recognisable expression.
Grouping together muscle movements develops various expressions eg.
smiling grinning, surprise, frown, anger etc...
Q36. What is a good 3D mathematics library to build?
----------------------------------------------------
If you are starting out in 3D and would like to experiment with vectors,
matrices, outward normals and polygons, then you will need data structures
to represent these. The first decision you will need to make is whether to
use homogenous matrices (4x4) or standard (3x3) matrices.
For most game applications 3x3 matrices require less calculations (ie. no
need to maintain the W coordinate).
For further details, see the Vectors and Matrices FAQ.
BIBLIOGRAPHY
============
B1. Bibliography
----------------
COMPUTER SCIENCE BOOKS
======================
Graphics Gems
Foley and van Dam
Computational Dynamics by Shabana.
Physically Based Modeling in Computer Graphics and Animation by Barr.
Ronen Barzel
----------------------------------------------------------------
Robots and Telechirs
M.W.Thring, Queen Mary College, University of London
Ellis Horwood Series Engineering Science (1983)
ISBN 0-470-20174-6
- Full discussion on the design and applications of robots,
particularly in the fields of medicine and workplace safety.
One chapter describes kinematics. A large number of robotic
devices, including "Wallace and Gromit" style walking legs!
ART AND DRAWING BOOKS
=====================
The Encyclopedia of Cartooning Techniques
Steve Whitaker
Headline Book Publishing (1996)
ISBN 0-7472-7782-6
- Complete guide to designing cartoon strip characters
----------------------------------------------------------------
How to Draw Animation
Christopher Hart
Watson-Guptill Publications
1515 Broadway, New York, N.Y. 10036
ISBN 0-8230-2365-6
- Complete guide to classical 2D character animation. Also
covers walk cycles of both humans and four legged animals
such as horse and cats.
----------------------------------------------------------------
How to Draw Comic Book Heroes and Villains
Christopher Hart
Watson-Guptill Publications
1515 Broadway, New York, N.Y. 10036
ISBN 0-8230-2245-5
- Complete guide to drawing comic strip heroes and villains
----------------------------------------------------------------
Fantasy Art
Mike Jefferies
Harper Collins Publishers (1997)
ISBN 0 00 412885 4
- General guide to drawing castles, dungeons and dragons creatures
such as wizards, giants, dwarfs and peasants
----------------------------------------------------------------
DIsney's Art of Animation
from Mickey Mouse to Hercules
Thomas, Bob, 1992-
Hyperion, 114 Fifth Avenue, New York, New York 10011
ISBN 0-7868-6241-6
An interesting review of the cartoon industry and the motives
behind the creation of each feature film
----------------------------------------------------------------
The Animator's Workbook
Step-by-Step Techniques of Drawn Animation
Tony White
Watson Guptill Publications, a division of
Billboard Publications Inc., 1515 Broadway, New York, N.Y 10036
ISBN 0-8230-0229-2
An excellent guide on hand-drawn cartoons, gags and SFX used
in cartoons
------------------------------------------------------------
Walt Disney
Imagineering
Kevin Rafferty with Bruce Gordon
Hyperion, 114 Fifth Avenue, New York, New York 10011
ISBN 0-7868-6246-7
An interesting review of all the many special attractions designed
for each Disney wonderland.
----------------------------------------------------------------
Dynamic Anatomy
Burne Hogarth
Watson-Guptill Publications, New York
ISBN 0-8230-1550-5
ISBN 0-8230-1551-3 (paperback)
Detailed information on the measurements, proportions, anatomical
details, surface forms, perspective foreshortening and movement of
the human body
SIGGRAPH PAPERS
===============
SIGGRAPH 97
-----------
Jessica K. Hodgins and Nancy C. Pollard
Adapting Simulated Behaviors for New Characters
Ferdi Scheepers, Richard E. Parent, Wayne E. Carlson, Stephen F. May
Anatomy-Based Modeling of the Human Musculature
Jane Wilhelms and Allen Can Gelder
Anatomically Based Modeling
SIGGRAPH 96
-----------
David Baraff
Linear-Time Dynamics using Lagrange Mulipliers
Charles Rose, Brian Guenter, Bobby Bodenheimer, Michael F. Cohen
Efficient Generation of Motion Transitions using Spacetime Constraints
Joseph Laszio, Michiel van de Panne, Eugene Fiume
Limit Cycle Control And Its Application To The Animation of Balancing
And Walking
SIGGRAPH 95
-----------
Bruce M. Blumberg and Tinsley A. Galyean
Multi-Level Direction of Autonomous Creatures for Real-Time Environments
Yuencheng Lee, Demetri Terzopoulos, and Keith Waters
Realistic Modeling for Facial Animation
Radek Grzeszckuk and Demetri Terzopoulos
Automated Learning of Muscle-Actuated Locomotion
Through Control Abstraction
Jessica K. Hodgins, Wayne L. Wooten, David C. Brogan, James F. O'Brien
Animating Human Athletics
Munetoshi Unuma, Ken Anjyo, Ryozo Takeuchi
Fourier Principles for Emotion-based Human Figure Animation
Armin Bruderlin, Lance Williams
Motion Signal Processing
'
Andrew Witken and Zoran Popovic
Motion Warping
==========================================================================
Graphics Gems
=============
p351
Ken Shoemake
Quaternions and 4x4 Matrices
p360
Overview and low-level specification
VIII.4, p377
John Schlag
Using Geometric Constructions To Interpolate Orientation With Quaternions
p498
Patrick-Gilles Maillot
Using Quaternions For Coding 3D Transformations
VII.I, p320
Spencer W. Thomas
Decomposing A Matrix Into Simple Transformations
==========================================================================