Transcript CSCE 590E Spring 2007 - Computer Science & Engineering

CSCE 590E Spring 2007
Collision Detection
By Jijun Tang
Announcements



Final game demo will be held at 2:00pm,
Tuesday, May 8th
Homework 4 will be given today
Second presentation will be held on April
16th and 18th


April 16th: Space Banditos, Slackers, Psychosoft
April 18th: Project Gnosis, Cheeze Puffs!, Team
Swampus
Needs to do



Two groups need to send me the first
presentation after the class
Some people didn’t send me the
members in their small project.
Please send the membership of the
small project to [email protected]
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
Difficult




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
Engines

Commercial




Game Dynamics SDK (Havok.com)
Renderware Physics (renderware.com)
NovodeX SDK (novodex.com)
Free



Open Dynamic Engine (ODE) (ode.org)
Tokamak Game Physics SDK
(tokamakphysics.com)
Newton Game Dynamics SDK
(newtondynamics.com)
Particle Physics

What is a Particle?



A sphere of finite radius with a perfectly smooth,
frictionless surface
Experiences no rotational motion (or assume the
sphere has no size)
Particle Kinematics


Defines the basic properties of particle motion
Position, Velocity, Acceleration
Particle Position
Location of Particle in World Space

SI Units: meters (m)
p  px , p y , pz
p(
t)


+
p(t
t)
Changes over time when object moves
Particle Velocity and
Acceleration

Velocity (SI units: m/s)

First time derivative of position:
p(t  t )  p(t ) d
V (t )  lim
 p(t )
t 0
t
dt

Acceleration (SI units: m/s2)


First time derivative of velocity
Second time derivative of position
d
d2
a(t )  V(t )  2 p(t )
dt
dt
Newton’s 2nd Law of Motion


Paraphrased – “An object’s change in
velocity is proportional to an applied force”
The Classic Equation:
Ft   mat 


m = mass (SI units: kilograms, kg)
F(t) = force (SI units: Newtons)
What is Physics Simulation?

The Cycle of Motion:




Force, F(t), causes acceleration
Acceleration, a(t), causes a change in velocity
Velocity, V(t) causes a change in position
Physics Simulation:

Solving variations of the above equations over
time to emulate the cycle of motion
Concrete Example: Target
Practice
V
ini
t
Projectile Launch
Position, pinit
Target
F = weight = mg
Target Practice

Choose Vinit to Hit a Stationary Target



ptarget is the stationary target location
We would like to choose the initial velocity, Vinit,
required to hit the target at some future time, thit.
Here is our equation of motion at time thit:
1
2
p target  p init  Vinit t hit  t init   gt hit  t init 
2



Solution in general is a bit tedious to derive…
Infinite number of solutions!
Hint: Specify the magnitude of Vinit, solve for its
direction
Example 1
Vinit = 25 m/s
Value of Radicand of tanf equation: 969.31
Launch angle f: 19.4 deg or 70.6 deg
45.00
Vertical Position (m)
40.00
35.00
Projectile Launch
Position
Target Position
30.00
25.00
Trajectory 1 - High
Angle, Slow Arrival
Trajectory 2 - Low
Angle, Fast Arrival
20.00
15.00
10.00
5.00
0.00
0.00
20.00
40.00
Horizontal Position (m)
60.00
Finite Difference Methods

The Explicit Euler Integrator:
d

St  t   S
t   t
St   O ( t 2 )



dt

prior state
new state
state derivative




Properties of object are stored in a state vector, S
Use the above integrator equation to incrementally update S
over time as game progresses
Must keep track of prior value of S in order to compute the
new
For Explicit Euler, one choice of state and state derivative for
particle:
S  mV, p
dS dt  F, V
Finite Difference Methods

The Verlet Integrator:
 d2

 2 S(t ) 






St  t   2 S
t

S
t


t


t







dt
prior state1
new state
prior state 2

2
state derivative




Must store state at two prior time steps, S(t) and S(t-t)
Uses second derivative of state instead of the first
Valid for constant time step only (as shown above)
For Verlet, choice of state and state derivative for a particle:
S p
2
d S dt  F / m  a
2
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
Additional forces





Linear Spring
Viscous Damping
Aerodynamic Drag
Friction
…
Linear Springs
Fspring  k (l  lrest )d
Viscous Damping
Fdamping  c((Vep 2  Vep1 )  d )d
Aerodynamic Drag
S: projected front area
CD: drag coefficient
Friction
Collision Detection and Resolution
What is Collision Detection


A fundamental problem in computer
games, computer animation,
physically-based modeling, geometric
modeling, and robotics.
Including algorithms:


To check for collision, i.e. intersection, of
two given objects
To calculate trajectories, impact times
and impact points in a physical simulation.
Collision Detection

Complicated for two reasons



Geometry is typically very complex, potentially
requiring expensive testing
Naïve solution is O(n2) time complexity, since
every object can potentially collide with every
other object
Two basic techniques


Overlap testing: Detects whether a collision has
already occurred
Intersection testing: Predicts whether a collision
will occur in the future
Overlap Testing (a posteriori)


Overlap testing: Detects whether a collision
has already occurred, sometime is referred
as a posteriori
Facts



Most common technique used in games
Exhibits more error than intersection testing
Concept


For every (small) simulation step, test every pair
of objects to see if they overlap
Easy for simple volumes like spheres, harder for
polygonal models
Overlap Testing Results

Useful results of detected collision




Pairs of objects will have collision
Time of collision to take place
Collision normal vector
Collision time calculated by moving
object back in time until right before
collision

Bisection is an effective technique
Bisect Testing: collision
detected
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
Bisect Testing: Iteration I
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
Bisect Testing: Iteration II
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
Bisect Testing: Iteration III
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
Bisect Testing: Iteration IV
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
Bisect Testing: Iteration V
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
Time right before the collision
Overlap Testing: Limitations

Fails with objects that move too fast
(compared to the object)


Thin glass vs. bulltes
Unlikely to catch time slice during overlap
window
t-1
bullet
t0
t1
t2
Solution for This Limitation


Speed of the fastest object multiplies
the time step should be smaller than
the smallest objects in the scene
Possible solutions

Design constraint on speed of objects


Hard to apply without affecting the play
Reduce simulation step size

Too expensive
Intersection Testing (a priori)


Predict future collisions
When predicted:



Move simulation to time of collision
Resolve collision
Simulate remaining time step
Intersection Testing:
Swept Geometry


Extrude geometry in direction of movement
Swept sphere turns into a “capsule” shape
t0
t1
Intersection Testing:
Sphere-Sphere Collision
t
A  B2  B2 Α2  rP  rQ 2 
 Α  Β  
B
2
A  P1  Q1
B  P2  P1   Q 2  Q1 .
,
Q2
t=1
P1
d
t=0
P
t
Q
Q1
t=0
P2
t=1
Special Cases

No collision:




 B Α  rP  rQ   0
B2 = 0: both objects are stationary,
or they are traveling at parallel
When will collision occur?
A  B
2
2
2
2
A  B2  B2 Α2  rP  rQ 2   0
Intersection Testing:
Sphere-Sphere Collision


Smallest distance ever separating two
spheres:
2

A  B
2
2
d A 
2
B
If d 2  rP  rQ 2
there is a collision
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
Dealing with Complexity
Two issues
1. Complex geometry must be simplified
2. Reduce number of object pair tests
Simplified Geometry

Approximate complex objects with
simpler geometry, like this ellipsoid or
bounding boxes
Minkowski Sum

By taking the Minkowski Sum of two
complex volumes and creating a new
volume, overlap can be found by
testing if a single point is within the
new volume
Minkowski Sum
X  Y  { A  B : A  X and B  Y}
X

Y
=
XY
=
XY
Using Minkowski Sum
t1
t0
t1
t0
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
Box Bounding Volumes
Axis-Aligned Bounding Box
Oriented Bounding Box
More Examples
Using Bounding Box in Game

Complex objects can have multiple
bounding boxes



Human object can have one big bounding box
for the whole body
Human object can have one bounding box per
limb, head, etc
Bounding box can be hierarchical:


Test the big first
if possible collision, test the smaller ones
Reduce Number of Detections
O(n) Time Complexity can be achieved.
One solution is to partition space
Achieving O(n) Time
Complexity
Another solution is the plane sweep algorithm
Requires
y (re-)sorting in x (y) coordinate
B1
A1
R1
B
A
B0
R
A0
C1
R0
C
C0
A0
A1 R0
B0 R1 C0 B1
C1
x
Terrain Collision Detection:
Height Field Landscape
T op-Down View
T op-Down View (heights added)
Perspective View
Perspective View (heights added)
Locate Triangle on Height
Field
Essentially a 2D problem
z
Q
Q
R
R
x
Qz > Qx
Rz > 1 - Rx
Qz <= Qx
Rz <= 1 - Rx
Locate Point on Triangle




Plane equation: Ax  By  Cz  D  0
A, B, C are the x, y, z components of
the triangle plane’s normal vector
Where D  N  P0
with one of the triangles
vertices being P0
Giving: N x x   N y  y   N z z    N  P0   0
Terrain Collision Detection:
Locate Point on Triangle

The normal can be constructed by taking the
cross product of two sides:
N  P1  P0   P2  P0 

Solve for y and insert the x and z
components of Q, giving the final equation
for point within triangle:
 N x Q x  N z Q z  N  P0 
Qy 
Ny
Treating Nonuniform Polygon
Mesh



Hard to detect the triangle where the
point lies in
Using Triangulated Irregular Networks
(TINs)
Barycentric Coordinates
Barycentric Coordinates


Even with complex data structure, we
still have to test each triangle (in a sub
region) to see if the point lies in it
Using Barycentric Coordinates to do
the test
P2
Point = w0P0 + w1P1 + w2P2
Q
R
P1
P0
Q = (0)P0 + (0.5)P1 + (0.5)P2
R = (0.33)P0 + (0.33)P1 + (0.33)P2
Terrain Collision Detection:
Locate Point on Triangle

Calculate barycentric coordinates for point
Q in a triangle’s plane
 w1 
1

w 
2
2 2
 2  V1 V2  V1  V2 
 V22

 V1  V2
 V1  V2   S  V1 


V12  S  V2 
S  Q  P0
V1  P1  P0
V2  P2  P0
w0  1  w1  w2

If any of the weights (w0, w1, w2) are
negative, then the point Q does not lie in
the triangle
Collision Resolution:
Examples

Two billiard balls strike




Rocket slams into wall




Calculate ball positions at time of impact
Impart new velocities on balls
Play “clinking” sound effect
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
Collision Resolution:
Parts

Resolution has three parts
1. Prologue
2. Collision
3. Epilogue
Prologue



Collision known to have occurred
Check if collision should be ignored
Other events might be triggered


Sound effects
Send collision notification messages
Collision


Place objects at point of impact
Assign new velocities


Using physics or
Using some other decision logic
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
Collision Resolution:
Resolving Overlap Testing
1. Extract collision normal
2. Extract penetration depth
3. Move the two objects apart
4. Compute new velocities
Extract Collision Normal


Find position of objects before impact
Use two closest points to construct the
collision normal vector
Extract Collision Normal for
Sphere Collision

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
Depth

Gilbert-Johnson-keerthi (GJK)
bisection to extract the depth of
convex objects
Minkowski supporting lines
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
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
Approach 2: Gradual change of velocity and position over
time, following collision
Approach 1

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
Approaches 2

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
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


Implicit finite difference equations can handle it


Instabilities galore
But more difficult to code
Geometric approach: Ignore physical response equations

Enforce purely geometric constraints once interpenetration
has occurred
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
See text for details on how to get started
Final Comments

Full-Up Simulation


The text and this presentation just barely touch the surface
Additional considerations









Multiple simultaneous collision points
Articulating rigid body chains, with joints
Friction, rolling friction, friction during collision
Mechanically applied forces (motors, etc.)
Resting contact/stacking
Breakable objects
Soft bodies
Smoke, clouds, and other gases
Water, oil, and other fluids
Homework 4


Page 390 problem 1 and 5
Handwriting or printing using
Word/Latex




Turn in before class
No need to upload to dropbox
5 points total (2.5 each)
Due on this Wednesday