Game Physics

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.