Dear Community, greetings everyone, my first entry here!! I have been writing on an impulse based rigid body simulator for some time now and may be in need of some help. Basically my simulator works fine now and I have begun implementing shock propagation when I stumbled over an effect that maybe one of you has already encountered. The algorithm I am using for the creation of the contact graph looks for a static body and assigns a layer number "0" on it. If the static body is in contact with another body, this body will be in layer "1". If that body is in contact with another one, well that will be in layer "2", and so on. During shock propagation, I am freezing (setting the inertias to infinity) a layer n and resolve all contacts within that layer and all that have contact with layer n+1. So this is pretty straight forward so far. If I have a stack of boxes, the floor will be in layer 0, the first box in 1 and the box on it in layer 2 and so on. Now imagine two stacks. The two stacks have the same height and now imagine there is one single stretched box resting on both stacks. It looks like a door. If both stacks contain the same amount of boxes, the stretched box will be in the layer with the highest number. Shock propagation will work fine. But if one increases the number of boxes in one stack while leaving the total height the same, then the box with the highest layer number will be in the stack with the many boxes. Example: left stack two boxes, right stack four boxes. On top, the stretched box. The box with the highest layer number will be in the right stack, it is the fourth box (let's call it BOX4) when counted from the floor. And this is where the problem occurs: As during shock propagation the simulation works its way through the layers and freezing one layer after the other, it will come to a point where the stretched box above our BOX4 is frozen and the box beneath BOX4 is also frozen. The simulation will fall in an endless loop because the stretched box has a little downward velocity (from its contact resolution before it was frozen) and the box beneath BOX4 moves a little upward (also due to its contact resolution). So how do I work around that effect. If the contact graph made sure that always the highest body has always the highest layer number, then the problem would be solved. It might really be a small problem for you guys so help is welcome!!!! Thanks, Alex PS: How do I attach a .jpg to my post?

Quote:Original post by hellobomm
PS: How do I attach a .jpg to my post?

I'm not the guy to answer most of your questions, but I can answer this one!

Answer: "Standard HTML." Just use an "img" tag. You'll need to find someplace to host your images -- either your own webspace, or one of the free image hosting sites (e.g., ImageShack).

This forum is a bit odd in that it accepts a mix of HTML and UBB. Some HTML it filters; some things it does with UBB; others it does with HTML. It's described in more detail in the overall forum FAQ ("overall" as different from the specific FAQs for each forum -- "Math and Physics," "Artificial Intelligence," etc).

Cheers.

Thanks mate!!

Here is a picture of the situation:




As the two blue boxes of layer 3 are frozen (infinitive inertia), the contact between the yellow box in layer 4 and the blue boxes in layer 3 can not be resolved.

Alex

Shock propagation is probably going to cause you more problems than it solves, and anyway it doesn't appear to actually be necessary - using accumulated impulses, warm starting and making sure your contacts are well placed and stable you should be able to stack plenty of objects without problems (e.g. see Bullet)

Well it is not that I have not tried to shorten the calculation time. But shock propagation made the calculation of a simple stack extremely quick and I don't want to throw that approach away.

So any suggestions are welcome guys [help]

When a box is resting on two boxes below it, it will have a higher number than both. Accomplishing this requires a topological sort of the contact graph. Here's the deal: Each body has a list of pointers to each body it is resting on, as well as pointers to each body resting on it. Layer 0 is all bodies resting on nothing. You remove these bodies from the graph, cancelling out the pointers to them from all bodies that were previously resting on them. Now, all bodies that are still in the graph and now are resting on nothing are assigned layer 1, and removed. And so on with increasing layer numbers, until all bodies are numbered and removed.

That technique will work as long as you have no cycles. If you get to a situation where no object in the graph is without resting-on pointers, the easiest thing to do is probably just to not do shock propagation for that frame. Alternatively you can assign all bodies in the cycle to the next layer, but that can be time-consuming to calculate.

I thought you were going in this direction, maybe you were: why not make the top blue box a layer5 ? It's a higher number than all the boxes below it. There would just be no 4 on the left..

So I guess I was not wrong when I thought that building a contact graph that is only topologically sorted is not the right way. Instead of finding out which body has contact with which it is more important to find out which body RESTS ON which body. If I do this, then the top blue box has indeed the highest layer number and the problem is solved.

I have found an algorithm on this site here:
http://www.abhik.com/code/project/5

Its a Directed Graph Template Class with the feature that it also finds and pops loops in a graph. The code is not working properly but I will try to implement it.

Thanks for now, I will post what I have found out as soon as I have results.

Hi Blackbird, of course it would work but I am not sure how loops are resolved with your approach.
Imagine standing dominos arranged in a circle. If you trip one, all will fall and each domino will lay on another one. As they are in a loop, the only way to resolve them is to asign the same level to each other.


By the way. The new approach I metioned above is now implemented and works fine.
A short youtube video shows the situation in the drawing I posted earlier.


http://www.youtube.com/watch?gl=DE&v=vHzc4QcKfTw


The key was to do two depth searches through the contact graph. One to identify loops and group them into one node. And then a second depth search is done with a simple sort algorithm. Each body that lies on another has now a higher level except it is in a loop, then it has the same level.

Thanks for your input guys!!!