Erin Catto wrote:In practice, no one wants to make high stacks of boxes, so 5 iterations of PGS is good enough. PGS prefers systems where the heaviest bodies are touching ground and the bodies get lighter as they branch out via joints and/or contacts. We use this as a design constraint.
Diagonalization of the system matrix can solve the problem of large mass ratio's (at a peformance cost, of course).
Erin Catto wrote:Shock propagation can solve this but leads to bad artifacts. Stacks become too stable and will arch over into impossible configurations.
This is true, Guendelmann et. al refered to this as a ``weight feeling'' problem. In my preliminary work I tried to solve this by a weighting of a full dynamics update step and one step using shock-propagation. It do solve the problem, but comes with two disadvantages: You get one parameter more to tune and the time-step is a little more expensive to perform (compared to doing PGS with 5 iterations).
There are other benefits one can gain from shock-propagation. It can basically be explained as a perfect way to turn GS into a blocked GS with a perfect ``directional'' preconditioner. By directional I mean that values can only change in one direction (upwards).
In fact shock-propagation partitions the problem into several smaller independent problems eventhough you only have one big contact group. It is thus possible to use direct methods for these small partitions and still get high performance.
From my viewpoint the biggest problem with shock-propagation is the stack-layer analysis that needs to be performed. It requres some book-keeping and a good computational cheap method to determine which contacts that would be violated and in which direction they would be violated. I used a breadt-first traversal on the contact graph to do this analysis. Tt is very fast and deals with most cases in a graceful manner, it is although not perfect.
Erin Catto wrote:About position projection. I tried this, but I still had to scale the position error by a Baumgarte type of parameter to avoid overshoot and loss of contact (leading to jitter). I found it to be more efficient to use a small Baumgarte parameter during integration and just live with errors being resolved over a few steps.
In my experience stabilization is good to deal with small errors. Projection methods are good to deal with large errors. Large errors seem to make things explode when using stabilization. I never had to scale my projections and I never experienced problems with overshooting.
Erin Catto wrote:Another possibility is to develop a projected conjugate gradient algorithm. Has anyone tried this yet?
This is well described in litterature and I think ODE have an implementation of a projected conjugate gradient (PCG). Most people I have talked with have reported that PGS has worse performance than PGS or PSOR. I must admit I have not fully understood why? Theoretically PCG should have quadratic convergence, so it should be better than GS and SOR, which have linear convergence. The cost per iteration should be equivalent.
Personally I believe that Newton methods and interior point methods will be the next kind of solvers that people in academia will try to use for computer graphics. Lacousiere did a comparision study of different types of solvers. The results were published in SIGRAD 2003. As I recall he found that the Keller method ( a direct method) were the best.