Real-Time Physics Simulation Forum

Re: Position Correction

2008-01-05T04:20:43+00:00

Hi all, I also experimented with constraint ordering for rigid body problems some time ago, but I never found a method that was noticably better than random ordering. Multiple iterations tend to smoothen out the difference a lot. Consider four iterations. The difference (in terms of dereferenced body velocities) is not huge:

C(0,1) C(2,3) C(1,2) C(0,1) C(2,3) C(1,2) C(0,1) C(2,3) C(1,2) C(0,1) C(2,3) C(1,2)
C(0,1) C(1,2) C(2,3) C(0,1) C(1,2) C(2,3) C(0,1) C(1,2) C(2,3) C(0,1) C(1,2) C(2,3)

Cheers,
Dennis

i believe that if there is an optimal ordering(why not?) surely real-time rigid bodies would not benefit from it for the the following reason:

the only large systems are typically stacks of objects with a highly varying connectivity. So the optimal sequence would not be computable in real-time.

then you have also multiple iterations for Jacobi but we know that GS is better for most cases. What you gain/loose in one iteration is propagated to multiple iterations i suppose.

so clothes and tetrahedral meshes with a fixed topology would be the field of application. Here we have many constraints in the order of thousands and so the difference maybe noticeable especially if the optimal ordering is compatible with the architecture we are implementing it on.

cheers,
Antonio

Statistics: Posted by Antonio Martini — Sat Jan 05, 2008 4:20 am

Re: Position Correction

2008-01-04T18:01:39+00:00

Hi all, I also experimented with constraint ordering for rigid body problems some time ago, but I never found a method that was noticably better than random ordering. Multiple iterations tend to smoothen out the difference a lot. Consider four iterations. The difference (in terms of dereferenced body velocities) is not huge:

C(0,1) C(2,3) C(1,2) C(0,1) C(2,3) C(1,2) C(0,1) C(2,3) C(1,2) C(0,1) C(2,3) C(1,2)
C(0,1) C(1,2) C(2,3) C(0,1) C(1,2) C(2,3) C(0,1) C(1,2) C(2,3) C(0,1) C(1,2) C(2,3)

Cheers,
Dennis

Statistics: Posted by Dennis — Fri Jan 04, 2008 6:01 pm

Re: Position Correction

2007-12-20T00:42:32+00:00

I found that using a stability factor caused some bad artifacts when simulating non-trivial cloth. So I left it out. For console performance we were getting killed by load-hit-stores. This is caused by reading from a vertex that has just been changed ( still on it's way to being stored in the cache ). Which is what accessing your mesh serially will do. So we ended up trying to randomize our vertex access as much as possible. How quickly optimization strategies change with new hardware!

Statistics: Posted by mewert — Thu Dec 20, 2007 12:42 am

Re: Position Correction

2007-12-06T19:22:41+00:00

Ahh. Yeah, for cloth constraint ordering can make a big difference, especially if you use a stability factor as in Andrew Megg's cloth presentation.

https://www.cmpevents.com/GD05/a.asp?op ... essID=3931

Statistics: Posted by Erin Catto — Thu Dec 06, 2007 7:22 pm

Re: Position Correction

2007-12-06T18:51:10+00:00

When I was studying constraint ordering, I would simulate a stack of boxes or a chain and export the MLCP to a text file and load it into Matlab. It was quite easy to try different orderings and measure convergence. You may get better results, but the best I could do was shave off one iteration.

i was thinking more about clothes and tetrahedral meshes, for rigid bodies i dont see many large systems with a fixed topology, usually chains and bridges are already arranged in a optimal way by construction i believe and as they are serially connected there are not many combinations available to be explored, just the bad ones:) then also for clothes and solids it could well be that there is not that much to be gained, however saving a couple of iterations by just rearraging the data is already a good result.

cheers,
Antonio

Statistics: Posted by Antonio Martini — Thu Dec 06, 2007 6:51 pm

Re: Position Correction

2007-12-06T18:16:18+00:00

When I was studying constraint ordering, I would simulate a stack of boxes or a chain and export the MLCP to a text file and load it into Matlab. It was quite easy to try different orderings and measure convergence. You may get better results, but the best I could do was shave off one iteration.

In my experience the performance killer for constraints is cache misses. Random access to constraints can be eliminated, giving a huge performance gain. As far as I can tell, random access to body state data (position, velocity) can not be eliminated.

Statistics: Posted by Erin Catto — Thu Dec 06, 2007 6:16 pm

Re: Position Correction

2007-12-05T16:42:20+00:00

I tried the several algorithms for position correction of Box2D’s revolute joint.
...
interesting comparisons, if i read it correctly they are also consistent with what intuition suggests, the more up to date the used information is(effective mass, positions, jacobians etc...) the better the solution behaves.

cheers,
Antonio

the idea of using the most up to date information is as we know also the difference between a Jacobi iteration and a GS iteration. A jacobi solver uses only information from the previous iteration when solving for a new variable.
Now let's say we start with a square cloth having many constraints and at each iteration we pick and solve constraints at random(like it has been suggested in the past) accordingly to a uniform distribuition. Given that the distribuition is uniform it's very unlikely that initially we will pick nearby constraints and so when we solve for the first n constraints we will be very likely use only values from the previous iteration. So as a matter of fact it would look more like a Jacobi style solution in the initial stage. This fact alone would seem to suggest that picking constraints at random isn't a good idea after all.

a constraint joining bodies B0 and B1 for can be written C(0,1)

for simplicity let's build a chain made of 5 bodies:

B0,B1,B2,B3,B4,B5

and constraints:

C(0,1), C(1,2), C(2,3), C(3,4), C(4,5)

if we solved the above constraints in the given order it would be a GS style solution, we also know that a Jacobi solver uses only the information from the last iteration, so if we change the order of solving as follow for example:

C(0,1), C(2,3), C(4,5), C(2,3), C(1,2), C(3,4)

we see that the first 3 constraints use no "fresh" information, if we just rename the indices of the constraints we can see that 3 constraints are Jacobi style steps with 3 GS style steps. Luckily chains are usually built serially so it's very unlilkely that we have that order. However for Ragdolls, clothes, tetrahedral meshes it maybe very different. so what's the optimal sequence? in general a body can be connected by n contraints to other bodies(or particles), let's say we add a counter n_i for each body i, everytime we solve a contraint connected body i we increase n_i , so a mesaure of how up to date the information for that body is can be defined by:

f(i) = n_i/max(n_i) ( max(n_i) = maximum number of connected constraints to body i)

so when the body is fully updated f(i) = 1 when it's using only "old" information(and so Jacobi style) is equal to zero.

so when choosing the next optimal constraint to solve for we should aim at picking the constraint C(a,b) with maximum g(a,b) = f(a)*f(b). Note that f(i) can be interpreted as a linear fuzzy membership function and "*" can be seen as a fuzzy AND operator.see also:

http://www.atp.ruhr-uni-bochum.de/rt1/s ... de118.html
http://www.atp.ruhr-uni-bochum.de/rt1/s ... de117.html

so we pick and solve the constraint that connects the 2 most up to date bodies(or particles)
However this choice could be only locally optimal, a global solution could be the one of finding a constraints ordering that minimise the sum of all g(i,j) for a single iteration (there is one g(i,j) for each contraint). for a fixed connectivity(ragdoll, clothes, volumes) this could be done offline.

i haven't got a chance to try this method yet so take it more as an idea rather than a solution, however i would be curious to see what kind of difference it would make, especially for highly connected systems with a fixed topology like clothes or tetrahedral meshes...

cheers,
Antonio

Statistics: Posted by Antonio Martini — Wed Dec 05, 2007 4:42 pm

Re: Position Correction

2007-11-05T00:26:01+00:00

I tried the several algorithms for position correction of Box2D’s revolute joint.
...

interesting comparisons, if i read it correctly they are also consistent with what intuition suggests, the more up to date the used information is(effective mass, positions, jacobians etc...) the better the solution behaves.

cheers,
Antonio

Statistics: Posted by Antonio Martini — Mon Nov 05, 2007 12:26 am

Re: Position Correction

2007-11-04T23:49:03+00:00

Erwin,

You raise a good point. My discussion has mainly centered on joints, not on contacts.

1) The split impulse method (aka Pseudo Velocities, aka First Order World) seems to work well for contacts. But the method is worse than Baumgarte for joints. NGS is my favorite method for joints (so far), but I don't have a favorite method for contacts. That is an issue I'll leave for another day.

2) With the demos you can do this. I set the period to 120Hz. The Baumgarte and Pseudo Velocity solvers were no better or worse on the Bridge. You should try this yourself using the GUI.

3) Gino's position correction algorithm is a stripped down NGS. The algorithm doesn't consider mass, rotation, or Lagrange multipliers. The algorithm only projects translations.

Gino's velocity solver is a stripped down sequential impulse algorithm. It doesn't use warm starting or accumulate impulses for clamping. The basic structure seems okay (not sure about the backup part).

What is your motivation for this comparison Erwin? Did you notice some interesting qualities in Gino's solver? (I haven't run the demos).

Statistics: Posted by Erin Catto — Sun Nov 04, 2007 11:49 pm

Re: Position Correction

2007-11-04T22:53:16+00:00

minor point:
It appears the Solid library's physics example just translates rigid bodies to deal with penetration. i.e. no rotation. There could be situations where some rotation is required to remove penetration. Imagine a dynamic box between two walls where the box somehow got rotated and is penetrating the walls on both sides. See attached picture. If the walls and box aren't spinning/moving, there is nothing to encourage the velocity part of the solver to reorient the box. In contrast any of the solutions that work at the contact points (fire an impulse along the contact normal or whatever) will correct this case.

Statistics: Posted by melax — Sun Nov 04, 2007 10:53 pm