Joint Limits (Box2D and Weinstein)

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Joint Limits (Box2D and Weinstein)

Post by raigan2 »

I've been fooling around with adding joint limits to my simulator, and so far it's working a lot less well than i expected.. the angular correction seems to really fight with the joint constraints, resulting in terrible convergence/stability.

(this is all in 2D)

I'm using angular-only impulses to constrain the relative orientations of two bodies to be within some range. I'm making sure to only apply impulses if the bodies are "non-seperating" (i.e if the relative angular velocity is pushign the objects further into error).

It seems obvious that this sort of approach will clash with joints, because each angular constraint rotates the bodies around their COMs, while each joint limits the bodies to rotate only around a shared point point.. which is NOT the COM.

Am i missing something? I don't really understand the method Weinstein uses to correct linear/angular joint error, but the idea is that each is handled seperately/independently of each other..


Also, it seems like in 2D it shouldn't be too hard to solve both the linear and angular constraints simultaneously, however i'm having a hard time figuring out how to formulate this. Any hints?
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

Here are a few thoughts:

- it is easier to apply the joint limit as a separate impulse from the joint constraint.
- the joint limit for a hinge should only produce an angular impulse.
- allow for some slop at the limit for Baumgarte (otherwise you'll get jitter).

The formulation goes like this:

Angular momentum:

w1 = w1b - invI1 N
w2 = w2b + invI2 N

N = angular impulse (scalar in 2D)


Constraint:

w2 - w1 = 0


With Baumgarte:

C = angle - angle_limit
if abs(C) < small_angle
then C = 0

w2 - w1 = - beta/dt * C

(now you can compute N).


Accumulated Clamping:

Na = Na + N

If at the lower limit: Na = max(Na, 0)
If at the upper limit: Na = min(Na, 0)

N = Na - Na_old

(now you can update w1 and w2).
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

In order to setup a simultaneous formulation you can do the following:

1) Build position constraints C(x1, x2)
2) Build velocity constraints dC/dt = J*v and find Jacobian by inspection
3) The K matrix is simply J*W*JT and the relativ velocity (that is the velocity error) can be comupted as v_rel = J * u with u = (v1, w1, v2, w2)
4) If you want stabilization you add a Baumgarte term using e.g. 0.1 *C(x1, x2) / dt

All together is looks like this: J*W*JT * lampda = -0.1 * C(x1, x2)/dt - J * u -> lambda = -Inv( J*W*JT ) * (0.1 * C(x1, x2)/dt + J * u)
In order to find the global impulses you can project them back onto the constraint manifold: P = JT * lambda with P = (P1, L1, P2, L2) where P_i is the linear impulse for body_i and L_i the corresponding angular impulse. Bot can applied at the center of gravity.

I also recommend applying limits as a separat 1D impulse and only solve e.g. hinge as a 5x5 block

HTH,
-Dirk
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

[Erin]: Thanks -- I'm sorry if my post was a bit vague, what I'm currently doing is what you recommended: the joint constraint is limit-less as in your Box2D code, and the joint-limit constraint is a seperate constraint that applies an impulse only to the angular components of the bodies.

Things work fine using Baumgarte stabilisation, however I'd like to use a better/less-soft stabilization technique, similar to your split-impulse/bias-impulse method or the recent pre-stabilization paper by Weinstein et al ("Dynamic Simulation of Articulated Rigid Bodies with Contact and Collision").

My question could be rephrased as: why can't I get split/bias-impulse position correction to work for joint limits? Is this related in any way to the similar problems with split/bias-impulse correction and joints? It seems to me that since your split/bias-impulse method works well for contact/normal impulses, which are similar to joint limits, I should be able to use split/bias-impulses and not Baumgarte in order to move things towards a valid state.


From what I understand of that Weinstein paper, they're solving both the joint and joint-limits together using an approach that seems similar to split/bias-impulse: before updating positions, use the current position error and current position-correcting-velocities to predict the future position error, and then apply impulses to the position-correcting-velocities to move the future error towards 0.

The part I'm struggling with is how they actually _do_ this, the math is beyond me. You want to end up with a regular impulse (they call this a "linear" impulse) which moves the joint points towards each other, and an angular impulse which moves the joint angle towards the clsoest valid angle.. I was hoping that in 2D the system you'd need to solve for these two impulses would be small enough to handle directly (instead of just solving for the linear and angular impulses seperately as Weinstein does).

[Dirk]: thanks, i'm still learning the math, i'll bust out my pencil and paper and get to work..
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

R. Weinstein computes an impulse such that the position constraint at t+dt will be satisfied when integrating forward in time. This is what she calls the Pre-Stabilization. Since position constraints are non-linear (as opposed to velocity constraints) she needs a Newton solver for this.

Did you try the impulse splitting for limits? I actually don't see a reson why this shouldn't work? What were you problems?

-Dirk
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

@Erin:
C = angle - angle_limit
if abs(C) < small_angle
then C = 0

What if C is big? Do you also clamp when there is a big violation of the limit? Also what do want to catch with this clamping and what is a common value you usually use for "small_angle"?

Cheers,
-Dirk
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

Dirk Gregorius wrote:Did you try the impulse splitting for limits? I actually don't see a reson why this shouldn't work? What were you problems?
-Dirk
I did try this, it converged _much_ less quickly than using Baumgarte; possibly I was doing something wrong though, I'm going to re-implement it tomorrow and see if things are the same.

I'd really like to know why impulse-splitting doesn't behave well for regular joints (it leads to oscillations). Working things out on paper, it seemed similar to problems that arise with some Jacobian-based IK methods around singularities -- the direction you want to move is perpendicular to Cross(r, impulse), so you end up oscillating back and forth along the axis perp. to the position error/delta.

One thing that bothers me is that even for a single joint and no gravity/external interference, the impulse-splitting method often doesn't correct the position error in one iteration.

To "fix" this I developed a procedural/geometric stabilisation method which corrected the position error exactly in one step by translating and rotating the objects as little as possible proportionally to their linear/angular masses.. it was similar to Lee's "A Procedural Approach to Solving Constraints of Articulated Bodies". This method works great -- it's a bit more expensive than split-impulses since you update the body states/mass-matrices/etc at each iteration. However it doesn't seem to cooperate well with joint limits, and I haven't been able to figure out a nice way to extend it.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

[Dirk]
My logic for slop wasn't complete. Here's the full logic.

Code: Select all

if (angle >= angleUpper)
{
	// use slop
	if (angle < angleUpper + smallAngle)
		C = 0;
	else
		C = angle - angleUpper;
}
else if (angle <= angleLower)
{
	if (angle > angleLower - smallAngle)
		C = 0;
	else
		C = angle - angleLower;
}
You can also limit C from being too big. This will help prevent the addition of momentum (in the Baumgarte case).

[raigan]
I hope you can get the split impulse to work with limits. This would be an important result. Dirk, did you ever try it?

I wonder if there is an interplay between Baumgarte on the joint and the split impulse on the limit. You should still use a scaling factor on the position correction. Rotational constraints are nonlinear, so you will not be able to make large angular corrections in one step with the split impulse method.

You should test this on a simple pendulum first. Try to hold the pendulum horizontal. You can verify this case easily.
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany
Contact:

Post by Jan Bender »

[raigan2]

Maybe you want to try with the approach I presented in this paper:

http://i31www.ira.uka.de/docs/Paper_VC05.pdf

In fact it is nearly the same method as R. Weinstein has presented. At my institute we use this method since many years. And I think this should converge very fast.

I also use a pre-stabilization method but without solving a nonlinear equation. Instead of solving the nonlinear equation iteratively I make an approximation for the velocity change and then I get a linear equation. Due to the approximation it has to be solved iteratively (usually I need one or two iterations) but a linear equation has big advantages. For example you can build up a system of linear equations for all constraints and get all impulses in one step.

Jan
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

[Erin]
I only implemented the split impulse for both joints and limits. Everything looked more rigid, and not so good as with the Baumgarte method. So I switched back to Baumgarte again. I will give it another try - with the pendulum - again when I have more time. I think we should also look into the suspension bridge to verify the problems you described with the Box2D demo...

-Dirk
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

Jan Bender wrote: Maybe you want to try with the approach I presented in this paper:
Jan
Thanks -- how many derivatives/what order of taylor-series do you typically calculate for a simulation step? Really what i want to ask is: is this method stable using only one taylor-series-term/using a standard integrator?

Also, I didn't understand if position and velocity are both integrated at the same time/in what order.. it says that after applying position-correcting impulses, you integrate forward, THEN you correct velocity error.. but it doesn't mention if you _then_ integrate velocities.

it seems like you're doing:
-iterate: velocity-correcting-impulses
-iterate: position-correcting-impulses
-integrate positions and velocities

which seems sort of like Baumgarte stabilisation, except that you use predicted/future positions instead of current positions to calculate the position error.


This also seems very similar to Erin Catto's method, I'm actually a bit confused about what the practical differences are.. the steps you each take are different, but you both seem to be currecting position error using a predicted position which is the sum of a constant position (position at time t) and a changing velocity (which varies as impulses are applied).


One difference is that you predict position error using position at time t and velocity at time t, while Catto uses position at time t and velocity at time t+h. You're also using a more complicated predictor, I think Catto uses linear prediction (i.e you're using a long Taylor-series and he's using only the first term).

This might be related to the other major difference, which is that he uses semi-implicit Euler instead of <not sure what your integrator is called>.


Actually, it seems like your two approaches are identical except that Catto tracks actual-velocity and position-correcting-velocity seperately, while you use a single velocity, applying both position-correcting and velocity-correcting impulses to it.

Aside from that, you're both doing similar position-prediction, with your repsective integrators. (i think..)


(I'd love it if someone a bit more experienced could summarize the differences between the various iterated-impulse simulation approaches.. each of the Guendelman, Catto and Bender seem to be doing the same thing with slight variations!)
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

The sequential impulse algorithm was developed to be mathematically equivalent to the Projected Gauss-Seidel algorithm for solving LCPs, but simpler to understand and implement.

The method for handling position projection is secondary. Basically you can do whatever you like, as long as it is convergent. Since position projection is a nonlinear problem, there are a huge range of algorithms available. The Baumgarte method is likely to be one of the fastest methods. However, it has some downsides, as many of us know.

When developing an algorithm for position projection, it is helpful to keep in mind the abstract mathematical problem being solved. We want to adjust the positions as little as possible to satisfy the position constraints. The position constraints are nonlinear. So this is a nonlinearly constrained minimization problem. The position adjustment can be measured in many ways, but it makes sense to consider the mass of the bodies being moved.

The split impulse method (SIM) seeks to remove the position error while adjusting the positions as little as possible considering the mass of the bodies. The solution is not terribly accurate because SIM seeks to solve the problem over several time steps. However, it is not hard to imagine a solver that applies SIM several times in one time step in order to reduce the position errors further. So the accuracy-performance trade-off can be adjusted freely.

I have not implemented Jan or Guendelman's algorithms. But I encourage you to give it a shot. A nice way to compare them might be to see how they handle the 1D problem of a particle hitting a plane (only vertical motion). From there you could look at the 1D problem of a simple pendulum with a single particle and a distance constraint (this would add some nonlinearity). From there I would consider how they handle box stacking. Are the stacks stable and do they behave realistically?
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

I've been working on just that (trying different "position correction" methods side-by-side); what i'm stuck on is joint-limits/orientation-constraints, I haven't found anything that works better than Baumgarte (unless you ramp up the iterations). Hopefully I'll have time in the next couple of days to actually try the Guendelman and Bender methods (instead of plugging in different position-correction methods into your code).

It just seems like correcting orientation in isolation is unlikely to be a great approach, because often the changes produced (rotations around the COM) are almost exactly opposed to those generated when correcting point-to-point/joint constraints.. convergence becomes a lot worse.

Since I only have another week or two before i need to actually get something working/finished, Baumgarte might have be good enough for orientations.

Thanks again for all your help.
gee
Posts: 14
Joined: Mon Aug 14, 2006 8:36 am
Location: Paris, France
Contact:

Post by gee »

Hello,

I have not read the complete thread, but I want to say that if you're using bouncing, do not do error correcting and boucing at the same time, it may lead to troubles.

Also be carefull with the value of the bouncing.
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany
Contact:

Post by Jan Bender »

[raigan2]

In fact it is not important, if you use a Taylor series, a Runge-Kutta or just Euler for integration, also for the predictor. The only difference is of course the accuracy.

The simulation step works as follows:
http://i31www.ira.uka.de/projekte/mechanik/img/Pic8.gif

- iterate to determine the position-correcting impulses
- integrate positions and velocities (first the velocities because you will need them to determine the new positions and rotations)
- iterate to determine the velocity-correcting impulses

For more information maybe you want to take a look at my homepage:
http://www.ibds.de.vu


If you want to solve a LCP with my method the paper

"Constraint-based collision and contact handling using impulses"

is maybe interesting for you.

Just tell me, if you have problems to implement the method.


Jan
Post Reply