Transcript Computer Game Physics

Computer Game Physics
CIS 487/587
Bruce R. Maxim
UM-Dearborn
1
Game Physics
• Not trying to build a perfect physical model
• Most things can be approximated assuming
Newtonian physics and rigid bodies
• Use discrete simulation (constant step)
techniques
• Just worry about center of mass for most
things
2
The next 6 slides come from
the Rabin text
3
Why Physics?
• The Human Experience
– Real-world motions are physically-based
– Physics can make simulated game worlds appear
more natural
– Makes sense to strive for physically-realistic
motion for some types of games
• Emergent Behavior
– Physics simulation can enable a richer gaming
experience
4
Why Physics?
• Developer/Publisher Cost Savings
– Classic approaches to creating realistic motion:
• Artist-created keyframe animations
• Motion capture
• Both are labor intensive and expensive
– Physics simulation:
• Motion generated by algorithm
• Theoretically requires only minimal artist input
• Potential to substantially reduce content development
cost
5
High-level Decisions
• Physics in Digital Content Creation Software:
– Many DCC modeling tools provide physics
– Export physics-engine-generated animation as
keyframe data
– Enables incorporation of physics into game
engines that do not support real-time physics
– Straightforward update of existing asset creation
pipelines
– Does not provide player with the same emergentbehavior-rich game experience
– Does not provide full cost savings to
developer/publisher
6
High-level Decisions
• Real-time Physics in Game at Runtime:
– Enables the emergent behavior that provides
player a richer game experience
– Potential to provide full cost savings to
developer/publisher
– May require significant upgrade of game engine
– May require significant update of asset creation
pipelines
– May require special training for modelers,
animators, and level designers
– Licensing an existing engine may significantly
increase third party middleware costs
7
High-level Decisions
• License vs. Build Physics Engine:
– License middleware physics engine
•
•
•
•
Complete solution from day 1
Proven, robust code base (in theory)
Most offer some integration with DCC tools
Features are always a tradeoff
8
High-level Decisions
• License vs. Build Physics Engine:
– Build physics engine in-house
•
•
•
•
•
Choose only the features you need
Opportunity for more game-specific optimizations
Greater opportunity to innovate
Cost can be easily be much greater
No asset pipeline at start of development
9
Position and Velocity
• Where is object at time t (using pixels)?
• Equations
player_x(t) = t * x_velocity + x_initial
player_y(t) = t * y_velocity + y_initial
• Computation
player_x = player_x + x_velocity
player_y = player_y + y_velocity
10
Acceleration
• Computation
x_velocity = x_velocity + x_acceleration
y_velocity = y_velocity + y_acceleration
• Use piecewise linear approximation
to continuous functions
11
Gravity
• Force of attraction between objects
F = G * (M1 * M2) / D2
G = gravitational constant
D = distance between objects
• Free falling objects on Earth
– Equation
V(t) = 1/2 * g * t2
g = 9.8 m/sec2
– Computation
x_velocity = x_velocity + 0
y_velocity = y_velocity + gravity
12
Projectile Motion
•
•
•
•
•
•
X = x + Vx + W
Y = y + Vy
Vxi = cos(A) * Vi
Vyi = sin(A) * Vi
Vx = Vx - WR(Vx)
Vy - WR(Vy) + G
•
•
•
•
W = wind
A = inclination angle
Vi = initial velocity
WR = wind
resistance
• G = gravity
13
Friction
• Conversion of kinetic energy into heat
• Equation
– Frictional Force = C * G * M
• C = force required to maintain constant speed
• G = gravity
• M = mass
• Computation
while (velocity > 0)
velocity = velocity - friction
14
The next 21 slides come from
the Rabin text
15
Collision Detection
Complicated for two reasons
1. Geometry is typically very complex,
potentially requiring expensive testing
2. Naïve solution is O(n2) time complexity,
since every object can potentially collide
with every other object
16
Collision Detection
Two basic techniques
1. Overlap testing
• Detects whether a collision has already
occurred
2. Intersection testing
• Predicts whether a collision will occur in the
future
Overlap Testing
• Facts
– Most common technique used in games
– Exhibits more error than intersection
testing
• Concept
– For every simulation step, test every pair of
objects to see if they overlap
– Easy for simple volumes like spheres,
harder for polygonal models
18
Overlap Testing:
Useful Results
• Useful results of detected collision
– Time collision took place
– Collision normal vector
19
Overlap Testing:
Collision Time
• Collision time calculated by moving object
back in time until right before collision
– Bisection is an effective technique
A
t0
A
t0.25
A
A
A
t0.375
A
t0.40625
t0.4375
t0.5
t1
B
Initial Overlap
Test
B
B
Iteration 1
Forward 1/2
Iteration 2
Backward 1/4
B
B
Iteration 3
Forward 1/8
Iteration 4
Forward 1/16
B
Iteration 5
Backward 1/32
20
Overlap Testing:
Limitations
• Fails with objects that move too fast
– Unlikely to catch time slice during overlap
• Possible solutions
– Design constraint on speed of objects
– Reduce simulation step size
window
t-1
t0
t1
t2
bullet
21
Intersection Testing
• Predict future collisions
• When predicted:
– Move simulation to time of collision
– Resolve collision
– Simulate remaining time step
22
Intersection Testing:
Swept Geometry
• Extrude geometry in direction of movement
• Swept sphere turns into a “capsule” shape
t0
t1
23
Intersection Testing:
Sphere-Sphere Collision
t
 Α  Β  
A  B 2  B 2 Α 2  rP  rQ 2 
B
2
A  P1  Q1
B  P2  P1   Q 2  Q1 .
,
Q2
t=1
P1
t=0
P
t
Q
P2
t=1
Q1
t=0
24
Intersection Testing:
Sphere-Sphere Collision
• Smallest distance ever separating two
spheres:
2

A  B
2
2
d A 
2
B
2
2
• If


d  rP  rQ
there is a collision
25
Intersection Testing:
Limitations
• Issue with networked games
– Future predictions rely on exact state of world at
present time
– Due to packet latency, current state not always
coherent
• Assumes constant velocity and zero
acceleration over simulation step
– Has implications for physics model and choice of
integrator
26
Dealing with Complexity
Two issues
1. Complex geometry must be simplified
2. Reduce number of object pair tests
27
Dealing with Complexity:
Simplified Geometry
• Approximate complex objects with
simpler geometry, like this ellipsoid
28
Dealing with Complexity:
Bounding Volumes
• Bounding volume is a simple geometric
shape
– Completely encapsulates object
– If no collision with bounding volume, no
more testing is required
• Common bounding volumes
– Sphere
– Box
29
Dealing with Complexity:
Box Bounding Volumes
Axis-Aligned Bounding Box
Oriented Bounding Box
30
Dealing with Complexity:
Achieving O(n) Time Complexity
One solution is to partition space
31
Collision Resolution:
Examples
• Two billiard balls strike
– Calculate ball positions at time of impact
– Impart new velocities on balls
– Play “clinking” sound effect
• Rocket slams into wall
– Rocket disappears
– Explosion spawned and explosion sound effect
– Wall charred and area damage inflicted on nearby
characters
• Character walks through wall
– Magical sound effect triggered
– No trajectories or velocities affected
32
Collision Resolution:
Parts
• Resolution has three parts
1. Prologue
2. Collision
3. Epilogue
33
Collision Resolution:
Prologue
• Collision known to have occurred
• Check if collision should be ignored
• Other events might be triggered
– Sound effects
– Send collision notification messages
34
Collision Resolution:
Collision
• Place objects at point of impact
• Assign new velocities
– Using physics or
– Using some other decision logic
35
Collision Resolution:
Epilogue
• Propagate post-collision effects
• Possible effects
– Destroy one or both objects
– Play sound effect
– Inflict damage
• Many effects can be done either in the
prologue or epilogue
36
Collision Resolution:
Resolving Overlap Testing
1. Extract collision normal
2. Extract penetration depth
3. Move the two objects apart
4. Compute new velocities
37
Collision Resolution:
Extract Collision Normal
• Find position of objects before impact
• Use two closest points to construct the
collision normal vector
38
Collision Resolution:
Extract Collision Normal
• Sphere collision normal vector
– Difference between centers at point of collision
t0
t0.25
t0.5
t0.75
t0
t1
t0.25
Co
No llisio
rm n
al
t0.5
t0.75
t1
39
Collision Resolution:
Resolving Intersection Testing
• Simpler than resolving overlap testing
– No need to find penetration depth or move
objects apart
• Simply
1. Extract collision normal
2. Compute new velocities
40
Simple Collision Handling
• Detect that collision has occurred
(bounding box)
• Determine the time of the collision
(may need to back up to point of collision)
• Determine where objects are when they touch
• Determine the collision normal
(angle of incidence = angle of reflection)
• Determine the velocity vectors after the collision
• Determine any changes in motion
41
Simple Kinematics
P(x, y)
• Forward kinematic
problem
– find position of P from
theta1, theta2, L1, L2
– use the 2D translation
and rotation matrices
– (TL2*Rtheta2)* (TL1*Rtheta1)
– generalizes to any
number of links
L2
theta2
L1
theta1
42
Particle System Explosions
• Start with lots of small objects (1 to 4 pixels)
• Initialize particles with random velocities
based on velocity of exploding object
• Apply gravity
• Transform color intensity as a function of time
• Destroy objects when they collide or after a
fixed amount of time
43
The next 7 slides come from
the Rabin text
44
Generalized Rigid Bodies
• Key Differences from Particles
– Not necessarily spherical in shape
– Position, p, represents object’s center-of-mass location
– Surface may not be perfectly smooth
• Friction forces may be present
– Experience rotational motion in addition to translational
(position only) motion
Z world
X world
Z object
X object
Center of Mass
45
Generalized Rigid Bodies –
Simulation
• Angular Kinematics
– Orientation, 3x3 matrix R or quaternion, q
– Angular velocity, w
– As with translational/particle kinematics, all properties are
measured in world coordinates
• Additional Object Properties
– Inertia tensor, J
– Center-of-mass
• Additional State Properties for Simulation
– Orientation
– Angular momentum, L=Jw
– Corresponding state derivatives
46
Generalized Rigid Bodies Simulation
• Torque
– Analogous to a force
– Causes rotational acceleration
• Cause a change in angular momentum
– Torque is the result of a force (friction, collision response,
spring, damper, etc.)
F
r
P
=r F
= Center-of-Mass
47
Collision Response
• Why?
– Performed to keep objects from interpenetrating
– To ensure behavior similar to real-world objects
• Two Basic Approaches
– Approach 1: Instantaneous change of velocity at time of
collision
• Benefits:
– Visually the objects never interpenetrate
– Result is generated via closed-form equations, and is perfectly
stable
• Difficulties:
– Precise detection of time and location of collision can be
prohibitively expensive (frame rate killer)
– Logic to manage state is complex
48
Collision Response
• Two Basic Approaches (continued)
– Approach 2: Gradual change of velocity and position over
time, following collision
• Benefits
– Does not require precise detection of time and location of collision
– State management is easy
– Potential to be more realistic, if meshes are adjusted to deform
according to predicted interpenetration
• Difficulties
– Object interpenetration is likely, and parameters must be tweaked
to manage this
– Simulation can be subject to numerical instabilities, often requiring
the use of implicit finite difference methods
49
Final Comments
• Instantaneous Collision Response
– Classical approach: Impulse-momentum equations
• See text for full details
• Gradual Collision Response
– Classical approach: Penalty force methods
• Resolve interpenetration over the course of a few integration
steps
• Penalty forces can wreak havoc on numerical integration
– Instabilities galore
• Implicit finite difference equations can handle it
– But more difficult to code
– Geometric approach: Ignore physical response equations
• Enforce purely geometric constraints once interpenetration has
occurred
50
Final Comments
• Simple Games
– Closed-form particle equations may be all you
need
– Numerical particle simulation adds flexibility
without much coding effort
– Collision detection is probably the most difficult
part of this
• Generalized Rigid Body Simulation
– Includes rotational effects and interesting (nonconstant) forces
51
Time-Based Modeling
• Time t is used in all kinematic equations that
move objects (to avoid discontinuities caused
by “slower” frame rates)
• This involves scaling dx and dy based on
elapsed time (rather than a virtual clock)
• This allow constant movement regardless of
processor slow downs
52