I'm doing pretty well on my RBD Engine now, and the last feature I'm stuck on is propagation. If a moving block hits a static chain of other blocks, then the impulse generated by the collision should be propagated to the last block on the chain. Right now, I'm just iterating over and over the collision stack until all collisions are satisfied, but its really slow. I'm getting usually 120 iterations before all collisions are resolved. Does anyone have a fast method for doing this? I've looked at Shock Propagation (forgot which paper it came from), which looked at setting specific object masses to infinity for the last propation iteration, but it sounds really artificial and contrary to real physics.

Is it necessary to sort the objects in order of gravity? I'm actually using an attractor for my simulation, so gravity really has no set direction (the direction of gravity depends on which side of the attractor the object is on).

Also a few other options:
Are there any ways of simultaneously solving for the collisions, instead of propagating? AND STILL get the same results?

And:
Does anyone know what Mirtich and Baraff use for propagation?

Quote:Original post by CuppoJava
Is it necessary to sort the objects in order of gravity? I'm actually using an attractor for my simulation, so gravity really has no set direction (the direction of gravity depends on which side of the attractor the object is on).

that can be solved by sorting on potential energy instead of height.

Quote:
Also a few other options:
Are there any ways of simultaneously solving for the collisions, instead of propagating? AND STILL get the same results?

yes. its hell.

Quote:
And:
Does anyone know what Mirtich and Baraff use for propagation?

ive read a lot of papers, but i cant keep track of the names, so the answer is no. changes are its rather complex, but i suppose you actually already know that, otherwise youd be reading the papers trying to implement it. shock propagation might look hackish, but its one hell of a tradeoff in terms of functionality vs complexity. ive seen it give some very nice results anyway. fast, stable, visually perfectly accurate. it would be what i would use were i to write a RB engine with stacking.

"Shock propogation", in the sense that you seem to be talking about using it, is just an extra step to take care of the problem that previous steps in your algorithm aren't actually doing their job properly. This could be because you're using iteration (processing each contact in turn), and not doing enough iterations, or maybe you've got some other approximate way of solving the LCP "simultaneously", but you terminate before it's completely solved.

Anyway, if you set up problems where iteration won't work - e.g. lots of touching objects, either vertically or horizontally, or interactions between objects of different mass, then you may encounter issues where your approximate method is just too, well, approximate. You have two choices:

1. Implement "shock propogation" to stop objects penetrating, at the expense of doing it in a slightly non-physical way. This doesn't have to have any direction dependance - I do it by working away from static geometry (conceptually recursively) - so it would work for "horizontal stacks" too - e.g. where you trap an object between a wall and another moving object.

2. Implement the basic contact processing accurately - formulate it as a LCP and read up on the numerous papers about how to solve it.

Also, you don't need to iterate until each collision is _completely_ resolved - you can have some tolerance, so long as you have a reasonably good method for dealing with object penetration when it does occur.

Hello again Mr. Rowl,
First I want to thank you for all your help in my last post, its been very helpful.

About the LCP solver, does it really handle collisions?

Someone recommended me to read "Fast contact force computation with Friction" by Baraff, where he discusses how to setup a LCP solver. But it seems to only calculate forces for contact, and not collisions. Also, he seems to be making it more complicated by converting the problem from linear programming to one of quadratic programming.

Please give me some more information on LCP solvers.

Have a look at:

http://isg.cs.tcd.ie/giangt/EGIrl2003.pdf

I should say that I've never implemented this (LCP for either collisions or contacts), but this paper makes things pretty clear, I think.

If I was going to go down the LCP route (and I hope to have time to at some point!) I would probably start by using it to calculate/apply the frictionless impulses. Then use the normal impulses at each contact point to calculate tangential friction impulses, and apply them sequentially, together with some normal impulses since friction would introduce some, hopefully small, normal accelerations.

I think Dave Eberly's physics book gives you a generic LCP solver.

Thank you again Mr.Rowl.

I know you haven't read the article yet, but do you know if it propagates correctly? eg. When a moving block hits a static string of blocks, does the impulse propagate to the end?

PS: I checked out your site. Its helped me unbelievably. That website should be a permanent sticky on this forum. :)

Quote:Original post by CuppoJava
I know you haven't read the article yet, but do you know if it propagates correctly?

It should do - so long as when you set up the LCP you do it for the system as a whole (or at least on each "island" of interacting objects) - not just on a per-object basis.

Quote:
PS: I checked out your site. Its helped me unbelievably. That website should be a permanent sticky on this forum. :)

Not sure how long it will be there - I'm about to move jobs and country, and haven't worked out what will happen to it!

Better save it to my harddisk then.

edit: And good luck with the move of course ;-)