I'm writing a small physics engine for learning purposes. Up till now, I've been using Euler integration, but I've heard that Euler integration is evil (unstable, inaccurate etc). I'd like to try out different alternatives, and ideally make the integrator a pluggable component so that it's easy to switch as needed. Unfortunately I know almost nothing about other integration techniques, and what info they need. So my questions are: 1. what information does a generic integrator need? At the moment, for each rigid body I store position, velocity, acceleration and mass (torque will not be included in the first version). This is enough for Euler. But will this be enough for other integrators, or do I need more info per body? Do I need to store old body states (from earlier frames) for some integration methods? 2. which integration methods are worth trying out, and where can I find info/source code for these? 3. I'll use an impulse-based technique for collisions later, i.e. compute a force based on mass and time step length of the object, such that the force will, when integration is applied, result in the exact change of momentum that a perfectly elastic collision should result in. Does the calculation of impulse depend on the choice of integration technique?

Hi there,

(1). Yes, this will be sufficient for most commonly used integrators. I think a line of integrators use old position and velocity data, but they're not used much afaik.

(2). Well, what integrator type to choose depends on the task. Here's a list of the most basic all-purpose integration scemes:

The 1st order non-symplectic Euler method is not worth using...

acceleration = force / mass
position += velocity * timestep
velocity += acceleration * timestep

The 1st order symplectic Euler, on the other hand, is. All you need to do is swap two lines, and you have yourself a much stabler and more accurate integrator (still 1st order though)...

Acceleration = force / mass
velocity += Acceleration * timestep
position += velocity * timestep

Then there's the 2nd order symplectic Leapfrog or Midpoint method. Only slightly more complicated than symplectic Euler, and only slightly better, too. It's more accurate, but only very slightly more stable.

Velocity += Acceleration * timestep * 0.5
Position += Velocity * Timestep
Acceleration = Force / Mass
Velocity += Acceleration * timestep * 0.5

And finally the 2nd order symplectic Velocity Verlet. This is the most accurate of these integrators, but again only slightly stabler than the Leapfrog.

Position += Velocity * Timestep + Acceleration * Timestep * Timestep * 0.5
Velocity += Acceleration * timestep * 0.5
Acceleration = Force / Mass
Velocity += Acceleration * timestep * 0.5

If it isn't stabe enough to run your - say - spring simulation, simply run it twice per program loop with half the timestep, or four times with 1/4 timestep.

More advanced integrators exist, like the non-symplectic Runge Kutta 4th order, but this should get you startet :-)

(3). I think you've slightly misunderstood the concept of impulse. When using an impulse based collision algo, you don't have to calculate force or even acceleration. Instead you find the new velocity of each object directly, completely avoiding having to use an integrator. In other words, no.

Cheers,
Mike

I've struggled with this problem as well. There's more to the integration problem than you might think.

You could say there's two "types" of integration. You are asking about the first which simply redefines your integration step. (i.e. x = v*dt):
If I remember correctly Runge-kutta (RK-4) is very decent, but quite complicated. I think there's another somewhat simpler one called "Improved Euler", but I'm not sure where to find it on the web since I found it in a textbook.

As for impulses, remember that an impulse is a (cool and useful) cheat that results in an instantaneous change in velocity, so it bypasses the whole integration step completely. (I.e. there is no delta time, so there is no integration either).

Just remember, it depends on whether you want to support dynamics (in other words joints) in your system and even how you do your collision responses. If you are content with a bunch of loose objects bouncing around then you can use one of the plain integration methods with impulses for collision response as you mentioned. You should realize that if you plan to connect objects using ropes or joints or even if you just want to do "better" collision response you'll need to use a proper matrix solver. This is because you need to solve all the constraints on the system simultaneously.
(For example: I think if you have 10 objects lying on top of each other, the plain impulse method should cause the heap to sink into the ground and the objects to sink into each other. There's also other problems with resting contact but I won't get into it now).

In this case you'd better take the time and study something like the bullet engine, because that's pretty complicated stuff.

Ok, I see you just want this for learning purposes. Sorry, I got a bit into my reply :)

Thanks and ++rating to both!

So, it seems like I have misunderstood the collision part then. That was going to be my next thing to implement after fixing the pluggable integrator.

@errantkid: About 10 boxes lying on each other: wouldn't a matrix solver lead to a O(N^2) sized matrix for N objects, and thus have problems scaling well with an increasing number of objects? Isn't there a way of instead using one of the integrators mentioned by h4tt3n by appropriately calculating the forces in a system of joints separately from the rest of the integration step? E.g. by a callback method calculateForces().

Well, you don't necessarily store the entire matrix. For example the matrix solver in bullet uses a special "sparse" representation of the matrix which it solves. This is because most of the entries in the matrix will turn out to be 0. The point is that you still need to gather all of the interacting objects into some kind of list that can be solved iteratively.

I actually did my whole engine including joints, ropes and collisions without using a matrix solver at all. It took me a couple of months working full time and to this day I'm amazed that it actually works :). Ok, but at the same time I have to admit that I was also dealing with huge forces and tiny masses which is very difficult integrate. Personally I plan to throw away my old engine and replace it with Iterative Dynamics with Temporal Coherence at the first chance I get. :)

EDIT: I don't keep up to date with the newest techniques however. This guy seems to know what the newest and best solvers are.

Ok! But isn't it possible to just create a game engine entirely based on forces? E.g. the springs/ropes etc cause forces, the collisions cause "forces" (you make up a force that'll give the correct velocity change in the current simulation step), then you just integrate it all?

Now, obviously that may cause (due to instability) resting contacts to jump a bit, but that's ok for now (I reckon this can be fixed by replacing a collision test by a distance test with some epsilon for resting contact).

Or?

Yup, it's certainly possible. Like I said I did my engine using a combination of forces and impulses that I solved iteratively. Your proposal sounds quite similar to what I did.

It just depends on how sophisticated you need the engine to be. I would recommend trying it with forces and/or impulses first and then only switch to a solver only if you do end up needing it. All I'm saying is to be aware that solvers are "the next step" up (in case you happen to run into efficiency and stability problems).

By the way, just to get you thinking a little: How do you implement a hinge using springs? (I.e. a joint that rotates only on one axis). Also, don't forget that friction is also present when you have sliding contact, so include it in your integration!

I'll leave you with that thought! Ciao! ( and good luck :) )

Bullet actually uses an impulse-based constraint solver similar to the one in Erin Catto's Box2D engine. It's equivalent to the matrix/LCP formulation using a Projected Gauss-Seidel solver, but more intuitive and arguably easier to code up efficiently. You can definitely get good results using impulses if done right.

That's actually exactly the "Iterative Dynamics with Temporal Coherence" paper I was referring to before :)