Sign in to follow this  

My spring based system blows up :(

This topic is 3739 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi guys, I've been trying to develop a very simple spring based system using just trivial F = kx, but my problem is that my system blows up all the time if some of the variables change too rapidly. One solution I could do is decrease the time increment dt, or perform many iterations of force calculations each tick, but I wanted to know if there are any other ways of doing this... like applying some sort of damping or friction? I couldn't find any proper article on this... Anyone knows of anything, or has some suggestions for me? Thank you

Share this post


Link to post
Share on other sites
You already have the answer. Damping will do the trick.

What damping does is, it allows you to keep a check on the maximum velocity.
Example, velocity of an object falling through the earths atmosphere is governed by F=ma, so if the object were to fall for an infinite amount of time then you would expect it to reach an infinite velocity. This doesn't happen because of the damping produced by the viscosity of the atmosphere - the final velocity will be equal to the terminal velocity (which depends on both gravity & damping produced by atmosphere)

Share this post


Link to post
Share on other sites
Quote:
Original post by Geoff the Medio
What integration scheme are you using? You may need to change to one that's more numerically stable...


Absolutely. I'd bet lemour9907 is using simple explicit Euler integration, which can only be stable when damping is implemented, for problems with springs. May want to search on Verlet integration, or maybe first try Symplectic Euler (since it is super trivial to switch from simple explicit Euler to Symplectic Euler).

Share this post


Link to post
Share on other sites
i don't understand what you guys mean by integration scheme...
F = kx
F = ma
=> ma = kx => a = kx/m

I have that all, so i get acceleration for each of the nodes that the spring connects, and i just apply that... v = at, and then add velocity to position each tick...

Share this post


Link to post
Share on other sites
You're using the euler integration method. The other methods mentioned here are Verlet, and "Symplectic Euler". Verlet doesn't store a velocity vector, and calculates the velocity from the past position, and current position. I'm not 100% what "Symplectic Euler" is, but I think it may be what some people call the "Semi-implicit Euler" integration, which just switches the calculations of the acceleration, velocity and position.

IE:
Euler -
acceleration = force/mass;
velocity = acceleration*dt;
position = velocity*dt;

"Symplectic Euler" -
position = velocity*dt;
velocity = acceleration*dt;
acceleration = force/mass;

You could also look into the RK4 integrator, which is much more numerically stable (4th-order), but also more costly to calculate.

Share this post


Link to post
Share on other sites
Quote:
Original post by lemour9907
i don't understand what you guys mean by integration scheme...
F = kx
F = ma
=> ma = kx => a = kx/m

I have that all, so i get acceleration for each of the nodes that the spring connects, and i just apply that... v = at, and then add velocity to position each tick...


Unfortunately its not as simple as that. Those equations assume the time step t to be infinitesimally small such that v and a are both constant over t.
With finite t errors accumulate and can cause instability.

As others have suggested, Euler integration is the simplest to implement but worst when it comes to stability. A quick way to solve this problem is to add damping.

More accurate integration schemes are available but are more complicated to implement. Numerical integration methods are based on the Taylor series - something you will need to take a look at before going to RK4 integrator.

Share this post


Link to post
Share on other sites
There's also RK2 which isn't as heavy as RK4. Having said that if you can do RK2 then you can probably do RK4.

All of these methods have different conditions for stability. I haven't touched it in a few years... I remember it was conditions like oscillating systems etc? Anyone refresh my memory?

Share this post


Link to post
Share on other sites
Quote:
Original post by bronxbomber92
You're using the euler integration method. The other methods mentioned here are Verlet, and "Symplectic Euler". Verlet doesn't store a velocity vector, and calculates the velocity from the past position, and current position. I'm not 100% what "Symplectic Euler" is, but I think it may be what some people call the "Semi-implicit Euler" integration, which just switches the calculations of the acceleration, velocity and position.

IE:
Euler -
acceleration = force/mass;
velocity = acceleration*dt;
position = velocity*dt;

"Symplectic Euler" -
position = velocity*dt;
velocity = acceleration*dt;
acceleration = force/mass;


Er, you got the two reversed:

Simple Explicit Euler is:
position = velocity * dt; // using the old velocity
velocity = acceleration * dt; // using the old acceleration
acceleration = force/mass;

Symplectic Euler (yes, a semi-implicit technique) is:
acceleration = force/mass;
velocity = acceleration * dt; // using the new acceleration
position = velocity * dt; // using the new velocity

(And, yes, flipping the order can have a dramatic effect on the results in some cases!)

Here's the Wikipedia page:

Symplectic Euler (aka Euler-Cromer)

Share this post


Link to post
Share on other sites
A great integrator for spring based systems imho is Verlet. Simple euler, symplectic euler and even the mighty RK4 will blow up unless you apply alot of dampening, and thats no fun. Verlet doesnt, and its pretty simple to implement too.

The wikipage for it is pretty good:

Here

Dont know if their implementation of a constraint system is very physically correct, but it does get the job done (unless the job was to physically correct, but in game developement it rarly is).

If you want a (very) simple verlet rope simulation example pm me your email.

Oh, your simulation will have to use a constant dt when using verlet, but thats usually a good ide anyway.

//Emil

Share this post


Link to post
Share on other sites
Quote:
Original post by bronxbomber92
Gotcha, I presumed Symplectic Euler meant Semi-Implicit Euler. I guess I was wrong.

So, was I correct in that the Semi-Implicit Euler is much more numerically stable?


You weren't really wrong, :). Well, symplectic Euler is a semi-implicit technique. I don't think "semi-implicit Euler" really is the proper name for any specific technique, but symplectic Euler is, basically, a semi-implicit Euler.

Perhaps, for some of those in this thread, the following discussion will be helpful. The way I wrote the equations is correct. If you update items in such an order that at least some items are able to use updated dependency values (e.g., position using an updated velocity instead of prior time step velocity), then you have a semi-implicit technique. If you update items in such an order that none of the items use updated dependency values, then you have a purely explicit method. A purely implicit method updates everything in lock step, and is harder to implement. The reason symplectic Euler is semi-implicit, and not purely implicit, is that the force will usually be based on prior time step info. That is, most force calculations require position and/or velocity, and so if you compute acceleration first, so that the velocity and position updates can use an updated acceleration, then the force used to compute acceleration must be based on prior position and velocity, making the acceleration update lag position and velocity. The acceleration is the thing that makes symplectic Euler "semi-" implicit.

Yes, as you know, semi-implicit and implicit techniques are going to be more numerically stable for most problems.

Share this post


Link to post
Share on other sites
Quote:
Original post by cannonicus
A great integrator for spring based systems imho is Verlet. Simple euler, symplectic euler and even the mighty RK4 will blow up unless you apply alot of dampening, and thats no fun.


Your comment about RK4 is quite true! Even though people have the feeling that it is far more stable. Well, it does have a larger stability region, and with time step limiting can be stable without damping, its stability region isn't that much larger than simple explicit Euler. It does have perhaps better accuracy, but for stability it isn't orders of magnitude better. I have not done a stability analysis of symplectic Euler, so I don't know what is stability region is. I do know that fully implicit Euler has a stability region that is vastly different, polar opposite to simple explicit Euler. A full implicit Euler implementation would be stable for springs of any stiffness, with any time step, though it could have other undesirable features.

(See my GDC 2001 talk at the following link for technical detail on stability regions and analysis of numerical methods:

Stable Rigid-body Dynamics @ GDC 2001

Share this post


Link to post
Share on other sites

This topic is 3739 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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