Assuming you’ve read the first post in this gripping two-part tale, we’ll just get straight to the goods: how things went.

After some very brief tests, we rejected (1) methods altogether. To be fair we didn’t really give them an honest chance, as past experience with (1a) made us feel that that sort of system is great for very quickly getting something decent but simple working, but extremely difficult and time-consuming when you want to add more sophisticated features (such as angular constraints). Having said that, Alex Austin has been using an approach similar to (1b) with great success; those sorts of systems are also pretty flexible in that they can easily model deformable/destructible materials. Pun!!

So, next on the list are impulse-based methods. We implemented both (2a) and (2b); in order to avoid the complexity of collision detection, our test case was a simple chain of bodies linked together. We also wanted to see how well these methods supported “snap-together” type behaviour (i.e if we start the simulation with the bodies randomly scattered, can the solver find a solution, or does it just explode?). Here are two test cases: a limp chain, and a rigid chain (which should behave like a rod).

As you can see, the results were somewhat disappointing; while impulse-based methods are great for simulating loose objects (as demonstrated by Erin Catto’s Box2D simulator), joints just don’t behave as well — chains of bodies felt gushy and weak, and often the solver would fail to converge to a solution. There are definitely things we could have added to prevent the more extreme problems (and Catto has since revised his method so that it better deals with joints), but we didn’t really feel it was worth pursuing — things just felt fragile compared to our experiences with (1a)-type simulators. If you can screw things up just by grabbing something with a mouse and yanking, how are you ever going to avoid problems in a game?! (In hindsight the implementations may have had some bugs.. but, too late now ;). Regardless, these simulators were a great place to start learning “real” physics stuff, since they required a bit of linear algebra which we needed to re-learn, but didn’t require anything beyond a first year university text (which is good since that’s as far as either of us got!).

That brings us to the final batch of potential solutions (3). Both methods have two things in common: they were both developed by the same person (Matthias Muller, who must be some sort of genius), and neither was originally developed to simulate jointed rigid bodies — we just thought they had promise and could be adapted to suit our needs.

The first of the two (3a) is a paper that somebody really needs to base a game around; ignoring the deformable part (which has anyway been superceded by this awesome FastLSM method), it presents a method for simulating a rigid body made up of a bunch of particles. This idea isn’t new — in fact it’s the basis for the (1) methods — but the actual process presented is brilliant: instead of connecting each of the N particles to each other (which requires N*N springs) so that they move as a single solid body, you update them in two steps. First, move them in isolation from each other (i.e not considering the fact that they should remain connected to each other); then, given the final position of all of the particles, you “average” them all to generate a single rigid position+orientation for the body. Of course, the process of “averaging” these particles together requires a bit of tricky matrix math — we were finally forced to develop a working knowledge of those two complicated bastards we avoided in school, the eigenvector and eigenvalue. This was another great learning experience since we were forced to actually learn and apply some linear algebra in order to figure out how to implement this paper.

Despite the somewhat tricky matrix manipulations required, Muller’s shape-matching technique is absolutely terrific because it allows you to simulate a world made of clumps of particles, without running into the two usual problems: needing wayyy too many springs (N*N springs gets really slow as N increases) and things being too soft/squishy when you want them to be nice and rigid. This is why it’s begging to be made into a game: it lets you take a bunch of particles, lock them together rigidly, and add/remove particles however you’d like, in a very simple and straightforward way. This is custom made for a city-type world that can be blown into and/or build out of pieces!

Despite its awesomeness, it wasn’t exactly a perfect fit for what we were doing — we didn’t want or need destructible shapes, so the major benefit was lost, while at the same time things like angular constraints were (yet again) hard to figure out. You can check out our little test simulation right here.

This leaves us with the last method, good old (3b). This is actually a generalization of (1a), which is what piqued our curiosity: over the years we’ve attempted to extend Jakobsen’s method in various ways, with little success. In fact, it wouldn’t be an exaggeration to say that applying Jakobsen’s solver to other sorts of constraints is Raigan’s “Moby Dick”: since the beginning of time he’s been trying to figure out how to do it, and each year several ideas are attempted and inevitably end up just not working.

One idea that did work, however, was to use a single stick (two particles + one distance constraint) to model a 2D rigid body — rather than using a triangle as in the original paper. Many years ago we discussed this idea in a thread (on the sadly-defunct Flipcode) with a few like-minded programmers; in a bizarre twist of fate one of the contributors was none other than Jamie Cheng, who managed to develop this crazy idea into a proper method (which I think is actually what’s being used in Eets!). This is one of those terrifically weird things because years later, when he was meeting with Microsoft about Eets on XBLA, one of the producers asked if Jamie knew the people who made a game called N — this may be the first time in history that the stereotypical “do you know Bob from Canada?” situation has actually resulted in a yes! Anyway, that’s a different story for another time.

The point is, “Jakobsen + Stick-Based Rigid Bodies + SomeFantasticMagicGoesHere” was an oft-pursued, ever-elusive goal around here, which led to a few successes; aside from Jamie’s method, we also had some success implementing an alternate method of collision response (the method in (1a) only works for triangles, not for sticks) based on an obscure thesis written by Jeroen Wagenaar — who worked with Jakobsen on his method.

So after many years of off-and-on tinkering, and countless pads of graph paper, you can only imagine our speechlessness when Muller came along and published what deserves to be the most heralded game-physics paper of all time, the glorious Position Based Dynamics. In a very straightforward way he demonstrates exactly how to generalize Jakobsen’s solver to deal with any imaginable sort of constraint or mechanism.. genius!