🔒 Locked

Verlet Physics: Help!

Started by FrancisXavier Jan 17, 2005 at 8:05 AM 18 replies 6.9k views

Original Post

Jan 17, 2005 at 8:05 AM

Greeting all, I've been trying to implement some Verlet physics stuff, as described in the "Advanced Character Physics" article. The problem I've come across is this: For test purposes, I just create a tetrahedron with a particle at each corner and joined together by infinitely stiff springs. Gravity is then applied at each particle and collision is done with a ground plane. My simple algo goes as follows: -> Update the positions of the 4 particles using Verlet integration. -> See if any of the particles are below the ground plane, if so, project them out (using the ground plane normal). -> Satisfy the 6 stick constraints which hold them together. -> Render the particles as points and the stick constraints as lines. -> Repeat the above steps in a loop. Now this all seems to work fine at first; the tetrahedron hits the ground and rotates a bit, slowing down. However it never completely slows down and keeps spinning slowly. I think that this is caused by the satisfying of the stick constraints, whereby a stick constraint "pulls" on a particle which is not constrained, which in turn causes its neighbour to be pulled and so on. I've been at this for quite some time now, and have no clue as to how to solve this. I wonder how it works in Hitman and other games using the Verlet system. If anyone knows how to solve this or has any ideas, please help. Thanks in advance, Francis Xavier

FrancisXavier

Jan 17, 2005 at 11:10 AM

Thanks for the reply. Well, no, I actually don't. But my integrator looks like this:

void RigidBody::IntegratePositions(float dt){	const float Kd = 0.99f; // Damping constant	// Integrate the particles' positions	FLOAT3 tmpPos;	for(int i=0; i < m_numBasicParticles; i++)	{		tmpPos = m_p.pos;		m_p.pos = m_p.pos + (m_p.pos - m_p.prevPos) * Kd +			m_p.Force * m_p.invMass * dt * dt;		m_p.prevPos = tmpPos;		// Clear out the force		m_p.Force = FLOAT3(0.0f);	}}

So with this I expect it to come to a halt after some time. Or is there something glaringly wrong in this code?

[Edited by - FrancisXavier on January 17, 2005 11:10:08 AM]

sbroumley

Jan 17, 2005 at 6:24 PM

Your code looks fine. I've also experienced the same "drift" implementing this method. The simple solution is to just put the rigid body to sleep once the sum of energy/velocity of all the particles falls below a threshold. Also, make sure you include some sort of friction in your collision response - this will help (one way is to compute the velocity at the time of the collision, then split it into collision plane parallel/perpendicular components. Scale the parallel component by some friction coefficient < 1, and reflect the perpendicular component by some elasticity < 1. Re-combine the components, then update the previous position to assign this new velocity).

Here's a verlet paper that describes the same method, but also applies it to the "orientation" of the particle too (so you only need one particle to simulate a rigid body).

http://www.gdconf.com/archives/2004/baltman_rick.pdf

The math turns outs to be faster (but slightly more complicated) than just using 4 particles + 6 stick constraints. If you read the paper, it also describes the "drift" problem in more detail and shows you the equations to solve it.

[Edited by - sbroumley on January 17, 2005 7:24:16 PM]

FrancisXavier

Jan 17, 2005 at 9:12 PM

Thanks for the reply. I tried putting the rigid body to "sleep" when its movement was negligent, but I couldn't get it right. Then thing is, what basis do I use for putting the rigid body to "sleep" and "waking" it up?

-> I tried putting it to sleep when the changes in position were minor. But this leads to the object going to sleep sometimes prematurely. Eg. If I throw the rigid body up, just before it begins to fall down, it goes to sleep in the air.
-> Using the above method itself, I tried decreasing the "sleep" threshold. But the above problem was still there in some cases. Also, while on the ground, the drift was large enough to overcome "sleeping" when the threshold was too small.
-> Then I tried looking at the engergy (force) of the object along with the position. But the problem there was that gravity is always acting on the object, so the energy of the object will always be some value greater than the threshold value for "sleeping". Also this is not such a good method because, suppose some other forces are acting on the object also, then the energy of the object is great, but it's not supposed to move. An example of this is stacking.

I'm sure many of you guys have implemented simple verlet systems. Didn't anyone run into this problem caused by the stick constraints before?

sbroumley

Jan 17, 2005 at 9:35 PM

Sorry - by energy I meant kinetic energy (0.5 * Mass * VelocitySquared), not force.

To avoid the body freezing in the air at the top of an arc, simply increment a timer when the velocity/energy is below your threshold, and set it to zero when it's not. Then - only freeze the body when the timer has reached say 2 seconds or something. You could also add other conditions into the freezing, like only freeze if there is a contact etc.

To wake up the body, clear the "frozen" flag and set the timer to zero in any function that applies an impulse to the body (eg. from an explosion or something).

For games, it's all about cheating :)

BTW - I have used this method successfully in Midway's first-person-shooter Area51 (coming soon).

[Edited by - sbroumley on January 17, 2005 9:35:15 PM]

FrancisXavier

Jan 17, 2005 at 10:21 PM

Hey that's major cool info, thanks. I never thought of doing it like that. Also, you've successfully implemented it in Area51, eh? Then I've definitely got to check the game out. I love 'em physics based games.

I'll try and implement that now, and if I still can't get it right, I'll come back to trouble you some more. :)

Thanks again,
Francis Xavier

sbroumley

Jan 17, 2005 at 10:52 PM

No problem, anytime.

Yes for Area51 I originally implemented the ragdoll using Jackobsen's method (don't be fooled by the paper - it may look simple, but wait until you get to the rotational constraints!).

I actually re-wrote the final ragdoll in Area51 using an impulse method based on this paper (and lot's of help from Danny Chapman - MrRowl ):

http://www.cs.ubc.ca/~rbridson/docs/rigid_bodies.pdf

Believe it or not, it turns out that the constraints are much easier to code using the impulse method and the results are much more realistic (static friction + rotation around limb axis makes ragdolls look so much better).

Still, the verlet method has proved to be nice and cheap (and it solves resting contact so elegantly) for "coke cans" and "barrels" in the game -modeled with just 2 spheres and 1 stick constraint! (rolling is faked). Also, the cloth in the game (flags etc) is done using the verlet method.

FrancisXavier

Jan 19, 2005 at 11:29 PM

Doing some more experiments at the moment. Putting the object to "sleep" does seem to give better results, but can't help feeling that it's not THE way to do it.

And whoever said it is right, using the traditional rigid body equations is easier (although I haven't managed to get resting contacts completely right). But somehow the particles and constraints approach seems to be more right.

I was just thinking, in real world physics, everything is made out of particles. And whole rigid bodies are made up of many particles all staying together due to an attractive force. So, all movement (translational and rotational) comes from the simple fact that the particles try to stay together, as they move. I think that the Verlet method is somewhat closer to this than the traditional way of doing rigid body physics.

Just some thoughts, I may / may not be right about this. This is getting pretty frustrating for me; it's been a long time now and I haven't been able to come up with a single stable implementation of rigid body physics till now. If anyone has any ideas or thoughts to share, please do! I'm all ears.

Thanks for listening,
Francis Xavier

Rompa

Jan 21, 2005 at 6:19 AM

From my experiences simply damping the velocity doesn't work reliably unless you run your physics at a constant rate - otherwise if you have a small timestep (physics update gets called more often) you'll be reducing the velocity at a faster rate than if you call it less frequently (a slow framerate). Another great reason to use fixed timesteps - cheap and dodgy damping :-)

y0y

Jan 21, 2005 at 2:21 PM

When you say dampening the velocity, you should be really be applying a constant force in the opposite direction of travel. Realize that we're dealing with a force, not an acceleration because we're dampening the velocity with respect to the mass. Therefore...

dtp = (dt for the last frame)
dt = 1 / FramesPerSecond
x' = x + (x - xo) * (dt / dtp) + a * dt * dt

And if all works out, your verlet integration should work at any framerate.

[Edited by - y0y on January 21, 2005 10:21:05 PM]

FrancisXavier

Jan 22, 2005 at 7:23 AM

I've noticed in my tests that this drift problem is quite severe. The more the force applied, the more the displacement of the particles, and the more the drift.

For e.g. in the my simple test application which I described above, when the gravity force is little, the drift is very small and almost not noticeable. But as I increase the magnitude of the gravity force, the drift increases drastically.

I feel that this error is caused by the fact that we satisfy each constraint one after the other, instead of satisfying all the constraints at once. This seems to be the key.

What do y'all think?

Francis Xavier

oliii

Jan 22, 2005 at 9:48 AM

that introduces drift. A quick bodge would be to satisfy constraints one way going up the list, and then next time the other way, going down the list.

I tried that, it reduces the drift a fair amount, but it's just a hack really. Resting the object properly would be the way to go.

FrancisXavier

Jan 22, 2005 at 11:27 AM

Thanks for the replies.

To Rompa & y0y:
Thanks for the info. I'm using a fixed timestep and plan on continuing to do so. I find that it's less troublesome and the results are deterministic.

To oliii:
I checked out your code samples and noticed that you do that. That's a pretty clever trick. I was thinking of doing it another way. Building a few random index lists and then satisfying the constraints by using a different list each time. However there would be quite some overhead if constraints were to be frequently added/removed.
Btw, your verlet examples are pretty impressive, good work and thanks for making the source available.

Francis Xavier

oliii

Jan 22, 2005 at 2:01 PM

no problemo [grin]

YOu have to be carefuil with verlet and variable frame rates. Verlet works only with fixed time steps. I haven't found a good way of making the plain verlet work with variable framerate, and I don;t know if it is possible.

something like

void Integrate(float dt)
{
tempx = x;
x += (x - prevx) + a * dt*dt;
prevx = x;
}

so basically, (x - prevx) represents the displacement the previous frame. to keep the velocity the same with a new timestep, it 'should' be

void Integrate(float dt)
{
temp_x = x;
x += (x - prev_x) * (dt / prev_dt) + a * dt*dt;
prev_x = temp_x;
prev_dt = dt;
}

but I might be totally wrong.

lonesock

Jan 22, 2005 at 2:04 PM

Quote:
Original post by oliii
but I might be totally wrong.

Nope! Right you are.

FrancisXavier

Jan 22, 2005 at 2:29 PM

Thanks for the info. However, I think that using a variable time step isn't going to cut it if we need the results to be deterministic (am I using the right word here??).
The results should be the same no matter when/where the simulation is run. For a network based game, or if we need to provide some kind of playback mechanism, given some initial state, we'll need the outcome to be the same at all times. I don't know if this is possible with a variable time-step approach. With a fixed time-step this works fine and it's also easier to understand and implement IMHO.

Francis Xavier

oliii

Jan 22, 2005 at 4:10 PM

it's certainly easier with fixed time steps for playback systems. You can always record the frame timestep as an input in your playback system. But then, it can get jittery (since the playback time step maybe different from the recorded timestep forthat frame), and then you'll have to de-sync the physics update with the render update. And in network games, I haven't tought about it, but a fixed time step seems a lot less painful.

FrancisXavier

Jan 23, 2005 at 12:14 PM

Quote:
Original post by oliii
and then you'll have to de-sync the physics update with the render update

But I thought that this was what everyone does. I've read that Doom 3's physics runs at about 60 Hz. And other games must be doing the same, right?

Btw, what does everyone recommend as the best way to do physics? I mean, verlet or traditional rigid body physics? With both ways I currently have a problem with simulating resting contacts. Mr. sbroumley has adviced me to put the body to sleep. And I've noticed that many do the same. Mr. Rowl also puts his rigid bodies (traditional rigid body physics) to sleep I think. But I somehow feel that this is not exactly the absolutely right way to do it. So I'm still experimenting.

Thanks for the replies. Ideas and suggestions are always welcome.

Francis Xavier

FrancisXavier

Jan 23, 2005 at 12:50 PM

Quote:
Original post by oliii
A quick bodge would be to satisfy constraints one way going up the list, and then next time the other way, going down the list. I tried that, it reduces the drift a fair amount, but it's just a hack really. Resting the object properly would be the way to go.

Actually I tried it and it works like a charm. Better than the method I suggested which satisfies the constraints using a randomized index list. I think this is because of the fact that the randomized list will introduce random drifts which may / may not cancel each other out. So the net result is a slight drift. But using your way, I think, that an equal and opposite drift is caused when the list is satisfied backwards. So the net result is ~zero drift. Cool going man!

Francis Xavier

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.