Physics 101 : Understanding physics simulation

In my experience, most people working with physics simulations (for a game, or a movie) don´t really understand what is going on underneath, so their tool of choice acts like a blackbox for them: they give it some input, and then they get an output which may or may not be the expected thing.

One could argue that a good system should be completely transparent and that its inner workings should be of little importance to those using it. That’s absolutely true in my opinion, and creating such systems should be the goal of any developer. But the reality is that in many cases understanding how the system works internally allows you, as a user, to feed better inputs and in turn obtain better outputs. Also, it helps immensely when identifying and fixing issues, and extrapolating your knowledge of one system to a different one.

In this post I will try to get anyone -regardless of their background- to understand how are physics simulation problems tackled in the games and VFX industry, and some key concepts behind it all. I´ll be grossly oversimplifying things so more advanced readers beware!

The problem

Solving physical problems for a movie or game is pretty much the same task. The only difference is that in a movie we can spend as much time as we want solving our problem, the only real limits are our budget and our patience. If we want to simulate a car crash (determine the motion of all the tiny bits and pieces that go flying and the two cars themselves) and render it (determine the color of each pixel in the screen based on things like light direction, color and intensity, surface materials and their properties), we can get a ton of computers to do all the math in a week, and then hand us the finished result (more or less).

In a game however we need to get answers to our problems really, really fast, as we have to present the result onscreen a few milliseconds after we were handed the problem. We also better be able to do it in a single, average computer to ensure anyone can play our game. Our goal is to create the illusion of motion before the user’s eyes, and let it all respond to his input on the fly.

So for all intents and purposes, the problems we need to solve in a movie and a game are the same, but in games we are much more resource limited.

What’s a “model”?

Let’s consider the car crash again: two cars are involved and we want to simulate it, so we need to know how many mechanical pieces are there in each car, their size, their mass, their shape, the way they interact to make the car work, the radius of the wheels, the type of tires they use and how much grip … wait … or do we?

Maybe we can simplify things: consider each car as a big chunk of metal sliding along the road without any friction. We no longer care about each individual mechanical part, or about the tires, or anything. Our problem is suddenly so much easier and faster to solve, but the result will be missing many details: the way cars bounce after the crash due to their suspension system, the windscreen cracks, etc. After all we are just simulating two big boxes and pretending they’re cars when the time to render (draw) them comes.

These are two different models of the same physical system. The former is hard and slow to solve but will result in a very detailed and realistic simulation, the latter is cheap and fast but will yield less visually enticing results. For games we tend to gravitate towards simpler models, as that’s the only way we can solve the problem fast enough.

What’s an “integrator”?

Every time the computer re-draws the screen (draws a frame), the two cars must change position, approaching each other until they go boom. We must devise a way to “advance” the simulation from one frame to the next.

What information do we have available in a frame? well, if we use a simple model of our problem it is probably enough to know the mass, position and velocity of each car. We also need to know how much of our virtual world’s “time” passes from one frame to the next.

Velocity is the rate of change in position over time. The faster our cars go, the greater the difference in position between frames. So it makes sense to say:

new position = current position + current velocity * time between frames

Now, what we just did is integrate velocity over time, to find the new position. Similarly, the rate of change in velocity over time is called acceleration.

new velocity = current velocity + acceleration * time between frames

Forces acting upon a body cause an acceleration, that is, they change its velocity. Since force = mass * acceleration ( I assume you are familiar with this one 😉 ):

acceleration = force / mass

This means that, under the exact same force, a heavy object will get less acceleration that a light one: If you kick a steel ball, it will hardly move (and you’ll end in ER with a broken toe) but if you kick a plastic ball it will change its velocity almost instantly. The math follows intuition very closely, right?

So, if we want to update the position of each car from one frame to the next, we can do this:

new position = current position + current velocity * time between frames
new velocity = current velocity + (force / mass) * time between frames

Neat, isn’t it? We integrate velocity to get position, and integrate acceleration to get velocity. This is Euler’s integrator, a very basic way to update our physics simulation and albeit a fast one, a quite inaccurate one too.

Regardless of how we choose to model our problem, we will need an integration scheme such as this one to advance the simulation from one frame to the next. Go read this great article for a more in-depth discussion about integration.

What’s a “solver”?

Up to the point when the two cars collide, their velocities and positions are pretty much independent. After the collision, their new velocities will depend on things like their relative mass -a truck hitting a bicycle will result in a radical change of velocity for the bicycle, not so much for the truck-, the contact point(s) during the collision, etc. This is a problem that involves several bodies, not just one.

Simply put, for us a solver is a program that takes this kind of problem, and solves it. The problems are usually formulated as an equation system that relates multiple physical properties of the bodies involved in it: their masses, velocities, positions, accelerations, and so on.

Broadly speaking, there are two kinds of solvers: direct and iterative. Direct solvers try to get the exact result in a single go. Iterative solvers do several passes over the whole problem (that is, over all equations that relate the bodies), each time getting a better approximation of the exact result.

Direct solvers (e.g. Lemke, Dantzig) are fast for small problems, but get progressively slower when the problem size grows: for problems with many equations (many bodies and relationships between them), they can be extremely slow, at least for game standards. There’s ways to present larger problems in a more digerible form in order to speed things up (e.g. Cholesky factorization), but still it would be nice to get the result faster, even if that means less accuracy. After all, any respectable game must be able to handle a pile of 50 objects without breaking a sweat! 😉

Iterative solvers (e.g. Gauss-Seidel, Jacobi) on the other hand, are able to give us an approximate solution faster. They will start with a guess of the solution, and progressively refine it through many quick passes (iterations) over all the equations. The more iterations we let them perform, the more accurate the result. For large problems, a few iterations can be performed and a good enough result obtained in a fraction of the time it would take a direct solver to give us any usable output. Too few iterations will however result in strange results at best, or an unstable simulation (things exploding and jittering wildly out of control) at worst.

It isn´t always 100% clear whether a solver is direct or iterative, as some methods can be regarded as either (e.g. conjugate gradient).

Wrapping up

At this point it shouldn’t come as a surprise that most game physics engines use:

• simple models
• relatively simple integrators
• iterative solvers

In the next post we will see how has been all of this considered and applied to a typical game physics engine, and a few posts later, our particle-based physics engine: Obi.