Contact Physics

One of my first jobs in game physics was writing the flight models for the fighter sim EF2000. Back in the mid-90's, the physics challenges were well suited to the PC's of the time, and contact physics wasn't part of the picture. A plane can be modelled very accurately as a point mass in the sky, and the challenge for the physics programmer is to get the right lift coefficients, drag, and engine model. It's hard to believe now, but combat flight sims were one of the biggest PC genres in 1996. Microprose's F15 Strike Eagle kicked the whole thing off, Spectrum Holobyte responded with the classic Falcon. Meanwhile, British upstarts DID challenged the big boys with TFX, and then EF2000. And a shareware game called Doom was slowing up development time, taking over office networks at lunch and dinnertime.

Today, flying and shooting is a niche market; todays games are much more "close-in", and it's ground-based car simulations like World Rally Championship that occupy the hardcore sim niche that flight sims once did. We now have the challenge of making games feel solid, creating an illusion of tangible physical presence. With today's advanced graphics you really notice when the physics are lagging behind. My colleagues at Evolution Studios (many of them DID alumni), are looking to bring that all-important sense of solidity to new levels as they begin work on their next WRC title.

In this article I will show how solid contact physics can be implemented, and describe some of the problems the programmer will encounter. The article should be of help to physics programmers, users of 3rd party engines, and decision makers who need to evaluate competing technologies.

A Solid Contact

An example: A car has flipped over, and hits the ground, as in Figure 2. With a single contact point and no friction, we do the math to calculate its motion. This simplest case has been covered by other authors, so I'll be brief. The mass of the car is m, and it has a 3×3 moment of inertia matrix J. We're looking for the force that the ground exerts on the car at the contact. The vector equations for linear and angular motion are:

(1)

where x is the car's position, g is the gravitational acceleration; w is the car's angular velocity, and q is the vector from x to the contact point. We've called the mystery contact force f, and N is the surface normal, which is also the direction our force will act in. In Matrix form, this is our "equation of motion":

(2)

I've put subscripts to describe the exact number of rows and columns. A 6 by 1 matrix and a 6-vector are interchangeable. The "constraint equation" should complete the picture by specifying that objects should not occupy the same space. We require that the car's contact point remains exactly on the surface. Call this r₁ in world space.

(3)
(4)

i.e. r₂ is just the projection of r₁ onto the surface. Our constraint is that r₁ remains on the surface:

(5)

and that works out as just . The 2nd order constraint is obtained by differentiating twice:

(6)

(7)

So after a little re-arrangement, we have the constraint equation in matrix form:

(8)

The left-hand term is a "centripetal acceleration" - all points on a rotating solid accelerate towards the centre. Note that the 1 by 6 matrix in the middle is the exact transpose of the one in the equation of motion: this is true in general. I prefer to use a single vector for the acceleration degrees of freedom, so:

(9)

(10)

Now, although I've used to describe the acceleration, we don't actually have a vector y, because angular position can't be properly described with a 3-element vector. But as long as we can obtain the change in w from one frame to the next, we can use quaternions or some other method to describe angular position. Now invert the 6 by 6 mass matrix M, and substitute equation. (9) into (10):

So we can define the scalars:

and :

(11)

This is our main equation. The solution is just f =- l/G. It's good to define l so it appears negative in our expression, as l is the acceleration that would exist between the contact points without the contact force. The force f acts in the opposite direction. If you calculate f and it turns out to be negative, that means we're pulling, not pushing, and you should deactivate the contact.

Now applying this acceleration over several timesteps will keep the car skidding along the surface in the correct manner provided the initial velocity between the contact points was zero. If it wasn't (e.g. when they first collided) we would need to apply an impulse to fix that. Without going into details, the answer is: i = - v/G, where v is the velocity of r₁ relative to r₂, normal to N and i is the impulse to be applied at the point of impact. You can apply this correction every frame to prevent drift, alternatively add a heuristic term to l which is proportional to v, so that the force will increase when the relative velocity is negative and decrease when it's positive. Do the same for the position so the contact points line up nicely.

Multiple Solid Contacts

You can now handle a single contact between the car and the ground. Fine for many fast-moving collisions, but eventually, the car will slow down and another corner will touch the ground. Now we have to consider multiple-contact solutions.

Figure 3 shows this situation, where a whole edge of the car is touching the ground. In reality the force will be spread across the whole contacting edge. For our purposes, we can just consider two forces at the two endpoints.

Our two contact points have normals N_a and N_b (these might be just the same vertical vector but let's keep it general). The forces are f_a and f_b. The equation of motion is

(12)

and as you might guess from Equation (8), the constraint equation is:

(13)

But we can still express this system as:

(14)

(15)

- and these two equations are like Equationns (4) and (5), except now f is a two-element vector, as is a. Re-arranging,

(16)

Equation (16) is like (11), except of course, that Gamma is now a 2x2 matrix. Here's where contact physics is different from the old-style video game collision. You can't apply the contact corrections sequentially. You have to find the one solution for f_a and f_b which satisfies both constraints. Now in this case, the matrix is only 2x2, and it's guaranteed to have an inverse (unless contacts a and b are in the same place).

So:

(17)

Now by putting in two constraints, we've turned our car from a six degree-of-freedom system, to four. Add another contact, and (usually) you'll take away another degree of freedom. With three contacts, we've effectively got a whole surface of the car touching the ground, and if the contact normals are vertical (i.e. we're on flat ground) none of the remaining degrees of freedom is affected by gravity. So with a bit of friction, our car can come to a halt.

And G would be a 3×3 matrix. Once again, as long as the three contacts are not at the same place, and don't fall in a line, you're guaranteed to have an invertible matrix G.

If you look in the literature, you'll find that this method isn't used much. That's because matrix inversion and other standard linear algebra techniques can't guarantee that all the forces will be positive. Suppose we require in advance that:

for all i (18)

This means all contact forces are positive or zero, and the accelerations they produce are positive or zero (no impinging between solids). Now we have what's called a "linear complementarity problem" (LCP), and an iterative method can give a solution where all forces are either positive, or zero. The common solution method is Lemke's algorithm, which you will find via [1]. A very good introduction to this approach is found in [2].

Redundancy

The problem is, our car may not have any triangular surfaces! When the next collision occurs, we'll most likely have four contacts. Not only that, but if the contact normals are all the same, the G matrix will now be singular - it has no unique inverse, and most matrix-inversion routines will fail. Why? Because four contacts between two surfaces is more than we need to zero out the relative motion at the contact points. As shown in Figure 4, there's an infinite number of combinations of forces at the contacts which will produce the same effect.

…etc.

Figure 4. Redundancy - obviously the forces should be equal. But why?
Of course, in special cases, like a table sitting on the ground, the solution is obvious - the forces should be equal. But that won't help us find the impulse to apply when the table rolls from two legs onto four. For a general solution we have three options:

1. Never add the fourth contact.

This would work as long as the three contacts we have are spaced well. But if they're all on one side of the object, it might start to tip over. Then one contact would vanish, and a new one would appear on the other side. We could end up with an ugly oscillation.

2. Treat surface-surface contacts as a special case.

We could detect when more than two points on a surface are touching another surface, then switch to a single "surface contact" which constrains three d.o.f. However, it would be awkward to then calculate when to deactivate this special contact, and it would mean introducing a different set of equations. This method would also not help when redundancy arose from contacts which are not on the same surface.

3. Eliminate the redundancy.

It stands to reason that there should be a relationship between the contact points which would allow us to find all the contact forces.

Redundancy is a different kind of issue if you're iterating to find a solution, because in most cases, you don't care which of the infinitely many solutions you find - the behaviour will be the same, provided you've already made sure of not finding negative forces.

Accuracy and Stabilty

It's quite common in contact physics applications to see objects which should move smoothly or settle down quickly, instead shake, wobble or jump into motion. There are two common causes for this behaviour.

1. The solution is wrong. Or not quite correct. This is common when the iterative scheme for finding the forces either can't reach a solution, or stops too soon. The short answer is to do more iterations - but there will be a speed issue.

2. The properties of the physical system can't be well-modelled at the framerate. One way this happens is if you've put some unrealistic values in your mass matrix (having moments of inertia too small for the object's size and mass is a frequent mistake). Friction can do this as well, if your friction coefficients are large enough that they more-than reverse the object's motion between one frame and the next. Physically realistic friction values will do this in many simulations.

Sometimes, programmers will solve No. 2 by having multiple physics iterations for each game frame. Please don't do this, there's almost always a better way.

Linked Objects

We've so far covered contacts between single, 6-d.o.f. bodies and a static world. But a lot of games need linked systems of bodies, for instance using a "ragdoll" model for realistic death animations (see Figure 5). There are two approaches you can use here:

1. Treat each part of the hierarchy as a separate body. Then define special contacts between the bodies at the joints. We would have a contact for, say, the hip-joint, which can have positive or negative forces, limits rotation, and acts in all directions. Using this method, you can use the techniques outlined above, but you will probably need a good iterative scheme, as you will be solving for, well, a lot of forces.

2. Treat the whole hierarchy as a single object. The object will have, not 6, but maybe 26 degrees of freedom. Calculating the mass matrix will be a daunting task, but with this method you won't have to worry about limbs stretching and detaching when too-big an impulse is applied.

Friction

Friction should be applied between nearly all contacts. Generally, if there is a sideways velocity between the contacting points r₁ and r₂, dynamic friction is:

(17)

where m_dynamic is the coefficient of dynamic friction, F_normal is the contact force Nf and is the unit vector in the "scraping direction". Note how even if the relative velocity is small we can still get a big force, and that can lead to the stability problem I mentioned earlier.
Static friction is different; it acts to prevent relative motion completely, and can do so provided the necessary friction force is smaller than m_static|F_normal|. To model static friction, treat it as two extra forces per contact to be solved for in f. It can also be considered as another complementarity condition in the solution method - either static friction is smaller than the maximum, or it is zero.

Generally, m_static is larger than m_dynamic - for example, a car's tyres on tarmac might have a static friction coefficient of 1.5, and a dynamic friction of 1.2. So you'll get better turning force if you stay in the static friction zone - or better braking if you don't lock the wheels. You can see this effect in action in WRC - on tarmac you can keep the vehicle just on the edge of the static limit, but on gravel or snow you'll be in the dynamic zone most of the time.
Many simulations either ignore static friction, or simulate it by having a larger coefficient when relative velocity is low. This can lead, along with inaccurate coefficients or bad inertia values, to a "floaty" behaviour - objects seem to slide too much, as though in slow-motion. Avoid this by correctly modelling static friction whenever possible, and by ensuring your dynamic friction coefficients are close to reality as you can get without causing instability.

Types of Contact

I've so far discussed only one geometric type of contact - of a point and a surface. Many games only use this type, but to fully model your objects as polyhedra, you'll need edge-to-edge contacts as well. Then the contact direction N is determined by the cross product of the edge directions. Most of the derivations are a little more involved, but the same principles apply as above. You can also implement curved surfaces. For each contact type (sphere-surface, point-cylinder, I could go on) you'll need an expression for the line of the b matrix (or three lines if you're including static friction). Rolling contacts are particularly tricky for all but the simplest types.

Final Words

A good place to start could be an impulse-based system that only ever has one contact at a time. Once you're happy with that, try multiple contacts. With only one or two, you will be able to get away with using the matrix inverse. When you get to having fairly complex systems like the ragdoll, it's worth trying an iteration scheme.

For anyone serious about game physics, the place to go next is David Baraff's page [1], where you can download some of the major papers on the subject. Chris Hecker [3] offers a more game-centric summary and a good overview of the field.

You should now be well on your way to some rock-solid contact physics, though it's a perilous road. Some programmers have had good results with approximate methods, like the Verlet particle systems described in [4]. Alternatively, there are several middleware packages which effectively provide a plug-in solution for dynamics. Unless you find the cost prohibitive or really want to do something new in physics, these are well worth a look. Game graphics are fairly racing ahead, and if the physics we use can keep pace, creating new and captivating experiences for gamers should be well within our grasp.

References

[1] David Baraff's homepage: http://www.pixar.com/companyinfo/research/deb/

[2] David Baraff, "Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies", Computer Graphics, Volume 23, Number 3, July 1989.

[3] Chris Hecker's homepage: http://www.d6.com/users/checker/dynamics.htm

[4] Thomas Jakobsen, "Advanced Character Physics", Gamasutra Game Physics Resource Guide