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.