Real-Time Physics Simulation Forum

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?

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?

Most popular (and unpopular) physics engines use iterative solvers.

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.

I think it is a little pretentious saying most popular and unpopular are using the same algorithm, how would you know that?

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.

Wasn't it safe to assumed Havok, PhysX/Novodex and ODE to be the most popular?

I agree with Erwin about the popularity.
I know physics engine could use anything except "direct" Lemke.
It's too slow and too generic.

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?

Um, dude - read what he said

I used to work for Havok, and currently I work for Sony on the Playstation 3 port of Novodex/PhysX.

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.

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

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.

Except our engine use a custimized version of PATH.
Let's wait and see how it compare to iterative solvers.

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 in-house 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 PGS-style 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 any-time soon?

- Michael Alexander Ewert

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

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.

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 16-bit floating point accuracy real-time simulations it just doesn't seem to work. My suspicion is that it might work well with double precision, as that is what the non-realtime cloth solvers use, with good results. I always wanted to try using PCG for rigid-body systems. Erin, did you try using double precision, and if so how did it compare to the single precision floats?

- Michael Alexander Ewert

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 16-bit floating point accuracy real-time simulations it just doesn't seem to work. My suspicion is that it might work well with double precision, as that is what the non-realtime cloth solvers use, with good results. I always wanted to try using PCG for rigid-body systems. Erin, did you try using double precision, and if so how did it compare to the single precision floats?

- 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/soft-rigid body simulator successfully both with single and double precision floating point accuracy.

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 non-realtime 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 on-the-fly 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 residual-error 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

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 non-realtime work. It is likely to be faster than a pivoting method (Lemke or Dantzig). In my experiments, GPCG benefited greatly from warm-starting. On the other hand, Lemke and Dantzig don't gain much from warm-starting (you still have to invert a matrix).