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.