Robotology, the end of the end of the beginning of the story thus far.

12 Jul / by: M&R / 9 comments /

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!

comments ( 9 )

  • Hehe, reading along is fun. 🙂

    I’ve briefly gone through Mueller’s paper, but I have yet to deciphered the awesome (like when you realize verlet can do rotations by solving collisions against one point in the body, or verlet spring constraints don’t explode). There’s certainly enough greek and single letter variables that I can’t help but roll my eyes at, despite the article being a heck of a lot more approachable than most. Alas, I’ll probably give it another go after some sleep. The balloons idea intrigues me. I love how they seem to inflate the character in Figure 7. 🙂

    Jamie’s paper is neat. I seem to forget that every time I hand out Jakobsen’s paper, I neglect that it doesn’t detail much more than the particle aspect of verlet, and basic particle constraints. Nothing like “this is how you use this in a game”. I have to remember to hand that one out too, though I probably suggest a few small changes. Like using the normalized vector between the points on the “stick” to directly construct a rotation matrix (co-ordinate space equivalent of [n.x n.y][-n.y n.x]), instead of “acos” and the “CreateRotationMatrix” mystery function, that probably wastes it’s time calling “sin” and “cos”. Though, I don’t think either way is technically clearer.

    More! More madness! 😀

  • All this theoretical stuff is making my brain hurt, where are the pictures 😛

  • […] The folks at N creator Metanet Software have been posting some absolutely fascinating, uber-technical blog pieces recently, and the latest is an in-depth look at creating the physics for their upcoming title Robotology, posted in two parts. […]

  • Thanks for writing this all out! It’s definitely a ‘fun and informative’ read 😀

  • Some days I really need to read/hear someone very very excited about something esoteric enough that digging past the surface level makes my eyes bleed. For days like that, Canada gave us Raigan and Mare.


    i swear you could turn that into a somewhat fun game of skip rope.

    oh wait.. only girls play skip rope.. nevermind. :p

    seriously, i dont fully understand everything you talk about, but its truly fascinating just the same.

    i’ve read every post you guy’s have written up to this point, and i’ve got to say, robotology is going to seriously kick ass…

    i cant wait to keep reading and see what else you guys have explored whilst making this game!

    this blog is really doing a great service to anyone who reads it. what a GREAT resource for aspiring flash/game designers and programmers.

    although personally i gave up my aspirations for such things long ago… but that wont stop me from spending hours toying around with the more user-friendly level editors.

  • I am “Muller” and was very flattered by what you wrote about me being a “genius” 🙂 That was slightly exaggerated though 🙂 Sorry for making some people’s brains hurt but without the greek symbols there is no way to get a paper accepted at any conference 🙂 Also some math is required to handle general constraints.

  • Seriously, I had tried over _several_ years to get a simple angle-constraint working with Jakobsen’s method, to no avail! So thanks for explaining how it _should_ be done 🙂

  • Hi, can you elaborate further on Stick-Based Rigid Bodies via PBD? For instance, how do you conserve angular momentum and properly deal with Friction and Restitution? Also, does PBD enable stable stacking?


Leave a reply