Game Development Reference

In-Depth Information

where
f
known
is the set of forces and torques we know we are applying (forces due

to gravity or due to other force generators) and
f
contacts
is the set of forces that are

generated in the contacts, which is what we're trying to find out.

Most often you see the equation written as

J
f
contacts
+
¨

p
known
=
¨

p

[18.1]

(although it is often given with different symbols such as
J
f

a
). In other words,

the Jacobian is multiplied by the known force vector to get a known acceleration. This

relies on a fact of matrix multiplication that I haven't explicitly stated before—namely,

it is distributive. For any valid matrix multiplication,
A

+

b

=

×

(B

+

C)

=

A

×

B

+

A

×

C
.

p
known
is a step before contact resolution, because this value will not

change as we try to work out the contact forces.

On its own, equation 18.1 could be solved by working out the inverse of the Ja-

cobian (a time-consuming problem and one often without a solution). But to make

things worse we have an additional constraint:

Calculating

¨

0

f
contacts

r

where
r
is a vector of limits on how big the forces can be. Normal reaction forces can

be as large as they need to be, but friction forces are limited. A particular entry in the

force vector may represent a friction force and will therefore need to be limited.

The final calculation, finding
f
so that it fulfills both equations, is called the “lin-

earcomplementaryproblem”(orLCPforshort).Analternativeapproachtriestofind

the smallest possible values for the components in
f
contacts. This becomes an op-

timization problem called “quadratic programming” (or QP). Some physics systems

build and solve the QP, but it is more common to work with the LCP.

A commonly used algorithm for solving the LCP is called the “pivot algorithm.”

It works by making guesses for components in
f
and checking the results. The errors

from one set of guesses can be used to modify components one at a time and converge

at a solution. Under some assumptions that are commonly met in rigid body simu-

lations, the guesses will always converge toward the solution. The pivot algorithm

(based on an algorithm called the “Lemke pivot”) was popularized in rigid-body sim-

ulation by David Baraff: see Baraff and Witkin [1997] for a step-by-step introduction

to the approach.

Complications arise because of numerical instability and the approximation of

fixed-length time steps. It is possible (and not uncommon) for a rigid-body simu-

lation to end up in a physically impossible situation where there is no solution to

the LCP. In this case the pivot algorithm can loop endlessly. A robust implementation

needs to take account of these kinds of problems and provide alternatives. A common

alternative is to impose impulses when there is no valid force solution. But getting it

right while remaining efficient can be very difficult. In my experience (I have cre-

ated two pivot-based engines, one of some significant complexity) it is easy to get

s
omething working, but it takes months to end up with a general and robust engine.