Multi-Level "Weight" Simulation

[Eternl Knight]

It is a well understood and (for gaming purposes) pretty much unsolved problem that one cannot have large weight ratios in a physics simulation without stability/feasibility issues.

The usual "solution" tends to be "squishing" the allowable object weights into a smaller range. Side effects of this are the ability to push around cars by "running" at them, bullets being able to twist tanks, etc.

This is something that will be popping it's nasty head up soon in my game. I put a little thought into it and came up with the concept that if the weight difference between two objects is outside a particular range - why not make the other object's mass "infinite". That is, for the purposes of interaction between the two objects, the object with larger mass is simulated "kinematically" only where as the other is treated as normal. Intuitively, this would result in things like tanks/cars/etc being unaffected by thrown objects and the like - but could still be effected by jeeps crashing into them, large missiles, etc.

I cannot be the first to think of this relatively simple idea. So my question is what is wrong with the concept. Are there known stability/performance issues with this idea? Has anyone tried this?

--EK

[Erin Catto]

The large mass ratio problem should be qualified. The actual problem comes up when low weight objects are supporting high weight objects. For example, stacking a 100 pound box on top of a 1 pound box will often lead to the so-called "watermelon seed" effect, where the bottom box will get squished out the side.

The opposite arrangement, a 1 pound box on top of a 100 pound box, is incredibly stable (at least with engines that operate like Box2D).

If you think about this limitation, it is not too bad at all and often leads to plausible behavior. What would happen in reality if you stack a 100 pound box on top of a 1 pound box? It will likely be unstable.

Going back to your bullet-vs-tank example, things are not so bad. Just make the tank as heavy as it should be and the bullet as light as it should be. Then the bullet will not move the tank and you will get a stable interaction. If the tank tries to drive over the bullet, the bullet will get squished out, and I think that is a reasonable behavior.

In TRL we had rigid bodies for trains that weighed thousands of pounds. We were able to easily stack boxes on the train. You could ride your motorcycle on top of the train and everything worked as it should. Now if you put the motorcycle in front of the train, the motorcycle would be brushed aside.

At one point we had a problem where grenades would push crates around too much, and that was resolved by realizing that a grenade should be about 1 pound, not 5.

Where you really get into trouble in games is with "superman" effects, where the characters are given abilities with insane strength. In TRL we made the mistake of making the grapple too strong and this lead to all sorts of tuning problems. So it is best to try to make all values as realistic as possible so that you get the expected behavior.

[raigan2]

One problem I can think of is that you're replacing "slow convergence" with "no convergence" for problem cases -- for instance, if a small object is squished between two tanks, between a tank and a static wall or floor, etc..

[mewert]

I don't mind watermelon seed effects so much. It's more of a problem when your tank pushes an object ( potentially an important game object ) completely through a wall or the floor. Depending on your character control scheme this can be a constant and annoying problem. Many games imlement their characters as infinitely heavy objects w.r.t physics. Being affected by the physics in a feed-back loop, rather than as a 1st class physics object being solved together with everything else. It becomes quite easy for this type of character to push boxes, etc through walls, or at least create some nasty jitter.

One solution I've seen, in that case, is to have a physics proxy for the character which has a reasonable mass and is attached to the infinitely heavy kinematic position by a point-to-point constraint or a strong spring. And you move the character to the point-to-point position when it gets stretched. The collision object is at the constraints position ( physics proxy ). You have to tune this carefully to avoid the character jittering and affecting the camera.

[ewjordan]

I've recently run into some nasty issues of this sort (light things getting hammered through walls) in a 2d Verlet engine I've been playing with - if you're using thin enough stationary walls (in my case they are necessarily infinitesimally thin lines with no clearly defined inside or outside, so allowing a small amount of penetration to be corrected later is not an option), a heavy object moving quickly can smash a light one right through just about no matter how many iterations you go through in a constraint loop, since at some level you have to cut it off. The end result is inevitably that the light particle ends up on the wrong side of the wall because a reasonable number of iterations cannot get the heavier particle to back away appropriately. Same problem would seem to apply under conservative advancement, where you end up taking ridiculously tiny steps that threaten to grind the whole simulation to a halt as the small object gets paddled back and forth increasingly fast between the large one and the wall (though perhaps a good treatment of contact avoids this? I've still never tried using CA before, so I'm not really sure).

It would seem that what really needs to happen in this type of case to absolutely prevent tunneling is that the effective mass along the surface normal needs to become much larger while still remaining small along the tangent direction. But it gets a little trickier when the object it's pressed against is not fixed, as that needs to respond correctly, too. Is there a standard way of dealing with this problem? [I know that even in pure textbook physics multiple simultaneous collisions can be tricky, as conservation laws alone don't uniquely specify the outcome - usually there you would have to sort along collision normals and figure out a chain of sequential collisions to calculate, but I haven't thought about it enough to implement an algorithm for the general case]

[Erin Catto]

I made a character system where the character proxy was purely kinematic and collision was handled by iterative position corrections. I accumulated position "impulses" for each constraint. Then I limited the impulse for dynamic constraints, so that static constraints would always win. You can iterate until your static constraints are satisfied.

With this system you could drop a 16 ton weight on the character and they would simply pop out to the side.

[ewjordan]

Right, that's an interesting approach - am I correct that when you say you limit the impulse that means that you keep summing the impulses and then constrain them to the limiting shell, so that even if you've maxed out the impulse along the normal you may still acquire a tangential component? Otherwise it would seem that you'd ultimately end up violating the dynamic constraint pretty severely (I'm thinking of a large heavy box pressing a light sphere into the ground plane at an extremely shallow angle - stiffness aside, unless you allow the impulse to accrue tangent to the plane once the vertical component has maxed, you'd eventually end up with the particle inside the box). However, that approach still doesn't entirely cover the back-reaction on the heavy object - ideally, the amount of weight something can successfully support and its own mass should be entirely disconnected (putting aside general relativistic effects for the moment...), and it should not be computationally prohibitive for a light object to prop up a very heavy one. In reality I agree with your earlier comment that most of the time a very light box is unlikely to support a much heavier one, but as far as the equations go, it's possible. The watermelon seed effect often seems reasonable, but I've definitely played a game or two where stuff like that broke the illusion of physicality, since the mass ratios where game physics becomes unstable tend to be quite a bit less severe than the ones that we see in the real world (propping a several thousand pound car up with a 2 lb jack comes to mind as an example).

I wonder if there might be a reasonably efficient way to set up something similar to your scheme where one does not need to draw a sharp distinction between static constraints and dynamic constraints, perhaps a method of tuning the incrementally applied impulse based on the current magnitude of the accumulated impulse so that you could handle a situation like two 1000 kg boxes hitting face on (no preferred direction of tangential projection exists, so any popping out the side would qualify as a hack or a bug) with a 1 g pebble between them and still end the step with the constraints fully satisfied (am I correct in my assumption that your method would not accomplish this since both are dynamic? Assume a 1-d simulation if you wish to avoid that whole tangent possibility...). The ideal would be to figure out a way for the pebble to transmit the entire momentum of the left box to the right one without having to explicitly handle both constraints simultaneously...this may be a tall order, though I'm not sure without some further thought. For something like this to work without too many iterations you'd need to figure out a way to do this that would speed up the rate of impulse transfer through the pebble so you don't need ~1,000,000 iterations to get all that momentum through, but something similar to your method may be able to achieve that, maybe a simultaneous lessening of the impulse in one direction and increasing in the other. Conservation would no longer be local once asymmetry in the collision response enters in, so a global conservation proof would need to accompany (and probably provide the details of) any such scheme, basically showing that the asymmetry induced at a particular constraint would necessarily have had to arise from a similar and compensating asymmetry from another constraint/set of constraints.

[Erin Catto]

I'll try to clarify my algorithm a bit more.

The physics world does not see the character. The character is processed after all the physics. I only used surface normal constraints, so there was no friction. This is a typcial situation where you want characters to slide smoothly along walls.

In the shallow angle situations you mentioned I would have more iterations. Any small angle would lead to the watermelon seed effect. In very constrained circumstances, the character would overlap dynamic objects. However, movement was not restricted, so the character could still move and quickly pop out of the dynamic object. While this could lead to a brief visual artifact in extreme cases, it would never lead to game play bugs.

Important game play objects like doors should be treated as static, even though they move. In these cases kindly ask your designers not to make doors that push characters out of the world.

I did not apply this algorithm to prevent light dynamic objects from tunneling or to solve the heavy-on-light problem. But it seems applicable if you have a separate position projection phase in your algorithm. I think if you solve your constraints with velocity impulses then you can do whatever you want in a separate position projection step (see our discussion of Jan's Impulse Based Dynamics library). You don't even need to consider mass at that level.

BTW, global solvers, such as CG do not have the heavy-on-light problem (at least not as bad).

Even in engineering codes, univeral joints are usually modeled without the little cross-brace due to mass ratio problems. So for your car-jack, I would try to use some sort of constraint without a small intermediate mass.

[Eternl Knight]

Erin,

Trying to grok how you work things in your engine. If I understand it correctly, the character can apply impulses to the physics world (obviously, otherwise why bother with physics) but the character's "collision" object is not present in the physics world. Is this a correct assumption?

If so, how do you handle the character's effects on the world? For example, dropping a brick onto said character should bounce (a little) off their head, however without their collision shape being a part of the standard world - is this ignored?

--EK

[Erin Catto]

Well, I think that having the player as a rigid body is frought with peril. My kinematic approach allows for total designer control over interactions without affecting control.

In your example, I could choose to apply an impulse to the brick or simply move out of the way. I don't need to worry about the brick getting stuck on the character's head and looking dumb.

In TR we made the conscious design decision to have all player physics interactions handled by purposeful/animated interactions, like kicking, grabbing, grappling, shooting, or simply standing/hanging with weight. I don't care much for the Max Payne look of running against boxes without any supporting animation or control modes.

So my approach won't let you stack boxes on the character. That's what the forklift is for.

[ewjordan]

Yup, that (your use of the algorithm and what it was/was not intended to do) makes sense. I'm not going to drop the discussion quite yet, however, because EternlKnight's original question did seem to relate to some of the things that your algorithm didn't address, but I suspect it may give a clue as to how to get to a decent solution.

I did not apply this algorithm to prevent light dynamic objects from tunneling or to solve the heavy-on-light problem. But it seems applicable if you have a separate position projection phase in your algorithm. I think if you solve your constraints with velocity impulses then you can do whatever you want in a separate position projection step (see our discussion of Jan's Impulse Based Dynamics library). You don't even need to consider mass at that level.

I'd agree with that, though for the purposes of heavy-on-light stacking, the position projection is not really at the root of the problem, it is the velocity stuff (which is all bound together if you're using Verlet, but that's another nasty issue altogether) that is difficult to handle. In my opinion, the fundamental problem is that the obvious way of iterating velocity constraints pairwise (using the standard collision resolution formula from high school physics) breaks down in 1D if you look at the "sandwich" problem:

A-> B <-C

with A.mass = C.mass >> B.mass (that's a "much greater than," not a shift). The velocity constraint is satisfied only when A.v < B.v < C.v. The difficulty is that the only reasonable way to resolve each pairwise velocity constraint is to do a collision with some coefficient of restitution, and unless you allow explosive coefficients of restitution, the number of iterations to get those constraints satisfied grows as O(sqrt(A.mass/B.mass)) if my back of the envelope calculation is right. This isn't horrendous, but it's not great, either - once you get up to a 100:1 ratio, you're probably pushing the limits of how many iterations you're going to be able to afford with all the other stuff that happens in your loop.

BTW, global solvers, such as CG do not have the heavy-on-light problem (at least not as bad).

Right, but global solvers have their own issues as well, so people are somewhat loathe to use them. Philosophically, at least (and for the purposes of simplicity in code), there is a lot to be said for considering a contact to be a purely local construct - Box2d always does this, no?

So the real question is the following: using _only_ the information locally available to a single contact, maybe including information from previous iterations, is there a way for the contact to figure out how to alter its response between two bodies so as to accelerate convergence when those bodes are also acted upon by other contacts? [that is, without explicitly figuring out chains of contacts, which starts to head into global solver territory] I'm not sure myself - maybe this is already a solved problem, I guess that's what I'm wondering. If not, it seems that the idea of looking at the degree to which a contact's hard work has been screwed up by other contacts when it comes time for the next iteration might be a pretty good local indicator of how the contact should change its behavior - for instance, if I put myself in the shoes of a contact, and every time I give a particle some velocity it is exactly reversed when it comes back to me during the next iteration, it seems pretty likely that I'm pushing that particle up against a solid wall and I might as well just zero out velocity altogether and handle the pressing body's velocity accordingly, skipping the whole back and forth dance that would otherwise slowly dole out the required momentum change. But maybe that's not a very promising way to handle this type of situation, I'm not sure.

As an aside, is the heavy-on-light effect the reason box stacks start to twitch when you build too high, or is that something else? Very roughly speaking, the mass ratios where you have single-box stacking problems seem similar to the number of equal mass boxes you can stack without dancing, but this could just be a coincidence.

[Erin Catto]

Yes, Box2D only solves constraints locally. This is much easier for people to understand than CG and CG does have some problems (not good with early termination).

So I took up your challenge and wrote a Matlab file that simulates a 1d chain hanging from a fixed point. There is a light mass m1 attached to ground and a heavy mass m2 attached to m1. Both masses feel regular gravity.

I noticed that the corrective impulses were always positive and decreasing (converging). With large mass ratios the convergence is slow. I had the idea to look at two corrections and guess what the remaining corrections might be. This is basically integrating the area under a triangle. I then used the triangle area as my corrective impulse. I apply the correction every other iteration to get a good slope.

It seems that convergence can be improved quite a bit using only the local history. However, I have no idea how this technique would behave in a general context.

Code: Select all

m1 = 1;
m2 = 100;
gh = 1;
v1 = -gh;
v2 = -gh;
lambda1 = 0;
lambda2 = 0;
t1 = [0];
t2 = [0];
c1 = [0];
c2 = [0];
extrapolate = 1;

for i = 1:100
   f1 = -m1 * v1;
   if extrapolate & mod(i,2) == 0
      slope = f1 - c1(end);
      if (slope < 0)
         run = -f1 / slope;
         area = 0.5 * f1 * run;
         f1 = area;
      end
   end
   lambda1 = lambda1 + f1;
   v1 = v1 + (1/m1) * f1;
   c1 = [c1;f1];
   t1 = [t1;lambda1];
   
   f2 = - m1 * m2 / (m1 + m2) * (v2 - v1);
   if extrapolate & mod(i,2) == 0
      slope = f2 - c2(end);
      if (slope < 0)
         run = -f2 / slope;
         area = 0.5 * f2 * run;
         f2 = area;
      end
   end
   lambda2 = lambda2 + f2;
   v1 = v1 - (1/m1) * f2;
   v2 = v2 + (1/m2) * f2;
   c2 = [c2;f2];
   t2 = [t2;lambda2];
end

plot([c1 c2])

[bone]

So the real question is the following: using _only_ the information locally available to a single contact, maybe including information from previous iterations, is there a way for the contact to figure out how to alter its response between two bodies so as to accelerate convergence when those bodes are also acted upon by other contacts? [that is, without explicitly figuring out chains of contacts, which starts to head into global solver territory] I'm not sure myself - maybe this is already a solved problem, I guess that's what I'm wondering.

It seems like you're alluding to one possible idea. Use the current force/impulse calculation, and then (before directly using it) extrapolate it some amount based on the previous iteration's final force/impulse.

Without trying it, I couldn't tell you if that's a good idea. I would guess not, it just seems like you're trying to cheat on the iteration process, trying to go faster than the algorithm actually allows. It may or may not work in this one case, and cause problems in others. Hey, but if it works, please let us know.

EDIT: looks like Erin beat us to it ...

[ewjordan]

bone: I agree, it very well may cause problems with the overall simulation, as it is trying to cheat the iteration process. I can think of a few cases where it should actually be all but provably impossible to end up with exactly the right outgoing momenta without actually going through each theoretical microcollision (basic one: particle A incoming with velocity 1 m/s hits particle B at rest next to a wall, all collisions are elastic - if you work it out or just run a sim, the outgoing velocities of both particles as functions of the mass ratio have cusp discontinuities, which indicates some nastiness in the actual functional form. I suspect this as an indicator that there is not going to be any easy way to pick out the exact correct outgoing momenta short of doing the full set of iterations.).

However, one characteristic of large mass ratio pinnings is that the iterations are primarily spent shuttling momentum quite trivially from a large source to a large sink, but it goes very slowly because the light particle acts as a bottleneck. Since for game purposes we're more concerned that the constraints are satisfied and done quickly, it's not necessarily such an evil thing to cheat a little and pipe the momentum over more quickly if it turns out not to affect stability (which it definitely could, to be fair) - it sounds like what Erin has tried is a linearization of the impulse curve, which might work with some tweaking (see below).

Erin: Very interesting, when I get a chance I'll see if I can try wedging an approach like that into an actual solver (probably later this week, I'm about to head into the woods for a few days so I won't have my computer). One thing that I do know is that the strictly decreasing quality doesn't hold in general. The following is a screen capture from a graph of the impulse between a 1000 kg particle entering with v = 1 and a 1 kg particle that's up against a wall. The particle/particle collision is elastic, and the particle/wall one has some inelasticity (though it's not entirely inelastic - that turns out to be the slowest converging case). This picture goes up to ~1000 iterations, I think.



With purely inelastic collisions you do get monotonic decay, as you noticed, but with any elasticity whatsoever you have a ramping up period during which you really couldn't apply the extrapolation technique. The upshot is that this initial period gets shorter the lower the restitution, and from there it's all downhill, so a linearization could probably be applied once you're far enough over the hump (probably when the second derivative goes positive would be safest). For perfect elasticity, the graph looks like a parabola, so a second derivative test wouldn't quite do it, but...

In any case, there's plenty of room to debate exactly how to do the extrapolation in the best way, but first I should check to see if this type of thing totally destroys an otherwise working engine in practice.

[Erin Catto]

My little algorithm above is reminding me of line searching techniques for one-dimensional minimization. However, in that case you can compute the function at any point. We have a function for the impulse increments that cannot be evaluated in the future. However, we do know that it is convergent to zero.

I think a quadratic extrapolation is worth trying. So you would extrapolate every third iteration (and then integrate the area under the parabola). Would anyone care to try this?

Certainly we should check that our increments are decreasing before extrapolating, otherwise the correction is unbounded. In my code above, I don't extrapolate if the slope is non-negative. I could imagine using some tolerance here to ensure sufficient decrease before boldly extrapolating. Of course this may be too late for the watermelon seed.