Over the past months, we've looked at several very different ways to simulate a range of real-world phenomena. Our simulations have been very simple, but I claim they capture the sorts of simulations really used by pure scientists, applied engineers, and game and movie developers.

Specifically, simulating physical phenomena boils down to three (interrelated) steps:

- Pick a data structure to represent your problem's data. Often, this is a set of discrete objects like particles or triangles, or a continuum field like a 2D or 3D texture.
- Pick a mathematical model
to represent your problem's behavior. This is usually a partial
differential equation, at least in all the literature generated since
the time of Newton and Leibnitz.

- Figure out how to apply your mathematical model to your data structure. This usually means discretizing your partial differential equation in space (taking steps equal to your data structure's size) and time (taking small time steps, like a few milliseconds). You can usually evaluate spatial derivatives by looking at your neighbors, and thus figure out how your value changes with time (see below).

- Particles. Separate disconnected entities. Easy to
store arbitrary data on each particle. Need a spatial search data
structure like a tree or grid if the particles interact with anything
spatially (e.g., other particles, grids, etc). Typical
representation for critters, fireworks, dust, etc.

- Unstructured meshes, like triangle or tetrahedron meshes. They're basically a set of particles with new force-generating entities between fixed neighboring points. You normally generate the meshes using a separate special program or library, not part of the main simulation. Typical representation for solid objects.
- Grids, like 2D or 3D textures. Grids are divided into
pixels or voxels that each represent a small part of the problem's
space. Typical representation for flowing fields like liquids or
gasses.

- Newton's Equations

F = mA

dV/dt = A

dP/dt = V

F: net force (vector, usually computed from something interesting!)

A, V, P: acceleration, velocity, and position (vectors)

m: mass (scalar)

dV/dt = A

dP/dt = V

F: net force (vector, usually computed from something interesting!)

A, V, P: acceleration, velocity, and position (vectors)

m: mass (scalar)

- Blurring model: du / dt = k * d
^{2}u / dx^{2} - Navier-Stokes
- σ=Ee (stress is stiffness time strain)

P (t+h) = P(t) + h*P'(t) + h

That is, the value of P at some future time t+h really depends not just on the current position P and the current velocity P' (dP/dt), but also on the current acceleration P'' (d

To "zeroth order", we can ignore all the h-dependent terms:

P(t+h) = P(t)

That is, we can assume objects don't move during our timestep. (Say, stationary objects!)

To "first order", we can ignore all the powers of h higher than one:

P(t+h) = P(t) + h*P'(t) = P + h*V

That is, we're assuming the object moves in a straight line during our timestep. (Say, no gravity, no friction.) This mathematics is *exactly* the formula we use to compute the new P:

P = P + dt*V

For derivatives in space, like dP/dx, you can expand the Taylor series in position:

P(x+h) = P(x) + h * dP/dx (x) + h

Again, to zero'th order,

P(x+h) = P(x)

which means dP/dx isn't involved (hmm... not very useful for computing dP/dx!).

To first order,

P(x+h) = P(x) + h * dP/dx (x)

Unlike the derivatives in time, where we knew the derivative, but not the left hand side, now we know the left hand side (we know P everywhere), but we want to find the derivative. So we rearrange to the well-known one-sided "finite difference equation":

(P(x+h) - P(x)) / h = dP/dx (x)

So, the value of our x derivative dP/dx is proportional to the difference between our right neighbor's value P(x+h), and our value P(x).

We can substitute in a negative value for h to get:

(P(x) - P(x-h)) / h = dP/dx (x)

This is the difference between us and our left neighbor. If you average both of these estimates, you get:

(P(x+h) - P(x-h)) / 2h = dP/dx

This is the same "right minus left" we've written perhaps fifteen times in class!

Similarly, the value of our y derivative is this same finite difference, but measured against our top and bottom neighbors. Again, we can actually compute any derivative in space or time using the Taylor series, and even (with a bit of practice) figure out what partial differential equation we're actually solving given a chunk of code!