Which LCP's solver have been used by popular physics engine?
Which LCP's solver have been used by popular physics engine?
I have written a small physics engine which use Lemke's algorithm to solve Lcp,but it so slowly. I wanna to know which algorithm are used by popular physics engine such as Havok ,Novedex.is it a iterative solver?
 Erwin Coumans
 Site Admin
 Posts: 4232
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
Re: Which LCP's solver have been used by popular physics eng
Most popular (and unpopular) physics engines use iterative solvers.jiangwei wrote:I have written a small physics engine which use Lemke's algorithm to solve Lcp,but it so slowly. I wanna to know which algorithm are used by popular physics engine such as Havok ,Novedex.is it a iterative solver?
With respect to Novodex, check out this paper:
http://bulletphysics.com/ftp/pub/test/p ... exSDK4.pdf
Check out this thread, is links sequential iterative impulse based solution to PGS: http://www.continuousphysics.com/Bullet ... .php?t=208
I think it is a little pretentious saying most popular and unpopular are using the same algorithm, how would you know that? You only presented vague slides from a presentation that does not say anything definitive one way or another.
You seem to have made your mind on engine comparison, so I am curious as which one are the popular engine and which one are the unpopular, I am guessing that Bullet and ODE are among the popular.
You seem to have made your mind on engine comparison, so I am curious as which one are the popular engine and which one are the unpopular, I am guessing that Bullet and ODE are among the popular.
 Erwin Coumans
 Site Admin
 Posts: 4232
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
I used to work for Havok, and currently I work for Sony on the Playstation 3 port of Novodex/PhysX. Then ODE has some iterative solvers too. That's how I know popular physics engines use iterative solvers. This doesn't mean they use the same algorithm, there are tons of algorithms for iterative solvers. The Novodex link was just to show some public information about this.I think it is a little pretentious saying most popular and unpopular are using the same algorithm, how would you know that?
Wasn't it safe to assumed Havok, PhysX/Novodex and ODE to be the most popular?
Again it is not a matter of agree or disagree.
Unless you guys have seen the source code and can confirm the fact by releasing the code, which will be a very dishonest act, it is a speculation.
I think you can say that Bullet and ODE are using that same iterative solver, and you think that other engines may be using iterative solver as well but you people have not idea what they are doing, for all I know other engines may be using exact LCP, and there is not way you can prove otherwise, can you?
Unless you guys have seen the source code and can confirm the fact by releasing the code, which will be a very dishonest act, it is a speculation.
I think you can say that Bullet and ODE are using that same iterative solver, and you think that other engines may be using iterative solver as well but you people have not idea what they are doing, for all I know other engines may be using exact LCP, and there is not way you can prove otherwise, can you?

 Posts: 58
 Joined: Sun Jan 22, 2006 4:31 am
Um, dude  read what he said
Given all the people commenting on the fact are actually developers with access to the code  I reckon they know what they're talking about.
So unless there is an implication of dishonesty  I think the matter is resolved.
EK
In other words  he KNOWS that Havok at the very least USED to use an iterative solver, and that Novodex/PhysX actually does. ODE we know uses it and comments from the author of Newton on this board indicate it does too.I used to work for Havok, and currently I work for Sony on the Playstation 3 port of Novodex/PhysX.
Given all the people commenting on the fact are actually developers with access to the code  I reckon they know what they're talking about.
So unless there is an implication of dishonesty  I think the matter is resolved.
EK

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Well, the Novodex API is publicly available and it lets you configure the number of iterations. Many people in the game industry have seen the Havok API and I understand that it lets you configure the number of iterations. And so did Meqon.
Of course it could all be a hoax. They could take the iteration specification and ignore it while they use a direct LCP solver.
Here's an experiment you could do. Download PhysX (was Novodex) and simulate a stack of boxes. Measure how the CPU cost increases with the number of boxes. If it grows linearly then it's likely to be an iterative method. You could also try varying the iteration specification to see if the cost grows linearly with the iterations.
Of course it could all be a hoax. They could take the iteration specification and ignore it while they use a direct LCP solver.
Here's an experiment you could do. Download PhysX (was Novodex) and simulate a stack of boxes. Measure how the CPU cost increases with the number of boxes. If it grows linearly then it's likely to be an iterative method. You could also try varying the iteration specification to see if the cost grows linearly with the iterations.
Every popular physics engine I've seen that can handle large(ish) stacks of objects has used a PGS iterative solver. This includes middleware, open source and inhouse game engines.
I'm interested in knowing how other techniques work. PGS is nice, but it requires some tuning and hacking to make it artifact free.
ngbinh, could you elaborate a bit on PATH? Or a link to some docs?
The author of Newton has stated he is not using an iterative PGSstyle solver: "..deterministic solver, which is not based on traditional LCP or iterative methods, but possesses the stability and speed of both respectively" You've got my attention Anyone have any idea what he's doing? Mr Jerez ( if you read this ), are you planning on publishing info on it anytime soon?
 Michael Alexander Ewert
I'm interested in knowing how other techniques work. PGS is nice, but it requires some tuning and hacking to make it artifact free.
ngbinh, could you elaborate a bit on PATH? Or a link to some docs?
The author of Newton has stated he is not using an iterative PGSstyle solver: "..deterministic solver, which is not based on traditional LCP or iterative methods, but possesses the stability and speed of both respectively" You've got my attention Anyone have any idea what he's doing? Mr Jerez ( if you read this ), are you planning on publishing info on it anytime soon?
 Michael Alexander Ewert

 Posts: 58
 Joined: Sun Jan 22, 2006 4:31 am
OK, I think the trick here is to look at the exact wording... "not based on traditional LCP or iterative methods". This does not necessarily imply that he is not using LCP or iterative methods  just that he is not using the traditional ones.
For example, he has stated in these boards that Newton DOES use LCP. Remember when reading "marketting" text, you must be very careful to read ALL the words used
EK
For example, he has stated in these boards that Newton DOES use LCP. Remember when reading "marketting" text, you must be very careful to read ALL the words used
EK

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
It turns out that LCPs are equivalent to quadratic programs (QPs). You can use conjugate gradients (GPCG) to solve QPs accurately.
I set up such a solver and was able to make very tall (~50) vertical stacks of boxes. However, I got sporadic velocity spikes if I terminated the iterations early. Also, the number of iterations required could be high (~100).
That's the advantage of methods like PGS, the velocity errors decrease uniformly.
I set up such a solver and was able to make very tall (~50) vertical stacks of boxes. However, I got sporadic velocity spikes if I terminated the iterations early. Also, the number of iterations required could be high (~100).
That's the advantage of methods like PGS, the velocity errors decrease uniformly.
Conjugate gradient methods are typically used for solving implicit cloth systems. We had very little luck with that approach. Seems the CG solver would start diverging and give us large velocity spikes. CG is so often referred to as the best way to solve a PSD system, but in 16bit floating point accuracy realtime simulations it just doesn't seem to work. My suspicion is that it might work well with double precision, as that is what the nonrealtime cloth solvers use, with good results. I always wanted to try using PCG for rigidbody systems. Erin, did you try using double precision, and if so how did it compare to the single precision floats?
 Michael Alexander Ewert
 Michael Alexander Ewert
Unlike a direct solver, PCG is a method for solving system of equations in the form of Ax = b iteratively, thus allowing for fast convergence in many cases. In the computer graphics community it is well know to be used as a solver for soft body simulations (cloth etc..), but it can be used to solve other problems too. Personally i use it for my commercial cloth/softrigid body simulator successfully both with single and double precision floating point accuracy.mewert wrote:Conjugate gradient methods are typically used for solving implicit cloth systems. We had very little luck with that approach. Seems the CG solver would start diverging and give us large velocity spikes. CG is so often referred to as the best way to solve a PSD system, but in 16bit floating point accuracy realtime simulations it just doesn't seem to work. My suspicion is that it might work well with double precision, as that is what the nonrealtime cloth solvers use, with good results. I always wanted to try using PCG for rigidbody systems. Erin, did you try using double precision, and if so how did it compare to the single precision floats?
 Michael Alexander Ewert
PCG work well only if your system matrix is square and positive definite, maybe this is the cause of your divergence.
Using PCG for rigid body simulations seems to be not a good idea for realtime applications, unless in your simulator you entrap into some sort of stiff constraints (e.g. springs), but i dubt that it can be of help if there are only few of them.
Due to the nonrealtime nature of my simulator (and taking into account that everything should interact with everything) i use PCG for all (rigid body too) and still there cases where it can fail or just give unplausible results, but i implemented an onthefly solver switching ability that can handle this.
Generally, using 16 bit floating point accuracy can cause more error accumulation, but depending on the size of your system this can be correctly handled by using some sort of adaptive residualerror control in the PCG's solver loop.
Using double precision floating points accuracy will help in the stability area but give less perfomance.
Hope this can be of help.
Carlo Lanzotti

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
To be clear, I used a gradient projection + conjugate gradient algorithm (single precision only) to solve the constraint equations for rigid body simulation. The gradient projection is used to determine the active set of constraints and conjugate gradient is used to minimize the quadratic cost function on the active set. So this is a bit different then using CG to solve a stiff cloth system.
GPCG seems good for nonrealtime work. It is likely to be faster than a pivoting method (Lemke or Dantzig). In my experiments, GPCG benefited greatly from warmstarting. On the other hand, Lemke and Dantzig don't gain much from warmstarting (you still have to invert a matrix).
GPCG seems good for nonrealtime work. It is likely to be faster than a pivoting method (Lemke or Dantzig). In my experiments, GPCG benefited greatly from warmstarting. On the other hand, Lemke and Dantzig don't gain much from warmstarting (you still have to invert a matrix).