Transcript Collision Response - Essential Math for Games Programmers

Collision Response
Jim Van Verth ([email protected])
Collision Response
• Physical response to collision
• Two main cases
 Colliding (opposing velocities)
• Bouncing
 Resting (orthogonal velocities)
• Rolling, sliding
Essential Math for Games
Contact Point
• Need location of point of collision and
normal to surface at actual time of
collision
• We might not have this
• Objects could be interpenetrating
Essential Math for Games
Determine Collision Time
• Do binary search
 Back off simulation half of previous time
step
• Still penetrating? Back off ¼ time step
• No collision? Move forward ¼ time step
 Continue until time step too small or exact
collision found
• Slow, may not find exact point
Essential Math for Games
Determining Collision Time
•
•
•
•
Or just fake it
Determine penetration distance
Push objects away until they just touch
Can use mass, velocities to adjust how
much each moves (if’n you feel fancy)
• Problem: can cause a new collision this
way
Essential Math for Games
Determining Collision Time
• Alternative: push apart a little, use
collision response to do the rest
• Assumes collision response can handle
penetration
• Apply force (penalty force) to push them
apart
Essential Math for Games
Determining Collision Time
• Or use predictive method to determine
time of impact (TOI)
• Integrate up to TOI
• Do collision response
• Find next TOI, integrate, respond,
repeat until done
Essential Math for Games
Determining Collision Time
• Ex: spheres
• Spheres sweep out capsules, intersect?
Essential Math for Games
Determining Collision Time
• Or: relative velocity
• Compare sphere vs. capsule
Sa
Sb
• Sphere centers Pa, Pb; radii ra, rb
• Relative velocity v = va- vb
Essential Math for Games
Determining Collision Time
• Idea: determine point(s) on velocity line
distance ra+rb from Pb
Sa
Sb
• Or: ||Pb – (Pa+vt)|| = ra+rb
• Or: (w – vt)•(w – vt) – (ra+rb)2 = 0; w = Pb – Pa
• Quadratic: solve for t
Essential Math for Games
Determining Collision Time
• Expand (w – vt)•(w – vt) – (ra+rb)2 = 0
• Get (v•v)t2 – 2(v•w)t + w•w – (ra+rb)2 = 0
• Use quadratic equation, get
Essential Math for Games
Determining Collision Time
• Could be 1 solution
 Just touching, radical = 0
• Could be no solutions
 Never touch, radical is imaginary
• Pick solution with smallest t  0,  1
Essential Math for Games
Have Collision, Will Travel
• Have normal n (from object A to object B),
collision point P, velocities va, vb
• Three cases:
 Separating
• Relative velocity along normal < 0
 Colliding
• Relative velocity along normal > 0
 Resting
• Relative velocity along normal = 0
Essential Math for Games
Linear Collision Response
• Have normal n, collision point p,
velocities v1, v2
• How to respond?
• Idea: collision is discontinuity in velocity
• Generate impulse along collision normal
– modify velocities
• How much depends on incoming
velocity, masses of objects
Essential Math for Games
Linear Collision Response
• Do simple case – two spheres a & b
 incoming velocities va,vb
 collision normal n
 want to compute impulse magnitude f
va
n
vb
Essential Math for Games
Linear Collision Response
• Compute relative velocity vab
vab
va
n
vb
Essential Math for Games
Linear Collision Response
• Compute velocity along normal
 Use dot product to project onto normal
vab
vn
n
Essential Math for Games
Linear Collision Response
• Outgoing velocity dependant on
coefficient of restitution 
or
•  = 1: pure elastic collision (superballs)
•  = 0: pure non-elastic collision (clay)
Essential Math for Games
Linear Collision Response
• Also need to conserve momentum
or
and
or
Essential Math for Games
Linear Collision Response
• Combining last two slides (with a wave
of my hand) gives
Essential Math for Games
Linear Collision Response
• Compute final velocities
va+
va-
n
vbEssential Math for Games
vb+
Angular Collision Response
• Like linear, but include angular velocity
• Compute velocity at collision point
va
b
a
ra
rb
vb
Essential Math for Games
Angular Collision Response
• Need to conserve angular momentum
or
and
or
Essential Math for Games
Angular Collision Response
• Final impulse equation (more waving of
hands)
Essential Math for Games
Angular Collision Response
• Compute new angular momentum
 remember, sim uses angular momentum
• Then angular velocity from momentum
Essential Math for Games
Multiple Colliding Contacts
• 3-body problem (kinda)
• Do one at a time, will end up with
penetration
• What to do?
Essential Math for Games
Multiple Colliding Contacts
• One solution:
 Do independently
 Handle penetration as part of collision
resolution
• Another solution:
 Generate constraint forces
 Use relaxation techniques
Essential Math for Games
Multiple Colliding Contacts
• Crunchy math solution
• Build systems of equations where
•
,
normal component of rel. vel. before &
after
• ai,j describes how body j affects impulse on
body i
• Get matrix equation:
Essential Math for Games
Multiple Colliding Contacts
• Results coupled – want “as close as
possible”
 If
 If
(separating) want close to
(colliding) want close to
• Represent difference by new vector b
 If
 If
then
then
Essential Math for Games
Multiple Colliding Contacts
• Now want to minimize length of vector
•
•
•
•
Impulses are non-positive so want
Also want
Quadratic programming problem
Can convert to Linear Complementary
Problem (LCP) – use Lemke’s Algorithm
Essential Math for Games
Resting Contacts
• Mirtich & Canny use micro-impulses,
simulate molecular micro-collisions
• Works with current impulse system
Essential Math for Games
Resting Contacts
• Impulses work, but can be kind of jittery
• Forces generate velocity into object
• Counteract in next frame – but still move a bit
g
• One solution: once close to rest, turn off sim
Essential Math for Games
Resting Contact
• Velocity along normal is 0, so look at
forces along normal
• If will push together, counteract with
new constraint force C = gn, g < 0
• Want acceleration along normal
• If will eventually push apart, want g = 0
• So want: ≤ 0, g ≤ 0, g = 0
Essential Math for Games
Resting Contact
• Can build expression for :
Essential Math for Games
Resting Contact
• Expand out, end up with expression like
•
•
•
•
•
Ag repr. acceleration due to response
b repr. acceleration due to other forces
Remember, want ≤ 0, g ≤ 0, g = 0
If b > 0, then g = -b/A, = 0
If b ≤ 0, then g = 0, = b
Essential Math for Games
Resting Contact
• Simple example: assume object on
ground, only linear forces
• If b > 0, then
 Counteracts force along normal
• If b ≤ 0, then C = 0
Essential Math for Games
Resting Contact
• Things get a lot more complicated if
both move, and angular terms
• See Eberly for the full details
Essential Math for Games
Multiple Resting Contacts
• Can have stacks of stuff
• What to do then?
Essential Math for Games
Multiple Resting Contacts
• Build systems of equations where
• Get matrix equation
where
,
,
• A is the same as with colliding contacts!
• Another LCP problem – use Lemke’s
Essential Math for Games
Resting Contacts
• Resting contact is a hard problem
• Very susceptible to floating point error,
jittering
• Don’t do more than application needs
• Don’t get discouraged
Essential Math for Games
Contact Friction
• Generate force opposed to velocity
• For contact: tangential relative velocity
• Magnitude is relative to normal force
• If using impulses, can ignore normal
force, use constant
Essential Math for Games
Putting It Together
1. Compute forces, torques on objects
2. Determine collisions
3. Adjust velocities, forces, torques
based on collision
4. Predict future collision
5. Step ahead to future collision (if any)
or fixed step (if not)
Essential Math for Games
Recap
• Try to keep objects non-penetrating
• Colliding objects get impulses
• Resting objects either micro-impulses or
constraint forces
• Multiple contacts hard, but manageable
Essential Math for Games
References
• Hecker, Chris, “Behind the Screen,” Game
Developer, Miller Freeman, San Francisco,
Dec. 1996-Jun. 1997.
• Lander, Jeff, “Graphic Content,” Game
Developer, Miller Freeman, San Francisco,
Jan., Mar., Sep. 1999.
• Witkin, Andrew, David Baraff, Michael Kass,
SIGGRAPH Course Notes, Physically Based
Modelling, SIGGRAPH 2002.
Essential Math for Games
References
• Mirtich, Brian and John Canny, “ImpulseBased Simulation of Rigid Bodies”,
Proceedings of 1995 Symposium on
Interactive 3D Graphics, April 1995.
(available online)
• Eberly, David H., Game Physics, Morgan
Kaufmann, 2004.
Essential Math for Games