Box2D-Lite despite being a compact tutorial code, has a lot of sophisticated features packed into it. In this final post of this series, I delve into a technique called Warm Starting that is included in Box2D-Lite.
Another technique for improved stability
We looked at penetration slop in an earlier post as being a technique to improve stabilisation. Warm starting is another technique to improve stability by exploiting a property of typical games called "frame coherence".
Frame Coherence
Frame coherence is a measurement of how much your game scene changes across each time step. If the position and velocity of rigid bodies do not change a lot between successive time steps, then these two frames are said to exhibit high frame coherence.
Having a high frame coherence has many implications, one of the most important ones is that the constraint resolution result of the current time step will be very close to the result from the previous time step. What warm starting does it to keep the constraint solution from the previous frame and use that as the starting point for constraint resolution in the current step. This would make the entire physics system converge to the solution faster. Generally speaking, sequential impulse solvers work better with larger number of iterations. Intuitively, warm starting has the effect of increasing the number of iterations.
Implementation
For warm starting to work, we need to keep track of contact manifolds, ie Arbiters. We cannot simply clear them at the beginning of every time step and recreate them during the collision detection phase, as I have done until now.
Also, warm starting is only applied to contacts that last more than one frame. Such contacts are often referred to as “persistent contacts”.
In our implementation to date, we loop through every possible pair of bodies, and get a new contact point per collision pair every step during the collision detection phase.
The key points to implementing warm starting are:
when a contact point is detected, first determine whether that contact pair existed in the previous frame (i.e. if it is persistent)
if the detected collision pair is a persistent contact, then apply the accumulated impulse from the previous frame
if it is a new collision pair, add the contact pair to the arbiters list, and initialise it
all the "dead" collision pairs from the previous frame should be delete
But how can the above be implemented? Let's look at the Box2D code.
(C++ code)
for (int j = i + 1; j < (int)bodies.size(); ++j)
{
Body* bj = bodies[j];
if (bi->invMass == 0.0f && bj->invMass == 0.0f)
continue;
Arbiter newArb(bi, bj);
ArbiterKey key(bi, bj);
if (newArb.numContacts > 0)
{
ArbIter iter = arbiters.find(key);
if (iter == arbiters.end())
{
arbiters.insert(ArbPair(key, newArb));
}
else
{
iter->second.Update(newArb.contacts, newArb.numContacts);
}
}
else
{
arbiters.erase(key);
}
}The red highlighted code is generating the new contact pair - we are looping through every single possible body pairs, with no regard to whether there is an existing collision manifold for the pair. Assessing whether the pair is "persistent" or not comes later.
You will note that in addition to instantiating the Arbiter object, another object called ArbiterKey is instantiated. This is important.
Arbiters, Arbiter and ArbiterKey
As briefly touched on in the first post of this series, the Box2D-Lite basically adopts the following structure for the collision manifold:
Arbiters - list of arbiter objects
Arbiter - essentially the collision manifold, holding up to 2 contact point details for a pair of bodies
Contact - each contact point details are held in the Contact class
FeaturePair - this is the pair of edges that "intersects" the contact point. This is used to identify the consistency of contact points across frames
ArbiterKey - a key associated with each Arbiter - it is not unique to individual Arbiter, but unique to a particular pair of bodies
ArbIter (with capital I) is the iterator for Arbiters (not so important to understand for Javascript implementation)
In the world class, arbiters is defined as follows:
(C++ code)
std::map<ArbiterKey, Arbiter> arbiters;std::map, in C++ is what's called a sorted associative container that contains key-value pairs with unique keys. The keys are sorted.
(C++ code)
typedef map<ArbiterKey, Arbiter>::iterator ArbIter;
typedef pair<ArbiterKey, Arbiter> ArbPair;The pair consists of an ArbiterKey and an Arbiter (which is the collision manifold).
This ArbiterKey is itself a customised object which comprises body1 and body2, ie a pair of bodies. The iterator is defined as ArbIter (with the I in capital!).
(C++ code)
struct ArbiterKey
{
ArbiterKey(Body* b1, Body* b2)
{
if (b1 < b2)
{
body1 = b1; body2 = b2;
}
else
{
body1 = b2; body2 = b1;
}
}
Body* body1;
Body* body2;
};So that C++ can sort the arbiters list according to the ArbiterKey, the following is also defined.
(C++ code)
// This is used by std::set
inline bool operator < (const ArbiterKey& a1, const ArbiterKey& a2)
{
if (a1.body1 < a2.body1)
return true;
if (a1.body1 == a2.body1 && a1.body2 < a2.body2)
return true;
return false;
}Javascript implementation
There is a similar object in JS (available from ES6) called.. Map.
this.arbiters = new Map();Using this class, I have managed to implement below:
broadPhase() {
// O(n^2) broad-phase
for (let i = 0; i< this.bodies.length - 1; i++)
{
var bi = this.bodies[i];
for (let j = i+1; j < this.bodies.length; j++)
{
var bj = this.bodies[j];
if (bi.invMass == 0 && bj.invMass == 0)
{
continue;
}
var newArb = new Arbiter(bi, bj);
var key = ArbiterKey(bi, bj);
if (newArb.numContacts > 0)
{
var iter = this.arbiters.get(key);
if (iter == undefined)
{
this.arbiters.set(key, newArb);
}
else
{
iter.update(newArb.contacts, newArb.numContacts);
}
}
else
{
this.arbiters.delete(key)
}
}
}
}JS Map can accept customised objects as its key. However, given the nature of JS objects, comparisons between one object and a separately instantiated object will always return false even if all the properties are the same. As such, if you use a custom object for the key for the Map, you will not be able to perform comparisons to check for "persistence". Hence rather than create a new ArbiterKey object, I have created a ArbiterKey function that returns a primitive unique identifier based on the id's of the pair of bodies.
function ArbiterKey (b1, b2) {
//Cantor's enumeration of pairs
var x, y;
if (b1.id < b2.id)
{
x = b1.id; y = b2.id;
}
else {
x = b2.id; y = b1.id;
}
return ((x + y)*(x + y + 1)/2) + y
}Otherwise, I have tried to be faithful to the C++ implementation where I can.
Applying the old accumulated impulse
If an existing "persistent" collision pair is identified, Arbiter.update method is called with the fresh contact details and the number of contacts (for the body pair).
(C++ code)
void Arbiter::Update(Contact* newContacts, int numNewContacts)
{
Contact mergedContacts[2];
for (int i = 0; i < numNewContacts; ++i)
{
Contact* cNew = newContacts + i;
int k = -1;
for (int j = 0; j < numContacts; ++j)
{
Contact* cOld = contacts + j;
if (cNew->feature.value == cOld->feature.value)
{
k = j;
break;
}
}
if (k > -1)
{
Contact* c = mergedContacts + i;
Contact* cOld = contacts + k;
*c = *cNew;
if (World::warmStarting)
{
c->Pn = cOld->Pn;
c->Pt = cOld->Pt;
c->Pnb = cOld->Pnb;
}
else
{
c->Pn = 0.0f;
c->Pt = 0.0f;
c->Pnb = 0.0f;
}
}
else
{
mergedContacts[i] = newContacts[i];
}
}
for (int i = 0; i < numNewContacts; ++i)
contacts[i] = mergedContacts[i];
numContacts = numNewContacts;
}By the time the above method is called, there is an existing "persistent" contact (ie the same two bodies were penetrating in the previous frame). In the update method, the blue highlighted code goes onto check whether the contact points remain the same as those of the previous frame. This is effected by defining clipVertex (ie the clipped contact point) as the junction of two different edges (an edge may come from either box) and treating the combination of the edges as the "contact ID"; more specifically, value member of the FeaturePair object.
This has been translated to Javascript as follows:
update(newContacts, numNewContacts) {
let mergedContacts = [new Contact(), new Contact()];
for (let i = 0; i < numNewContacts; i++)
{
let cNew = newContacts[i]
let k = -1;
for (let j = 0; j < this.numContacts; j++)
{
const cOld = this.contacts[j]
if (cNew.feature.equals(cOld.feature)){
k = j;
break;
}
}
if (k > -1)
{
mergedContacts[i] = cNew;
let cOld = this.contacts[k];
let c = mergedContacts[i];
if (world.warmStarting)
{
c.Pn = cOld.Pn;
c.Pt = cOld.Pt;
c.Pnb = cOld.Pnb;
}
else
{
c.Pn = 0;
c.Pt = 0;
c.Pnb = 0;
}
}
else
{
mergedContacts[i] = newContacts[i];
}
}
for (let i = 0; i < numNewContacts; i++ ) {
this.contacts[i] = mergedContacts[i];
}
this.numContacts = numNewContacts;
};
Impact of warm starting
The most basic test to assess the "accuracy" of a physics engine is stacking boxes. I have ported the "pyramid" example from the original Box2D-Lite (as well as all the other samples). Running this sample in my previous port with no warm starting sees the boxes collapse after a while. However, in the below implementation with warm starting, the pyramid settles quickly and retains its pyramid shape.