Possible optimization for dynamic Pyramid OBB stacking scene

[XperienS]

Iterative Solver ( SOR-PGS, 15 iterations with W = 1.1, convergence-testing ), optimized matrix calculations ( i.e. using matrice sparsity ) and contact joints caching. But all it handles only pyramid with 10 OBBs in basement. Collision broad phase is via bounding spheres intersection tests. Is there anything that could rise performance of my engine ( on this scene )?
Dividing total matrix A on contact groups in this case have no point because all of the cubes connected with contact joint.

[Dirk Gregorius]

Do you use iterative impulses or a PGS method? BTW I suggest using w_sor = 1.0 otherwise you might add energy to the system. I am sure you know that for the case w_sor = 1.0 is SOR equivalent to PGS.

I assume for now you use PGS like solver like in the ODE. What do you solve for? The ODE tries to solve for the constraint forces:

J*W*JT*lambda = -ERP * C / dt2 - J*( v/dt + w*f_ext )

You could reformulate this and solve for impulses instead what might be a little faster since you can integrate forward in time without considering the constraints, compute the correcting impulses, apply those impulse and integrate the positions using the corrected velocities:

J*W*JT*(lambda*dt) = -ERP * C / dt - J*( v + w*f_ext*dt)

Still this this would be slower (and has most propably worse convergence) then using impulse because you implictly solve blockwise. Assume one single spherical joint. With the above method you will need to compute the impulses using:

P = JT * lampda

The contains redundant information since you will compute P1, L1 = r1 x P1, P2 and L2 = r2 x P2 instead of simply applying the computed impulse at the anchor point. You don't use that P2 = -P1 in this case. You also solve blockwise when using impulses what would equivalent to a blockwise PGS which has superior convergence.

Finally one side note. Pyramids and walls are more stable then simple stacks. I suggest stacking 5 boxes (1x1x1) with a mass of 1kg falling down onto each other (preferable also rotated against each other). I checked the method of E. Catto a while ago and this can be handled with one iteration using the accumulated impulse and warmstarting. He also suggest applying the friction at the manifold center instead at each contact point what gets you down from 12 to 7 constraints for a face-face contact and what is a nice improvement as well (I would say both in speed and quality).

HTH,
-Dirk

[XperienS]

I'm using PGS, not impulses and w value 1.1 is for faster convergence. Energy gain is possible, but it is a little bit faster than classical PGS algo..
Solving for impulses, not for constraint forces is not much faster ( adds about 2 fps to my scene ) but it digs right into simulator basics so it is not preferable way
I'm interested in so-called "warm starting". What is it and why it should add performance or stability in my solver?

P/S: i've always thought that ODE uses direct solver ( something like Dantzig or Lemke ), not iterative ones..

[Dirk Gregorius]

adds about 2 fps to my scene

Take what you get

but it digs right into simulator basics so it is not preferable way

What do you mean by this? Can you give an example?

I'm interested in so-called "warm starting"

Warm-Starting means to use your results from the last frame as starting value for the next frame. Basically you save your lambdas and use them in the next frame instead of reseting them to zero. See Erin presentations for ideas how to match contact impulses over frames

i've always thought that ODE uses direct solver

The ODE has a direct solver, but in quickstep.cpp you have an iterative (PGS) solver

[XperienS]

What do you mean by this? Can you give an example?

It's not for some examples it is for idea I need my simulator to be force-based, not impulse-based [ and remember that this change adds quite small amount of fps to scene ], so this optimization is not needed for me.

About warm starting: sorry i'm confusing terminology and now i understand that warm starting is simple caching lambda values. In this case i have warm starting, yes.

[Dirk Gregorius]

Since forces and impulse are linear related - we assume the forces to be constant over the interval dt. You still could compute the force from the accumlated impulse. It is simply F = P/dt

I recommend looking at ODE quickstep.cpp and joint.cpp and see if you can find some clever optimization there that you maybe missed in your code.

HTH,
-Dirk

[XperienS]

Ok, thanks for your replies