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.

I am a researcher at the
University of Cambridge,
working on the TRVE DATA project
at the intersection of databases, distributed systems, and information security.