Resource Guide

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. Two points, or one edge, are now touching the ground.

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 Stability

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2002 CMP Media LLC

privacy policy | terms of service