Animation And Ai

Animation And Ai - Transcript

CSCE 590E Spring 2007
Animation and AI
By Jijun Tang

Announcements
 April 16th/18th: demos
 Show progress/difficulties/change of plans
 USC Times will have reporters in the class
 High school outreach
 Anyone can contact their high school
admin to arrange direct talks to students
 Of course, in SC only

Homework
 P 655 questions 1 and 2
 5 points total
 Due April 16th

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).

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

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

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

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

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

Pose

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

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

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

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”

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

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

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”

Example

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
 Each vertex has several bones affect it (the
number is generally set to <=4).
 Vertices each have n bones
 n is usually 4
 4 bone indices
 4 bone weights 0-1
 Weights must sum to 1
 Deformation usually performed on GPU
 Delta transforms fed to GPU
 Usually stored in “constant” space

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 important for shading and are done
similarly to positions
 When transformed, normals must be transformed
by the inverse transpose of the transform matrix
 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

Example of Forward
Kinematics
 http://www.cs.nyu.edu/~lyl209/hw4/doll/

Example of Inverse Kinematics

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

Procedures
 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 Constraints
 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

Example
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

Example
 One has poses for look ahead, look
downward (60 。 ), look right, look down and
right
 Now to aim 54 。 right and 15 。 downward,
thus 60% (54/90) on the horizontal scale,
25% (15/60) on the downward scale
 Look ahead (1-0.25)(1-0.6)=0.3
 Look downward 0.25(1-0.6)=0.1
 Look right (1-0.25) 0.6=0.45
 Look down and right (0.25)(0.6)=0.15

IK by Interpolation results
 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 triangles 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

Network and Multiplayer

Multiplayer Modes:
Event Timing
 Turn-Based
 Easy to implement
 Any connection type
 Real-Time
 Difficult to implement
 Latency sensitive

Multiplayer Modes:
Shared I/O
 Input Devices
 Shared keyboard layout
 Multiple device mapping
 Display
 Full Screen
 Funneling
 Screen Swap
 Split Screen

Multiplayer Modes:
Connectivity
 Non Real-Time
 Floppy disk net
 Email
 Database
 Direct Link
 Serial, USB, IrD, … (no hops)
 Circuit Switched (phones)
 Dedicated line with consistent latency
 Packet Switched
 Internet
 Shared pipe

Protocols:
Protocol Design
 Packet Length Conveyance
 Acknowledgement Methodology
 Error Checking / Correcting
 Compression
 Encryption
 Packet Control

Protocols:
Packets
 Packets
 Header = Protocol Manifest
 Payload
 Gottchas
 Pointers
 Large/Variable Size Arrays
 ADTs
 Integer Alignment
 Endian Order
 Processor dependant Intrinsic Types (int and long)
 Unicode vs. ASCII Strings

Protocols:
Request for Comments
 RFC web site
 http://www.rfc-editor.org/
 Protocol Specifications
 Definitive Resource
 Public Criticism
 Future Protocols

Protocol Stack:
Open System Interconnect
R o u t e r
S e n d e r R e c e i v e r
N e t w o r k
D a t a L i n k
P h y s i c a l
N e t w o r k
D a t a L i n k
P h y s i c a l
A p p l i c a t i o n
P r e s e n t a t i o n
S e s s i o n
T r a n s p o r t
N e t w o r k
D a t a L i n k
P h y s i c a l
A p p l i c a t i o n
P r e s e n t a t i o n
S e s s i o n
T r a n s p o r t
N e t w o r k
D a t a L i n k
P h y s i c a l
G a m e E v e n t s
G a m e P a c k e t i z a t i o n
C o n n e c t i o n & D a t a E x c h a n g e
I n p u t U p d a t e s
S t a t e U p d a t e s
S e r i a l i z a t i o n
B u f f e r i n g
S o c k e t s
T C P
U D P
I P
E t h e r n e t ( M A C )
W i r e d ( C 5 , C a b l e )
F i b e r O p t i c s
W i r e l e s s

Protocol Stack:
Physical Layer
 Bandwidth
 Width of data pipe
 Measured in bps = bits per second
 Latency
 Travel time from point A to B
 Measured in Milliseconds
 You cannot beat the physics
 The Medium
 Fiber, FireWire, IrD , CDMA & other cell
Serial USB1&2 ISDN DSL Cable
LAN
10/100/1G
BaseT
Wireless
802.11
a/b/g
Power
Line T1
Speed
(bps) 20K
12M
480M 128k
1.5M down
896K up
3M down
256K up
10M
100M
1G
b=11M
a,g=54M 14M 1.5M
Table: Max Bandwidth Specifications 

Protocol Stack:
Data Link Layer
 Serializes data to/from physical layer
 Network Interface Card (NIC)
 Ethernet
 MAC Address

Protocol Stack:
Network Layer
 Packet Routing
 Hops
 Routers, Hubs, Switches
 Internet Protocol (IP)
 Contains Source & Destination IP Address
 IPv4
 Widespread Infrastructure
 IPv6
 Larger IP address

Protocol Stack:
Network Layer: IP Address
 Unicast
 Static
 DHCP
 Multicast
 Requires multicast capable router
 Broadcast
 Local
 Directed
 Loop Back
 Send to self
 AddrAny
 0 = address before receiving an address

Protocol Stack:
Network Layer: DNS
 Domain Name Service
 Converts text name to IP address
 Must contact one or more DNS servers to
resolve
 Local cache resolution possible
 Game Tips
 Store local game cache to use when DNS out of
order.
 DNS resolution often slow, use cache for same
day resolution.

Protocol Stack:
Transport Layer
 Manage data deliver between
endpoints
 Error recovery
 Data flow
 TCP and UDP used with IP
 Contains Source and Destination Port
 Port + IP = Net Address
 Port Range = 0-64k
 Well known Ports 0-1k

Protocol Stack:
Transport Layer: TCP
 Guaranteed Correct In Order Delivery
 Acknowledgement system
 Ack, Nack, Resend
 Checksum
 Out of Band
 Connection Required
 Packet Window
 Packet Coalescence
 Keep Alive
 Streamed Data
 User must serialize data

Protocol Stack:
Transport Layer: UDP
 Non Guaranteed Delivery
 No Acknowledgement system
 May arrive out of order
 Checksum
 Not Connected
 Source not verified
 Hop Count Limit = TTL (time to live)
 Required for Broadcasting
 Datagram
 Sent in packets exactly as user sends them

Protocol Stack:
Session Layer
 Manages Connections between Apps
 Connect
 Terminate
 Data Exchange
 Socket API live at this layer
 Cross platform
 Cross language

Protocol Stack:
Session Layer: Sockets
 Based on File I/O
 File Descriptors
 Open/Close
 Read/Write
 Winsock
 Provides standard specification implementation
plus more
 Extension to spec prefixed with “WSA”
 Requires call to WSAStartup() before use
 Cleanup with WSAShutdown()

Protocol Stack:
Session Layer: Socket Design
 Modes
 Blocking
 Non-Blocking
 Standard Models
 Standard
 Select
 Extended Models
 Windows
 WSAEventSelect
 I/O Completion Ports
 Unix
 Poll
 Kernel Queues

Protocol Stack:
Presentation Layer
 Prepares App Data for Transmission
 Compression
 Pascal Strings
 String Tables
 Float to Fixed
 Matrix to Quaternion
 Encryption
 Endean Order
 When used cross platform or cross language
 Serialize
 Pointers
 Variable Length Arrays

Protocol Stack:
Presentation Layer: Buffering
 Packet Coalescence
 Induced Latency
 Dead Data
 Large Packets

Protocol Stack:
Application Layer
 Handles Game Logic
 Update Models
 Input Reflection
 State Reflection
 Synchronization
 Dead Reckoning
 AI Assist
 Arbitration

Real-Time Communications:
Connection Models
 Broadcast
 Good for player discovery on LANs
 Peer to Peer
 Good for 2 player games
 Client / Server
 Good for 2+ player games
 Dedicated lobby server great for player
discovery

Real-Time Communications:
Peer to Peer vs. Client/Server

Broadcast Peer/Peer Client/Server
Connections 0 Client = 1Server = N
N = Number of players
Broadcast Peer/Peer Client/Server
Send 1 N-1 Client = 1 Server = N
Receive N-1 N-1 Client = 1Server = N
∑−
=
1
1
N
x
x
P 1 P 2
P 1
P 2 P 3
P 1 P 4
P 2 P 3
P 1
P 2 P 5
P 3 P 4
2 p l a y e r s
1 c o n n e c t i o n
3 p l a y e r s
3 c o n n e c t i o n s
4 p l a y e r s
6 c o n n e c t i o n s
5 p l a y e r s
1 0 c o n n e c t i o n s

Security:
Encryption Goals
 Authentication
 Privacy
 Integrity

Security:
Encryption Methods
 Keyed
 Public Key
 Private Key
 Ciphers
 Message Digest
 Certificates
 IPSec

Security:
Copy Protection
 Disk Copy Protection
 Costly Mastering, delay copies to ensure
first several months’ sale
 Invalid/Special Sector Read
 Code Sheets
 Ask code from a line in a large manual
 Watermarking

Security:
Execution Cryptography
 Code Obfuscation
 Strip Symbols: int numOfPlayer;int a1;
 Heap Hopper
 Move sensitive data around in the heap to avoid
snapshots
 Stack Overrun Execution
 Check for buffer overflow
 NoOp Hacking
 Timer Hacking
 Do not allow time to change backward
 DLL Shims

Privacy
 Critical data should be kept secret and strong
encrypted:
 Real name
 Password
 Address/phone/email
 Billing
 Age (especially for minors)
 Using public key for transforming user name
and password

Security:
Firewalls
 Packet Filter
 Allow a packet based on its headers
 Proxies
 Check contents
 Circuit Gateways
 Setup secure sessions

Security:
Firewalls: Network Address Translation
L A N A d d r e s s W A N A d d r e s s
1 9 2 . 1 6 8 . 1 . 1 : 2 0 0 2 4 . 1 5 . 1 . 1 1 8 : 2 0 0
1 9 2 . 1 6 8 . 1 . 1 : 2 0 1 2 4 . 1 5 . 1 . 1 1 8 : 2 0 1
1 9 2 . 1 6 8 . 1 . 2 : 1 9 9 2 4 . 1 5 . 1 . 1 1 8 : 1 9 9
1 9 2 . 1 6 8 . 1 . 2 : 2 0 0 2 4 . 1 5 . 1 . 1 1 8 : 4 0 0 0 *
I S P
W A N I P
2 4 . 1 5 . 1 . 1 1 8
L A N I P
1 9 2 . 1 6 8 . 1 . 1
L A N I P
1 9 2 . 1 6 8 . 1 . 2
N A TR e q u e s t e d P o r t s
2 0 0
2 0 1
R e q u e s t e d P o r t s
1 9 9
2 0 0
R o u t e r

Security:
Firewalls: NAT Traversal
 Port Forwarding
 Port Triggering
 DMZ
 Determining WAN IP

Summary:
Topic Coverage
 Multiplayer Modes
 Protocols
 Protocol Stack
 Real-Time Communications
 Security

Summary:
Further Study
 Socket Programming
 Serial Communication
 Server Design
 Network Gear & Infrastructure
 VOIP
 Tools of the Trade
 Unit & Public Beta Testing
 Middleware
 Databases
 Web Development
 Asynchronous Programming