Sign in to follow this  
HalcyonX

Verlet ragdoll problems

Recommended Posts

HalcyonX    130
I'm writing a 3D verlet ragdoll, mainly along the lines of stuff found here: http://www.teknikus.dk/tj/gdc2001.htm It seems to be mostly working, but I've come across a problem. When multiple objects that are constrained to each other (ie. parts of the ragdoll) pile together, the pile sometimes starts sliding in some random direction. I'm guessing that this is caused when trying to satisfy multiple conflicting constraints (fixing one violates another, and in trying to fix them, the points get a net movement). I have no idea how this could be fixed without major changes. Can anyone help? Thanks.

Share this post


Link to post
Share on other sites
MrRowl    2490
You could cache your contacts from one update to the next - in particular those contacts that should result in no relative motion due to friction. Then during collision detection if you detect a contact between two features that matches a cached value, use the original constraint.

The same method will/should work for any physics system - see b34r's demos (e.g. here) which use an impulse-based simulator.

Share this post


Link to post
Share on other sites
AlfredR    122
You need to do some sort of damping.

In the real world, if the floor had no friction, the simulation would proceed as you describe. If you're seeing what I think you're seeing, then you're looking at a physically accurate simulation.

The problem here, though, is that friction is a velocity-dependent force. Velocity in verlet is only accurate up to second-order, while position is accurate up to the fourth.

So by introducing velocity into a force you will be increasing the error in the position, however, this is an acceptable solution for a game since it should still look right.

If the random direction is always different each time you run a test, in spite of having the same initial conditions you have another problem. I'm guessing, in that case, that your physics is dependant upon the frame rate. Small differences in the frame cause forces to be approximated as constant over varying sized timeslices. This causes radically different outcomes when running the simulation multiple times.

To fix that you'll need to make sure you digest passing time in the same sized timesteps. Do something like this pseudocode:

void Evaluate(float dt)
{
//member variable holding any left over fractions of time from the last time
_TimeAccumulation += dt;

// precalculate useful quantities;
float TimeStep = 1f / EvaluationFrequency;

while (_TimeAccumulation >= TimeStep)
{
_TimeAccumulation -= TimeStep;
//now accumulate forces and integrate using TimeStep^2
}
}



Kind Regards

Share this post


Link to post
Share on other sites
MrRowl    2490
Quote:
Original post by AlfredR
The problem here, though, is that friction is a velocity-dependent force. Velocity in verlet is only accurate up to second-order, while position is accurate up to the fourth.


No - friction is independant of velocity - at least in the sense you're implying. Also, the integration scheme (verlet, euler, RK etc) is not actually relevant either. The most likely things are that:

1. the OP hasn't implemented friction

2. it's implemented wrong (i.e. it's dependant on relative tangential motion, in which case it will never completely halt the motion)

3. The simultanteous constraints don't all get satisfied before you finish the time-step.

The last is probably extremely hard to do exactly using a particle-verlet method, because it operates on positions, and modifying the position to resolve one contact point will probably result in complicated effects on other points (it's "just" hard using an impulse based method due to solving the LCP exactly). Hence the "caching" solution - this allows you to detect that your constraints aren't getting satisfied and gradually ramp up the "strength" over a short period of time. The final error should be a constant position offset, rather than a constant velocity error.

Share this post


Link to post
Share on other sites
HalcyonX    130
Thanks for the replies, guys. You guys are right about the friction not being implemented being the problem. I tried removing the velocity component from the verlet integration, and the pile stops moving. However, I do use a bit of damping during the verlet integration (ie. x’=x+0.95(x-x*)+a*×Dt2), which usually brings the objects to a stop within a second or two. However, it doesn't seem to work for the pile, it does not. Any ideas why?

Share this post


Link to post
Share on other sites
AlfredR    122
Quote:
Original post by MrRowl
No - friction is independant of velocity - at least in the sense you're implying. Also, the integration scheme (verlet, euler, RK etc) is not actually relevant either.


I also get the impression that you attacked my previous post out of spite, if that's the case there's no need for you to be hostile.

As for friction being velocity dependent there's no "No" about it. Kinetic friction as it is modeled typically in physics depends upon velocity, as it opposes the direction of motion. The limit of the coefficient of kinetic friction as velocity goes to zero should be the coefficient of static friction.

A body sliding across a floor is a typical case for kinetic friction. If you take a moment to consider it you'll see that velocity dependent friction is a good idea, since very large forces can be brought back to reasonable levels quickly. the limit as velocity goes to infinity of the coefficient of kinetic friction can converge to some nice constant, if desired. And random erratic motion, in any direction, can be countered.

Velocity dependent friction goes by another name: Damping. It's very common and you should damp by some small amount in all directions naturally to avoid anything seeming frictionless.

Further, The integration method is most certainly relevant in a discussion of the order of the error terms due to the integration method (the context in which I mention verlet).

I agree with you and have already stated that he'll need to implement some sort of friction. I agree that it could be implemented wrong. Though I don't understand your example:

When things rub together the friction only depends on the relative tangential motion (note you say motion -- which implies velocity), i.e. the velocity with which object A rubs against object B and from the point of view of object A it doesn't matter what object B and C are doing.

Share this post


Link to post
Share on other sites
AlfredR    122
Quote:
Original post by HalcyonX
Thanks for the replies, guys. You guys are right about the friction not being implemented being the problem. I tried removing the velocity component from the verlet integration, and the pile stops moving. However, I do use a bit of damping during the verlet integration (ie. x’=x+0.95(x-x*)+a*×Dt2), which usually brings the objects to a stop within a second or two. However, it doesn't seem to work for the pile, it does not. Any ideas why?


How many times do you loop over your full set of constraints?

It's possible that your correction code is wrong, and that the constraint code actually diverges instead of converges.

Try taking smaller timesteps and see if the simulation is more well-behaved.


Share this post


Link to post
Share on other sites
HalcyonX    130
Quote:
Original post by AlfredR
How many times do you loop over your full set of constraints?

It's possible that your correction code is wrong, and that the constraint code actually diverges instead of converges.

Try taking smaller timesteps and see if the simulation is more well-behaved.


I loop over the constraints 5 times every 20 milliseconds, each time checking all constraints and then resolving collisions.

I tried turning it down to 10 milliseconds, and the sliding does get slower, but so does everything else, so I'm guessing it's just because the 0.95 multiplier in the verlet integration is being applied more frequently.

As for friction, how exactly should I implement it? I'm thinking that each time i find a collision, I'll apply onto each object a force against its velocity along the tangent of the surface. But how should this force be applied? Should I add the vector to the acceleration portion of the verlet integration equation? Or should I simply calculate the final velocity and adjust the object's previous position accordingly?

Share this post


Link to post
Share on other sites
MrRowl    2490
Quote:
Original post by AlfredR
Quote:
Original post by MrRowl
No - friction is independant of velocity - at least in the sense you're implying. Also, the integration scheme (verlet, euler, RK etc) is not actually relevant either.


I also get the impression that you attacked my previous post out of spite, if that's the case there's no need for you to be hostile.


AlfredR: No - very sorry if you got that impression, but that certainly wasn't the intention. I was in a hurry so I didn't really explain why I wrote what I did so:

The reason for saying friction is independant of velocity is that the usual (i.e. both simple and pretty accurate) friction force approximation has it being less than the NormalForce*StaticFrictionCoefficient when there's no slipping, and NormalForce*DynamicFrictionCoefficient when there's slipping. Thus during the integration step it's only dependant on whether the relative velocity is zero, not on the actual magnitude. The reason why the integration scheme is irrelevant is that if you let your friction change state (e.g. slip->non-slip) _during_ the integration step you'd get a discontinuous force which would invalidate the approximations (taylor series expansion etc) that went into it (you can make the friction approximation continuous then the equations of motion become stiff which is bad news). So - if you're modelling friction as a force you need to decide just once at the beginning of the step if it is sticking or slipping - and thus the friction force would be constant over the step, and so the integration scheme is irrelevant in this context.

Having a friction force something like this:

frictionVector = coefficient * normalForce.mag() * -relativeTangentialVelocityVector

will "work" in that it will slow objects down, but making it depend on the actual magnitude (rather than just the zero-ness) of the tangential velocity is non-physical, and unnecessary.

HalcyonX: But anyway... trying to get realistic friction into a particle-verlet system is a pain (actually, trying to get realistic friction and 3D ragdoll working is, in my experience, much more of a pain with particle-verlet than with a simple impulse-based model). To do it correctly you'd need to be able to work out the contact-normal force and then apply that force through moving your particles. So, I suggest

(a) giving up on the idea of accurate friction

(b) making sure you use a fixed timestep

(c) adjusting your parameters (like the 0.95 damping factor) automatically so that when you modify the timestep the parameters get adjusted accordingly. Also, that value should only be there to keep things stable (it's artificial damping) - so it should be more like 0.999 or something... (I would set it to 1 until you've got friction working).

(d) using the friction as described in the Jakobsen paper - this won't give you perfect static friction but maybe it will be good enough, even though it's an awful hack. Forget about any idea of force - just modify your particle positions (actually, the old-position) to fake a velocity change. I don't know what you'd do if you're using the "tetrahedron" thing he mentions..

(e) If you want perfect static friction use the contact caching scheme I mentioned... (perfect in the sense of preventing drift... not in any other sense of perfect)

(f) Have some deactivation algorithm that will deactivate objects when they're nearly at reast. I.e. a box on a slope will be drifting slow enough that it gets deactivated.

(g) Do what I did and give up on particle-verlet method as being more trouble than it's worth when you try to make it realistic!

Share this post


Link to post
Share on other sites
lonesock    807
I found I have better results when I reverse the order of my evaluation of the constraints for every frame. (i.e. on odd updates use "for (i = 0; i < n; ++i) {fix_constraint(i)}", and on even updates use "for (i = n-1; i >= 0; --i) {fix_constraint(i)}")

Share this post


Link to post
Share on other sites

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