Skip to main content
gamedev.net
🔒 Locked

Question (Leap Frog Method, implicit Euler's Method, etc)

Started by bargasteh Nov 21, 2005 at 7:39 AM 12 replies 3.7k views
Original Post
bargasteh
bargasteh
Hello I wanted to know that how I can implement Leap Frog Method, implicit Euler's Method and Runge-Kutta fourth-Order Method). I found this code:

double* ImplicitEuler (double theta0, double dtheta0, double h, int n)
{
int c = 1;
const int maxIterations = 32;
double* theta = new double[n];

for (int i = 0;i < n; i++){

double theta1 = theta0;

for (int j = 0; j < maxIterations; j++){
double g = theta1 +h * h * c * sin(theta1) - theta0 - h * dtheta0;
double gder = 1.0 + h * h * c * cos(theta1);
theta1 -= g/gder;
}//end for inner

double dtheta1 = dtheta0 - h * c * sin(theta1);
theta = theta1;
theta0 = theta1;
dtheta0 = dtheta1;

}//end for outer

return theta;
}

The above code is implicit Euler but I couldn’t figure out where I have to apply the 3D vector forces? Do any of you know? Apparently Leap Frog is a Verlet method that considers Velocity and for my simulation I need the velocity to calculate the frictional forces (it is important). Is it possible to adopt the Velocity less verlet to approximate the velocity in each time step ? Or if it is not possible could you please help me with Leap Frog? The Verlet method that I use is:

	Vector x1 = force * oneOverMass * dt2; 
	vel= (pos - m_prevPos) + x1;
	vel.y-=9.81f*dt2;
	m_prevPos = pos;
	pos+=vel;

vel in here is not the real velocity it is the change of position. I just use this variable because I declare it somewhere else. Thank you in advance
OpenGl + C++
grhodes_at_work
grhodes_at_work
The first example doesn't really resemble implicit Euler, and isn't a general purpose solver. I would say it is a poorly named method, at least, without the context of its application. Where did you get it? I don't see that it is suitable for what you want to use it for.

Also, I do not recommend Leap Frog. Its stability region makes it a poor choice for general simulation.
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net
Sneftel
Sneftel
The implicit euler method is that x(t+Δt) = x(t) + x'(t+Δt)Δt. In other words, the derivative used as a uniform d/dt for the timestep is taken from the end of the timestep.
bargasteh
bargasteh
Quote:
Original post by grhodes_at_work
The first example doesn't really resemble implicit Euler, and isn't a general purpose solver. I would say it is a poorly named method, at least, without the context of its application. Where did you get it? I don't see that it is suitable for what you want to use it for.

Also, I do not recommend Leap Frog. Its stability region makes it a poor choice for general simulation.


Yes, you are correct the function I posted only draw a Sin diagram to show how stable this solver is.
I got it from GAME PHYSICS book.

How about my question about Velocity Verlet ? I need the velocity to do the friction, dont I?

Could some one explain a little bit more.
OpenGl + C++
Sneftel
Sneftel
Quote:
Original post by Anonymous Poster
Okay, so the code posted by bargasteh is an implementation of the implicit Euler method for the simple pendulum with friction at the joint.

True implicit euler uses an exact solution for computing the derivative at the end of the timestep, rather than approaching it via Newton's Method. (Because of this, it has no general closed-form solution.) If you're going to do several iterations per timestep, you may as well do Runge-Kutta, which'll give you a lower error bound.
grhodes_at_work
grhodes_at_work
Quote:
Original post by Anonymous Poster
Quote:
Original post by grhodes_at_work
The first example doesn't really resemble implicit Euler, and isn't a general purpose solver. I would say it is a poorly named method, at least, without the context of its application. Where did you get it? I don't see that it is suitable for what you want to use it for.


What do you define as "implicit Euler's method"? The OP's code appears to be for a simple pendulum with friction at the joint.



Yes, but "simple pendulum with friction" != "implicit Euler"! The function solves a very specific problem, and isn't a generic solver as the function name implies. This was my point, :).
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net
Sneftel
Sneftel
Quote:
Original post by Anonymous Poster
I think we agree on the definition for "implicit Euler", but the choices for implementing this on a computer are many. I do not understand what you mean by "uses an exact solution for computing the derivative". You do not know the exact solution to the differential equation, so how can you use it?

Though there's no closed-form solution, you can exactly compute the derivative for certain situations, such as damped springs. Unfortunately, I don't have my notes here with me, or I'd post the derived equations.
grhodes_at_work
grhodes_at_work
Quote:
Original post by Anonymous Poster
Quote:
Original post by grhodes_at_work
Yes, but "simple pendulum with friction" != "implicit Euler"! The function solves a very specific problem, and isn't a generic solver as the function name implies. This was my point, :).


I agree. The OP did mention the code came from "Game Physics". The section of the book from which it came is specifically for the simple pendulum with friction.
From what I can tell, that book discusses how to set up the implicit Euler method for general forces.

I am curious how you avoid using Newton's method to solve the implicit equation. Any hints on other alternatives?


Your general understanding is correct. To solve an implicit system of equations numerically, you do need one or more derivatives, in order to compute the incremental correction that nudges you toward the answer at each iteration. Newton's method is one approach, but there are many variations that use one or multiple derivatives, different weighting and preconditioning strategies to accelerate and improve the chances of reaching convergence. In general the derivatives may have to be themselves approximated numerically, and this can introduce new equations into the system. (For the sample code, the derivative is computed analytically.)

The book does talk about implicit Euler in a more general fashion. It just happens that the example code (the quoted example code) is not a general-purpose implementation of the method. It is a problem-specific example. The sample code from "Game Physics" does solve the pendulum problem using the implicit Euler technique. It does illustrate exactly what the author intended to illustrate in his book, very nicely. To do so, it uses built-in knowledge of the specific geometry of the pendulum problem to produce the input at each step.

From the wording of the original post, I gathered that the OP thought a general force could be simply added in and the code would work fine for a more general problem, e.g., a non-pendulum problem. This isn't the case, of course. The method cannot be used, as-is, for general problems. This is in part because it is built specifically around the geometry of a pendulum, exactly as the author intended. The other reason the method isn't too flexible as is (and this is the reason I didn't immediately see what was going on before the OP mentioned where the code came from and I had a chance to see the context of the code in the book) is because it is written in a way that the entire motion time history is computed in one call, for n time steps. There are no provisions to allow the applied forces to change at each time step, and it isn't really intended to be called in sequence multiple times.

[Edited by - grhodes_at_work on November 25, 2005 11:06:42 PM]
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net
bargasteh
bargasteh
Quote:

From the wording of the original post, I gathered that the OP thought a general force could be simply added in and the code would work fine for a more general problem, e.g., a non-pendulum problem. This isn't the case, of course. The method cannot be used, as-is, for general problems. This is in part because it is built specifically around the geometry of a pendulum, exactly as the author intended. The other reason the method isn't too flexible as is (and this is the reason I didn't immediately see what was going on before the OP mentioned where the code came from and I had a chance to see the context of the code in the book) is because it is written in a way that the entire motion time history is computed in one call, for n time steps. There are no provisions to allow the applied forces to change at each time step, and it isn't really intended to be called in sequence multiple times.


Thank you Mod, you are correct I thought I can just apply the force and use the code, but as you said its not possible. Ok does any of you know that how I can implement this (is there any tutorial that show how I can do implicit from scratch)?
I have one more question. As we all know its extremly hard to have a very realistic cloth or deformable object in real time (specially stable cloth with good resolution), how does new PP (physics processors) or I would better say physicX AGEIA approach this problem ? I mean will they have a PPU (Physics processing Unit) that can solve implicit equation really fast ? Does any of you have any idea that how they want to simulate stable cloth ? Is it implicit or explicit ?

Thank you
OpenGl + C++
grhodes_at_work
grhodes_at_work
Quote:
Original post by bargasteh

Thank you Mod, you are correct I thought I can just apply the force and use the code, but as you said its not possible. Ok does any of you know that how I can implement this (is there any tutorial that show how I can do implicit from scratch)?
I have one more question. As we all know its extremly hard to have a very realistic cloth or deformable object in real time (specially stable cloth with good resolution), how does new PP (physics processors) or I would better say physicX AGEIA approach this problem ? I mean will they have a PPU (Physics processing Unit) that can solve implicit equation really fast ? Does any of you have any idea that how they want to simulate stable cloth ? Is it implicit or explicit ?

Thank you


I can point you to the following page that has some presentations by David Wu. He has implemented implicit solvers for games, quite successfully. I cannot promise the presentations will be complete or easy to follow. But it is something. I'm not aware of a truly straightfoward introduction of implicit solvers for rigid body dynamics. (Eberly's book might have something, but I haven't read it thoroughly enough to know.)

Pseudo Interactive Past Projects

Look at "The Physics That Brought Cell Damage to Life.." for example.

Now...for cloth simulation, which involves a discrete approximation to an medium that behaves somewhat like a continuum, it would be very straightforward to implement a spatially implicit system. The time implicit stuff is fuzzier, just as it is with rigid bodies.
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Topic Locked

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

Sign in to reply to this topic.