Euler Stability

Well, about euler integration, there's really not much you can do...
The best thing would be to reduce the timestep, but it won't be long till this starts having an an effect on the framerate; there's a limit to this if you want your application to keep up with real time...

The problem with euler is very prominent when integrating acceleration (forces essentially) that can change very fast for euler to keep track.
In fact, it's not the actual rate of change that matters; E.g. Euler yields precise results if the integrand increases very fast but at a constant rate;
It's when the rate of increase/decrease is not constant (and also very high), that Euler really mucks up! (like with stiff spring forces...)

One quick tip to increase Euler's accuracy is to use both the current and previous value of acceleration and velocity, in order to derive the current position.

e.g. usual euler:
1. x(n) = x(n-1) + v(n-1)*dt
2. v(n) = v(n-1) + a(n-1)*dt

Mod
v(n) = v(n-1) + dt*(a(n-1)+a(n))/2
x(n) = x(n-1) + dt*(v(n-1)+v(n))/2

The geometric meaning behind it is to use trapezoids (instead of rectangles in simple euler) to approximate the area under the function's curve.
The former is precise only for constant functions, while the latter obviously offers better approximation.
You'll just have to adjust your calculations to be one step ahead of the visible part of your simulation.
And don't expect any miracles, this is still euler.
If you totally want to get rid of exploding simulations etc. you may want to consider switching to a more advanced integrator.

Quote:

Original post by someusername If you totally want to get rid of exploding simulations etc. you may want to consider switching to a more advanced integrator.

What would you suggest? I tried verlet, but it was much worse. Am I correct in thinking that collision response in verlet is just projection?

Quote:

Original post by Alrecenk Quote: Original post by someusername If you totally want to get rid of exploding simulations etc. you may want to consider switching to a more advanced integrator. What would you suggest? I tried verlet, but it was much worse.

Are you certain that you didn't miss something in the implementation? It should be far more accurate than Euler...
The tricky part with Verlet is actually starting it up. Since it requires two "previous" positions in each step, this is a little troublesome in the beginning. Some tests I did a month ago, showed that when starting verlet with an initial value calculated with Euler's method (instead of the actual value indicated by the mathematical formula), the error would increase by 200%!
This showed that minimum error in the initial conditions, propagated -and possibly escalated- during the simulation.

Quote:

Am I correct in thinking that collision response in verlet is just projection?

I'm not quite sure about that. Haven't tried to implement collision response with it, to be honest. From what I've read though, I know that you can explicitly move an object in a certain position/orientation and let the simulation handle the rest.
I think this is -pretty much- how constraints are handled with Verlet.
You meant something similar?
I believe you'll need the input of someone with more experience in Verlet for this.

To conclude, I cannot just suggest one method or another...
Euler is -often- enough for simple simulations, where a good ratio of speed/accuracy is necessary.
Verlet is more accurate in calculation of position by 2 orders of magnitude, than Euler. However that doesn't seem to be fully verified by numerical results.
However, it is far more accurate.

RK2 seemed to yield pretty accurate results with relatively little CPU overhead. It only needs evaluation of one extra intermediate point in the timestep.
Probably because of the error in verlet's initial values, it seemed to be more accurate than Verlet, but this is in contrast with theory...
RK4 would be your choice if you wanted the maximum possible accuracy. It will be quite "heavy" for a simple simulation though.

I guess you should weigh the pros/cons, consider the ratio of speed/accuracy you want.
Why not implement them all and be able to switch from one to another, anytime?
Btw, try the modified euler I suggested... If you want to stick to the classic Euler scheme, I doubt it can get any more accurate. And it's fast!

Quote:

Original post by Alrecenk On another note I'd like to handle collisions with lines instead of polygons. I want to be able to collide a piece of string against another piece of string (or maybe itself), but I have no idea how to handle the collision response. I'm using discrete time steps so I'd like to avoid fancy parametric exact time of collision type things if you know what I mean.

im writing a paper on precisely this subject at the very moment, and i hope to be able to post it here asap (although that could still be a while). it provides a simple and efficient solution to your abovementioned problem.

I think I'll try my luck with RK4. It sounds good though I haven't found any really good articles on how to do it for physics(please post if you know any). A lot of pure math articles... One thing I would like to know: does it define velocity explicitly or implicitly?

Eelco, I look forward to reading your paper. I've been working on some ideas of how to do that myself. I haven't tested anything yet though as I'm still working on getting a better physics core. The collission detection should be as simple as checking which side of the lines each point is one before moving and then checking again after moving and if they are different and if the line connecting the point's positions crosses the line in question then there has been a collision. Though the line will be moving as well and I'm not really sure how that will affect things. As for the reaction I would distribute the collision force between the objects based on their mass and then on the line I distribute that force based on where the collision was on the line. But that is all just speculation. Of course, if you're talking about 3D that's a whole different story...I'd like to talk about this more though I probably won't even begin the implementation for a week or two(depending on how difficult it is implement RK4).

Quote:

Original post by Alrecenk I think I'll try my luck with RK4. It sounds good though I haven't found any really good articles on how to do it for physics(please post if you know any). A lot of pure math articles... One thing I would like to know: does it define velocity explicitly or implicitly?

No integrator defines velocity, displacement, or any other physical quantity; They solve differential equations. RK4 solves a system of 1st order differential equations. Typically people here are solving physical systems and so often solve for displacement and velocity. The classic RK4 method is explicit. There are implicit versions, but you almost certainly don't want to go there.

Feel free to use this demo as a basis for you work.

That would explain why I didn't find anything relating directly to physics. I guess I've got a lot of research to do. Glad it is explicit, I'll checkout your demo, hopefully it will clear things up.

Doesnt Newton physics engine use euler? http://www.physicsengine.com

Seeing as how it is stable I would have to say no...

Believe it or not...

Quote:

Well, about euler integration, there's really not much you can do...

Well, now I'm confused...Can you have a stable euler engine? and more importantly, how?

Quote:

Original post by Alrecenk Well, now I'm confused...Can you have a stable euler engine? and more importantly, how?

Euler is not accurate. It is not terribly stable. But often it is enough. If |h*f| < 1, where h is the timestep and f is the largest frequency in the simulation, Euler is stable. You can also "force" stablity on the system by clamping values like velocity, etc. This is not going to produce a physically realistic simulation, but then you're using Euler and making a game... so who cares as long as it works and it looks good [smile]

Quote:

Original post by Alrecenk Quote: Well, about euler integration, there's really not much you can do... Well, now I'm confused...Can you have a stable euler engine? and more importantly, how?

Use Newton-Stormer-Verlet (NSV), AKA "semi-implicit" Euler (don't use Runge-Kutta):

v += a*dt
x += v*dt

Note the order is reversed compared to explicit Euler:

x += v*dt
v += a*dt

With a reasonable timestep (1/60, 1/100, etc.), NSV is extremely fast, accurate, and stable. Clamp delta-velocity/momentum (springs, etc.) for 100% stability. The clamping won't kick in very often, and won't affect visual-physics quality (I can make the car springs in my game 100% rigid, and realistically stable). High angular velocity rigid body motion requires a little more work (not generally a problem for game applications, though).

Also, RK4 is less accurate, and loses energy (acts as low-pass filter on motion): it is however more stable (for spring-like elements). Don't use RK for game applications.

Cloth can be 100% stably implemented using the methods presented in Jacobsen's paper (Velocity-less Verlet).

More info here.

Well, I tried trapezoidal equations, and I tried reversing the order of velocity and position changes and I turned off all the collision stuff and it still doesn't take much to make a simple model(triangle and square attached by string) explode. I tried setting a maximum speed and decreasing my forces this does help, but it costs so much realism to stabalize the system that it would defeat the purpose of having a physics engine...and right in the middle of writing this post I figured out what was causing it to explode so easily. I had the string set to nearly weightless while the objects on it were heavy. Apparently the inbalance of weight caused the simulation to go out of control.

Quote:

Original post by Alrecenk I had the string set to nearly weightless while the objects on it were heavy. Apparently the inbalance of weight caused the simulation to go out of control.

Consider the acceleration a_n exerted on an abject, at frame n.
Now consider the quantities Δ_n+1 = a_n+1-a_n and Δ_n = a_n-a_n-1

It is the maximum of the quantity Δ⁽²⁾_n = |Δ_n-Δ_n-1| that affects the stability of your simulation. The higher it may become, the more accuracy you lose, and the more the chances that your simulation will explode.

In your example, the nearly massless string may start experiencing huge acceleration (due to its mass) from zero, in a matter of a few frames. If you get away with only some error the first time, and the same scenario repeats again after a few seconds (which is quite likely for such scenes), it will be a matter of time till your simulation explodes.

It is common belief that Verlet is the best choice when it comes to implementing constraints between objects. That is, because you can set the position yourself, and let the simulation derive the velocities.
If you want to keep Euler though, it may turn out to be a good idea to dynamically adjust the timestep of the simulation based on the maximum value of Δ⁽²⁾_n of all objects, and perform more simulations (for all objects, of course) where more resolution is needed in the scene.
Depending on the timestep subdivision, this may end up too heavy for simulations with lots of objects, but if there was a "cheap" way to get rid of exploding simulations, I guess we wouldn't even be considering Euler today.

Quote:

Original post by John Schultz Use Newton-Stormer-Verlet (NSV), AKA "semi-implicit" Euler (don't use Runge-Kutta): v += a*dt x += v*dt Note the order is reversed compared to explicit Euler: x += v*dt v += a*dt With a reasonable timestep (1/60, 1/100, etc.), NSV is extremely fast, accurate, and stable

It is intuitive to consider that the position at time "t₀" should be calculated from the position and velocity at time "t₀-dt" for very small dt.
The same thing goes for velocity from acceleration too.
So, indeed, the semi-implicit method *should* be more accurate.
I don't see, though, why one implementation should be more stable than the other.

Quote:

Original post by John Schultz Also, RK4 is less accurate, and loses energy (acts as low-pass filter on motion): it is however more stable (for spring-like elements). Don't use RK for game applications.

eh? its hardly more stable, certainly not in terms of stability / clockcycle. and for continuous functions, its definitly a lot more accurate.

Quote:

Original post by Eelco Quote: Original post by John Schultz Also, RK4 is less accurate, and loses energy (acts as low-pass filter on motion): it is however more stable (for spring-like elements). Don't use RK for game applications. eh? its hardly more stable, certainly not in terms of stability / clockcycle. and for continuous functions, its definitly a lot more accurate.

Actually, for a properly-implemented RK4, John is correct. If you look at the stability domain in the complex plane, RK4 clearly admits spring elements without requiring damping for stability while explicit Euler requires damping elements when there are springs. (By the way, though I've derived some of this myself, one reference is Figure 11.5.1 in "Numerical Computation of Internal and External Flows: Volume 1" by C. Hirsch, a book that covers stability issues for RK4, explicit Euler, and other time marching integrators. You can also see this in Dave Eberly's "Game Physics" book.) Further, the RK4 stability region covers more area and so RK4 is stable for larger (but not unlimitedly large) time steps compared with explicit Euler. In practice, this can be measured reliably, compared with real-world experiments, only for quite simple configurations.

The accuracy thing is harder to judge. Any given method may be very accurate for dissipative physical situations (object moving with friction) but not for dispersive physical situations (wave-like motion, such as springs), or vice versa, on a case-by-case basis. The behavior of a particular method is indicated by whether the largest truncation error term in the Taylor series expansion contains an odd derivative (dispersion error) or an even derivative (dissipative/energy loss error). But....(and this is a super critical point that I'm about to make)...the actual accuracy of a method is a combination of the time integration technique (RK, explicit Euler, Verlet, Graham's super-duper ultimate integrator) plus the spatial representation/discretization, e.g., the actual representation of your physical model. That is, the measurable accuracy is a function of your model and time integrator together, as a whole.

Quote:

Original post by grhodes_at_work Quote: Original post by Eelco Quote: Original post by John Schultz Also, RK4 is less accurate, and loses energy (acts as low-pass filter on motion): it is however more stable (for spring-like elements). Don't use RK for game applications. eh? its hardly more stable, certainly not in terms of stability / clockcycle. and for continuous functions, its definitly a lot more accurate. Actually, for a properly-implemented RK4, John is correct. If you look at the stability domain in the complex plane, RK4 clearly admits spring elements without requiring damping for stability while explicit Euler requires damping elements when there are springs. (By the way, though I've derived some of this myself, one reference is Figure 11.5.1 in "Numerical Computation of Internal and External Flows: Volume 1" by C. Hirsch, a book that covers stability issues for RK4, explicit Euler, and other time marching integrators. You can also see this in Dave Eberly's "Game Physics" book.) Further, the RK4 stability region covers more area and so RK4 is stable for larger (but not unlimitedly large) time steps compared with explicit Euler. In practice, this can be measured reliably, compared with real-world experiments, only for quite simple configurations.

yeah, RK4 might cause a little damping, but thats really the last of your worries in a game engine. its a non-issue, considering euler adds energy, which is much worse, and a lot more of it than RK4 dissipates. this is most certainly no reason to prefer euler over RK4.

Quote:

The accuracy thing is harder to judge. Any given method may be very accurate for dissipative physical situations (object moving with friction) but not for dispersive physical situations (wave-like motion, such as springs), or vice versa, on a case-by-case basis. The behavior of a particular method is indicated by whether the largest truncation error term in the Taylor series expansion contains an odd derivative (dispersion error) or an even derivative (dissipative/energy loss error). But....(and this is a super critical point that I'm about to make)...the actual accuracy of a method is a combination of the time integration technique (RK, explicit Euler, Verlet, Graham's super-duper ultimate integrator) plus the spatial representation/discretization, e.g., the actual representation of your physical model. That is, the measurable accuracy is a function of your model and time integrator together, as a whole.

ofcource. but when comparing integrators for accuracy, its a good idea to do so for the same spatial discretization. on a comparable, stable timestep, RK4 is MUCH more accurate than euler. but you dont care about that anyway for a game, whats more important is that RK4 is a multitude more expensive, which is what makes it the loser for game applications.

I agree with Eelco, FWIW.