Transcript The Basics of a Rigid Body Physics Engine

Concepts for Programming a
Rigid Body Physics Engine
Part 1
Presented by Scott Hawkins
source:
Game Physics
Engine
Development
by Ian Millington
Topics
• Mathematical Data Types
• Rigid Body Data
• Algorithm for Updating the Physics
– Finding the timestep
– Applying forces and torques
– Integration
– Collision Detection
– Collision Resolution
Mathematical Data Types
• real
– time, t
• Vector
– position, p
• Quaternion
– orientation, θ
• 3x3 Matrix
– inertial tensor, I
• 4x4 Matrix
Quaternions
• q represented using four reals, w, x, y, z:
• q = w + xi + yj + zk
• relationship between i, j, and k:
• ij = -ji = k
• jk = -kj = i
• ki = -ik = j
• ii = jj = kk = ijk = -1
Quaternion Operations
• q1 + q2 = (w1 + w2) + (x1 + x2)i +
(y1 + y2)j + (z1 + z2)k
• q1 * q2 = w1w2 - x1x2 - y1y2 - z1z2 +
(w1x2 + x1w2 + y1z2 - z1y2)i +
(w1y2 - x1z2 + y1w2 + z1x2)j +
(w1z2 + x1y2 - y1x2 + z1w2)k
Rigid Body Data
•
•
•
•
•
•
•
•
mass, m
inertia tensor, I
position, p
velocity, p’
acceleration, p”
orientation, θ
angular velocity, θ’
angular acceleration, θ”
(real)
(3x3 Matrix)
(Vector)
(Vector)
(Vector)
(Quaternion)
(Vector)
(Vector)
Rigid Body Data
•
•
•
•
•
•
force accumulator, f
torque accumulator, τ
inverse mass, m-1
inverse inertia tensor, I-1
I-1 in world coordinates
transform matrix
(Vector)
(Vector)
(real)
(3x3 Matrix)
(3x3 Matrix)
(4x4 Matrix)
Computing the Inertia Tensor, I
• I = [ Ix -Ixy -Ixz]
[-Ixy Iy -Iyz]
[-Ixz -Iyz Iz ]
• Ix = Σmi(yi2 + zi2)
• Iy = Σmi(xi2 + zi2)
• Iz = Σmi(xi2 + yi2)
• Ixy = Σmixiyi
• Iyz = Σmiyizi
• Ixz = Σmixizi
Meaning of Orientation, θ
• θ is of the form:
• θ = cos(θ / 2) +
nxsin(θ / 2)i +
nysin(θ / 2)j +
nzsin(θ / 2)k
• θ represents a rotation by angle θ about a
vector axis n.
• If θ is zero, the object is not rotated, and
• θ = 1 + 0i + 0j + 0k
Meaning of Angular Velocity, θ’
• θ’ is of the form:
• θ’ = nxωi + nyωj + nzωk
• This is called “axis-angle” form.
• θ’ represents an angular rate of ω about a
vector axis n.
• Angular acceleration is also in axis-angle
form.
Computing the Transform Matrix
• Useful for transforming geometry from
local coordinates into world coordinates
M = [2θx2+2θw2-1
[2θxθy-2θzθw
[2θxθz+2θyθw
[
0
2θxθy+2θzθw
2θy2+2θw2-1
2θyθz-2θxθw
0
2θxθz-2θyθw
2θyθz+2θxθw
2θz2+2θw2-1
0
px]
py]
p z]
1]
Updating the Physics
•
•
•
•
•
Find the timestep Δt
Apply forces and torques
Integrate
Collision detection
Collision resolution
Computing Δt
• Remember the clock value for the
previous frame
• Δt = tcurrent - tprevious
Adding Forces and Torques
• Force and Torque Generators
– in C++, use classes with virtual methods
– in Java, use interfaces
– user implements updateForce() or
updateTorque() method
• All force and torque generators should be
registered before the frame begins
Adding Forces and Torques
• p” = m-1f
• θ” = I-1τ = I-1[(ppoint - p) x f]
Adding Forces and Torques
• Call the updateForce() or updateTorque()
method for every registered force or
torque generator
• These add to the force and torque
accumulators in the rigid bodies
• f = Σfi
• τ = Στi
Integration
•
•
•
•
•
p” = m-1f
θ” = I-1τ
pnext = p + p’Δt
p’next = p’ + p”Δt
θnext = θ + (Δt/2)ωθ
• ω = 0 + θ’x i + θ’y j + θ’z k
• θ’next = θ’ + θ”Δt
Integration
• Use Newton’s second law to get p” and θ”
• f = mp”
• p” = f / m
• p” = m-1f
• τ = Iθ”
• θ” = I-1τ
Integration
• Use the explicit version of Euler’s method
to integrate position and velocity
• pnext = p + p’Δt
• p’next = p’ + p”Δt
Integration
• Also use explicit Euler’s method for
orientation and angular velocity
• θnext = θ + (Δt/2)ωθ
• ω = 0 + θ’x i + θ’y j + θ’z k
• why it works: magic?
• θ’next = θ’ + θ”Δt
Collision Detection
• Return a list of contacts
• Each contact consists of
– references to the two rigid bodies
– contact point in world coordinates, q
– contact normal in world coordinates, n
– penetration depth, d
– coefficient of restituion, c
– coefficient of friction, μ
(Vector)
(Vector)
(real)
(real)
(real)
Collision Detection
• Implementation is very complicated
• Two phases:
– Coarse Collision Detection
– Fine Collision Detection
Collision Detection
• Use spatial data structures to perform coarse
collision detection
• Examples of spatial data structures:
–
–
–
–
–
bounding volume hierarchy
binary space partitioning tree
quad-tree
oct-tree
grids
• Coarse collision detection eliminates pairs of
objects that could not possibly be in contact
Collision Detection
• Run fine collision detection on the
remaining pairs of objects
• Fine collision detection generates the list
of contacts
• For polygon meshes, two types of contacts
must be checked:
– point-face contacts
– edge-edge contacts