Stable box stacking

[ngbinh]

Sorry if it's OT: I'm wondering if stable box stack is something nice to have?

Well, generally stack is like show for physics engines, if you have working sleeping system and more or less stable stacks, they're not a problem anymore (they'll fall asleep). And about article - if it is something really new and don't ruin general simulation case (like "shock propagation" - earlier it was not suitable in practice because of its influence on general simulation, lack of plausibility; don't know if now there is kinda fixes on it), you should write about it for sure.

Follow up on that discussion:

download the demo here: http://www.cs.rpi.edu/~nguyeb2/BoxStack.zip

A small demo to show how Stewart-Trinkle method can:
a) BoxStack scene: Simulate stable box stacking without "sleep". This demo has about 50 boxes. The limitation here is the solver. I'm using PATH, a direct solver so it wont scale that well. Note that, iterative LCP solver should work as well. <--This demo may need a powerful machine to run fast enough.

b) BoxStackWeight scence: Simulate a large, heavy box (50 kg) drops into a small and light (1kg) box below without any unstablity.

Note:
+ Read the xml, you may be able to change the scene.
+ I'm using a very naive polygon-polygon collision detection (almost like brute force). It's buggy and very slowwww...


I used:
a) PATH : http://www.cs.wisc.edu/cpnet/cpnetsoftware/
b) Qt 4.5

[raigan2]

I'm quite interested in this method, as we're currently doing something similar to Stewart-Trinkle for collision (i.e potential future collisions are solved during the current step), and it's a bottleneck -- for instance when you have e.g a pile of octagons, you end up solving a lot of useless constraints.

Are you sure this would work just as well with an iterative solver? AFAIK the reason that "heavy box on light box" and "tall stack" are typically unstable is that the large mass ratio (in the former case) and deepness of the constraint graph (in the latter case) adversely effect the convergence of iterative solvers, so a direct solver is sort of cheating in these cases!

[ngbinh]

I'm quite interested in this method, as we're currently doing something similar to Stewart-Trinkle for collision (i.e potential future collisions are solved during the current step), and it's a bottleneck -- for instance when you have e.g a pile of octagons, you end up solving a lot of useless constraints.

I think the main idea here is it's too late if you wait for penetration to happen. For prevention method (like this Stewart-Trinkle method) actively prevent potential penetrations. That leads the much less penetrations than wait-and-correct approaches even penetrations still happen due to numerical, linearization errors (which are inherent to time-stepping methods). About your comments on large number of contacts : In general, ST method cd results in more contacts than usual as you mentioned, but most of those contacts have positive distances (not penetration) and if you careful enough , you can solve them quickly in the solver. Think of them as many "easy" to satisfy constraints. So in performance point of view, you either have a bunch of "easy" constraints in ST, or a few if "hard" constraints like most current methods.

Are you sure this would work just as well with an iterative solver? AFAIK the reason that "heavy box on light box" and "tall stack" are typically unstable is that the large mass ratio (in the former case) and deepness of the constraint graph (in the latter case) adversely effect the convergence of iterative solvers, so a direct solver is sort of cheating in these cases!

I don't have an iterative solver for ST yet, but there are a couple of people have done that. Fundamentally, iterative methods also need to satisfy those constraints some how. If not, it means the method has too slow convergence rate and you need to do something different.
Some pointers:
1) Danny's works: http://people.cs.ubc.ca/~dkaufman/
2) Mihai's works: http://www.springerlink.com/content/3tl371gx8172321k/
which result in a physics engine here: http://www.deltaknowledge.com/chronoengine/

[raigan2]

[uh, please see following comment]

[raigan2]

About your comments on large number of contacts : In general, ST method cd results in more contacts than usual as you mentioned, but most of those contacts have positive distances (not penetration) and if you careful enough , you can solve them quickly in the solver. Think of them as many "easy" to satisfy constraints. So in performance point of view, you either have a bunch of "easy" constraints in ST, or a few if "hard" constraints like most current methods.

As far as I can tell, what happens is that you end up performing narrow-phase collision detection at each solver iteration, i.e for these "potential" collisions, when you're determining whether you have to solve them (i.e determining whether the current error is positive) this is equivalent to a separating axis test or similar; in an iterative solver this also requires that you transform the contact points/normals so that you have their most current state, so even though each test is simple it still adds up.

I agree that it's cheaper than a full solve since you only need to calculate the constraint error, you can skip updating the Jacobian etc. if the shapes aren't actually colliding. But, calculating the constraint error is still fairly expensive when you have to do this again and again; if you consider two boxes, Box2D uses a single constraint (with one or two contact points) to model collision between them, whereas unless I'm confused ST will need 4 point-vs-pair-of-planes constraints. This gets worse as the shapes get more complex, i.e Box2D needs only a single constraint for any pair of convex shapes, while ST needs more constraints as the number of faces/verts on each convex shape increases.

In other words, not only are you performing narrow-phase inside the solver loop, but your narrow-phase collision method is actually much more costly than if you were using SAT or similar because you're using a feature-by-feature method rather than a convex-convex method.


These issues seem fundamental to position-level solvers, I really hope that someone smarter than I will address them at some point since we haven't really found any great solutions.. they present some big performance issues which I can't really see how to resolve.

We had a test scene of 100 boxes piled in a room which were generating 2k or more collision constraints; since each box can be close to ~8 boxes when in a pile or stack, and each pair of close boxes generates up to 4 collision constraints.. these things add up. This was very depressing when compared to the performance of something like Box2D

[ngbinh]

As far as I can tell, what happens is that you end up performing narrow-phase collision detection at each solver iteration, i.e for these "potential" collisions, when you're determining whether you have to solve them (i.e determining whether the current error is positive) this is equivalent to a separating axis test or similar; in an iterative solver this also requires that you transform the contact points/normals so that you have their most current state, so even though each test is simple it still adds up.

Potential contacts here means those who would penetrate in the next time step if we don't do anything. I don't see how it can be equivalent a SAP test in current time step. You can view it this way: Box2D/Bullet method try to solve current problems (penetrations) while ST tries to solve both current and next time step problem (in a sense). Actually, ST is somewhat similar to doing continuous collision detection but it does a better job as no way you can know the exact position of a body unless you actually solve the time stepping problems.

I agree that it's cheaper than a full solve since you only need to calculate the constraint error, you can skip updating the Jacobian etc. if the shapes aren't actually colliding. But, calculating the constraint error is still fairly expensive when you have to do this again and again; if you consider two boxes, Box2D uses a single constraint (with one or two contact points) to model collision between them, whereas unless I'm confused ST will need 4 point-vs-pair-of-planes constraints. This gets worse as the shapes get more complex, i.e Box2D needs only a single constraint for any pair of convex shapes, while ST needs more constraints as the number of faces/verts on each convex shape increases.

Consider box-box resting case, ST will need 4 contacts normally, but you can use 2 ( between the 2 lower points of upper body and the upper edge of lower one) if you can preprocess the case. Feeding 4 or 2 points of contacts to ST in this case is the matter of how good is you collision detection. I bet Box2D CD has to do the same thing to find the one contact it gets. Moreover, for box-box stacking, I don't see how one contact can get you a stable simulation at all not mention more complex convex shape.

In other words, not only are you performing narrow-phase inside the solver loop, but your narrow-phase collision method is actually much more costly than if you were using SAT or similar because you're using a feature-by-feature method rather than a convex-convex method.

ST doesn't do narrow phase inside the solver loop at all. I don't know how you get that impression? ST looks at those pairs that "would be in penetration" if you don't do anything. No way SAT can detect such pairs active or not as you won't know the exact positions until you actually solve those constraints. Maybe feature-feature is the right way to do collision response? I don't see how a single contact can model interaction between to polygonal convex shapes. You can use single contact between two convex implicit surfaces but you have to consider features-features when dealing with polygonal shapes.

These issues seem fundamental to position-level solvers, I really hope that someone smarter than I will address them at some point since we haven't really found any great solutions.. they present some big performance issues which I can't really see how to resolve.

We had a test scene of 100 boxes piled in a room which were generating 2k or more collision constraints; since each box can be close to ~8 boxes when in a pile or stack, and each pair of close boxes generates up to 4 collision constraints.. these things add up. This was very depressing when compared to the performance of something like Box2D

I don't see how performance would be a big issue with ST. Sure, ST ask for more contacts than Box2D but it only more than a constant factor not scale with number of shapes features like you imagine. And if you have a linear solver then your app only run a constant factor slower. ST should scale well with number of bodies if you do it right.

The main issue for me here is that there is no collision detection returns information I need (at least in 3D). I'm hoping by sharing these ideas, maybe some one will redesign a collision detection library that work with ST.

[raigan2]

Potential contacts here means those who would penetrate in the next time step if we don't do anything

This is something I may not properly understand; our current implementation simply extrapolates object states and generates "potential collision" constraints between pairs of features whose extrapolated states are in close proximity.

I don't see how you can determine "would penetrate in the next step" perfectly, but I'd like to know if there's a better method.

I don't see how a single contact can model interaction between to polygonal convex shapes.

Not a single contact point, a single collision *constraint*, which internally is one or two contact points (which are solved together as a single block); this is how Box2D handles convex-convex collision AFAICR.

The point is that a pair of convex shapes colliding generates a single row/block in the matrix of constraints, whereas in ST the number of constraints generated is based on the relative complexity of the shapes.

ST doesn't do narrow phase inside the solver loop at all. I don't know how you get that impression?

My understanding was that each ST potential collision is a vertex vs plane (or pair-of-planes) constraint; re-evaluating the constraint error at each (iterative solver) iteration is analogous to determining the signed distance between a point and a plane, which is exactly what happens during narrow-phase collision detection -- for example some implementations of SAT test extreme vertices on shape A vs the planes bounding shape B, i.e a point-vs-plane test, hence my likening the process to a SAT-based narrow-phase. Maybe it was a poor analogy

Consider box-box resting case, ST will need 4 contacts normally, but you can use 2 ( between the 2 lower points of upper body and the upper edge of lower one) if you can preprocess the case.

I'm unsure how you can determine this, since during the time step the configuration can go from (if we look at the box corners along the axis tangent to the contact normal) ABBA to ABAB for instance (i.e one box slides relative to the other).

Also box-box is almost the best case for ST (tri-tri would be best), my problem comes with rounded shapes where dozens of verts potentially collide with dozens of tiny edges; convex-convex methods scale nicely with such cases (almost constant if you exploit coherence) while ST requires huge numbers of constraints.

I don't see how performance would be a big issue with ST. Sure, ST ask for more contacts than Box2D but it only more than a constant factor not scale with number of shapes features like you imagine.

Maybe it's a bounded constant factor but it can be rather large; I'm not imagining!

Perhaps my implementation isn't optimal; my experience is that the more vertices and edges of a shape, the more potential collision constraints you need to generate, and it's somewhat worse than linear: for box-vs-box two verts on each box can "see" (potentially collide with) two edges on the other box, but for octagon-vs-octagon it's 4-5 verts per shape which "see" 3-4 edges on the other shape.

I guess the problem is that, although two convex shapes will only collide in at most two points, the set of potential points (in which the two actual contact point will be contained) can be much larger.

There is also the problem of missed collisions due to the predicted state being only a guess, and thus failing to generate the proper set of potential collisions.

[ngbinh]

This is something I may not properly understand; our current implementation simply extrapolates object states and generates "potential collision" constraints between pairs of features whose extrapolated states are in close proximity.

I don't see how you can determine "would penetrate in the next step" perfectly, but I'd like to know if there's a better method.

The term "would penetrate in the next step" is the goal. For ST, if you pick the super set of that list, it would hurt your application performance but wouldn't hurt the outcome (accuracy). So your cd implementation is one of the possible ways.

Not a single contact point, a single collision *constraint*, which internally is one or two contact points (which are solved together as a single block); this is how Box2D handles convex-convex collision AFAICR.

This is something I don't understand : you meant in Box2D, convex-convex can generate 2 contacts but only one row in the constraint Jacobian? How can you merge them?

The point is that a pair of convex shapes colliding generates a single row/block in the matrix of constraints, whereas in ST the number of constraints generated is based on the relative complexity of the shapes.

Ah, I see here you meant a convex-convex colliding can generate a block (i.e multiple rows) in the Jacobian. So how does it different from ST? You can as well do the same to those list of contacts between the two bodies. And the number of contacts ST generates scale with the complexity of two bodies's regions that in close proximity. And I think it should be that way. The main point here is if your shapes are complicated, you may have to pay more in order to have a stable simulation. Actually, no one ever compared the performance difference between ST and current popular methods. In my little 2D physics engine, I also have a wait-and-correct method implementation (based on Anitescu-Potra) and I dont see much difference in term of performance between the two. But the accuracy of ST is much better.

ST doesn't do narrow phase inside the solver loop at all. I don't know how you get that impression?

My understanding was that each ST potential collision is a vertex vs plane (or pair-of-planes) constraint; re-evaluating the constraint error at each (iterative solver) iteration is analogous to determining the signed distance between a point and a plane, which is exactly what happens during narrow-phase collision detection -- for example some implementations of SAT test extreme vertices on shape A vs the planes bounding shape B, i.e a point-vs-plane test, hence my likening the process to a SAT-based narrow-phase. Maybe it was a poor analogy

I bet narrow phase contains much more than just calculated vertex-plane signed distance. Moreover, that's like a magnitude of 10-ish floating points operation. I don't see why it can become a burden. Also, as I mentioned, I never tried GS/SOR to solve our problems as my main concerns are always accuracy and I've never dealt with thousands of objects cases. But I really don't think GS/SOR/etc is a good way. Take a look at those references I gave previously, you can see that they can solve them fast enough (at least to my taste). The demo I posted in this thread is another example. Even I'm using PATH, a direct solver and a very very naive collision detection, it does run fast enough in my tablet pc.

Consider box-box resting case, ST will need 4 contacts normally, but you can use 2 ( between the 2 lower points of upper body and the upper edge of lower one) if you can preprocess the case.

I'm unsure how you can determine this, since during the time step the configuration can go from (if we look at the box corners along the axis tangent to the contact normal) ABBA to ABAB for instance (i.e one box slides relative to the other).

Also box-box is almost the best case for ST (tri-tri would be best), my problem comes with rounded shapes where dozens of verts potentially collide with dozens of tiny edges; convex-convex methods scale nicely with such cases (almost constant if you exploit coherence) while ST requires huge numbers of constraints.

Would you explain how convex-convex handle such cases different from ST? In my view, ST doesn't have anything to do with features-features or shape-shape. It basically try to stop penetration before it happen so if you can write a constraint for convex-convex, ST should work for such constraint also. Anyway, if you have rounded shape vs tiny edges, then maybe using polygonal model is not a good choice. Maybe you need to consider implicit surfaces here.

I don't see how performance would be a big issue with ST. Sure, ST ask for more contacts than Box2D but it only more than a constant factor not scale with number of shapes features like you imagine.

Maybe it's a bounded constant factor but it can be rather large; I'm not imagining!

It's kind of waving-hand statement. I doubt the factor can be more than 2. On the other hand, look at the benefit of ST:
+ No need special treatment for high speed object
+ Stable (physically)
+ Can handle high weight ratio stacking
+ Much less penetrations
and very important thing is that you can mix Box2D/Bullet constraints with ST style constraints.
I also want to mention the theoretical advantage of ST. I will come back later on this point when I have time.

Perhaps my implementation isn't optimal; my experience is that the more vertices and edges of a shape, the more potential collision constraints you need to generate, and it's somewhat worse than linear: for box-vs-box two verts on each box can "see" (potentially collide with) two edges on the other box, but for octagon-vs-octagon it's 4-5 verts per shape which "see" 3-4 edges on the other shape.

I guess the problem is that, although two convex shapes will only collide in at most two points, the set of potential points (in which the two actual contact point will be contained) can be much larger.

There is also the problem of missed collisions due to the predicted state being only a guess, and thus failing to generate the proper set of potential collisions.

As mention above, when you deal with complex shape, you have to pay more than simple one. For the octagon-vs-octagon case, you wouldn't have 4-5 verts in one body "see" 3-4 edges in other if your time step is small enough. So you gotta slow it down until only 2 or 3 vertices "see" 1 or at most 2 edges. It also make me wonder, how Box2D handle this case? Doesn't it have to spend more time when dealing with complex shapes?

[raigan2]

It also make me wonder, how Box2D handle this case? Doesn't it have to spend more time when dealing with complex shapes?

It uses SAT+clipping to generate one or two contact points (for a pair of convex colliding shapes), and solve the contacts together: http://www.gphysics.com/archives/38

The main issue is that in Box2D this collision process is performed exactly once per simulation step, prior to solving constraints, whereas with an iterative solver ST requires that you perform similar collision tests ** at every solver iteration **, for every potential collision.

Ah, I see here you meant a convex-convex colliding can generate a block (i.e multiple rows) in the Jacobian. So how does it different from ST?

Because there are one or two contacts which are known prior to solving, the block can be handled as in the previous link; with ST in order to do this you would need to test all potential points in order to determine which two are the "real" collision points for the current iteration, and then solve those using the same sort of process.

But at this point you are performing your narrow-phase collision query inside your solver's inner loop (i.e the process of resolving all the potential contact points into the one or two actual contacts *is* narrow-phase collision), arguably it would be better to avoid the overhead of all those potential points and just perform the full convex-vs-convex narrowphase test at each iteration.

This is the main drawback of position-based methods for me so far, it's a large performance problem in our simulator. Taking smaller time steps does indeed decrease the number of potential collisions, but it doesn't help the big picture because you're also taking more steps per second, so on the whole nothing changes.

And the number of contacts ST generates scale with the complexity of two bodies's regions that in close proximity. And I think it should be that way. The main point here is if your shapes are complicated, you may have to pay more in order to have a stable simulation.

My problem with this is that it does make sense for your *collision* process to take longer when the shapes are more complex, but it sucks when your constraint solver also takes longer! But this is what happens when collision and costraint solving are tangled together, as it seems they must be in a position-level solver.

In contrast Box2D takes the exact same amount of time to solve convex-vs-convex collision regardless of the complexity of the shapes; collision will of course take longer since there are more faces to test, but the solver itself is agnostic to the shapes' complexity.

+ Stable (physically)
+ Can handle high weight ratio stacking

I think these two points may have more to do with using a direct constraint solver instead of relaxation, rather than the specific simulation method.

Actually, no one ever compared the performance difference between ST and current popular methods. In my little 2D physics engine, I also have a wait-and-correct method implementation (based on Anitescu-Potra) and I dont see much difference in term of performance between the two. But the accuracy of ST is much better.

It would be extremely interesting if you tried implementing an ST type solver inside Box2D, since that way there would be an apples/apples comparison.

[ngbinh]

Well, let do it in a different way here. Reading through your posts, here is my summarize about your method:
1) Wait for collision to happen, use SAT then clipping to find the one or two points in penetration
2) Use MLCP 2-2 to resolve the penetrations.

If it's correct then surely it will get less number of contacts but it kinda run into infinite loops of error-corrections if you don't put them to sleep. It also suffers from high speed object as the penetration depth scales with time step and object velocity.

In the other hand, ST need, in an addition to usual Box2D pair, a number of "potential contacts". But you need to take into account that in-penetration contacts place a bigger burden on the solver than separating. So you can imagine that in ST, you could have a bunch of potential, some in-contact and very few penetration. In contrast, Box2D would have many more number of in-penetration. And as I said before, we may be able to have a specialized ST solver to take such positive-distance contacts into account. But, till now, no one know what would be the actual price paid for ST compare to Box2D.

But at this point you are performing your narrow-phase collision query inside your solver's inner loop (i.e the process of resolving all the potential contact points into the one or two actual contacts *is* narrow-phase collision), arguably it would be better to avoid the overhead of all those potential points and just perform the full convex-vs-convex narrowphase test at each iteration.

This is the main drawback of position-based methods for me so far, it's a large performance problem in our simulator. Taking smaller time steps does indeed decrease the number of potential collisions, but it doesn't help the big picture because you're also taking more steps per second, so on the whole nothing changes.

My problem with this is that it does make sense for your *collision* process to take longer when the shapes are more complex, but it sucks when your constraint solver also takes longer! But this is what happens when collision and costraint solving are tangled together, as it seems they must be in a position-level solver.

We agree on this point. ST and Box2D are two different methods. And each serves its own purpose. There is no way and by no mean ST should replace Box2D method completely. I'm just pointing that there are other methods like ST and its benefits.

In contrast Box2D takes the exact same amount of time to solve convex-vs-convex collision regardless of the complexity of the shapes; collision will of course take longer since there are more faces to test, but the solver itself is agnostic to the shapes' complexity.

I would look more into your method, but isn't it only work in 2D? Are there any similarity in 3D? Box2D idea of getting on 2 points are quite clear to me now. I may try to apply ST-style constraint to take advantage of it.

+ Stable (physically)
+ Can handle high weight ratio stacking

I think these two points may have more to do with using a direct constraint solver instead of relaxation, rather than the specific simulation method.

No, if you wait for penetration, stop it, then correct it. No way you can solve such problems even with direct method. In fact, You can try to solve your problem directly and I bet you still find the same problems there. For ST, if you iterative method is "good" enough for it, you should get more or less the same results.

Actually, no one ever compared the performance difference between ST and current popular methods. In my little 2D physics engine, I also have a wait-and-correct method implementation (based on Anitescu-Potra) and I dont see much difference in term of performance between the two. But the accuracy of ST is much better.

It would be extremely interesting if you tried implementing an ST type solver inside Box2D, since that way there would be an apples/apples comparison.

[/quote]

I would love to do so, but I guess no one pay me to do that. . This discussion is more focus on the "idea" part of the methods.

All I want to send across is: There is a method (ST) that can do such things, requires different collision detection and arguably slower (in my belief, not more than 2x).

[Dirk Gregorius]

How do the speculative contacts work with restitution? Actually there are some engines that use this concept for quite a long time. It can actually also be applied to limits for example. All the implementaions I am aware off suffer from very bad restitution since they artificially stop the object. How does ST behave here?

[ngbinh]

How do the speculative contacts work with restitution? Actually there are some engines that use this concept for quite a long time. It can actually also be applied to limits for example. All the implementaions I am aware off suffer from very bad restitution since they artificially stop the object. How does ST behave here?

ST works with any restitution law like usual. What's the problems with them? I have Poisson and Newton restitution in my engine, and it works fine.

[Dirk Gregorius]

So how do you treat restitution for the potential contacts? Do apply the collision for them as well?

[ngbinh]

So how do you treat restitution for the potential contacts? Do apply the collision for them as well?

No, look at the result, you can find which contacts are actually active ( normal force positive ), then you can apply any restitution law to them. It's basically the same as everyone doing.

[fishboy82]

Hi ngbinh:
Impressing Demo, Could you show me the Triankle's Paper about those Prevention Method rather than Correction Method for read further. So the prevent Method is the main idea you want to introduce? And the Solver which we choose is insignificant right?