Animation

Animation - Transcript

CSCE 590E Spring 2007
Animation
By Jijun Tang

Rendering Primitives
 Strips, Lists, Fans
 Indexed Primitives
 The Vertex Cache
 Quads and Point Sprites

Strips, Lists, Fans
1
2
3
4
5
6
7
8 9
1
2
3
4
5
6
7
8
1
2 3 4
5
6
1
2
3
45
6
1
2
3
4
5
6
Triangle 
list
Triangle fan
Triangle strip
Line list Line strip

Strips vs. Lists
32 triangles, 25 vertices 4 strips, 40 vertices
25 to 40 vertices is 60% extra data!

Indexed Primitives
 Vertices stored in separate array
 No duplication of vertices
 Called a “vertex buffer” or “vertex array”
 Triangles hold indices, not vertices
 Index is just an integer
 Typically 16 bits
 Duplicating indices is cheap
 Indexes into vertex array

Textures
 Texture Formats
 Texture Mapping
 Texture Filtering
 Rendering to Textures

Texture Formats
 Textures made of texels
 Texels have R,G,B,A components
 Often do mean red, green, blue colors
 Really just a labelling convention
 Shader decides what the numbers “mean”
 Not all formats have all components
 Different formats have different bit widths for
components
 Trade off storage space and speed for fidelity

Common formats
 A8R8G8B8 (RGBA8):
 32-bit RGB with Alpha
 8 bits per comp, 32 bits total
 R5G6B5: 5 or 6 bits per comp, 16 bits total
 A32f: single 32-bit floating-point comp
 A16R16G16B16f: four 16-bit floats
 DXT1: compressed 4x4 RGB block
 64 bits
 Storing 16 input pixels in 64 bits of output
 Consisting of two 16-bit R5G6B5 color values and a 4x4
two bit lookup table

MIP Map
8x8 2D texture with 
mipmap chain
4x4 cube map
(shown with sides 
expanded)

Texture Filtering for Resize
Point sampling enlarges without filtering
 When magnified, texels very obvious
 When minified, texture is “sparkly”

Bilinear filtering
 Used to smooth textures when
displayed larger or smaller than they
actually are
 Blends edges of texels
 Texel only specifies color at centre
 Magnification looks better
 Minification still sparkles a lot

Trilinear Filtering
 Trilinear can over-blur textures
 When triangles are edge-on to camera
 Especially roads and walls
 Anisotropic filtering solves this
 Takes multiple samples in one direction
 Averages them together
 Quite expensive in current hardware

Lighting and Approaches
 Processes to determine
 the amount and direction of light incident on a surface
 how that light is absorbed, reemitted, and reflected
 which of those outgoing light rays eventually reach the
eye
 Approaches:
 Forward tracing: trace every photon from light source
 Backward tracing: trace a photon backward from the eye
 Middle-out: compromise and trace the important rays

Hemisphere lighting
 Three major lights:
 Sky is light blue
 Ground is dark green or brown
 Dot-product normal with “up vector”
 Blend between the two colors
 Good for brighter outdoor daylight
scenes

Example

Lightmap Example

Normal Mapping Example

Specular Material Lighting
 Light bounces off surface
 How much light bounced into the eye?
 Other light did not hit eye – so not visible!
 Common model is “Blinn” lighting
 Surface made of “microfacets”
 They have random orientation
 With some type of distribution

Example

Environment Maps
 Blinn used for slightly rough materials
 Only models bright lights
 Light from normal objects is ignored
 Smooth surfaces can reflect everything
 No microfacets for smooth surfaces
 Only care about one source of light
 The one that reflects to hit the eye

Example

Character Animation

What is animation?
 Animation is from the latin “anima” or soul
 To give motion
 Means to give life
Anything you can do in your game to give it more
“life” through motion (or lack of motion).

Animation Example
 MSTS

Overview
 Fundamental Concepts
 Animation Storage
 Playing Animations
 Blending Animations
 Motion Extraction
 Mesh Deformation
 Inverse Kinematics
 Attachments & Collision Detection
 Conclusions

Animation Roles
 Programmer – loads information
created by the animator and translates
it into on screen action.
 Animator – Sets up the artwork.
Provides motion information to the
artwork.

Different types of animation
 Particle effects
 Procedural / Physics
 “Hard” object animation (door, robot)
 “Soft” object animation (tree swaying in
the wind, flag flapping the wind)
 Character animation

2D Versus 3D Animation
 Borrow from traditional 2D animation
 Understand the limitations of what can be
done for real-time games
 Designing 3D motions to be viewed from
more than one camera angle
 Pace motion to match game genre
Image courtesy of George T. Henion.

Animation terms
 frame – A image that is displayed on the screen, usually as part
of a sequence.
 pose – a orientation of an objects or a hierarchy of objects that
defines extreme or important motion.
 keyframe – a special frame that contains a pose.
 tween – the process of going “between” keyframes.
 secondary motion – An object motion that is the result of its
connection or relationship with another object.
 Baking – setting every Nth frame as a key frame.

Fundamental Problems
 Volume of data, processor limitations
 Mathematical complexity, especially
for rotations.
 Translation of motion

Fundamental Concepts
 Skeletal Hierarchy
 The Transform
 Euler Angles
 The 3x3 Matrix
 Quaternions
 Animation vs Deformation
 Models and Instances
 Animation Controls

Skeletal Hierarchy
 The Skeleton is a tree of bones
 Often flattened to an array in practice
 Top bone in tree is the “root bone”
 May have multiple trees, so multiple roots
 Each bone has a transform
 Stored relative to its parent’s transform
 Transforms are animated over time
 Tree structure is often called a “rig”

Example

The Transform
 “Transform” is the term for combined:
 Translation
 Rotation
 Scale
 Shear
 Can be represented as 4x3 or 4x4 matrix
 But usually store as components
 Non-identity scale and shear are rare
 Optimize code for common trans+rot case

Examples

Euler Angles
 Three rotations about three axes
 Intuitive meaning of values

Euler Angles
 This means that we can represent an orientation
with 3 numbers
 A sequence of rotations around principle axes is
called an Euler Angle Sequence
 Assuming we limit ourselves to 3 rotations without
successive rotations about the same axis, we could
use any of the following 12 sequences:
XYZ XZY XYX XZX
YXZ YZX YXY YZY
ZXY ZYX ZXZ ZYZ

Using Euler Angles
 To use Euler angles, one must choose
which of the 12 representations they
want
 There may be some practical
differences between them and the best
sequence may depend on what exactly
you are trying to accomplish

Interpolating Euler Angles
 One can simply interpolate between the three
values independently
 This will result in the interpolation following a
different path depending on which of the 12
schemes you choose
 This may or may not be a problem, depending on
your situation
 Interpolating near the ‘poles’ can be problematic
 Note: when interpolating angles, remember to
check for crossing the +180/-180 degree
boundaries

Problems
 Euler Angles Are Evil
 No standard choice or order of axes
 Singularity “poles” with infinite number of
representations
 Interpolation of two rotations is hard
 Slow to turn into matrices
 Use matrix rotation

Rotation Matrix

3x3 Matrix Rotation
 Easy to use
 Moderately intuitive
 Large memory size - 9 values
 Animation systems always low on memory
 Interpolation is hard
 Introduces scales and shears
 Need to re-orthonormalize matrices after

Quaternions
 Quaternions are an interesting mathematical
concept with a deep relationship with the
foundations of algebra and number theory
 Invented by W.R.Hamilton in 1843
 In practice, they are most useful to us as a
means of representing orientations
 A quaternion has 4 components
[ ]3210 qqqq=q

Quaternions on Rotation
 Represents a rotation around an axis
 Four values
 is axis vector times sin(angle/2)
 w is cos(angle/2)
 No singularities
 But has dual coverage: Q same rotation as –Q
 This is useful in some cases!
 Interpolation is fast

Quaternions (Imaginary Space)
 Quaternions are actually an extension to complex
numbers
 Of the 4 components, one is a ‘real’ scalar number,
and the other 3 form a vector in imaginary ijk space!
3210 kqjqiqq +++=q
jiijk
ikkij
kjjki
ijkkji
−==
−==
−==
−==== 1222

Quaternions (Scalar/Vector)
 Sometimes, they are written as the
combination of a scalar value s and a vector
value v
where
[ ]321
0
qqq
qs
=
=
v
vq ,s=

Unit Quaternions
 For convenience, we will use only unit length
quaternions, as they will be sufficient for our
purposes and make things a little easier
 These correspond to the set of vectors that form the
‘surface’ of a 4D hypersphere of radius 1
 The ‘surface’ is actually a 3D volume in 4D space,
but it can sometimes be visualized as an extension
to the concept of a 2D surface on a 3D sphere
123222120 =+++= qqqqq

Quaternions as Rotations
 A quaternion can represent a rotation by an
angle θ around a unit axis a:
 If a is unit length, then q will be also
2sin,2cos
2sin2sin2sin2cos
θθ
θθθθ
aq
q
=



=
or
aaa zyx

Quaternions as Rotations
( )
11
2sin2cos2sin2cos
2sin2cos
2sin2sin2sin2cos
22222
22222
2222222
2
3
2
2
2
1
2
0
==
+=+=
+++=
+++=
+++=
θθθθ
θθ
θθθθ
a
q
zyx
zyx
aaa
aaa
qqqq

Quaternion to Matrix








−−−+
+−−−
−+−−
2
2
2
110322031
1032
2
3
2
13021
20313021
2
3
2
2
2212222
2222122
2222221
qqqqqqqqqq
qqqqqqqqqq
qqqqqqqqqq
 To convert a quaternion to a rotation
matrix:

Matrix to Quaternion
 Matrix to quaternion is doable
 It involves a few ‘if’ statements, a
square root, three divisions, and some
other stuff
 Search online if interested

Animation vs. Deformation
 Skeleton + bone transforms = “pose”
 Animation changes pose over time
 Knows nothing about vertices and meshes
 Done by “animation” system on CPU
 Deformation takes a pose, distorts the
mesh for rendering
 Knows nothing about change over time
 Done by “rendering” system, often on
GPU

Pose

Model
 Describes a single type of object
 Skeleton + rig
 One per object type
 Referenced by instances in a scene
 Usually also includes rendering data
 Mesh, textures, materials, etc
 Physics collision hulls, gameplay data, etc

Instance
 A single entity in the game world
 References a model
 Holds current position & orientation
 (and gameplay state – health, ammo, etc)
 Has animations playing on it
 Stores a list of animation controls

Animation Control
 Links an animation and an instance
 1 control = 1 anim playing on 1 instance
 Holds current data of animation
 Current time
 Speed
 Weight
 Masks
 Looping state

Animation Storage
 The Problem
 Decomposition
 Keyframes and Linear Interpolation
 Higher-Order Interpolation
 The Bezier Curve
 Non-Uniform Curves
 Looping

Storage – The Problem
 4x3 matrices, 60 per second is huge
 200 bone character = 0.5Mb/sec
 Consoles have around 32-64Mb (Xbox
and PS3 have larger, but still limited)
 Animation system gets maybe 25%
 PC has more memory
 But also higher quality requirements

Decomposition
 Decompose 4x3 into components
 Translation (3 values)
 Rotation (4 values - quaternion)
 Scale (3 values)
 Skew (3 values)
 Most bones never scale & shear
 Many only have constant translation
 But human characters may have higher requirement
 Muscle move, smiling, etc.
 Cloth under winds
 Don’t store constant values every frame, use index instead

Keyframes
 Motion is usually smooth
 Only store every nth frame
 Store only “key frames”
 Linearly interpolate between
keyframes
 Inbetweening or “tweening”
 Different anims require different rates
 Sleeping = low, running = high
 Choose rate carefully

Key Frame Example
 3D Canvas

Linear Interpolation

Higher-Order Interpolation
 Tweening uses linear interpolation
 Natural motions are not very linear
 Need lots of segments to approximate well
 So lots of keyframes
 Use a smooth curve to approximate
 Fewer segments for good approximation
 Fewer control points
 Bézier curve is very simple curve

Bézier Curves (2D & 3D)
 Bézier curves can be thought of as a
higher order extension of linear
interpolation
p0
p1
p0
p1 p2
p0
p1
p2
p3

The Bézier Curve
 (1-t)3F1+3t(1-t)2T1+3t2(1-t)T2+t3F2
t=0.25
F1
T1
T2
F2
t=1.0
t=0.0

The Bézier Curve (2)
 Quick to calculate
 Precise control over end tangents
 Smooth
 C0 and C1 continuity are easy to achieve
 C2 also possible, but not required here
 Requires three control points per curve
 (assume F2 is F1 of next segment)
 Far fewer segments than linear

Bézier Variants
 Store 2F2-T2 instead of T2
 Equals next segment T1 for smooth curves
 Store F1-T1 and T2-F2 vectors instead
 Same trick as above – reduces data stored
 Called a “Hermite” curve
 Catmull-Rom curve
 Passes through all control points

Catmull-Rom Curve
 Defined by 4 points.
Curve passes through middle 2 points.
 P = C3t3 + C2t2 + C1t + C0
 C3 = -0.5 * P0 + 1.5 * P1 - 1.5 * P2 + 0.5 * P3
C2 = P0 - 2.5 * P1 + 2.0 * P2 - 0.5 * P3
C1 = -0.5 * P0 + 0.5 * P2
C0 = P1

Non-Uniform Curves
 Each segment stores a start time as well
 Time + control value(s) = “knot”
 Segments can be different durations
 Knots can be placed only where needed
 Allows perfect discontinuities
 Fewer knots in smooth parts of animation
 Add knots to guarantee curve values
 Transition points between animations
 “Golden poses”

Looping and Continuity
 Ensure C0 and C1 for smooth motion
 At loop points
 At transition points
 Walk cycle to run cycle
 C1 requires both animations are
playing at the same speed
 Reasonable requirement for anim system

Playing Animations
 “Global time” is game-time
 Animation is stored in “local time”
 Animation starts at local time zero
 Speed is the ratio between the two
 Make sure animation system can change speed
without changing current local time
 Usually stored in seconds
 Or can be in “frames” - 12, 24, 30, 60 per
second

Scrubbing
 Sample an animation at any local time
 Important ability for games
 Footstep planting
 Motion prediction
 AI action planning
 Starting a synchronized animation
 Walk to run transitions at any time
 Avoid delta-compression storage methods
 Very hard to scrub or play at variable speed

Delta Compression
 Delta compression is a way of storing or
transmitting data in the form of differences between
sequential data rather than complete files.
 The differences are recorded in discrete files called
deltas or diffs.
 Because changes are often small (only 2% total
size on average), it can greatly reduce data
redundancy.
 Collections of unique deltas are substantially more
space-efficient than their non-encoded equivalents.

Animation Blending
 The animation blending system allows
a model to play more than one
animation sequence at a time, while
seamlessly blending the sequences
 Used to create sophisticated, life-like
behavior
 Walking and smiling
 Running and shooting

Blending Animations
 The Lerp
 Quaternion Blending Methods
 Multi-way Blending
 Bone Masks
 The Masked Lerp
 Hierarchical Blending

The Lerp
 Foundation of all blending
 “Lerp”=Linear interpolation
 Blends A, B together by a scalar weight
 lerp (A, B, i) = iA + (1-i)B
 i is blend weight and usually goes from 0 to 1
 Translation, scale, shear lerp are obvious
 Componentwise lerp
 Rotations are trickier – normalized
quaternions is usually the best method.

Quaternion Blending
 Normalizing lerp (nlerp)
 Lerp each component
 Normalize (can often be approximated)
 Follows shortest path
 Not constant velocity
 Multi-way-lerp is easy to do
 Very simple and fast
 Many others:
 Spherical lerp (slerp)
 Log-quaternion lerp (exp map)

Which is the Best
 No perfect solution!
 Each missing one of the features
 All look identical for small
interpolations
 This is the 99% case
 Blending very different animations looks
bad whichever method you use
 Multi-way lerping is important
 So use cheapest - nlerp

Multi-way Blending
 Can use nested lerps
 lerp (lerp (A, B, i), C, j)
 But n-1 weights - counterintuitive
 Order-dependent
 Weighted sum associates nicely
 (iA + jB + kC + …) / (i + j + k + … )
 But no i value can result in 100% A
 More complex methods
 Less predictable and intuitive
 Can be expensive

Bone Masks
 Some animations only affect some bones
 Wave animation only affects arm
 Walk affects legs strongly, arms weakly
 Arms swing unless waving or holding something
 Bone mask stores weight for each bone
 Multiplied by animation’s overall weight
 Each bone has a different effective weight
 Each bone must be blended separately
 Bone weights are usually static
 Overall weight changes as character changes
animations

The Masked Lerp
 Two-way lerp using weights from a mask
 Each bone can be lerped differently
 Mask value of 1 means bone is 100% A
 Mask value of 0 means bone is 100% B
 Solves weighted-sum problem
 (no weight can give 100% A)
 No simple multi-way equivalent
 Just a single bone mask, but two animations

Hierarchical Blending
 Combines all styles of blending
 A tree or directed graph of nodes
 Each leaf is an animation
 Each node is a style of blend
 Blends results of child nodes
 Construct programmatically at load time
 Evaluate with identical code each frame
 Avoids object-specific blending code
 Nodes with weights of zero not evaluated

Motion Extraction
 Moving the Game Instance
 Linear Motion Extraction
 Composite Motion Extraction
 Variable Delta Extraction
 The Synthetic Root Bone
 Animation Without Rendering

Moving the Game Instance
 Game instance is where the game thinks the
object (character) is
 Usually just
 pos, orientation and bounding box
 Used for everything except rendering
 Collision detection
 Movement
 It’s what the game is!
 Must move according to animations

Linear Motion Extraction
 Find position on last frame of animation
 Subtract position on first frame of animation
 Divide by duration
 Subtract this motion from animation frames
 During animation playback, add this delta
velocity to instance position
 Animation is preserved and instance moves
 Do same for orientation

Problems
 Only approximates straight-line motion
 Position in middle of animation is
wrong
 Midpoint of a jump is still on the ground!
 What if animation is interrupted?
 Instance will be in the wrong place
 Incorrect collision detection
 Purpose of a jump is to jump over things!

Composite Motion Extraction
 Approximates motion with circular arc
 Pre-processing algorithm finds:
 Axis of rotation (vector)
 Speed of rotation (radians/sec)
 Linear speed along arc (metres/sec)
 Speed along axis of rotation (metres/sec)
 e.g. walking up a spiral staircase

Benefits and Problems
 Very cheap to evaluate
 Low storage costs
 Approximates a lot of motions well
 Still too simple for some motions
 Mantling ledges
 Complex acrobatics
 Bouncing

Variable Delta Extraction
 Uses root bone motion directly
 Sample root bone motion each frame
 Find delta from last frame
 Apply to instance pos+orn
 Root bone is ignored when rendering
 Instance pos+orn is the root bone

Benefits
 Requires sampling the root bone
 More expensive than CME
 Can be significant with large worlds
 Use only if necessary, otherwise use CME
 Complete control over instance motion
 Uses existing animation code and data
 No “extraction” needed

The Synthetic Root Bone
 All three methods use the root bone
 But what is the root bone?
 Where the character “thinks” they are
 Defined by animators and coders
 Does not match any physical bone
 Can be animated completely
independently
 Therefore, “synthetic root bone” or
SRB

The Synthetic Root Bone (2)
 Acts as point of reference
 SRB is kept fixed between animations
 During transitions
 While blending
 Often at centre-of-mass at ground level
 Called the “ground shadow”
 But tricky when jumping or climbing – no ground!
 Or at pelvis level
 Does not rotate during walking, unlike real pelvis
 Or anywhere else that is convenient

Animation Without Rendering
 Not all objects in the world are visible
 But all must move according to anims
 Make sure motion extraction and
replay is independent of rendering
 Must run on all objects at all times
 Needs to be cheap!
 Use LME & CME when possible
 VDA when needed for complex animations

Mesh Deformation
 Find Bones in World Space
 Find Delta from Rest Pose
 Deform Vertex Positions
 Deform Vertex Normals

Find Bones in World Space
 Animation generates a “local pose”
 Hierarchy of bones
 Each relative to immediate parent
 Start at root
 Transform each bone by parent bone’s world-
space transform
 Descend tree recursively
 Now all bones have transforms in world
space
 “World pose”

Find Delta from Rest Pose
 Mesh is created in a pose
 Often the “da Vinci man” pose for humans
 Called the “rest pose”
 Must un-transform by that pose first
 Then transform by new pose
 Multiply new pose transforms by inverse of rest
pose transforms
 Inverse of rest pose calculated at mesh load
time
 Gives “delta” transform for each bone

Deform Vertex Positions
 Deformation usually performed on
GPU
 Delta transforms fed to GPU
 Usually stored in “constant” space
 Vertices each have n bones
 n is usually 4
 4 bone indices
 4 bone weights 0-1
 Weights must sum to 1

Deform Vertex Positions (2)
vec3 FinalPosition = {0,0,0};
for ( i = 0; i < 4; i++ )
{
int BoneIndex = Vertex.Index[i];
float BoneWeight = Vertex.Weight[i];
FinalPosition +=
BoneWeight * Vertex.Position *
PoseDelta[BoneIndex]);
}

Deform Vertex Normals
 Normals are done similarly to positions
 But use inverse transpose of delta transforms
 Translations are ignored
 For pure rotations, inverse(A)=transpose(A)
 So inverse(transpose(A)) = A
 For scale or shear, they are different
 Normals can use fewer bones per vertex
 Just one or two is common

Inverse Kinematics
 FK & IK
 Single Bone IK
 Multi-Bone IK
 Cyclic Coordinate Descent
 Two-Bone IK
 IK by Interpolation

FK & IK
 Most animation is “forward kinematics”
 Motion moves down skeletal hierarchy
 But there are feedback mechanisms
 Eyes track a fixed object while body
moves
 Foot stays still on ground while walking
 Hand picks up cup from table
 This is “inverse kinematics”
 Motion moves back up skeletal hierarchy

Single Bone IK
 Orient a bone in given direction
 Eyeballs
 Cameras
 Find desired aim vector
 Find current aim vector
 Find rotation from one to the other
 Cross-product gives axis
 Dot-product gives angle
 Transform object by that rotation

Multi-Bone IK
 One bone must get to a target position
 Bone is called the “end effector”
 Can move some or all of its parents
 May be told which it should move first
 Move elbow before moving shoulders
 May be given joint constraints
 Cannot bend elbow backwards

Cyclic Coordinate Descent
 Simple type of multi-bone IK
 Iterative
 Can be slow
 May not find best solution
 May not find any solution in complex
cases
 But it is simple and versatile
 No precalculation or preprocessing
needed

Cyclic Coordinate Descent (2)
 Start at end effector
 Go up skeleton to next joint
 Move (usually rotate) joint to minimize
distance between end effector and target
 Continue up skeleton one joint at a time
 If at root bone, start at end effector again
 Stop when end effector is “close enough”
 Or hit iteration count limit

Cyclic Coordinate Descent (3)
 May take a lot of iterations
 Especially when joints are nearly
straight and solution needs them bent
 e.g. a walking leg bending to go up a step
 50 iterations is not uncommon!
 May not find the “right” answer
 Knee can try to bend in strange directions

Two-Bone IK
 Direct method, not iterative
 Always finds correct solution
 If one exists
 Allows simple constraints
 Knees, elbows
 Restricted to two rigid bones with a rotation
joint between them
 Knees, elbows!
 Can be used in a cyclic coordinate descent

Two-Bone IK (2)
 Three joints must stay in user-specified plane
 e.g. knee may not move sideways
 Reduces 3D problem to a 2D one
 Both bones must remain same length
 Therefore, middle joint is at intersection of
two circles
 Pick nearest solution to current pose
 Or one solution is disallowed
 Knees or elbows cannot bend backwards

Two-Bone IK (3)
Allowed
elbow
position
Shoulder
Wrist
Disallowed
elbow
position

IK by Interpolation
 Animator supplies multiple poses
 Each pose has a reference direction
 e.g. direction of aim of gun
 Game has a direction to aim in
 Blend poses together to achieve it
 Source poses can be realistic
 As long as interpolation makes sense
 Result looks far better than algorithmic IK with
simple joint limits

IK by Interpolation (2)
 Result aim point is inexact
 Blending two poses on complex skeletons
does not give linear blend result
 Can iterate towards correct aim
 Can tweak aim with algorithmic IK
 But then need to fix up hands, eyes, head
 Can get rifle moving through body

Attachments
 e.g. character holding a gun
 Gun is a separate mesh
 Attachment is bone in character’s skeleton
 Represents root bone of gun
 Animate character
 Transform attachment bone to world space
 Move gun mesh to that pos+orn

Attachments (2)
 e.g. person is hanging off bridge
 Attachment point is a bone in hand
 As with the gun example
 But here the person moves, not the bridge
 Find delta from root bone to attachment bone
 Find world transform of grip point on bridge
 Multiply by inverse of delta
 Finds position of root to keep hand gripping

Collision Detection
 Most games just use bounding volume
 Some need perfect triangle collision
 Slow to test every triangle every frame
 Precalculate bounding box of each
bone
 Transform by world pose transform
 Finds world-space bounding box
 Test to see if bbox was hit
 If it did, test the tris this bone influences

Conclusions
 Use quaternions
 Matrices are too big, Eulers are too evil
 Memory use for animations is huge
 Use non-uniform spline curves
 Ability to scrub anims is important
 Multiple blending techniques
 Different methods for different places
 Blend graph simplifies code

Conclusions (2)
 Motion extraction is tricky but essential
 Always running on all instances in world
 Trade off between cheap & accurate
 Use Synthetic Root Bone for precise
control
 Deformation is really part of rendering
 Use graphics hardware where possible
 IK is much more than just IK
algorithms
 Interaction between algorithms is key