f = ma

games, math, code

December 7, 2011

Hi there…

some time ago, I posted a video about my C++ implementation of the Articulated Body Algorithm (ABA), one of the best available algorithms available to perform forward dynamics computations on kinematic tree structures (if this sounds weird, replace “forward dynamics computations” by “physics simulations” and “kinematic tree structures” by “human-like figures” and you might be able to get a clue what you can do with it).

I mostly use it for my scientific work, which is funded by the Heidelberg Graduate School of Mathematical and Computational Methods for the Sciences. I spent quite some time in programming it and making sure it does what it should (91 tests!).

Some highlights:

- Articulated Body Algorithm (ABA)
- Newton-Euler Algorithm
- Composite Rigid Body Algorithm (CRBA)
- Contact force computation as described by Kokkevis & Metaxas in “Practical Physics for Articulated Characters”, Game Developers Conference, 2004
- Basic forward and inverse kinematics routines
- Extensive doxygen documentation

So far I am very happy with it and thought that maybe other can benefit from it as well.

Therefore I decided to publish it under an open-source license, namely the very permissive zlib license (which is also used by Bullet), which should allow pretty much anyone to do what he/she/it wants with it. However comments, suggestions or acknowledgements are still very welcome.

You can grab it at:

https://bitbucket.org/MartinFelis/rigidbodydynamicslibrary

It does feel a little weird to let it out into the wild, but I hope it is of use for anyone.

Martin

January 7, 2011

**Update:** my code a.k.a. Rigid Body Dynamics Library is now available at http://bitbucket.org/rbdl/rbdl

During the last month I was working on an implementation of Roy Featherstones “Articulated Body Algorithm” which is one of the most efficient algorithms for simulating the dynamics of articulated figures. It has an asymptotic complexity of *O(n)* with *n* being the numbers of degrees of freedom. Here is a first video of a simple OpenGL visualization I hacked together yesterday:

I used Featherstones book “Rigid Body Dynamics Algorithms” which I highly recommend to anyone undertaking this task**(*)**. Additionally I used Featherstones Matlab Code of his algorithm that is available from his site at http://users.cecs.anu.edu.au/~roy/spatial/index.html to verify my results. I also used The HuMAnS Toolbox to double check my implementation. Furthermore I used exhaustive unit testing (algorithm + library: ~2600 lines of code, automated tests: ~1500 lines of code) to make sure I don’t brake things too much or at least have some feedback what I am currently breaking. Thanks to UnitTest++ this was nice and easy.

Now what is remarkable about this video is that it is the first time I see my implementation in live action. Before that I only knew from my tests and the comparisons that it is correct. It is comparable to flying blindly through fog only by using your instruments and trying to land. Luckily this bird has landed! … actually using “luckily” here is rather odd… let’s go with: WICKED!

(Even though the instruments said it is all right it is very nice when the sun comes out suddenly and you have landed very well and are already at the correct parking position.)

The book is also very useful for other well-known algorithms used in robotics and mechanics, such as the Composite Rigid Body Algorithm or the Newton Euler Algorithm, as this book is very clear and complete. It also discusses other topics such as system with closed (kinematic) loops, impacts and other stuff. Additionally there is a detailed section about efficiency and how to implement the algorithms. For every major algorithm there is always the mathematical expressions next to the actual pseudo code for clarity – nice!

But The Best Thing Ever™ in his book is the spatial algebra he uses to formulate rigid multi body problems. It is a very sleek way to overcome the hassle of using two types of equations: one for linear motions and forces (translations, etc.) and another one for rotational motions and forces. Instead of the two 3D equations he uses one 6D equation that is further grained with Screw Theory. It takes some time to get the point of it all, but it absolutely pays off once one understands the elegance of it.

There is also a very good 2 part tutorial written by Featherstone concerning spatial algebra, which is published at the Robotics and Automation Magazine in the two recent issues which you might get through here:

**Update:** link to the September issue of RAM pointed to the December issue, now fixed.

February 2, 2009

It seems as if there haven’t been too many updates here lately. I’ve been quite distracted with studying and getting the simulation of multi body systems into my head. And by doing so I stumbled over a few quite amazing papers and dissertations that seem to cope pretty much everything you need to know for a fully fledged physics engine (assuming you have some spare time).

For example the dissertation of Brian Mirtich (which you should be able to download here or here) covers just about everything from advanced collision detection to collision response. Even the calculation of inertia tensors in 3D is contained and the appendix covers all the math basics such as quaternion arithmacy and a rigid body primer. The whole thing wheighs a bit over 250 pages and is freely available. It still requires a lot of math knowledge, but as a math major I hope I have enough knowledge.

The method he describes in his thesis is the so called impulse based simulation which is stated in contrast to analytical methods as they are used in David Baraffs papers (as far as I understand). Instead of trying to fulfill all constraints simultaneously, instead if a constraint is violated it applies an impulse to the constrained bodies so that the constraint stays fulfilled within the next integration time horizon.

A more recent version of Mirtich’ aproach can be found at the site of Jan Bender (www.impulse-based.de). He also wrote a dissertation over impulse based simulation (however in German) which has less math in it. The best is: his code is available under the zlib license! There is also a lot of documentation in English available, so go check it out!

Oh, and of course I have not just been doing multi body simulation stuff. I was playing around with Blender already for a while to have a nice visualization for my thesis. And I finally made a model for a character in a game I have been planning already for ages. Now I added a little movement to the model. Here you have it:

Be nice, she is a little older (and my first animation). You can get the full resolution version here.

Cheers,

Martin