Implementing constrained rigid body simulation - source code now available

Published by Martin Kleppmann on 25 Oct 2008.

My final-year project at university was on “Rigid body simulation for 3D character animation”, which is a very fancy way of saying that I spent a year trying to make a video of a person falling down a flight of stairs. Without hurting any real people obviously – it’s all simulated and 3D animated, and most of the content of the project is working out the maths and the algorithms to calculate how bodies move and rotate in space, how they collide, and how they react when they are being held together by joints. I started out on that project thinking it would be fun, and it actually turned out to be fairly hard, so I published the results in a technical report of the University of Cambridge afterwards.

More importantly, here’s the video which was the end result of the project. It presents several scenes of increasing complexity:

• starting with simple pendulums (2 pendulums joined together, as well as 3-part, 8-part and 25-part pendulums – demonstrating basic rigid body movement and simple joint constraints),
• continuing with Newton’s Cradle (aka Newton’s Balls) with both fully elastic and less ideal collisions,
• followed by a scene of 10 cubes falling, bouncing off a table and off each other (demonstrating more complex collisions and resting contact between bodies),
• and ending with two scenes in which a human figure (Alfred) falls down a straight staircase and a spiral staircase (lots of complex joints, collisions and interactions going on).

There’s a better quality MPEG download on maniation.com. Feel free to download and read the report; it’s not the most exciting read and contains a lot of maths, but it does contain one or two minor new discoveries. I tried to make it unpretentious and useful by explaining the material in such a way that it serves as a readable and useful introduction to the topic (mainly because I struggled to find decent introductory texts myself).

And in fact, in the 2 years since I completed the project I have had a few people contact me and ask for further details and/or bits of source code for their own projects. I have not developed it any further and probably won’t be doing so anytime soon, but I’m still keen to hear from anybody who’s doing things in this space. And as a help for anybody working on their own physics engine, I am now releasing some of the source code from my project.

SOURCE CODE NOW AVAILABLE

The code is in Java 5 and covers some of the fundamental data structures and algorithms which I needed to implement:

• A bunch of mathematical datatypes: vectors, matrices, sparse matrices, quaternions etc.
• Some numerical algorithms: a Runge-Kutta ODE solver and a conjugate gradient solver for systems of linear equations. These are taken from Numerical Recipes.
• Implementations of a number of different constraint and collision types, as described in the report. This includes code for the Jacobians, those crazy matrices which get unbelievably complicated for some of the more tricky types of constraint.
• An implementation of the simulation loop using constraints and collisions, variable step sizes, and backtracking to find the time of a collision.

Note that this is not elegant, optimised or even particularly robust code; if you’re writing a computer game and need a physics engine, consider using something like the Open Dynamics Engine (open source), Tokamak (open source) or Havok (commercial). But if you want to learn how to make a simulation like this using Lagrange multiplier methods, then maybe this is for you.

You will quickly notice that the source is not complete. Hell, there’s not even a ‘main’ method. That’s deliberate – this code is there to help you figure out how this stuff works, it’s not intended to work out of the box. If you want to write an application which uses it, you’re probably going to have read the whole report and some of the papers it references, read all of the code, think about it for a while, get annoyed about the fact that I didn’t put more comments in the code (sorry), and then start writing some stuff around it.

Nevertheless, I hope it will be useful. I release it under a MIT license.

Download the source code