Multi-Level "Weight" Simulation

[Eternl Knight]

Two mini-subjects now to respond to....

General Character vs World Simulation:
So, assuming I have this correct, there are X steps in your simulation:

1. You simulate the world without the character included
2. You obtain the impulses needed to drive the character in the world from your kinematic model (i.e. user/animation input)
3. You simulate the character in the world (tracking any impulses to be applied to dynamic world objects)
4. Back to step one (carrying over impulses from above step)

So in step one, the brick falls into the area that WOULD be obstructed by the character head, except said head is not in the model. In step two, you get the movement impulses for the character. Step three checks the character collision/physics model against the world (finding the brick collision with head and obtaining the impulse to "bounce" it away). Then back to step one where the brick will bounce away due to the previously obtained impulse.

this I guess works well for pure dynamic objects in the game, but how do you handle the "immovable object" issue. Given the fact that character is controlled kniematically - is there "special case" code for handling character/static-world collisions or is this somehow catered for in a way I am not grasping?

If this is not too difficult - is it possible to whip up a quick Bullet demonstration fo the technique (say with just cubes/capsules representing the character, static-world & dynamic objects)?

Predictive Impulses / Constraint Resolution:
This is an interesting hack. Are either of you intending to implement this in a test case (Bullet or otherwise) to see if the intuition matches the mathematical reality? I think that it might improve the weight ratio issue, but by now means fix it. I think that by the time the slope becomes negative, the issue will have already cropped up for the "watermelon seed".

--EK

[Erin Catto]

This is how the character system works:

• Physics step without any character representation at all.
  Collect collision planes for character, mark each as static or dynamic.
  Use a PGS/SI style position solver that tries to reach the goal position while satisfying constraints. Only the character is affected by this solver (a single capsule).
  Move to new position and loop back to step 2 as needed.
  A record of all collision planes (with associated shapes/rigid bodies) is now available to the game logic.

The position impulses have units of length, so I can clamp position impulses for dynamic planes so that static planes always win. Note that in the character solver, dynamic planes don't move, they are just labeled dynamic as a priority scheme.

I'm not very familiar with the Bullet code base, but eventually I will try the impulse acceleration in Box2D. I also plan to implement the character system at some point (close to the bottom of my todo list).

[Erwin Coumans]

If this is not too difficult - is it possible to whip up a quick Bullet demonstration fo the technique (say with just cubes/capsules representing the character, static-world & dynamic objects)?

I'm planning to add a similar character controller system to Bullet, using the convex cast. This convex cast essentially sweeps an arbitrary convex object (not just a box or capsule) to find collision planes (each point and normal at a given time of impact produces a plane). The most interesting part is mostly two-way interaction between character and rigidbodies indeed, so I might do some experiments using different approaches. One approach has a dual representation for the character, both a kinematic capsule as well as a proxy-rigidbody. This proxy-rigidbody is purely to 'measure' the interaction/impulses with rigidbodies. So the rigidbody simulation is only aware of this character proxy-rigidbody. Some explicit synchronization happens to keep the character capsule and proxy-rigidbody together. This gives full control of the interaction. But there is many other approaches to handle two-way interaction, which is not specific to character versus rigidbodies. Such two-way synchronization happens any time when two separate physics systems meet (for example rigidbody versus cloth).

Hope this helps,
Erwin

PS: from reading the posting on this forum, Box2D seems very similar to Bullet (3D) in most perspectives/concepts, although the naming is different (Bullet's btCollisionAlgorithm maps to Box2D Arbiter etc).

[Dirk Gregorius]

Erin,

is your acceleration method similar to Aitkin's method? E.g.: http://math.fullerton.edu/mathews/n2003 ... enMod.html

There are methods that can improve the convergence of GS or Newton methods (quadratic or super linear convergence vs linear convergence). I think basically you extrapolate the (lambda) series. Where I see a potential problem is for unary constraints where you could potentially extrapolate over the limit. I some simple implemetations that compute an optimal SOR parameter each iteration. I see that this might work for LSs, but I am not sure for LCPs.

Another acceleration method are Chebyshev polynominals, but I don't understand this.

Anyway, I will try your method and post the results here...


Cheers,
-Dirk

[Erin Catto]

It is a variation of Aitkin's method. If you apply Aitkin's acceleration blindly it will give you a predicted accumulated impulse. This leaves no room for clamping or checking for a negative slope on the corrective impulses.

[Dirk Gregorius]

Can you explain the idea with the negative slope? I can't follow here. Do you know any references on this topic?

[Erin Catto]

When I say slope, I'm talking about the slope of the curve. If you run my matlab code, you will see a plot of the corrective impulses (c1 and c2). Set extrapolate to 0. The plot shows that the corrective impulses are converging (descending) to zero. Since the corrective impulses are positive, this means the slope of the curve is negative. In this case it is safe to extrapolate. If the corrective impulses were diverging (ascending) it would not be safe to extrapolate.

[Dirk Gregorius]

I see - in order for the whole system to converge the delta impulses must vanish. So a basically we require dP(n) < dP(n-1).

But why extrapolate using the area under a triangle or parabola?

[Erin Catto]

Because the accumulated impulse is the sum of a train of corrective impulses, in other words:

accumulated impulse = sum(1, n, corrective_impulse_i)

This is completely analagous to integration of the area under a curve.

[ewjordan]

Here's a picture that might explain a little bit of what's going on with the negative slope issue (just a gimp-job, not results from a simulation or anything...):



This is a position space picture of a two element chain attached to the ceiling, where the x-axis represents the distance from the ceiling to the first particle, and the y axis is the distance from ceiling to the second (I know we've been talking about velocity constraints, but this will serve to illustrate the general idea here). The blue line is the locus of points where the first link is satisfied, the red line is where the second link is. The global solution is where these intersect.

The way the normal iteration process works is:

1) Project the current position to the blue line along the line with slope 0.
2) Project the current position to the red line along the line with slope -m2/m1 (using Verlet this enforces conservation of momentum)
3) Goto 1 until done.

The green sawtooth shows this process in action - as you can see, for -m2/m1 fairly close to 0, we make very little progress in each iteration. Furthermore, after the first step, everything is very regular and predictable.

As far as the negative slope thing: Erin's approach is to wait until we've reached that regular region, which is measured by checking that the magnitude of the sawtooth is decreasing iteration to iteration, and then use that information to follow the purple path instead of the green one and jump right to (or just about to) the correct global solution. Notice that the first couple of iterations would lead us to think that the magnitude of correction was increasing, which means we can't make any best guess about where the convergent bit will end up. It seems like a physically plausible assumption that most of these processes will eventually end up in a predictable and slowly convergent tail period, and this is what the extrapolation would accelerate.

Obviously the main potential pitfall is that the horizontal purple line jumps WAY out into a different region of phase space (off the image, even) in order to force the diagonal move to end up at the global solution (keep in mind that the slope of the diagonal line is constrained by conservation of momentum); it goes further off the worse the mass ratio. For this particular case this is fine, since the error function is very simple over this 2d slice of phase space but with other constraints in effect, there is no guarantee that this far off point will have anywhere near the same properties as the current one - in particular, subsequent projections may be extremely poorly behaved under such a scheme. Also if one of the constraints takes a very strange form we may jump to the wrong global solution. The assumption of linearity may even lead us into a divergence if things go badly enough - I'm doing some testing at the moment to see about this, to figure out what assumptions we need about the constraint functions so we can avoid such scenarios.

To some extent this method is really just a slightly beefed up version of straightforward gradient descent: we start with a naive minimization along coordinate axes and see if we can use the information gained from that attempt to (effectively) pick better axes to minimize along. In particular, this method would get us along a thin valley very quickly; however, its potential failure is that it gets us along the valley by jumping very far out to the side of the valley and hoping that it will get pushed back in by the next constraint applications, which it probably will if they are linear enough. In contrast, a more usual (but not quite naive) gradient descent method would explicitly choose to minimize along the direction of the valley floor.

I am not familiar enough with Box2d or Bullet to put together a demo that would test this idea (I finally got both compiling, but I haven't hacked around either one before so I'd need too much time just learning what goes where to knock off something quick), however I do have a 2d Verlet engine running, so I will eventually be able to test the idea in that slightly different context. I'll certainly report what happens.

[Erin Catto]

ewjordan, this is funny. Your example reminds me of character collision. Character collision solvers typically have a hard problem with acute angles like that.

A character will run into a acute corner and the solver will ping-pong back and forth trying to find the goal position. Some character systems don't iterate and can't handle acute angles at all (the artists must fix it).

So we could potentially use this acceleration technique to help out character collision with acute angles. So now I managed to bring the topic back to character handling again.

Anyhow, velocity constraints are linear so I'm guessing a mathematician wouldn't have to hard a problem determining the convergence requirements for impulse acceleration.

[ewjordan]

Right, this type of thing would accelerate the acute angle projection problem. But (and this is a pretty big but), it breaks down if there are other walls in the scene, as the intermediate acceleration step moves the character a long way away from the allowed region, possibly into proximity of other walls that might upset the whole process. This is probably the clearest example of the problem with this approach - the linear assumption can break down quite violently since we have to project so far out into phase space. For the acute angle thing there are certainly hacks that could be applied to restrict the acceleration to only combinations of two walls that "fight" each other, and it could probably be tuned to work quite well for those situations.

I also tried using this technique with a Verlet/Jakobsen-style N-chain, with position-based impulses and gravity, with a very large mass hanging at the bottom. Long story short? It does considerably speed up the convergence, sometimes, but when it fails, it fails spectacularly, with blowups galore. The problem is that every accelerated step bumps the system into a displaced state that takes several iterations to settle back, the number of which depends on the mass ratio and how long the chain is. If you do another accelerated step during this settling period, things get pretty unstable. This means that merely doing an accelerated step every other iteration doesn't work very well. It appears that if everything is tuned correctly, even a 50 element chain with a huge weight on the end can have its convergence sped up quite a bit, but if you've got the constants set badly, the whole thing blows up violently. I have yet to try the same thing with pure velocity constraints instead of the Verlet position/velocity/acceleration mashup, so things might be better behaved there, I'm not sure - when I get a chance, I'll try it out.

I think there's definitely a bit of utility somewhere here, the trick will be to figure out if we can apply it in a safe way to a completely general situation. The other thing I've noticed is that we're not likely going to achieve much with something like this unless we're doing quite a few iterations - you don't get much help in the first three or four, but if you're going out to 10 or 20 you might see some significant improvements. One last thing: it's absolutely vital that the last iteration is a regular one, because these accelerated constraint rounds do not generally cause you to satisfy _any_ of your constraints by themselves!