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.