Equivalence sequential impulses & Projected Gauss Seidel

Issues with the forum and all license/patent related discussion
Dirk Gregorius
Posts: 875
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

The advantages of the separate solver for tree-like structures with bilateral constraints are better performance but most of all the bilateral constraints are accurately enforced without being pulled apart due to typical numerical issues of other constraints (like too many or conflicting contacts)
Thanks for the reply! Maybe two simple questions regarding your solver:

1) You say that bilateral constraints are enforced more accurately. So you got rid of the "stretchy" constraints which are typical for the iterative solvers (e.g. PGS). I mean the problems Erwin mentioned:

"Typical scenario is a high speed car against a pedestrian, or a character standing next to a barrel (explosion)"

2) Did the solver give usable results for over-constraint system (e.g. to many or conflicting contacts). Are the scenarios when the solver may fail?


Vedran Klanac
Posts: 1
Joined: Fri Jul 29, 2005 1:25 am
Location: Zagreb, Croatia

Re: Equivalence sequential impulses & Projected Gauss Se

Post by Vedran Klanac »

Erin Catto wrote:So ODE got the PGS optimizations from Croteam. I wonder where Croteam got it from.

If you study the mathematics of PGS, you can find that they are equivalent to the sequential impulse algorithm of Mirtich. In the sequential impulse approach, the sparsity and auxilliary variables are implicit. The impulse method has low/high limits for friction so that's covered too.
Hi !

I just encountered on this post which was referenced in one of the posts on ODE mailing list and I can see that this message is directly addressed to me, but I obvioulsy missed it.

So here it goes. The question that you're posing here is where Croteam got the PGS method from. Well the answer is, from me. I developed quickstep method and whole Croteam's physics engine in general. The algorithm was later on contributed to ODE. It doesn't have anything to do with Mirtich method, as a matter of fact I didn't have a chance to read that paper when I was developing the method.

Background history, how quickstep method was developed is totaly different. The exact algorithm name is Gauss-Southwell, and it is special case of SOR and Gauss-Seidel inherently.

The main idea for the algorithm evolved from improved factorization method for direct Danzig solver that I developed also earlier. At specific point in my research I figured out that iterative scheme must be more effective and less time consuming for CPU per frame. Early versions of algorithm which would solve separately all equations in stacked matrix rather then calculating sparse matrix blocks proved to be the right way to go. If you go step by step and multiply just one row of constraint equation matrices, jacobians for source and destination body with inversed mass matrix, the one can see that A matrix becomes a scalar. And all you have to do is go through the stacked matrix and perform bunch of divisions and clamp result value inside lo and hi limits. It is simple as that. I did it in first place on the piece of paper in a form of proof.
I must say that several e-mails from Mr. Richard Tonge on ODE mailing list were very resourceful to guide me towards iterative scheme.

Everything fell in its place when I read Murtay's book on iterative LCP solvers. First I implemented SOR and later on it turned out that omega factor for SOR which fit best solution convergence was 1, and that is exactley the value which makes SOR being Gauss-Seidel method. Gauss-Southwell method is different in a way that you don't calculate new solution in every frame from the beginning, but you actually maintain error of the solution and thus save some CPU time.

That's how quickstep method came to the day of light. The whole thing happened in april 2004, few months later we contributed method to ODE.

Vedran Klanac
Lead Programmer
Big Blue Bubble Inc.
395 Wellington Rd, Unit 200
London, Ontario, Canada
N6C 5Z6
Tel: +1 (519) 649-0071
Fax: +1 (519) 649-0072
Posts: 57
Joined: Sat Oct 08, 2005 1:16 am
Location: Itinerant

Post by mewert »

I arrived at the same optimization by staring at the equations after implementing the solution as a sparse southwell relaxation solver also. It's easier to see the factorization that leads to the quick-step optimization with southwell relaxation, I think.

Regarding Mirtich, you need to read the section of his paper on micro-collisions. You will end up with a solver that looks very similar to an impulse-based Mirtich micro-collision solver if you use the velocities of the rigid-bodies as your "auxiliary variable", rather than as a modification of the error term. I use the term Auxillary variable from the posted patent. A micro-collision solver iterates a number of times on a system of contact points, applying impulses until an error threshold in the relative velocities is reached. Your jacobians ( they are not always explicit in a micro-collision solver ) are constructed from the collision equations ( conservation of momentum, etc. ). The Jacobians for a LCP solver are formulated to satisfy the principle of virtual work and least constraint. I haven't sat down and worked it out, but I wouldn't be surprised if; in the case of an inelastic collision, the jacobians of both methods are identical.

- Michael Alexander Ewert
Dirk Gregorius
Posts: 875
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

I just read the PhD thesis of Rober Bridson who is one of th authors besides Eran Guendelman. Actually the authors themselves identified their algorithm as some variation of the Gauss-Seidel method:

From the PhD (Page 6):

"It was also observed that this
procedure can be interpreted loosely as a Gauss-Seidel iteration for solving the nonlinear equations
of an implicit time integrator using a more realistic biphasic model of cloth forces."

This quote is from their Cloth simulation algorithm, but since the Rigid Body Simulation is based upon the work this will hold there as well.

Later (Page 49) - now in the context of rigid body simulation:

"That is, all the non-interpenetration constraints at
contacts can be viewed as one large system of equations, and processing them one at a time is similar to a slow Gauss-Seidel approach to solving this system."

For those interessted the thesis can be downloaded here. Unfortunately the rigid body part seems to be a one to one copy of the original Siggraph paper:



Edit: Changed link
Posts: 85
Joined: Sun Jan 07, 2007 4:29 pm
Location: Oxford, England

Post by DannyChapman »

Erwin Coumans wrote:
It is typical to mix a direct LCP solver with iterative method. Especially high speed Ragdolls don't behave well on impact, their limbs detach. Typical scenario is a high speed car against a pedestrian, or a character standing next to a barrel (explosion). I've seen this in a game I worked on in the past, and we used Featherstone for the ragdolls, and impulse based for contacts.
Apologies for opening an extremely old thread! However, I thought I'd mention that if you reconstruct the animated character skeleton from the ragdoll using relative angles between ragdoll limbs then even if the physical ragdoll limbs separate temporarily, then the animated character won't visibly stretch.

For example, measure the rotation of the lower arm limb in the ragdoll around the elbow hinge joint. Then apply this same angle to the corresponding joint in the skeleton. So long as the additional joints in the skeleton have been relaxed back to some default value that was used during ragdoll setup, and the ragdoll has been set up to match its joints against the skeleton joints correctly, then the physical/rendered characters will match perfectly when the physical ragdoll joints do not detath. This will be the case during all situations where things aren't moving much (i.e. when the viewer can inspect things).

Under hard collisions if the ragdoll joints detach then (a) it will only be for a few updates (b) it only tends to happen when things are moving really fast and (c) the visible effect will simply be that the rendered limb is orientated slightly incorrectly (i.e. different to the ragdoll) - in the worst case resulting in a temporary visible (but likely invisible!) intersection with the environment.

This lets you get away with only a few iterations per joint - not only cheap, but the inaccuracy means that the resulting ragdoll actually looks more organic than a perfectly simulated set of limbs+hinge-joints.
Antonio Martini
Posts: 135
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

DannyChapman wrote: Under hard collisions if the ragdoll joints detach then (a) it will only be for a few updates (b) it only tends to happen when things are moving really fast and (c)
at very high speeds like a collision of a car at over 100mph against a pedestrian the stretching can be quite a lot. And nobody want to see awful things even for a few frames. Suppose you see some bad stretching "only" for a few frames, now suppose that you run over 10 pedestrians in a row, those few frames multiplied by the number of pedestrians will become many frames.

Posts: 1
Joined: Thu Aug 18, 2011 9:07 am

Re: Equivalence sequential impulses & Projected Gauss Seidel

Post by scarlett45 »

Thanks for letting me know about other good stuff !
Posts: 2
Joined: Mon Aug 22, 2011 7:31 am

Re: Equivalence sequential impulses & Projected Gauss Seidel

Post by Jinky »

You have just posted a bunch of useful stuff that I never known about it before. Thanks for sharing it. I could fix my challenge:)
Post Reply