Game Physics

A while ago, I mentioned that I was interested in writing a Gem on buoyancy. Well GPG6 is now available with my buoyancy Gem. The title is “Exact Buoyancy for Polyhedra.” I hope you find it useful.

You can download my GDC tutorial here:

GCD 2006 Slides and Code

I’m giving a physics tutorial at the GDC this year, along with some other math-heads.

Physics for Games Programmers

I’m presenting a new algorithm based on sequential impulses. I developed this algorithm in the pursuit of extreme simplicity. It is much easier to grok and implement than my Iterative Dynamics paper. I will post the tutorial and demo code here after the conference.

If you can make it to the tutorial, please introduce yourself. I always look forward to meeting people interested in physics programming. I’ll be there the whole week, so you will probably find me in any of the physics presentations.

(Note: this post comes from a debate I was having over on gamedev.net, so the tone is a bit harsher than my usual friendly demeanor. :))

I suggest you read the following article to understand my position:

Joel on Software

The conventional wisdom is that it is better to use components off the shelf (COTS). It seems mature, modern, and hip. It is also over generalized.

So license Renderware, license Havok, and so on. Put this altogether and just concentrate on gameplay. Sounds great, right? But what happens when EA comes along and buys up your middleware? What if EA is your main competitor? How good is support going to be at that point?

What if you need a new feature for a totally new game play mechanic, are you going to ask EA to implement this for you? How long will it take? In our game, my turn around time for new features is typically a day or two. My turn around time for support is a 10 second walk across the office.

If physics or graphics are a core feature of your game, it is incredibly risky to out-source this to an external library. That’s why I think many games so far have had limited use of physics, because it is not core, it is out-sourced.

(Here’s an e-mail I just sent that I thought might be of general interest.)

Well, I tried creating rigid bodies for wheels. They have nice traction and braking behavior but I ran into other problems. At high speeds (~60mph) the wheels would lose alignment. Perhaps this could be mitigated by using more iterations and/or smaller time steps. Another effect I didn’t anticipate is wheel tunneling. Now that can be reduced by ray casting, but this means the wheel won’t keep up with the chassis. I guess I could put in special logic to slow down the entire vehicle, but I didn’t try that.

I went back to my ray casting model and tuned it a bit more. I found a trick that really improves handling. Basically, I just offset all traction, braking, and friction forces up from the ground. The helps to diminish roll and pitch. This can’t easily achieved with rigid body wheels.

Anyhow, it was an interesting experiment and I’m glad I tried it.

Our main target is the PS2. Up to this point I have mainly been making algorithmic optimizations. We use SIMD in our math library and this helps with performance and code size. However, as you may know, data cache misses are killer on the PS2. So getting the best performance requires drastic measures.

For a stack of 15 boxes arranged in a pyramid shape, the cost is 45% collision and 55% physics. As I described in my GDC paper, the heart of the physics solver is the Projected Gauss Seidel constraint solver. This takes about 65% of the physics cost. So, by Amdahl’s Law, if I can double the PGS speed, I’ll get an overall boost of about 20%. Not tremendous, but it’s a good start.

The PGS algorithm suffers from data cache misses. These can be avoided by double buffering with the scratch pad. Another boost can be had by double buffering on the vector unit registers. Basically, the vector unit solves one row of the constraint equations at a time. While one row is being solved, the CPU is loading the next row into an alternate set of registers.

Cool stuff. It’s fun programming to the metal. I know I’m not treading on new ground here as Richard Tonge has written about these kind of optimizations he did for the PS2 version of MathEngine.

My question to all the physics heads out there: do optimizations on other platforms, such as PC or XBox, go to such extremes? Are the days of programming to the metal fading? Will fat L2 caches save us?

Another question: do you know the typical cost in milliseconds of an 11 body ragdoll on the PS2?

A while back I developed a nice little algorithm for computing buoyancy forces. I would like to write it up and have it published in GPG6. So I submitted my abstract today.

If any of you know someone on the GPG board, please put in a good word for me.

Game physics is a difficult subject. It must be layered on top of collision detection, which is also difficult. So the difficulty is compounded. In my opinion, the difficulty in writing a physics engine is not entirely necessary.

Learning the physics and mathematics necessary to write a physics engine is challenging and a good education helps. However, education is not enough because many of the techniques needed to write an efficient physics engine are not taught in school. Furthermore, I have not found any book that shows how to write a physics engine. Yes, there are books on game physics. I’ve seen at least three. But none of these books comes close to showing how to write a physics engine.

There are good books on collision detection by Gino van den Bergen, Christer Ericson, and Dave Eberly. They have proven invaluable to me in my day-to-day work. So why are there no books that explain the algorithms needed to write an efficient physics engine? Well, until recently there has not been any papers on the matter.

Yes, I know about the papers by Baraff, Mirtich, Jakobsen, Anitescu, and Guendelmen. I would argue that none of these algorithms are used in commercial physics engines without serious overhaul.

It seems to me that almost everyone who develops a good algorithm for game physics keeps it under wraps. This is too bad. The graphics community has shared algorithms since the beginning and look at how far it has progressed. What has stopped the game physics literature from flourishing in a similar way?

This is my open question to you.

I tried the shock propagation algorithm as described in Kenny Erleben’s dissertation. It does amazing things for stacking. I was able to easily stack 20 boxes at a 30Hz time step and 5 iterations. However, it has some bad side effects.

The problem is that stacks of boxes are too stable. You could have a stack where each box has its center of mass just inside the edge of the box below it. The centerline of the stack would make almost a 30 degree angle from the vertical. Clearly such a stack should fall, but due to shock propagation, lower boxes don’t feel the weight of higher boxes. Shock propagation only provides for downward transfer of momentum, not of static forces.

Consider a suspension bridge. The normal dynamics phase will spread out the joint error among all joints. When the shock phase is added, all the error is pushed to the middle joints, resulting in a nasty gap in the bridge.

I was curious how well the commercial engines do under similar conditions. So I fired up NovodeX. It appears that NovodeX does not use shock propagation and behaves somewhat similar to my engine. I also tried Newton and it does not use shock propagation.

Still, I recommend reading Kenny’s dissertation due to the wealth of information it contains.

I’ve posted my slides and paper from GDC 2005. If you have any questions about his paper leave a comment and I’ll try to respond for everyone’s benefit.