Handeling Unilateral Contact Constraints

[amacchietto]

It seems that there is a unanimous agreement that the best way to solve for contact forces is using Projected Gauss-Seidel. I've recently read the paper, Fast Contact Force Computation for Nonpenetrating Rigid Bodies by Baraff, and in it he proposes an algorithm for computing the contact forces which avoids the need for an optimization. What advantages does PGS have over this approach? The algorithm presented by Baraff seems easy enough to implement and, given the difficulty of finding resources that explain PGS, it seems preferable. Any thoughts or pointers to useful information?

[Dirk Gregorius]

Basically you have the choice between iterative solvers like Projected Gauss-Seidel (potentially implemented using sequential impulses) and direct solvers like e.g. Danzig or Lemke. The PGS solver is much softer than the direct solvers, but the iterative solvers are fast and easy to implement and *most* important can handle over-constrained system. This means that you can send any overconstrained configuration to the solver without the problem that the solver might fail. This is a huge advantage since in a game it is kind of hard to guarentee that the LCP is always solveable. You usually don't want to identify redundant contact points.

A common approach is to have an iterative solver with a stiff subsolver like e.g. Baraffs linear time solver. Mathematically this would be a Block Projected Gauss-Seidel. While it is kind of hard to guarentee that the whole system is always solveable, you can do this for specific sub-systems like for bilateral constraint hierarchies as e.g. found in a ragdoll. So you solve the full ragdoll using a direct solver and then iteratively solve the contacts, limits and motors. This can, but not necessarily does, improve the global solution. I did implement such a system a while ago, but I only see practiical need for it if you do want to do physics based animation. Practically I only solve linear and angular 3x3 subsystems of the 6x6 joint constraints as a block. This helps especially for the dreaded prismatic joint (slider).

Finally note that the Baraff paper is kind of outdated. In the paper Baraff solves on the so called acceleration level. Basically for every geometric (position) constraint you also have a velocity and acceleration constraint - sometimes called the hidden constraints. Think of a spherical joint (ball-socket) where you require that two points on each body should stay coincident. This also requires that the relative velocity and acceleration at these points vanishes, since otherwise the points would drift apart. More recent engines all solve on the velocity level applying impulses (this is what PGS basically does) since it is easier to implement and doesn't suffer from infinite friction forces.

If you search resources on PGS I recommend the presentations of Erin Catto ( http://www.gphysics.com ), the PhD of Kenny Erleben and I would also study the ODE Quickstep solver.


HTH,
-Dirk

[amacchietto]

Thanks for the input. Since I am using a reduced-coordinate parameterized rigid body system, I think I will have to implement unilateral constraints as described in "Practical Physics for Articulated Characters" paper using a PGS solver as you recommend.

In case you are wondering, I am trying to create a balance controller for a physically-simulated humanoid character. Currently, the algorithm works by first solving a least-squares optimization across the generalized accelerations of the character with acceleration constraints on the supports (0 for static ground): the assumption being that during statically stable motion the character has full control over all degrees of freedom and there should exist a combination of realizable ground forces and actuator torques which produce the desired accelerations. The optimization works by tracking motion while simultaneously regulating momentum change to achieve extra stability. Once the accelerations are determined, an inverse dynamics algorithm computes the actuator torques needed to achieve the optimized accelerations in the presence of penalty-based ground reaction forces. Finally, external forces and the actuator torques provided by the inverse dynamics are used in the forward dynamics. Basically, the system compensates for the ground and gravitation forces, while remaining reactive to external forces without solving a costly quadratic programming problem.

My current interest lies in removing the penalty-based ground model and solving for the actuator torques and ground reaction forces simultaneously, with the expectation that this should allow me to have more control over the contact forces generated by the foot. With the penalty-based approach I cannot generate all of the freedom that human feet exhibit and have limited control over the center of pressure.

Here are a few old examples of some of my work:
http://www.youtube.com/macchiea . I post this here in case anyone has any criticisms or advice of this approach.