Transcript Introduction to 3D Rendering

KIPA Game Engine Seminars
Day 11
Jonathan Blow
Seoul, Korea
December 7, 2002
1
Character Animation
• The goal: let artists make animation, and get
it into the game
• Usually animation is made in a separate tool
– Maya / MAX
• Made out of hierarchical transforms
• Probably we need to write an exporter
plugin and some game-engine import code
– Unless we use a licensed character animation
system (like Granny)
2
Goals for in-engine
reproduced animation
• As much like the art package’s version of
the animation as possible
• But small (low memory) and fast
3
How animations are authored
• The artist sets up a bunch of keyframes for
transform data
– Usually separated into translation, rotation,
scale
• The art tool interpolates between these
keyframes at runtime
• Maybe we should export the keyframes and
interpolate them in the engine
4
Why you don’t want to
export the keyframes (1)
• They can be in weird formats that require
confusing code to interpolate
– 3DS max TCB curves
• They can be in formats that are slow to interpolate
– Euler angles
• They are not necessarily well-compressed
– Keyframes get fragmented over time
– What happens when you import an animation from
another package
5
Why you don’t want to
export the keyframes (2)
• Artists use IK tools to help create
animations
• You would have to reconstruct all this IK
functionality exactly for the animation to
look right
– Footstep controller
– Guy grabbing something from a table
6
A better solution:
Sample the transforms
• Don’t worry about the original keyframe
data, just evaluate the transforms at some
sampling interval
• Save those transforms out, interpolate them
at runtime
– Sample at perhaps 30Hz
7
Interpolating transforms?
• We don’t want to interpolate a 4x3 matrix
– It will denormalize, introduce shear
• Break it into intuitive pieces (translation,
rotation, scale)
– By matrix decomposition
– But… which decomposition you choose
matters!
• Shear easily confused with rotation
• Use the polar decomposition
8
Interpolating transforms? (2)
• If samples are close together, our
interpolation will not diverge much from the
art tool’s
– Euler vs slerp for small angles
• But those samples take a lot of memory!
– Example of how much
9
Want to compress those samples
• Hopefully at export time (small file size)
• How to compress?
– Fourier / Wavelet compression
– Curve fitting
• Performance ramifications of each method
10
Compression
• Probably, curve fitting is the best choice
• Each curve stored as an array of unevenly
spaced knots
• At runtime we just evaluate a simple
polynomial to reconstruct values
– For linear values like translation and scale
– What about rotation?
11
Rotation interpolation
• For interpolation between two rotations,
slerp is the “right answer”
• This may be too slow
– Review of slerp code
• Can we do something else
12
Different kinds of
rotation interpolation
• slerp
• exponential map
• lerp
– lerp approximates slerp for small angles
• sin(x) = x as x -> 0
– It’s not that bad for large angles either
13
Re-derivation of slerp
in 2D
• Did this once before, but will do it again
quickly, as an introduction to the lerp
derivation
14
What happens when we
lerp two quaternions?
• Assuming they don’t differ by more than 90
degrees
– double cover!
• We can analytically quantify the distoritions
in angle and length
15
Using lerp as a
substitution for slerp
• Probably we have to renormalize
• Maybe we have to compensate for the angle
• Discussion of fast unit vector normalization
– Newton-raphson approximation to 1/sqrt(x) in
the neighborhood near 1
– Walk-through of code
16
How to compensate for
the angle
• Discussion of approximating the inverse of
the angular distortion
17
Maybe we don’t have to
compensate for the angle
• When curve-fitting, we measure our error
with respect to the lerped/normalized
reconstruction of a spline (not the ideal
slerp solution)
• This causes us to insert more knots in the
curve when we might need better angle
accuracy
• So maybe there is a trade-off here, memory
for runtime speed
18
Fitting algorithm
• (discussion on whiteboard, including
quirks)
19
Data structures
• An animation structure contains:
– Number of nodes, names of the nodes
– Keyframe data for compressed curves
– Information about how to blend in/out of
animation, when to start/stop
• Explanation of some different ways you
might want to arrange things
20
Data structures
• A mesh contains:
– Number of nodes, names of the nodes
– Vertex data
– Vertex weight information
21
Binding data structures
• A lot of systems work by building a table
that cross-references between node names
in the animations, and node names in the
mesh
– Animations might not be stored in the same
order node-wise
– Some might have nodes that the others don’t
• This is called the “bind step”
22
I don’t like the bind step
• It means that you can’t have animation playback
without a mesh attached
• I want animations to be meaningful without
meshes yet, i.e. I want to be able to play them
back and mix them
– Though there are bone length assumptions built into the
animations
• Lately I rewrote my animation system to not use a
bind step
23
What I do
• An “animation player” class handles animation
playing
• One “channel” per animation on the same figure
(so, 2 channels for upper/lower body)
• The player has a string hash table that keeps track
of values, and maps each channel’s nodes to a
central node array
• To animate an object, we map that object’s node
names through the hash table (every frame,
potentially)
24
Structuring node order
by dependency
• So you can compose a bunch of relative
transforms into object-space transforms in
one pass
– Only constraint is that any node’s parent has to
have an index less than its own
• If you mix two arrays like this, it is easy to
maintain this constraint
– So the player’s central animation array will be
correctly ordered
25
Mixing Animations
• Sometimes you want to play back two
different animations on various nodes of the
body
– Description of how this reduces data size and
artist time
• This will produce inappropriate results for
some actions
– Because the meanings of various rotations
depend on what’s higher up in the hierarchy
– Example: Guy swinging a sword
26
Mixing Animations
• Interpolate transforms relative to a common
root between the two animations
• Put these into the relative transform slots
during animation playback
– Or else interpolate in object space, but that
might be inconvenient
27
Brief discussion: quaternion
splines
• Very hard to precompute, not cheap to
evaluate either
• Though Casey says you can do a de
Casteljau-like formulation, using slerp
instead of lerp
• I am not sure if this is the “right answer”
but it seems to work in many cases
• So if lerp is not good enough, think about
using this layered slerp technique
28
Mixing IK with
playing animations
• Evaluate the animations first
• Solve IK given those object-space
coordinates
• Mix the IK back in as though it were an
animation channel
29
Putting sound effects
in animation data
• Only robust way to generate sound cues at
appropriate times!
• Put tag names in the animation; these tags
are later converted to sound effect names
– based on material contacted, etc…
• (example of footsteps)
30
Putting other auxiliary data
in animations
• Example of “attack strength” in
swordfighting game
• Advantage: Easy for animator to change
this without programmers, easy to keep in
sync with animation
• Disadvantage: Maybe animator should not
be in charge of this; might be better to have
a separate specification system
31
Instead of IK
for aiming things…
• Blending between pre-generated animations
• (Example of aiming a gun)
• Can do an iterated search through the
animation space until you find something
“close enough”
32
Reasons you still might
want IK
• Example of two-handed weapon
– Shows why requiring a tree hierarchy is bad
33
Facial Animation
• Probably should use morph targets, not a
bone system
• Each facial expression is probably a short
animation (not a frozen mask)
34
Code Inspection
35
Questions?
36