Steffe.se

I recently started on a small 2D physics engine project that I for now call p2.js. It contains just the basics, spheres, particles, planes. They can interact either through frictionless contacts or spring forces.

There are a few reasons why I wanted to roll my own engine, however, the most important one for now was the question about using typed arrays or not. Now I’ve got the answer to that.
I followed Brandon Jones simple instructions on how to use the typed arrays correctly, and as one of his slides implies, I was indeed barfing rainbows when seeing the results. Okay, maybe not barfing rainbows, but I must agree that I was a bit surprised.

In total I get a performance gain of about 30% when using Float32Array instead of vector objects such as {x:2,y:1}. This number, 30%, is just a very rough estimate, because it depends on a lot of different parameters. However, my implementation made it relatively easy to switch between these. Another thing that I noticed was that switching between ordinary Arrays and Float32Array didn’t affect performance much at all, though there are a few other advantages of using the latter.

The key to using Float32Arrays is to avoid creating new ones. In the physics engine case this can get a bit tricky since there are things added and removed to the simulation in every timestep. A good example is the contacts. When two geometries collide I need a new ConactEquation instance in the engine. This is basically a holder for a number of vectors, so making a new instance every time it is needed is a no go. To solve this I made sure these objects are reused in between every timestep, and if there are excess objects, I store them for later use.

The scene you see in the image above is a simulation of 900 circles trapped in container consisting of 3 planes. The number of solver iterations is 10. I can get reasonable results by using fewer iterations too. Rendering is made in a small 2D demo renderer I built with Three.js.

I’m going to make a demo page for the engine soon, though for now only the code is available.

As I had recently implemented some graph traversing code, I was keen on using it in Cannon.js. You may think, why use graph algorithms in a physics engine? The idea is a bit tricky but I’ll try to explain.

In the usual contact solving case, we iterate over all contacts in the system. For each iteration, we transfer impulses from one body to another. In the example case of stacked boxes, iterating like this will make the top box “feel” impulses from the bottom box as the impulse travel through the stack (this depends on how many times we iterate over the system and what iteration order we use, though that’s another problem).

Many solvers have a “tolerance” parameter and it is used to check when to stop iterating. If the total error (read: contact overlap) is small, then the solution is good enough and we can stop. The tolerance is compared to the *sum* of all errors in the system.

Say we have one stack of boxes on a static plane and a sphere on the same plane. The total error will include both the errors from the stack and from the sphere. We will stop iterating over all the contacts when the total error is below the tolerance limit. Say we reach M iterations. This means we compute stuff M times on each of the N contacts in the system (a total of N*M computations).

Now what if we split the system into two independent systems, one for the stack+plane and one for the sphere+plane, and run the solver once for each of the two systems? The stack will probably still need M iterations, but the interesting thing is that the sphere will only need one. Why? Because the case of a single contact does not need to propagate impulses, and it can directly report the exact solution.

So, in the big system we need M*N computations and in the split system we need M*(N-1). That’s great! And this strategy works for many other systems too. In most cases, we can get away cheaper by using a split solver.

But what about the graph algorithm, you may say. It is used to find the independent sets in the system. Yes, it will add some complexity. However, that computation needed is not as hard as the solve part, and it has linear complexity (with respect to the number of contacts and bodies). The solving complexity depends on the number of contacts times the number of iterations. The number of iterations should be linearly dependent on the number of contacts to be able to propagate all impulses across the system, and so we end up with a quadratic solving complexity.

There is another advantage with the split solver: the subsystems can be solved in parallel. But that is another story!

The CANNON.SplitSolver class is available in the cannon.js/dev branch, and here is a live demo where you can toggle split for a scene.