Timestep schemes for physics simulations

Question

The operations used for stepping a physics simulation are most commonly:

• Integrate velocity and position
• Collision detection and resolution
• Contact resolution (in advanced cases)

A while ago I came across this paper from Stanford that proposed an alternative scheme, which is as follows:

• Collision detection and resolution
• Integrate velocity
• Contact resolution
• Integrate position

It's intriguing because it allows for robust solutions to the stacking problem. So it got me wondering...

What, if any, alternative schemes are available, either simple or complex? What are their benefits, drawbacks, and performance considerations?

Answer 1

The technique I found which has worked best for me over the years is this:

• Integrate velocity

• Collision detection

• Constraint solver (including contact resolution)

• Integrate position

Apparently this is called 'semi-implicit'. I've found it to be the most stable of all the techniques I've tried. I used this in the physics engine behind Little Big Planet PSP.

Hope it helps!

Cheers, Paul.

Answer 2

Another scheme I encountered is the one from Position Based Dynamics where you:

• Integrate velocity and position (unconstrained)
• Collision detection
• Constraint solver (position based)
• Update velocities from new positions (basically you're integrating them using the computed constraint forces, just like you did for the positions)

This is to show that there are indeed other schemes. Each has its benefits. PBD is good for cloth for example, while the semi-implicit velocity solver is better suited for rigids.

The collision detection step has to be somewhere after the positions were updated, as it doesn't matter if you put it before or after a velocity update (unless you're using velocity for continuous detection). Things can get even messier is you use higher order methods like Runge-Kutta: where do you put collision then and how often? I think Kenny Erleben has some paragraphs on this (lazy and eager approaches) at the beginning of his PhD thesis.