Motor Physics released

100 stacking boxes at 60Hz with 30 iterations

More examples:

200 stacked boxes
polygon soup
compound shapes

So here it is – due to lack of free time I have not managed to include all planned features, but I’m working hard to include those in the next update. For now I have removed many things and tried to clean up the source a little bit. Still some parts are very messy but will be fixed in the next days, so this is more a preview than a fully functional version. I also need to setup a SVN repository, write a TODO list etc. Currently you can get the source for the preview here. The engine’s name was changed to Motor2.

The new core was written according to Erin Catto’s brilliant Box2D source. Besides many things, it features a contact graph, compound objects, a working sleeping system, restitution.., all things which I have tried to implement but the Box2D version is better and it actually works :) I recommend everyone interested in learning how to write a physics engine to look at the source.

Performance

The biggest performance gains come from efficient high-level algorithms. Most algorithms in Motor run in O(n log(n)) to O(n) in the average case, and O(n^2) in the worst case only. It’s also very important that these algorithms have an efficient low-level implementation. For Flash, this means in most situations: the fewer instructions used, the faster the code executes. This is different for the Box2D C++ version. Here memory optimizations and cache-wise design are much more important. Following are my developing guidelines:

  • precompute as much as possible
  • avoid frequent object creation/deconstruction, instead create objects once and reuse them
  • constrain function calls, inline critical parts
  • inline vector and matrix math
  • use linked lists for data structures that are constantly under modification
  • limit array access (especially nested arrays)
  • accept code duplication instead of trying to encapsulate everything
  • avoid using flash’s build in methods, e.g. the Math class
  • prefer ‘extend and override’ instead of defining interfaces (template pattern)
  • don’t cast objects often

A special word about how to deal with vector and matrix math. I haven’t defined methods for vector operations at all. I have seen many vector classes, packed with dozens of methods for performing additions, multiplications etc. This makes your code incredible slow and ugly to read, resulting in spaghetti code when concatenating many operations. Without the possibility to inline functions and overload operators I recommend to just stick with writing the expressions component-wise. (an alternative would be to use a preprocessor, which I left out to make the code more accessible)

Collisions

Because the most time in a physics simulation is spend on detecting and resolving collisions, I tried to make them as efficient as possible. I have not ported Box2D’s collision code, instead I further enhanced my existing SAT collisions. Computing the support vertex of a polygon along a given direction (aka the separation axis) is now accelerated by a BSP tree-based structure for performing extremal queries on a convex polygon [1], a O(n log(n)) search. Compared to my previous brute-force method this is about 4-6x faster. Another very important change was to include separation axis hints in a contact object – if a separation axis was found, I start the search in the next time step with the previously found axis. So when for example the AABBs of two shapes are touching, but the shapes themselves do not, you get an almost instant collision resolving.
The overall result is that it’s now 40-70% faster than my latest ‘polygon soup‘ demo. This makes it possible to simulate more than 100 stacked boxes at +60fps on a decent machine.

Broad-Phase

Motor uses a quad tree as the default broad phase, based on articles in [2] and [3]. It copes very well with varying object sizes and scene dimensions so it should be fine for a wide range of applications. Erin’s Box2D uses Sweep&Prune, which is a very attractive solution making best use of spatial and temporal coherence. The implementation looks very impressive and complex – but since I don’t want to include something I don’t fully understand I started to write a pure linked Sweep&Prune detector on my own.

Creating Shapes

motor structure shape creation

I’ve adopted Box2D’s structure for creating bodies and shapes:
A ShapeData instance defines the geometry of the shape and is responsible for computing mass, moment of inertia and the centroid. A RigidBodyData objects contains a list of ShapeData objects and in addition defines the initial state (position, velocity) of the rigid body. The RigidBodyData object is then passed to a RigidBody object, which finally creates all collision shapes from this data.

Vector representation

Polygons are stored in a data structure I call a vector chain, which is nothing more than a doubly linked circular list of 2d vectors. In addition, each vector also stores its position index and a flag indicating if it’s the last vertex in the list. So it’s something between an array and a linked list. I created this format to handle wraparounds in both directions easily and fast. You could also create an arrayed doubly linked list lookup table of vertex indices like this:

var prev:Array = [];
var next:Array = [];
for (var i:int = 0; i < k; i++)
{
	prev[i] = i - 1;
	next[i] = i + 1;
}
prev[0] = k - 1;
next[n - 1] = 0;

Retrieving the next/prev vector in the circular list can be then done this way:

//next vertex in list
v = vertexList[next[i]];
v = vertexList[prev[i]];

But nothing is simpler and faster than:

v = v.next;
v = v.prev;

Also, since everyone tends to use either plain arrays, their own custom vector classes, or the build in point class I tried to stick with plain x and y properties.

Rendering

There are two different ways to show your objects on the screen. The first and most straight-forward way is to draw all objects in world-space coordinates into one DisplayObject (you have to invoke the toWorldSpace() method on each ShapeSkeleton instance to force a WCS transform before doing so). The alternative is to draw the shape’s modeling-space outline into individual DisplayObject instances and then just update their position and rotation to get in sync with the rigid bodies. This is faster and usually the best way to draw anything else besides plain vector graphics.

The package includes a simple renderer to demonstrate how it’s done, but since rendering is not handled by the physics engine you have to write something of your own.

Coordinate spaces

Collisions are all processed in the WCS (World Coordinate System). Normally you do this by transforming object B into the local space of object A, but in the 2D case it’s easier and faster to just transform every polygon into world space and process collisions there. To avoid unnecessary transformations, they are only computed if a client requests them for rendering or the collisions need them. For example, Box-Box collisions don’t need vertices, but the Polygon-Box detector does generate vertices for both shapes.

Works cited

[1] Eberly, David in Game Physics, Morgan Kaufmann Publishers, 2004
[2] Game Programming Gems, Multi-Resolution Maps for Interaction Detection
[3] Game Programming Gems II, Direct Access Quadtree Lookup