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.
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.
Big Blue Bubble Inc.
395 Wellington Rd, Unit 200
London, Ontario, Canada
Tel: +1 (519) 649-0071
Fax: +1 (519) 649-0072