quote:

---

Original post by lusinho

> And certainly there are more accurate implicit methods.

You can''t just leave it like that Graham.
We are all waiting (well, maybe just me) for a detailed description of these wonderfull methods you talk about.

---

Better time accuracy may not be important for games, so don''t assume that just becaues more accurate exists that it would be a good idea. For example, the implicit Euler method does happen to have stability characteristics among the best of the implicit methods, and better than probably all of the explicit methods. And stability may likely be more important than accuracy.

HOWEVER, to answer the question.. Implicit Euler is 1st-order accurate in time. What''s better? Almost EVERY other implicit method is more accurate in time. A good choice might be the two-step trapezoidal method, but its just one of dozens/hundreds.

My GDC 2001 paper details some of this. In particular, look at page 30 of the presentation PDF file, available here:

http://www.gdconf.com/archives/2001/rhodes_slides.pdf

On this page, you can see a table of implicit methods and their time accuracy. All are A-Stable, and if you can figure out how to interpret the equation you will be able to figure out how to use the method. I''ll tell you how to use the table and formula using implicit Euler, which is at least somewhat understood here. Take the numeric parameters from the 3 right-most columns and plug those values into the equation to get the formula for the method. Thus, plugging in the table values, implicit Euler becomes:

(1+0)*xn+1-(1+2*0)*xn+0*xn-1=dt*(1*fn+1+(1-1-0)*fn-0*fn-1) 

or, simplifying and dropping zero terms,

xn+1-xn=dt*(fn+1) 

which can be written,

xn+1 = xn + dt*fn+1 

Now, the notation is weird. Those superscripts really represent the time. They are NOT exponents. Thus, "xⁿ⁺¹" means "x at time step n+1" not "x raised to the n+1 power". There''s a reason for that, but it isn''t important to you. Just convert the superscripts into parentheses:

x(n+1) = x(n) + dt*f(n+1) 

Now, doesn''t that look familiar? Looks kind of like the following code for using implicit Euler to integrate velocity to obtain position, doesn''t it?

x(n+1) = x(n)+v(n+1)*h 

Its exactly the same. We derived implicit Euler using the formula and table. My formula (which is actually courtesy of Hirsch, one of the references in the accompanying paper, gives you any number of implicit formulas for calculating x based on f. When x is position, f is velocity. You can use the same formula substituting velocity for x and acceleration for f.

There are more exotic methods, but this should be all you''d want to know for now.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

quote:

---

Original post by minorlogic
Can you talk how you plan to test stability ? It is very intresting ! Let me know please if you will test .

---

There are methods to determine the stability bounds of different numerical methods before actually running a simulation. For example, Von Neumann stability theory can be used. My GDC paper talks about stability in some detail:

http://www.gdconf.com/archives/2001/rhodes_paper.pdf

quote:

---

Original post by minorlogic
And i don''t understand how can be calculated ?
x(n+1) = x(n)+v(n+1)*h
v(n+1) = v(n)+a(n+1)*h
if a(n+1) based on x(n+1) and v(n+1) , how can we know a(n+1) ?

---

This is the challenge of implementing an implicit method. These two equations contain 3 unknowns, x(n+1), v(n+1), and a(n+1). With just two equations you cannot know all three. Therefore, you need to add a third equation. That third equation should not introduce another unknown (e.g., q(n+1)), or you still cannot solve the problem. As Zipster suggested, you could first calculate a(n+1) using x(n) and v(n). That would be a perfectly acceptable way. Then, after finding a(n+1), you have two equations and two unknowns. No problem to solve that using standard ways of solving linear systems.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Thanks , it is intresting discussion !

"quote:
x(n+1) = x(n)+v(n+1)*h
v(n+1) = v(n)+a(n+1)*h
"
Ok, than equation writen is a just equation, not a solution. And should be rewriten like :
a(int) = f_some_interpolated_a(v,a,x)
v(n+1) = v(n)+a(int)*h
x(n+1) = x(n)+v(n+1)*h
//--------------
Ok, i am back again, many times i had seen that Particle systems was implemented by StepSimple, but used a only one constant force. if used StepSimple, solution depend of time_step, if CorrectStep it is exac. The diffrence is a 3 additions, do thay cost so much ?
//-------------- to experts
In systems with forces like friction , can we increase stability with linear interpolation of Acceleration ? (my control system of rigid body not stable without dumping, i try to find )

Body::StepCorrect( float time_step ){
AccelerationOld = Acceleration;
CulcAcceleration();

VelocityOld = Velocity;
Velocity += (AccelerationOld + Acceleration) * 0.5 * DT;
Position += (VelocityOld + Velocity) * 0.5 * DT
}
Can this help ?