Physics For Game Developers 328
| Physics For Game Developers | |
| author | David M. Bourg |
| pages | 326 |
| publisher | O'Reilly |
| rating | 8 |
| reviewer | Richard Jones |
| ISBN | 0-596-00006-5 |
| summary | A good introduction to the difficult subject of writing 3D games and simulations with accurate physics, let down by a few minor snags. |
Programmers who want to get serious about game physics will love David M. Bourg's Physics for Game Developers. As I've said, the subject is inherently very difficult, and the book assumes that you are already familiar with vector and matrix arithmetic up to college level, integration and differentiation, and at least you hazily recall your mechanics/physics lessons from school. You also won't be afraid to wade through Bourg's carefully documented derivations of formulae for various physical effects, and his well-commented source code.
The book starts off by recapping the basic concepts of mass, centre of gravity, moment of inertia and inertia tensors. Bourg assumes that you have a working grasp of these subjects, and I admit that I had to go back to some of my A-level mechanics text books. He then goes straight into kinematics, where he uses standard (but forgotten!) integration techniques to calculate velocities from accelerations and positions from velocities. His examples are excellent, although a few exercises wouldn't have gone amiss. The chapter on forces covers a great many different types of forces such as springs and buoyancy, but curiously omits the important subject of contact forces (the normal force that a table, for instance, exerts on your computer monitor to stop it falling through the floor). In fact contact forces don't appear until much later in the book. Particles, rigid bodies and impulses (forces from collisions) are introduced in chapters 4 and 5.
At this point I have to say I was a little bit confused. What did this have to do with game programming? Everyone knows that games spend most of their time running round a single big "main loop," working out the forces on each object, looking for collisions and working out which keys the user is pressing. It doesn't seem imaginable that a game programmer could completely solve all the equations of motion by pure integration at the beginning of the game, and then just run the positions of the players through the graphics engine like a movie!
I already knew a little about this from what I'd found from the web, but what most games actually do is calculate all the forces on all the objects (players, scenery, etc.) in the game, and then integrate them at each step. Some of these forces will be generated by human players pressing keys on the keyboard or wiggling the joystick, and that's how the objects end up moving. Pure integration isn't usually possible, so the physics engine performs numerical integration - a kind of fast approximation to the pure "closed form" solution. Numerical integration is itself a tricky subject, but it's the meat-and-veg of good game programming. Surprisingly, numerical integration and a realistic main loop doesn't appear until chapter 11 (172 pages into the book). I skipped straight to this section, and I suggest you do so too...
The chapter on numerical integration is excellent and contains the first realistic gaming (or at least simulation) code. Many games I've examined use simple numerical integration, like this:
// At each step ... A = acceleration, dt = time step
Vx += Ax * dt;
Vy += Ay * dt;
Sx += Vx * dt;
Sy += Vy * dt;
Unfortunately this method (Euler's method) is very inaccurate and unstable: if you tried to simulate planets orbiting around a sun using this method, they'd soon fly off into outer space unrealistically. Bourg gives an excellent introduction to better methods such as the "improved Euler" method and the popular Runge-Kutta method, and he covers them in a context which will make it clear how to use these methods in your own programs.
The book reaches a crescendo with three fully developed simulations: two hovercraft which you can drive around and jolt into each other like bumper cars -- they spin around realistically; a flight simulator; and a 3D car which can be crashed into blocks that bounce around. Again the source code is meticulously commented and generally well written. My only two reservations about the code are: It would be nice if Bourg had chosen to use OpenGL instead of Direct3D so that those of us without regular access to Windows could actually compile and run the examples. The book would make an ideal companion to the OpenGL Red Book. And coming firmly from the Windows camp, Bourg's examples are full of all the horrors of Win32 APIs and Hungarian Notation. But maybe that's just my personal preference :-)
So in summary: The Bad Points:
- Measurement systems: Bourg moves uneasily between the English/US system and the European SI units. So we get examples which combine ft/s, meters, slugs and kilograms, uneasily converting between the two. He should have chosen one system and stuck with it.
- A common complaint about computer books: I've just spent 25 quid on a book which will sit open on my desk for months. Is it too much to ask that it be ring bound?
- Some subjects are not explained in enough depth. Particularly: moments, contact forces, impulse methods. Bourg should probably have written a chapter or three on collision detection.
- The chapters are presented in a very strange order. Move chapters 6-10 until later, or introduce numerical integration earlier.
- A few of the illustrations are inaccurate.
and The Good Points:
- Considerably better than the usual round of maths/physics text books which make up this field. In fact, this is really one of only about 2 or 3 significant books in this area which are pitched for game developers as opposed to mathematicians, and it's certainly the best.
- The areas which are covered are done well, in significant depth, with a good bibliography where you can find out more.
- The commentary on the difficult equations is good, and Bourg resists the temptation to derive many of the formulae he presents, instead referring interested readers to other references.
- Code is well documented and explained.
And now I suppose I have no excuse not to resurrect XRacer :-)
You can purchase Physics for Game Developers at Fatbrain
on numerical integatration in programming.. (Score:0, Informative)
Simpsons method is more accurate method to integrate, since it creates a exponential polynome that more accurately represents the function. The method follows:
S(n) = dX/3(y(0)+4y(1)+2y(2)+4y(3)+
Use this in your gameengine the next time, and impress!
i just bought this book online.... (Score:3, Informative)
i read thru the sample chapter [here] [oreilly.com] it's all about particle physics. i was quite impressive, i enjoy the *conversational* style that most o'reilly books have.
i implemented all of the examples in java using java3d. [j3d.org]
i hope the book meets my expectations....
Chris Hecker's Physics tutorials are FREE! (Score:5, Informative)
provides an excellent, and free alternative to purchasing a weighty tome on the subject. Chris covers the details of rigid body mechanics in a thorough, but light manner.
I went to a physics lecture at GDC, the most memorable part of which was Chris saying:
"Here's how it's going to go... you're going to write your first rigid body dynamics simulator. You're going to simulate a cube dropping onto a plane. You'll run the program, the cube will drop, hit the plane... and disappear."
So, so true.
HL (Score:2, Informative)
Runge-Kutte? Give me a break! (Score:3, Informative)
Runge-Kutta is a complex method for quickly and accurately solving differential equations by numerical means. It is used instead of simple Euler iteration because it is equivalent in speed and gives much more accurate results. It works by adjusting the timestep dynamically to skip over regions where the system is changing slowly, and to integrate more carefully when the system is changing quickly.
This is all well and good when you are trying to do something important, like simulating heat flow within in a heatsink. But for simulating the orbits of planets around a star, for example? What a waste of time! The orbit is elliptical, so just simulate a freaking ellipse!
What about space missiles? Do you need Euler integration? No! There is a closed-form solution to the linear acceleration problem -- it's a quadratic. This procedure does not give low error. It gives zero error.
I read this guy's articles several months ago. I thought he was off his rocker then, and I still think so now.
Re:Great... (Score:2, Informative)
In the summer i took a numerical methods course using "Introduction to Numerical Methods and MATLAB: Implementations and Applications" [amazon.com] by Recktenwald. If you can use procedural languages, you can read/write Matlab scripts. I'd give the link to the course website, but the prof changes the password every term; it's a damn shame, too. He's a fellow of the IEEE, really smart guy. Had good course notes.
Forgotten downforce? (Score:3, Informative)
A very simple (*) way to model downforce is to drop the centre of gravity of the model so that it is below the ground. Other variables such as tire grip also have to be changed as well but these are generally constants.
(*) Downforce changes with vehicle speed so this is a very simple model.
Why game physics is hard (Score:3, Informative)
As someone else pointed out, there's a straightforward way to approach game physics, based on what you learn in a first-year dynamics course, and it won't work. Free flight is easy. Contacts and collisions are hard.
Detecting contacts between objects is complicated, but well-understood. There are several free collision-detection engines available, and many research papers. The time bounds are quite good; only slightly worse than O(N) with the better algorithms. Writing a collision detection system is a big job, but the theory is tractible.
Taking appropriate action when you detect a contact is the hard part of the problem. Bouncing balls are easy. Multiple irregular objects with multiple contacts, slipping and sliding, are hard. Most current games simplify their collision geometry down to cubes or spheres and botch the hard cases ("But my sword went right through him and he didn't even notice!") The latest generation of games is just starting to get contact right. In another year, correct contact handling will be a "must-have" for commercial games.
If you simulate contacts between objects with a spring and a damper, you run into numerical stiffness during integration. Soft objects at slow speeds will bounce fine. In a hard collision, the forces become huge for short periods. The simple integration algorithms will result in huge errors, and the objects will go flying off into space.
If you simulate contacts between objects as impulses (an impulse is an infinite force applied for zero time, but with a finite energy transfer), two objects bouncing off each other will work great. More than one contact per object doesn't work too well. Resting contact doesn't work; objects may fall through each other. And everything bounces like it's a pool ball, because all collisions take zero time.
If you try to do everything with constraints, resting contact works. But combinations of sliding and resting contact result in wierd corner cases that are hard to get right. Trying to solve contact, rather than simulate it, leads to static indeterminacy. (Think of a table with four legs, slightly different in length. How the table behaves is very sensitive to small changes in leg length. Numerical solutions of multipoint contact problems become similarly sensitive). This is the approach Baraff preaches at SIGGRAPH, but few others have been able to implement it.
After a few years on the problem, I developed Falling Bodies [animats.com], which successfully solves this problem well enough to simulate a human figure falling down a circular staircase. It can be done. I hammered through the spring-damper problem by using unusual and robust integration techniques. This is computationally expensive, but sound.
If you're developing a commercial game, and need working physics, go with the Havok [havok.com] engine. They have a rigid body engine, a soft-body system, and a specialized vehicle simulation engine. (Yes, vehicle physics in games typically has fake components. In most racing games, the tires are impossibly good and the vehicle CG is impossibly low. But you need a real physics engine to fake it properly.) It's not cheap, but you're not going to solve this problem in a few months. Major developers have blown years on this problem and failed. Trespasser, from Dreamworks, went down the drain that way.
Not inaccurarte and unstable (Score:3, Informative)
This is only true if you're simulating a standalone system (like the orbiting planet example). In real games, the player is constantly pressing the controller, collisions are occurring, and the "AI" is making decisions. Stepwise integration makes perfect sense in that case. Calling it "inaccurate and unstable" shows a lack of game development experience.
Re:Don't need to be that exact (Score:2, Informative)
My background is in physically based modeling
in computer animation, so here is what I know:
The integration scheme can have such a strong
influence on the stability of the system that
it can mean going from an integration timestep
of a microsecond to a hundredth of a second.
That's a speedup of 10,000. Generally, the
finer the spatial resolution of you simulation
(how fine your cloth mesh or fluid volume is),
the faster a timestep you need.
The brief description of the book cites the
Runga-Kutta method as a preferred technique
over basic Euler integration. The former
is a fourth-order method, the latter a
first-order method. Three orders of magnitude
is nothing to laugh at.
The big breakthrough in cloth deformations came
because Witkin and Kass figured out how to
simulate cloth with a large timestep (they use
implicit integration techniques). Jos Stam
did some nice work with real-time fluids that
relied on a semi-Lagrangian integration scheme
with a vorticity term to undo the artifical dissipation caused by the coarse numerical
simulation.
Re:on numerical integatration in programming.. (Score:2, Informative)
calculus course and then proclaim themselves
experts on slashdot.
First of all, Simpson's method does not
create an "exponential polynome." It models
a curve locally as a parabola.
Second, this method is useless in many situations
where one integrates over time. Simpson's rule
is designed to find the area under a curve.
Yes, distance is just area under a velocity
curve, but you are not given the velocities
a priori. You have to solve for them on the
spot, and even worse, velocities can be
influenced by the current position. In fluids
and soft-body deformations, things can get
even uglier. Some of the better methods for
numerically integrating through time involve
estimating the next values in time and solving a
system of equations using old and new values to
get a more accurate result (very hand-wavy explanation).
Re:Why game physics is hard (Score:1, Informative)
Fuck you too. Or to put it another way - did you really invent the whole idea of simulating springs and dampers? If so, good for you. If not, you're an opportunistic asshole.
Troll? (Score:3, Informative)
Hrm. Seems my last five comments have each been modded down one point. Fortunetly for me, I could care less.
Re:Grand Prix Legends (Score:2, Informative)
Spacecase