Hi, I am implementing a physics demo, I am trying to base it on the 'Nonconvex Rigid Bodies with Stacking' paper by Eran Guendelman http://www.cs.ubc.ca/~rbridson/docs/rigid_bodies.pdf I have acheived a simple simulation with no friction or stacking, just a box bouncing on the floor and jittering and sliding on the ground. I want to implement the same simulation loop as in the paper but am a bit confused about some of the steps and was wondering if anyone had implemented it and could help? From what I understand the simulation is as follows 1) Apply External Forces 2) Save the Velocitys (angular and linear) and positions (and orientation) 3) Integrate to Velocitys and Positions 4) Check for collisions and store collision point data (normal etc...) 5) Apply elastic impulses at collision points 6) Restore velocitys and position 7) Check for contacts and store contact point data (normal etc...) 8) Apply inelastic impulses at contact points 9) update new position 10) reset forces In the paper it says you need to iterate a few times over the collision and contact points which I dont understand. If anyone can clear this up or offer suggestions to improve my above step back step algorithm above I would be very grateful. Thanks in advance Pot

Quote:
5) Apply elastic impulses at collision points
6) Restore velocities and position

But if you restore your velocities at stage 6 how could stages 1-5 affect the simulation?
In the collision stage you change the original velocities of the objects (that is the velocity that you had before stage 3),

Try this instead:
1) Apply External Forces
2) (x,v) <- Get state
3a) v' <- Integrate velocity from (x,v)
3b) x' <- Integrate position from (x,v')
4) Detect collisions at (x')
5) v <- Iteratively apply elastic impulses to v.

6) Optionally return to stage stage 3. (this concerns your question about iterative collision processing)

7a) v' <- Integrate velocity from (x,v)
7b) x' <- Integrate position from (x,v')
8) Detect collisions at (x')
9) v'' <- Iteratively apply inelastic impulses to v'

10) (x') <- Integrate position from (x,v'')
11) (x',v'') -> Store state
12) reset forces

Note: This is not the full version of the algorithm proposed in the paper. It still lacks shock propagation and iterative contact resolution.

Let's see what happens at stage 5.
During the collision detection at stage 4 we found a set of pairs.
At each pair we measure a relative velocity urel and a normal n.
A pair is said to be non-separating if urel.n < 0, that is the bodies are moving towards each other at the collision point.
At stage 5 we'd like to turn all non-separating pairs into separating pairs, that is, make the bodies go apart at those points. Since we apply correction impulses at each pair at a time, fixing one pair does not mean that the rest are fixed.
The problem is even worse, making one pair non-separating can turn a separating pair into a non-separating one.
This is why they perform their "aggressive optimization" iteratively.

Consider an example: We have a table falling and hitting the floor with all of its legs.
Lets assume that although each table leg registered a collision with a floor only one of the legs is non-separating.
If we apply an impulse on the non-separating leg, we can suddenly turn the other three to be non-separating as well.
(You can easily repeat the experiment at home :))

This problem can be solved iteratively (aka aggressive optimization):

a: Store colliding pairs in the list
b: Find deepest non separating pair
c: Fix the deepest pair (this adjusts the velocity of the affected bodies)
d: Remove all separating points from list
e: If list is not empty go to step b (step b will use the adjusted velocity from step c)

Unfortunately sometimes even this is not enough. After performing stage 5, new collisions can arise since the original velocity was changed. This is why you can perform stage 6 for a limited number of times to even futher improve the quality of the simulation.

Thanks for your reply, thats helped. Still I have some questions.

At step 6 would you integrate from the new velocity if you went back to step 3?

When you say 'fix the deepest pair' at c: do you mean apply an impulse, or use a penalty method to separate them?

Also im a bit confused where the aggressive optimisation fits in, is it at the collision AND contact stage?

Also do I have to account for stacking at the contact phase?

Cheers

pot

[Edited by - pot on February 7, 2006 4:39:10 PM]

Quote:Original post by pot
At step 6 would you integrate from the new velocity if you went back to step 3?

Yes, this is not a mistake. Stages 3-5 fix the initial velocity v. Notice that the velocity v' which was computed in stage 3a is discarded once we complete stage 6.

Quote:
When you say 'fix the deepest pair' at c: do you mean apply an impulse, or use a penalty method to separate them?

Impulse. The paper does not use penalty methods at all! In fact, this is one of most important innovations of this paper.

Quote:
Also im a bit confused where the aggressive optimisation fits in, is it at the collision AND contact stage?

I haven't covered the contact stage at all. In the paper they suggest to use the aggressive optimization at the collision stage only. For the contact stage they propose a more expansive and accurate approach where they gradually stop the non-separating pairs using decreasing negative restitution coefficients. Also notice that they use the current geometry to process contact information (end of section 8).

A word of advice. Don't implement those fancy algorithms just yet. Have something working at first and make sure that your code is modular enough to expand it later. Just having both collision and contact stages should be enough to make that box of yours stop jumping around.

Good luck and don't forget to send the demo once you get it working. :)

Yeah I will definately keep it simple to start, just trying to get an overview of everything because I no the ordering is very important.

just to clarify is the outline now this?

1) Apply External Forces
2) (x,v) <- Get state
3a) v' <- Integrate velocity from (x,v)
3b) x' <- Integrate position from (x,v')
4) Detect collisions at (x')
a: Store colliding pairs in the list
b: Find deepest non separating pair
c: Fix the deepest pair (this updates the velocity by an impulse and therfore the relative velocities at some of the contact points)
d: Remove all separating points from list
e: If list is not empty go to step c (but stop at some threshold)

7a) v' <- Integrate velocity from (x,v)
7b) x' <- Integrate position from (x,v')
8) Detect collisions at (x')
9) v' <- Iteratively apply inelastic impulses to v'

10) (x') <- Integrate position from (x,v')
11) (x',v') -> Store state
12) reset forces


Cheers for your help! much apreciated. will stick up some demos when I get to that stage ;)

pot

Quote:Original post by pot
e: If list is not empty go to step c (but stop at some threshold)

You should go to step b rather than c because you want to find the new deepest non-separating pair. Also, there should be no threshold since every time we fix a non-separating pair, we remove it from the list (along with any other pair that because separting), hence the process is finite and each pair is processed one time at most.

Quote:
Cheers for your help! much apreciated. will stick up some demos when I get to that stage ;)

I can hardly wait. :)

Here are samples I posted a while ago on gdalogo:

http://www.dirkgregorius.de/dynamix.rar

In this particular version I perform only one collision step and no shock-propagation. I also use an average impulse, but not the artihmetic mean. Instead I take the velocity field over the contact region into account and build a weighted sum. Such that I drag the impulse closer to the point where the actual action takes place :-)

This works fine for the examples there, but if you have e.g. twisted stacks you miss the friction against "torsion", since you actually reduce the box to "sphere" when using average impulses. I think John Schultz suggested something similiar. Anyway, though not suited for the contact phase, it seems quite useful for the collision processing...

-Dirk

Nice work man. Very impressive.

Thanks Ury!

I have another version with shock-propagation and a different collision model - basically a refreshment of the contact data per feature intersection. This works correct then finally...

Most important: Thanks for your help! Without your help with the Langrangian stuff and some other topics I wouldn't have got there :-)

I finished the impulse-based stuff and work with the LCP method with PGS currently. I like the big-matrix. Anyway, in the end I get the same results. There was a thread at the Bullet forum regarding the similarity between both methods...

Maybe you like to drop me an e-mail. Unfortunately I haven't got it. Such that we could discuss some physically based modelling stuff in more detail. I am currently looking into cloth simulation. I would appreciate to hear of your ideas... :-)

At: Pot
For further information on your project I suggest looking at the follow up paper by Rachel Weinstein et al. Also very interessting is the PhD by Bridson. Looking at the two cloth related papers of Prof. Fedkiw is also a help, since they use quite the same ideas there. Finally I recommend looking at some of the course notes (teaching) of Prof. Bridson. You will find valuable information there as well...

You find it all the Stanford Graphics where you got your Guendelman paper from and by googling for Bridson...

-Dirk

Thanks for the link, v impressive!

Im getting on well now thanks to ury. I no understand everything with more clarity than I did. Although some things are unclear after reading some other reseources. Do I sum the external forces (gravity) before the collision or contact stage? And to set up a contact graph is it sufficient to order in the direction of gravity and process contacts bottom up or do I need some more sophisicated links between objects in contact? Also during the collision iteration (a: - e:), when solving the impulse do I use the current position/velocity or the predicted values?

Thanks

Pot