Rigid Body Dynamics

I am continuing to learn how to simulate rigid bodies. This is something I've worked at in desultory fashion for many years. Unfortunately, since I'm in the middle of learning it, my thoughts are not especially well-ordered.

As I said last week, I'm following the Witkin/Baraff tutorials. I also found an interesting-looking paper by François Faure, which looks like it might show a better way to compute contact forces in a game.

Here's a shot of how far I'd gotten a long time ago. I was working with balls, simplified by ignoring rotation. A 2D box contains marbles of different sizes. Rotating the box makes them roll and bounce from one end to the other:



Exact Collision Times vs. Post-Collision Fixup

The Baraff tutorials assume that integration proceeds from collision to collision. At each exact collision time, the colliding bodies are adjusted so they won't pass through each other, and then the integration is resumed with the new velocities and accelerations.

The problem with this is that the amount of work per frame can vary quite a bit. A step of integration costs the same no matter how much time you're covering, so the per-frame cost is going to be proportional to the number of collisions during that frame.

In games, the ideal simulation costs the exact same amount every frame no matter what. We're even willing to tolerate a less-accurate simulation to achieve this, since it lets us budget CPU and memory better.

I have been deviating from the tutorial in that I'm attempting to essentially treat all collisions as if they occur at the start of a frame. Integration proceeds in whole-frame increments. Of course this means that objects can wind up inter-penetrating each other at the start of the next frame. To correct for this I do physical position fixup.

When an inter-penetration is detected, the objects are moved apart the minimum distance necessary. The movement is weighted by mass, so the lighter object does a bigger share of the movement. In the case of a collision with an immobile object, the mobile object does all of the moving.

Moving one pair of objects can cause another pair of objects to inter-penetrate. In simple situations, things converge toward a solution where nothing interpenetrates over the course of the simulation. For objects that aren't too interdependent this works surprisingly well. Problem cases involve resting contact (a stack of crates, for instance). I hope to deal with resting contact as in the tutorial, by introducing additional forces to keep objects apart during the integration. We'll see how well that works.

Progress

This week, I've gotten 2D boxes working. The environment is made out of (tan) boxes with infinite mass, which makes them immovable. I've got a little chute into which I can drop random boxes:



There's no friction yet. At the moment, gravity is the only force being integrated, so I just integrate assuming constant acceleration during the frame. I may be adding springs or things that require more complex integration, but I'll cross that bridge when I get to it.

In 3D, you have to consider point/face contacts and edge/edge contacts. In 2D, there are only point/edge contacts, so things are a bit simpler. In 3D, the rotational inertial tensor is a matrix, while in 2D it is reduced to a single scalar value.

I'm still struggling to work out a good code architecture. Next up, I plan to generalize my colliding bodies so I can support both boxes and circles; I want to make a simple 2D vehicle, and circles should work for wheels. After that, friction and resting contact.