Jump to content
  • Advertisement
Sign in to follow this  
taby

4th order Runge-Kutta, varying time step

This topic is 4809 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 am making a simulation which consists of 1 cube and 1 sphere inside of it. Integration is handled via RK4, with a fixed-length time step of 1/60th of a second. The simulation also detects and responds to collisions between the sphere and each of the 6 planes that make up the cube. The reason I am using RK4 is because eventually I will be adding spring forces into the mix. The situation that I am wondering about is when a sphere-plane collision occurs somewhere in-between two of the fixed-length time steps -- for example, exactly 1/3rd of the way. Would it be problematic, in terms of simulation stability, to take a 1/3rd step, apply the collision response force to the sphere, and then take the remaining 2/3rd step in order to get back into the regular fixed-length time step rhythm? What if there are 10,000 spheres inside the cube? The fixed-length time step could potentially be sliced up into many hundreds, or even thousands, of mini-steps of varying lengths. Would this be catastrophic? I only ask because the "Gaffer Articles" indicates that RK4 relies on the use of a fixed-length time step. Would it have been more accurate if the article had stated that RK4 relies on a fixed maximum length time step, and that taking even smaller mini-steps is OK? This is assuming that the maximum length time step is something reasonably precise, such as 1/60th of a second. Ultimately, if this method of using varying mini-steps is problematic, how does one go about handling collision detection and response while using RK4 integration? I am also open to the idea that my method of collision detection and response using mini-steps is altogether flawed. [Edited by - taby on June 17, 2005 2:08:36 PM]

Share this post


Link to post
Share on other sites
Advertisement
I'm starting real time integration but I have a fair background in integrating boundaries problems.

Adaptation of step is currently used with an integration procedure to fit the variation rate of the area currently integrated.

A difference I see with real time is that the adaptation is done on knowledge gathered on the way the function is varying, justifying an adaptation.

The same could be applied to real time but maybe sync problem will appear.

That would mean integrating fast particles with slight speed variation for example and integrating slow particles with a steep velocity variation.

In this end, all these threads might become tedious to sync.

Using a constant time step makes that part easier I think.

Still in the vicinity of borders the time step can be lowered for every particle.

Share this post


Link to post
Share on other sites
Quote:
Original post by taby
Would it be problematic, in terms of simulation stability, to take a 1/3rd step, apply the collision response force to the sphere, and then take the remaining 2/3rd step in order to get back into the regular fixed-length time step rhythm?

yes

Quote:

What if there are 10,000 spheres inside the cube? The fixed-length time step could potentially be sliced up into many hundreds, or even thousands, of mini-steps of varying lengths. Would this be catastrophic?

yes

Quote:

I only ask because the "Gaffer Articles" indicates that RK4 relies on the use of a fixed-length time step.

Would it have been more accurate if the article had stated that RK4 relies on a fixed maximum length time step, and that taking even smaller mini-steps is OK? This is assuming that the maximum length time step is something reasonably precise, such as 1/60th of a second.

yes

Quote:

Ultimately, if this method of using varying mini-steps is problematic, how does one go about handling collision detection and response while using RK4 integration?

I am also open to the idea that my method of collision detection and response using mini-steps is altogether flawed.

further splitting up your intergration timestep for collision purposes is not a very good idea for the reasons you mentioned.

collision detection and handling should first and foremost focus on being stable under all conditions. youre going to get errors anyway, if its not due to your fixed integration timestep it will be floating point error or something else. better make sure your collision detection/handling simply wont mind reasonable error, and can deal with it in a plausible and stable manner.

Share this post


Link to post
Share on other sites
1. There's no reason why you shouldn't have a timestep with RK4 that varies. However, if there are springs/dampers (etc) in the system there will be a maximum timestep for which your system will be stable.

2. If you decide to wind back the simulator to the time of first collision (e.g. 1/3 of the way through the timestep, as you say) it's not obvious to me how to do that - you could run the RK4 step again with dt/3 but then there's no guarantee that the collision will occur! Similarly linear interpolation between the start and end positions/orientations won't necessarily put objects in the collision positions either.

3. After working out how to do the dt/3 step you'll apply collision impulses. Subsequently I don't see why you need to "finish" the step - why not just do another full step? In general your program's main even loop can just run however many physics steps as are necessary (with some limit!) to make the physics time progress just beyond the real/game time - this way you can interpolate between physics old and new states to get the render position/orientation.

4. Generally game physics make the assumption that the collisions that happen "inside/during" the integration step happen so close together in time that the exact time (maybe even order) is irrelevant - thus it's a perfectly reasonable approximation to say that they all happen either before or after the integration step. Doing this makes things much simpler, and can prevent the problems of needing to take tiny timesteps when you have a lot of collisions (or an object trapped between two parallel planes etc). Because it's simpler the code will probably run faster, meaning you can probably use a smaller timestep too, so the approximation is maybe not as drastic as might seem at first.

5. Generally it's considered a good idea to keep a constant timestep - it makes things so much simpler - for example: storing replay data; making the physics code deterministic; being sure a simulation running on one machine will behave the same as on another (on the same platform/OS); making your sim independant of other processes going on on the machine. There are other things too.

Share this post


Link to post
Share on other sites
If you search for adaptive Runge Kutta you will find an entry in the numerical recipes book together with source code. It includes error checking and adjusting the step size on the fly.

Share this post


Link to post
Share on other sites
Thank you all for your advice.

moucoulin and Eelco, I will stay away from non-fixed time steps while using RK4.

After much thought, I found that handling collisions only at the time of each time step is a suitable solution, as mentioned by MrRowl in point 4 of his post. It also seems logical that floating point precision issues raised by Eelco would be solved for the most part.

Thank you for the pointer on adaptive RK, Airo. I will look into this.

Thanks again!


Update: RK4 integration is now operating completely using fixed time steps. Sphere-plane collision detection and response, as well as friction are working as they should.

[Edited by - taby on June 20, 2005 7:43:41 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!