Naturally, once I had the fluid dynamics running I wanted to hook it up to the physics engine and have the explosions move objects around. It didn’t quite work at first because

  • The characters moved by setting their velocity directly, so the force from the blast didn’t affect them.
  • Other objects had no friction and would fly forever once set in motion.
  • Collisions only resolved overlapping bodies and didn’t affect velocity.

It turns out that resolving positions in a collision is pretty easy but resolving velocities is a tricky business. Well, I can’t resist this kind of thing so I had to have a go.

Suppose we have a large number of objects that need to be updated in a time step. In that time, some of them may collide, and the positions and velocities at the end of the time step should respect certain constraints, such as non-overlap and positive or zero relative velocity at every contact point. Also, basic laws of collisions such as conservation of momentum and the coefficient of restitution should apply. Numerical artefacts such as jitter should be minimised. And it needs to be fast.

I’ll start with a method for resolving positions, because, as I’ve said, it’s quite straightforward and leads on to part of the velocity solution. First, we need a list of potential collisions. Why not actual collisions? At this stage, it’s just not possible to tell. Object A may appear to miss object B, but then object C comes along and knocks B into the path of A. I collect collisions using a tolerance based on the maximum local velocity. Each potential collision provides a constraint equation, and these equations form a linear system, which can be solved, for example, using the Gauss-Seidel method. The output is a list of offsets which, when applied along the collision normals, will prevent intersection at the end of the time step. Although iterative, the solution can be calculated to any accuracy so there is little jitter.

Now, a related technique can resolve intersections by changing the velocity of each body so that it brings colliding bodies exactly into contact at the end of the time step. This works only for perfectly inelastic collisions, where the objects stick together. The post-collision velocity is used to correct intersection and therefore it can’t carry any bounce.

What if we resolve positions and velocities separately? Can there be bounce in that case? It turns out that no, it doesn’t work. You need to know the outgoing velocities at the start, but these depend on the global system. Get them wrong and energy is not conserved, and the bounce may look odd.

There is another method, though. The collisions can be processed one by one until none remain, that is, all the relative velocities are positive. This works (almost) correctly for perfectly elastic collisions, and not quite so well for inelastic collisions. Even slightly inelastic collisions dissipate too much energy over several iterations, and convergence becomes poor as the coefficient of restitution (Cr) approaches zero.

Interestingly, a combination of the two methods is perfectly fine. Calculate a result for Cr = 0 using a linear system and another for Cr = 1 using sequential impulses and they can be mixed together according to the desired value of Cr. A limitation of this technique is that all simultaneous collisions have the same Cr. But it’s the only one I know of that works! All others are a poor approximation. (As opposed to a better approximation – there is no exact solution.)

The only collision paper that makes sense:

http://www.cs.columbia.edu/cg/rosi/

A 600 box stack.

A 600 box stack.

Advertisements