Simple Rigid Body Physics
by
Ben Kenwright
Lots of bouncy of Cubes and Balls....well thats how it should begin....and
you'll find that 90% of all your game physics can be approximated with these
objects....for example, if we where going to do a racing car...we'd approximate
it as a box!....for a character, we'd approximate all his box parts using lots
of spheres...its simple and effective!...always keep it simple :)
Some things we've got to look at:
Work out the collision, and for each collision point we work out its
position, collision normal and its penetration distance.... We've got to add in
static and dynamic friction.... Then theres the added complexity of stacking
...I mean anyone can bounce a single cube around...but put 2 or 3 of them on top
of each other and just watch them go funny ...either sinking of jiggling out of
control with a life of there own!
Keep it simple! The best code is the simplest...we'll use the
basics that work and add in some extra tweeks to account for problems that we
notice.
Impulse based game physics are simple, math is quiet easy to understand and
implement and its usually very robust.
The two areas that usually cause problems is making objects not jiggle and
bounce making them stack and slide (friction).
Sleeping is one way to fix some things...ToDo
The algorithm at its simples is:
 Collision Detection (Store all the contact points)
 AddForces (i.e. Gravity)
 Update Velocitys (Angular & Linear)
 Apply Impulses
 Update Position & Rotation
 Loop
For the Collision Detection examples I've used Object Bounding Boxes (OBB's)
...since its much more realistic and useful than dealing with spheres....as we
can have multiple contact points for a single shape. The collision
detection code can be a bit messy, but for each collision point you need to
determine its position, normal and penetration depth....this was done using
Seperating Axis Test and a mixture of plane clipping.

The two main parts of a collision impulse are the Normal
impulse, which basically pushes the objects appart...without this, we've got
problems...they'd just penetrate each other. Next we have the Friction
impulse, which would stop our object from sliding, we in effect set a
friction threshold, so an object sitting on a steep slope wouldn't just
jiggle down the slop, alternatively it would just sit still...unless its
throw with some force to cause it to slide along the tangent slope.
One thing to notice is that the Impulse along the normal should be
pushing the objects away from each other...hence it must be >0.....else it
would be pulling them together!!! 
Relative velocity  it allows us to determine the state of each collision
point...very important when we have multiple collision points, as you'll see, we
iterate over our collision data a few times for each update to remove jitter and
stablise our values, and we can determine when and which collision points need
further updating :)
Once we know the relative velocity for a collision point
tells us the objects are approaching each other, we can apply a suitable
collision pulse which will push them apart.


Working out the normal impulse, so that the collision points velocity is
reduced to zero is just as easy as:
One great bit of extra code you'll need, is a bit of biasing code that
prevents our objects sinking! Its such a simple bit of extra code, but it
makes things so much more stable.
It uses the following facts:
 Proportional to the penetration depth
 Allow some penetration (also sometimes called slop)
 Impulse is along the normal
 Small!
One thing you'll be able to notice with the bias factor, is that for
single objects on the floor it takes a long time before sinking can
happen...and maybe for a couple of objects....but once you start stacking
cubes and having a lot more interaction, you'll notice the objects sinking
into each other more....try toggling it on and off and see :)



Added bias not makes our objects more stable...and leads to
a more robust system.
Onions!....one thing to look into is different penetration depths causing
different responses...as some of the comercial engines take do different
htings in different cases...for example, if the penetration was over a
certain threshold, you'd actually push the position of the object back along
that direction...would cause a jump of the object...but if it reached that
threshold it would be going to far into the other object..maybe even passing
through it...but you get the idea.

Friction!...you don't want your cubes to slide!. Using the basic
impulse above, this works great and is all thats needed for simple flat
worlds...but if you stack a couple of cubes, or put a cube/ball or some other
object on a slope...then it will just slide off the edge!. As we dont have
any friction! We can do this by taking the tangental direction part of the
collision and working out how much along that direction is happening...then
we'll clamp it, so it's not allowed to move along that direction unless its over
a certain threshold :)
The tangent impulse Pt, is tricky to see at
first!...basically its an impulse which will STOP any movement along the
tangent direction. So between a minimum and maximum range, there will
be no slipping!....hence Pt will counteract the tangent force to keep the
object from slipping.
The threshold is determined to be proportional to the normal impulse, so
once it passes as certain magnitude, we let it slide. 

The basic equations for impulses all rely on the principle of a single
collision point....but we're interested in Multiple collision points...for
example, a chair sitting on the floor would have an impulse for each leg...and a
cube on a plane, we'd have an impulse for the four corners. The problem is
applying an impulse to one corner rotates and shifts the object so that when we
apply it to the other corners the object is no longer correct.
Secret to making it work, it so continue to apply impulses multiple times to
our object collision points until it settles down.

 Apply an impulse at each contact point
 Continue applying impulses for fixed number of iterations

So the heart of the program code looks like this...and produces some
reasonably stable rigid body results:
Code Snippet: 
...
void
Step( float dt )
{
// Integrate Forces
for (int i=0;
i<g_numCubes; i++)
{
g_cubes[i].UpdateVel(dt);
}
// Update a few times to take into account
stacking and multiple
// contact points  applys impulse to each contact
point on the cube
for (int i=0;
i<g_numIterations; i++)
{
ApplyImpulses(dt);
}
// Finally update the new position of our cube
for (int i=0;
i<g_numCubes; i++)
{
g_cubes[i].UpdatePos( dt );
}
}
... 
I put together a simple demo that demonstrates various test
senarious using cubes...either on a plane or stacked...the performance in
release stays around 60fps with 20 boxes stacked so its not to bad...but you
can easily make it more efficient...most of the code has been kept simple so
you can follow it.
Everything in the demo is 3D Cubes....even the ground is a large thin
cube which is imovable...but it would be so easy to add in other shapes once
you get to grips with the basics...Spheresphere, spherebox, convex poly's
etc.
Download Source Code
(30k)
On the right you can see some screenshots of some test cases. 

Sleeping!
Now we can make things more stable and happy by not updating objects when
there kinetic energy level falls below a certain threshold....we meet some
certain criteria so it wakes up under certain conditions. So how do we
determine the kinetic energy of an object?....well its really quiet smart.
The energy for kinetic energy is:

We have access to all the values to calculate the kinetic
energy...but we can make it a lot more simple...as things like mass and the
moment of inertia are constant!....also, the 0.5 is constant...so we can in
effect simplify it down to:
This means that the code to caculate our rigid body motion simply
becomes:
float
motion = Dot(m_linVelocity, m_linVelocity) +
Dot(m_angVelocity, m_angVelocity);

But if you use this motion value as is, you'll find its still inefficient,
because the linear/angular velocities can jump arround a lot and are quiet
irratic at times due to the objecta all bouncing around like crazy beans.... so
we'll include some linear interpolation between the current value and the next
one...so depending upon some scalar value we pass in, depends how fast it
converges to its new value....This is sometimes called RWA  Recently Weighted
Average...but I usually just think of it as lerping.
float motion = Dot(m_linVelocity, m_linVelocity)
+
Dot(m_angVelocity, m_angVelocity);
float bias = 0.96f;
m_rwaMotion = bias*m_rwaMotion + (1bias)*motion;
The closer the bias is to 1.0f the slower it goes to the new value....so if
its 1.0f, then it would never go to the new motion value and would remain at the
old value...if we make it 0.0f, then it would immediately go the new value....
We call this function in our main update loop so its updated each frame.
Now to determine when our object sleeps or wakes up, we test the motion value
against some test epsion value:
if (m_rwaMotion < g_sleepEpsilon)
{
m_awake
= false;
m_linVelocity
= D3DXVECTOR3(0,0,0);
m_angVelocity
= D3DXVECTOR3(0,0,0);
}
else if
(m_rwaMotion > 10 * g_sleepEpsilon)
{
m_rwaMotion
= 10 * g_sleepEpsilon;
m_awake
= true;
}
If our motion is less than the epsilon value...I found 0.05 a good
value...but a bit of trial and error is good.....once an object falls alseep...it
takes a larger value to wake it up...so an object isn't sleeping and waking up
all the time...so to fix this, a wake up value of 10 times sleepEpsilon is
required.
Some additional rules need to be obeyed to keep the system working correctly
as well:
 The sleeping object must be in a collision with another sleeping object or
in collision with an object with infinite mass.
 If the sleeping object is in a collision with another object who's motion
energy is over 2 times sleepEpsilon then our object must wake up.
 The objects motion energy must be below sleepEpison to go to sleep. (Also
it must remain below this threshold for a certain time)
As a side not, I've added in the demo whether we want to start our objects
asleep or awake...for example if we start them awake, we start with an initial
motion value greater than sleepEpsilon...then it would take 56 frames for the
objects to settle down and go to sleep. But I found if your doing walls
and other stacked objects it was reasonable to assume the objects starting
asleep, since there all resting on each other.....its a bit tricker if your
objects start all mashed together in the sky...as you'd have to add an extra
check to check if groups of sleeping objects are actually in contact with a
infinite mass object...such as the ground.

Adding in sleeping, and a few more complicated test
configurations, such as domino's and stack of tables and a some random cubes
thrown around the place.
You can start with sleep enabled or disabled when the cubes start...has
the added benefit of not having to wait for stacked cubes to settle.
So you can actually notice the objects go to sleep, I've done it so that
for debug when an object goes to sleep, its alpha is set at 50%.
Using 2030 boxes the frame rate remained pretty stable...even when the
20 objects where all asleep so wern't being updated, the limiting factor is
the collision detection...so with a lot of collision detection optimisation
you could dramatically increase the number of objects to the hundreds.
Download
Source Code (31k)
Compile with Visual Studio 2005 and Directx9.1

Other things to add later on, which are for later tutorials are:
Contact point caching...so new contacts are added to a list, and we can keep
track of how old/new a contact point is
Optimize the code for multiple iterations  certain things we do when we
iterate over the impulse code can be taken out of the loop as there values
remain the same.
Better Sleep code  hundreds or thousands of rigid bodies in a world, but
only update those which aren't sleeping.
Further Reading
