Sign in to follow this  

Implementing Runge Kutta integrators in existing engine

This topic is 4804 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

I have my physics using a standard Euler integrator right now, and have been playing with the idea of switching to RK2 for some time now. The problem is I can't see a simple way to do it in my existing setup. Basically I have a list of objects which represent a physical body and the forces/torques acting on it - this can be updated by a small timestep. For my car, I have a single body with spring type things attached and this is what confuses me. For RK2 I need to basically perform a normal Euler integration with timestep dt/2, then get the forces on each object after that and use them in the original states for a full timestep. I can update my world by dt/2 easily, but I don't have a 'Calculate forces On body' method for my body objects as the forces are applied to the bodies rather than the body working out what force is applied to it. Any clues on a good way to sort this out? As a side note, since for RK2 you perform 2 updates to advance one timestep, is this more accurate than just running a Euler integrator with half the current timestep?

Share this post


Link to post
Share on other sites
Are you using explicit Euler? I presume you're changing integration schemes due to numerical instabilities?
Might be worth just trying implicit euler as it's a simple change.

Share this post


Link to post
Share on other sites
Hmmm, I don't recall the difference. I am basically getting an acceleration from the force on the body; the position is changed using the current velocity before the velocity is changed using this acceleration.

I think that's explicit, could you elaborate or point me somewhere please for implicit?

Share this post


Link to post
Share on other sites
I had this with my simulator...

i ended up with organizing my data so there's floating point arrays "state array" and "d/dt" and my simulating function calculates "d/dt" from "state array".
That is, in C++ it can be written as
void Simulate(int datacount, const double *pstate, double *pdelta);


and make completely separate integrator class with public members

typedef (*SimulatorProc)(int,const double*,double*);
void Initialize(int datacount, SimulatorProc sproc);// allocates temporary arrays for RK . It may be constructor, if you like
void DoStep(double dt);
void Shutdown();// or destructor, if you like.

And DoStep may work in any way you like, may use any integration method.
Also you will be even able to swich integrating method at runtime, if you make a generic integrator class and make a child classes that implements Euler, RK4, and other methods.

It's hard to work with state/delta as array, so you can 1: make a separate struct with your world data that contains doubles only(or structs made from doubles only), static_cast your array pointer to pointer to it. So you'll have
delta->velocity=state->force/state->mass;
like sintax.
It's probably not very good from standard point of view, i.e. you'll need to set alignment, etc, and it(hypotetically) may break at some systems.


2: Or you can make
enum{
VariableName1,
VariableName2,
....
VarCount
}
and use VarCount as length of array, and VariableName as index in array.

So for example, for space rocket you can do something like that(in "simulate" function)

if(state[fuelmass]>0){
force=state[excaust_velocity]*state[excaust_kg_per_second];
delta[fuelmass]=-state[exaust_kg_per_second];
delta[velocity]=force/(state[fuelmass]+rocketmass);
}else{delta[fuelmass]=0; delta[velocity]=0;}
delta[position]=state[velocity];



Looks clean and readable, but there's some problems with vectors, you'll need to make function that takes index in array and return a reference to it as vector. Something like
Vec3 &delta_vec(int i);
Vec3 &state_vec(int i);
It becomes more difficult if you have more datatypes...

[Edited by - Dmytry on October 8, 2004 8:30:28 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Aph3x
Might be worth just trying implicit euler as it's a simple change.


Not really. If you're talking about just reversing the update so that you update velocity first, then position...that's NOT implicit Euler. The velocity update is still explicit Euler. A true implicit method creates a system of simultaneous equations in which all unknowns are solved for simultaneously by solving the system of equations either via something liks Gaussian elimination or an iterative technique such as Jacobi or Gauss-Siedel iteration...not a simple change. RK2 is a way simpler change than any implicit method.

[Edited by - grhodes_at_work on October 9, 2004 11:54:10 PM]

Share this post


Link to post
Share on other sites
Made the change over from Euler to RK4 in a car sim I've been working on recently. Took us several tries, but we've finally got it right. I would recommend RK4 over 2, if you're going to make the change, you may as well go all out.

A few things you need to keep in mind, that we had to figure out the hard way.
1) You need to update each "step" of the integration for EACH object together. You cant do all 4 RK4 steps for a wheel, and then do all 4 steps for a spring, etc. Need to do step1 spring...step1..body...step1 wheel..etc.

Quote:
but I don't have a 'Calculate forces On body' method for my body objects as the forces are applied to the bodies rather than the body working out what force is applied to it.


I dont really understand what you mean by this. You mean forces on each object are incremented as the simulation progresses, rather than being added up all at once? The body MUST know what forces are on it to get it's accelerations, doesnt it?
We ended up taking the weighted average of the acceleration on each body, and applied that to it's initial velocity. You know the accelerations for your bodies, I would think, otherwise you cannot draw them? Could you not solve the whole system for each incremental timestep and just save the accelerations of each object, then reset to initial conditions and apply a weighted acceleration?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Good comments Mr. Wombat. I'll add that RK4 is, of course, more expensive than RK2. It does give you a bit more accuracy (maybe or maybe not important) and also a bit larger stability domain, which can be important if you want to use larger time steps.

Share this post


Link to post
Share on other sites
The Anonymous msg just above was me, by the way. I do not actually like that the new gamedev forum software kills my auto login after about 1 day----I never remember to take the time and go log in the old fashioned way...

Share this post


Link to post
Share on other sites
I've used the array states as described in one of baraffs lecture notes.

Now i have just two sets of structs and use that together with a compute force function. Chris Hecker uses an index to a target and source array. I'm just copying everything over now.

I'm no expert so i don't know if this is better or not.

Share this post


Link to post
Share on other sites
Quote:
Original post by grhodes_at_work
Not really. If you're talking about just reversing the update so that you update velocity first, then position...that's NOT implicit Euler. The velocity update is still explicit Euler. A true implicit method creates a system of simultaneous equations in which all unknowns are solved for simultaneously by solving the system of equations either via something liks Gaussian elimination or an iterative technique such as Jacobi or Gauss-Siedel iteration...not a simple change. RK2 is a way simpler change than any implicit method.


Whoops sorry - that is what I meant.
What exactly does this do then? It seems to work for me and cured the instabilities I had... probably at great expense to accuracy, although it fits my requirements.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sweenie
I think this tutorial by Marco Monster is pretty good.
Achieving a stable simulator


If by "pretty good" you mean "vague, confusing, and lacking important details as to how it actually works", then yes, I agree.
I read that a few dozen times in my attempts to make RK4 work, and it always confused me more. What is a CalcDerivitives function and how does it work? Why bother? What is a solutionVector? Why make things so over-complicated, especially when the goal is to teach other people how to do something? Sometimes examples seem to be more interested in creating code that looks elegant and can be used in 47,000,001 situations, instead of something solid and reliable that fits exactly what you need. Darn show offs.

Share this post


Link to post
Share on other sites
Well RK2 basically entails generating a new state at time=t+dt/2 from the previous one at time=t using Euler methods, then getting the forces on this state and using them to generate a state at time=t+dt from the initial state. So you do two actual world updates. Is this more accurate than just doing Euler on a dt/2 timestep - CombatWombat I'd be keen to hear what timesteps you used before/since switching to RK4.

Share this post


Link to post
Share on other sites

This topic is 4804 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