Apologies for the continued infrequency of posting, it’s been non-stop deadlines for the past several weeks. woooooo! exhausting. By mid-September we should be able to move N+ work to part-time and return to Robotology in earnest.. finally! Writing this post is somewhat frustrating as it just serves as a reminder of what we should have spent the summer doing — there are so many interesting Robotology-related things we’d rather be working on right now..

Anyway, to continue where we left off: our simulator is based on this paper (by Matthias Muller), which is in turn an improvement of the method presented in this paper (by Thomas Jakobsen), which is what we used in N for the player’s movement and ragdoll.

While the Muller paper presents the solver in the context of cloth (and other soft/deformable) modeling, we’ve found a fairly straightforward way to apply it to 2D rigid bodies; we definitely plan on releasing some tutorials to cover the technical details, much as we did with N, because this method is magical in both simplicity and power. (Sadly this won’t be for many months, as we’d like to get Robotology off the ground before starting any new projects.. alas.)

And so we present to you: MetaPhysics! (at least, until we can think of a more clever and/or sillier name)

You may notice that the demos are rather soft-/spongy-feeling; the constraints are pretty easy to violate. This is the case for two reasons: we’re only using 4 constraint iterations (more on this later), and we’re allowing the user to interact with the bodies directly via an infinitely heavy mouse (rather than using a more well-behaved solution which would prevent you from really screwing things up). One exception is the second demo, which is identical to the first scene but uses 32 iterations.. resulting in a much more stiff or solid-feeling chain. So, if more stiffness is required it’s just a simple matter of upping the iterations.

We decided to leave things at 4 iterations because it demonstrates the best properties of this solver: stability and convergence. Most rigid-body constraint solvers require a far higher number of iterations to converge on a solution, and (worse) can fail miserably if the iteration count is too low, or if the system is unsolveable — as can be the case when you’re pulling things around with the mouse. In contrast, our solver will converge no matter what — at least, we haven’t been able to break it yet! You can violently drag and shake the boxes around as much as you like, but the solver will always pull them back together. Nice! We’re not quite mathy enough to properly prove guaranteed convergence, but it’s much more solid-feeling than anything else we’ve made.

We tried to show a good assortment of constraint-types, from simple joint/pin constraints, to joints with limits on how much the boxes can rotate with respect to each other, to rigid “weld” constraints which lock two bodies together, to “slider” constraints. As well, we’ve included both tree-type and looping mechanisms. A really nice property of this solver is that it’s quite simple to define any sort of constraint imaginable — as long as you can describe it as an equation, you can solve it.

Calling it a “simulator” is somewhat misleading as it barely has any dynamics-related code in it — it would more properly be called a “geometric constraint solver”. In fact, if you disable the integration step (which moves the system forward in time, updating velocities based on accelerations, and positions based on velocities) you can use the solver as a really awesome IK solution.

The illusion of physics is achieved (as in the two papers linked above) by using a backwards difference on the positions to approximate velocity, also known as the ubiquitous Verlet integration. This method is really pretty neat — instead of having to track position and velocity separately, you simply look at the vector from the previous position to the current position, and use that as the current velocity. This sort of little mathematical trick is simple, clever, and quite useful — you can apply it anywhere you have a value that’s changing over time.

At a very high level, the simulator works in a pretty simple way: you start by defining a bunch of bodies, and a bunch of constraints between the bodies. These constraints are simply formulas which relate the position and/or orientation of the bodies to each other — for instance “body A should be no closer than 10cm from body B”.. in other words, each constraint describes a rule which must be obeyed by the bodies involved.

Then comes the magic part, the solver calculates a “solution” — a set of body states (positions and orientations) which obey all of the constraints, while at the same time being as close to the initial (pre-solved) state of the bodies as possible. This last condition ensures that we move the bodies by the smallest amount possible in order to satisfy the constraints, so that their motion is coherent — otherwise the states of the bodies could jump all over the place erratically!

The way in which the solution is found is a process of optimization or minimization (those two terms mean slightly different things to mathematicians, but we’re not really clear on the distinction… What we want to do here involves finding a solution which best fits a set of rules or conditions). Specifically, the Gauss-Newton method is applied to the system. At least, as far as we can tell, this is what’s going on! 😉

We sort of cheat — proper Gauss-Newton requires that you build up a big matrix which describes the entire world (each row of the matrix represents a single constraint), and then solve this matrix to find a solution. This is often the approach taken by more mathematically sophisticated solvers, such as David Wu’s.

Unfortunately, implementing this sort of “big matrix” solution is quite complex and well beyond our mathabilities, so instead we adopt the approach presented by Muller in the aforementioned PBD paper: rather than solve all the constraints at once, we apply the Gauss-Newton algorithm to each constraint individually. This means that rather than finding a set of body states which satisfies all of the constraints, we’re finding a set of body states which satisfies a single constraint at a time. This process is repeated again and again, the bodies gradually moving towards the solution which would have been found had we solved all constraints together. Iteratively solving constraints one-by-one is also called “relaxation”, and just like finite differences it’s a deceptively simple but incredibly useful idea.

So, that’s it for now — there is a ton more work to be done on the solver, but it mostly consists of little things such as figuring out how to implement certain behaviours (such as conveyor-belts). One big disadvantage that comes with using a position-based approach is that you lose the ability to easily enforce velocity constraints such as friction and “bounce”. We’ve found a decent solution to this using motorized position constraints, and if worse comes to worst we could always use a two-phased approach: solving position constraints using our current method, and then solving velocity constraints using a more traditional impulse-based method. Luckily motors are a snap to implement in this solver — but that will have to wait for another post!

An even larger complication (which we’ve avoided mentioning here) is collision detection: since object positions are adjusted at each iteration, bodies which aren’t initially colliding can end up being pushed into each other by the solver. This is something we’re still working on — we have a pretty decent solution that works well (and, excitingly, even supports concave-vs-concave collision!), however it’s quite slow. Probably we shouldn’t worry too much about speed until we’ve ported things into C++, but we’d still feel more comfortable if we had a more optimized solution — a faster method which was limited to convex shapes would be a great complement to our existing solution.

At any rate, we’re really excited about Robotology, and can’t wait to get back to work on it. We’ve strayed quite a bit from our initial plan — we had originally intended to use a vastly simplified “fake physics” solution — but now that the simulator is up and running we’re completely psyched about the possibilities. Hooray!