Sign in to follow this  

Contact graph/shock algorithm flaw?

This topic is 4308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working from the "Non Convex Rigid Bodies with Stacking" paper and have implementated the contact graph as they described, which I'm using for shock propogation and ordering my contact resolution. However, I may have come across a pathological case that breaks the algorithm: Image hosting by Photobucket The numbers in the form of x.y represent a contact level of x (with 0 being the base, unmoveable objects) and a random order within that level of y. So the problem is that this big block leaning on the stack causes the middle of the stack to be the top of the contact graph, when really what i want is for the top of the stack to be the top of the graph. You can see the middle of the stack is the farthest from an unmoveable object (wheras if the leaning block wasnt there, the top of the stack would be the farthest) As a result, the whole thing gets squished into the middle of the stack, as the big leaning block pushes downward on the top and the blocks at the top of the stack move downward to get out of its way (since its at a lower level of the contact graph, as dictated by the shock propogation algorithm). Are there any clever ways around this problem? Maybe if I dont build my contact graph based on what the objects touch, and just instead build it based on the highest-vertical point of the object - that would put the leaning block as the highest object and fix this problem (while revealing a dozen more problems though, i'm sure). Thanks in advance! -John

Share this post


Link to post
Share on other sites
I don't know why you would want to do this anyway, certainly for a 2d simulation, unless you're planning on stacks 1000s of objects high, or running on antique hardware. In 2D you should have plenty of CPU to do the number of iterations sufficient to get decent stacking behaviour anyway.

Share this post


Link to post
Share on other sites
The algorithms are the same complexity in 2d vs 3d, the speedup is not going to be massive between them. And it would take a comprable number of iterations as in a 3d simulation. And yes, i do plan to have crazy stacks and other processor intensive things going on.

Share this post


Link to post
Share on other sites
Rather than use object positions for building a complicated contact graph, I implemented shock propogation by simply processing the contacts in lowest to highest order (just sort them before processing). For each contact resolve, simply make the lowest object be immovable. Very easy to implement and it produces good results.


-Steve.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Think that you do stack, and the top is slepery soap. And then you push soap by the big block. That is what your stack looks like. So it is unimportant for stack what is below. Friction which cause force in second block, is just too small to move second block. So if you want crash stack in middle you must setup sliperies part in middle and very big friction ones in the top.

In other word you must have biger contracy in your stack frictions.

Share this post


Link to post
Share on other sites
Quote:
Original post by johnnyk
However, I may have come across a pathological case that breaks the algorithm:

I am afraid that the flaw is in the implementation of the algorithm.
I don't quite understand how the middle part of your stack got the highest level. Could you describe your algorithm and explain how you got those numbers?

Things to keep in mind:
1) The graph is directional.
2) When you construct the graph, for each object (A) you do the following:
2a) Move object (A) in the direction of the gravity pull.
2b) Detect collisions with other objects and for each collision, create a directed edge that points towards A.
2c) Restore the position of the object A.
3) Look here for a more thorough discussion.

Share this post


Link to post
Share on other sites
Quote:
Original post by ury
I am afraid that the flaw is in the implementation of the algorithm.


But there's a flaw in your algorithm (which is different to johnnyk's) too - it won't handle the case where a heavy object is moving horizontally and squashing a (number of) lighter objects between it and some static geometry.

The thing is - there's going to be flaws in all such algorithms - in order to prevent penetrations by adjusting velocities you'd have to run some algorithm that contains global knowledge of the situation - for example running the system through an exact LCP solver - and you're only using a shock step because you didn't want to do that in the first place. Trying to solve it by incrementally solving the problem locally is never going to be fool-proof, and is going to be "unphysical" as well.

It still may be useful in some situations of course. It may be that in practice you get fewer bad situations if you just sort by height (rather than psuedo-distance from static geometry), so I would definitely try that - but it depends on what situations you're going to throw at the engine in the end.

As for complexity/efficiency - everything is going to be related to the number of contact points you have to solve for. This number will be much smaller (and scale less quickly) in 2D than 3D. Collision detection, likely to be a major bottleneck in 3D, should be so much quicker in 2D too. Fewer floating point operations (2 elements in a vector vs 3), big cache-hit improvement... I would expect a vast difference between 2D and 3D.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hey MrRowl I am really impressed with your progress. You have come a long way since the time you’d considered the shock wave as the magic bullet, now you know that the law of physics and math cannot be shifted and get away with it.
Yes you could cheat them, and you may even get some magic act that may convince the untrained public, but you cannot get away with it.

This was a case of tuff love, but I guess that better late than never.

Share this post


Link to post
Share on other sites
Quote:

But there's a flaw in your algorithm (which is different to johnnyk's) too - it won't handle the case where a heavy object is moving horizontally and squashing a (number of) lighter objects between it and some static geometry.

As far as I can remember we are discussing the algorithm proposed in "Non Convex Rigid Bodies with Stacking" paper. I wish that it was my algorithm but it's not. What I am trying to do is to compare the results that I'd expect to get from the original algorithm against the results in johnnyk's post.
Here's what I do... After thinking about the problem, I try to post a constructive reply in this forum. No, the reply doesn't include references to LCP solvers, complexity/efficiency analysis of collision detection, a brief introduction to optimization techniques and the inner workings of a CPU. I just try to provide a meaningful answer that might help johnnyk.

"My" algorithm talks about shock propagation which comes to solve the problem of multiple contacts with stacking. "My" algorithm doesn't handle the collision of a horizontally moving heavy object that squashes light objects. That's what the collision stage is for.

Quote:

It still may be useful in some situations of course. It may be that in practice you get fewer bad situations if you just sort by height (rather than psuedo-distance from static geometry), so I would definitely try that - but it depends on what situations you're going to throw at the engine in the end.

This is a very useful suggestion. Although it can prove to be somewhat problematic in complex situations like the example with the domino stack in the "Non Convex Rigid Bodies with Stacking" paper. Still the implementation is very straight-forward and it'll probably work in many situations. Thank you sbroumley.

Share this post


Link to post
Share on other sites
Some very nasty undertones and egos at play in the responses here.. what's up with that?

Ury as for your reply, I am moving each object with respect to gravity and tracking which objects it collides with, then I create the contact graph where the level of each object represents "the lowest number of objects seperating me from an unmoveable object". Thus, since the blocks on the top are touching the leaning-block, which is touching the ground, they are at contact level 2 (whereas if the leaning block wasnt there, they'd be 15 or so). Thats how the algorithm is described in the paper, am i wrong?

I'll give it a try using the height of the object instead, but i have a feeling that will work poorly in the domino situation as mentioned. I know shock propogation is a rather "unphysical" solution but I have found it to be very useful with other problems I've been having - reducing jitters and penetration in large stacks. Of course I'm open to other methods of doing this, shock propogation just made the most sense to me, minus a few of the pathological cases i've illustrated here.

As for 2d vs 3d, yes 2d may be signifigantly faster by a constant factor, but its the same big-O complexity as 3d, suffers the same problems as 3d, and thus still needs similar techniques.

Thanks for your replies..
-John

Share this post


Link to post
Share on other sites
Quote:
Original post by ury
"My" algorithm talks about shock propagation which comes to solve the problem of multiple contacts with stacking. "My" algorithm doesn't handle the collision of a horizontally moving heavy object that squashes light objects. That's what the collision stage is for.


Well - I suppose your last sentence is the important one - except - what is the "shock" step for? I see it as being a last-ditch effort to attempt to prevent excessive inter-object penetration using a partially physics based approach, given that the basic collision/contact handling is not exact (especially interactions between objects with very different masses, when you terminate an iterative solver early). If you're writing a game that has cars zooming around environments with walls and lightweight non-breakable boxes then the horizontal collision problem is probably a far more important one to "solve" than the stacking one. Other games might have more "stacks" of objects of similar mass.
Either way I think we all agree it's a bit hacky, and you have to tune/pick the hack appropriate to the situation :)

Ury - I'm sorry if you interpretted the "my" expression in a negative/personal way - it certainly wasn't intended like that.

AP (the 2nd) - grow up.

Share this post


Link to post
Share on other sites

This topic is 4308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this