Real-Time Physics Simulation Forum

When there are many constraints, we can solve them one by one iteratively until getting the converged result. In other way, we can assemble those constraint into a sparse matrix and treat it as an over-determined problem.

In physics simulation, the iteration method seems popular. However, the convergence speed of iteration method may be slow. If I treat it as a over-determined problem, I can get the best solution by solving this over-determined problem immediately. What's the difference between those two methods?

I think you've highlighted the main advantage of direct solving.

One downside, however, is that it is not simple to directly solve certain types of constraints, in particular collision and friction with their limits. So you need an MLCP solver. If this has ever been combined with a sparse matrix solver, I'm not aware of it. So then you might need a 'full' matrix, which uses O(n^2) space and takes O(n^3) time to solve, a major problem when you have lots of constaints.

Solving iteratively can be dead simple - you just do one constraint at a time. No need to have matrix-ready data or anything. The constraints can be complicated and non-linear (although both that and limits may hinder or outright prevent convergence, IIRC, although I've yet to run into that particular problem). And while you will never get the 'exact' answer, you can get a 'good enough for games' answer faster than you might with a direct matrix solver.

bone wrote:I think you've highlighted the main advantage of direct solving.

One downside, however, is that it is not simple to directly solve certain types of constraints, in particular collision and friction with their limits. So you need an MLCP solver. If this has ever been combined with a sparse matrix solver, I'm not aware of it. So then you might need a 'full' matrix, which uses O(n^2) space and takes O(n^3) time to solve, a major problem when you have lots of constaints.

Solving iteratively can be dead simple - you just do one constraint at a time. No need to have matrix-ready data or anything. The constraints can be complicated and non-linear (although both that and limits may hinder or outright prevent convergence, IIRC, although I've yet to run into that particular problem). And while you will never get the 'exact' answer, you can get a 'good enough for games' answer faster than you might with a direct matrix solver.

Thank you for your detailed explanation. If I solve all constraints iteratively, I think the order to solve those different constraints has great impact on the convergence rate, isn't it? Is there any topic concentrate on this?

Yes, that can have a significant effect in some cases, for example when stacking boxes. Various people have tried various orders with varying success. As a start, you might search for 'shock propagation' which I think was originally proposed by Guendelman.