CG Physics
other posts

An overview of how computers simulate physics.

In computer graphics, it is commonly desired to have something on the screen move “‍realistically‍”. This leads to the question, how do real things move?

Physicists have several answers. I’ll skip the quantum level entirely. One step above that is the field-based physics model: there are gravitational fields and electromagnetic fields and so on. Each field contributes to a second-order differential equation: that is, the position of each object within the field tells us the acceleration of that object.

We can solve second-order differential equations in computers with a fair degree of accuracy, but fields don’t give rise to common things ideas like being solid and colliding unless you model a really really large number of really really small particles, and it just isn’t worth the computing time.

Instead, most computer simulations of reality These simulations are often called some kind of “‍dynamics‍”, like “‍soft-body dynamics‍” or “‍fluid dynamics.‍” are based a combination of a few simple ideas.

# A Common Dynamics Pipeline

Most physics simulations in a computer run using the same basic steps:

1. Break the world into a manageable set of pieces
2. Consider a snapshot of those pieces at one point in time
3. Write constraints on the motion of those pieces
4. Linearize the motion and constraints, and solve the resulting linear system of equations
5. Use the solution to move forward in time a tiny step

There are little tweaks added here and there, but the general structure is very often like this.

## Manageable Pieces

How you break the world up has a big impact on a simulation. Consider modeling water: we could look at a region of water and see how fluid flows into and out of it; or we could look at a representative subset of water particles. Similarly, to model concrete fractures we could have the pieces represent the volume as a whole or represent the interesting boundaries of the volume. There are names for these ideas: when the pieces represent regions we call it a “‍finite difference method‍” or an “‍Eulerian specification‍”; when they represent parts of the thing we call it “‍finite element method‍” or a “‍Lagrangian specification‍”.

There are many more nuances to picking pieces. Often given two models, one is more accurate and the other is faster. But the faster model lets you handle more, smaller pieces which provides better accuracy… the “‍right‍” thing to do is rarely obvious.

## Discrete Time

Not all models of physics use discrete time. A collision system can, for example, solve for the exact time of collision and not discretize time at all. But most simulations consider a sequence of snapshots.

The time between snapshots matters a lot. A simple example may be seen by considering collision detection. If the snapshots are close together then we can detect collisions by finding out which objects overlap in a given frame. But if the snapshots are too far apart we might have a fast-moving object pass from one side of an object to another between two frames and never detect the collision at all.

## Constraints

Most interesting things that happen in the real world can be modeled as constraints of various kinds. Mass, energy, and momentum is conserved. Water is constrained not to change volume, solids are constrained not to pass through one another, friction reduces kinetic energy, and so on.

Usually, the set of constraints is known, having been identified by physicists long ago. How they apply to the particular pieces and time discretization is not always as obvious, but is rarely more work than a little math and geometry.

## Linearity

In rare cases, constraints can be considered one piece at a time. For example, if we model things as little particles with mass connected by little springs, then the force on each particle is independent of the force on each other particle.

For many situations, however, we have to consider the interplay of all of the pieces and constraints at once. Push down on a liquid somewhere and it rises up somewhere else. Forces and actions propagate through the entire model.

Excepting a handful of special-case solutions, we basically know how to solve only one kind of system of interrelated constraints: linear systems of equations. When constraints interact we almost always linearize everything and solve the linear system.

Methods for solving linear systems of equations can fill several semesters of college study in itself. There are lots of special classifications of various systems and each has a few special methods that are faster or more accurate for them then are more general methods. But the salient point is they can all be solved. You can’t say that about much else when it comes to interacting equations.

## Move to the next time

How to move to the next time step is not as trivial as one might expect. The simplest way is to add velocity to position, add acceleration to velocity, and be done. But this can lead to instability where energy is created from nothing, or to numerical damping where things look thick and sluggish, or to inaccuracy where collisions are missed, or to any of a wide variety of other visually-unpleasant results. So you might use Runge-Kutta or interleaved time steps or backwards advection or any of a variety of other techniques to allow you to take large time steps and still have a nice-looking result.

But whatever the technique, the end result is a new time snapshot from which we repeat the whole process.