Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

jag_oes

Numerical Integration

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

For the longest time, whenever I needed to move crap around the screen I did something as simple as this:
      
// change velocity due to acceleration

velocity += acceleration;


// change position due to velocity

position += velocity;
      
That is just a simple Euler integration with a very inaccurate "delta_t" equal to one. So, if I wanted more accuracy I would set "delta_t" to a really small number and change my code to this:
       
// time step between this and last time calculations were done

delta_t = .01;

// change velocity due to acceleration

velocity += acceleration * delta_t;

// change position due to velocity

position += velocity * delta_t;
      
But, of course this makes everything slower. So, my question, when people use smaller values for "delta_t" to make the integration more accurate do they increase the fps? Or is there something else that I am missing? Edited by - jag_oes on December 14, 2001 4:50:36 PM

Share this post


Link to post
Share on other sites
Advertisement
There are more accurate integration method than Euler''s, which can handle larger timesteps, from Gaussian Quadrature to Fourth Order Runge-Kutta (for Differential eqns).

Usually, the frame rate fixes the timestep, not the other way around, because you measure the elapsed time between 2 frames and use that as your timestep.

Share this post


Link to post
Share on other sites
Fruny sums up my thoughts pretty well. I would just add that if you have enough CPU, then you can do multiple Euler steps for each frame, so you can get the "accuracy" and still maintain frame rates.

Don''t know what you''re doing, but you should know that Euler integration is highly susceptable to numerical instability, and if you''re doing physics this can show up depending how you implement collision response, rigid body joints, or if you have springs.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Unless I misunderstand the question you do it in a loop so perhaps delta_t is the frame duration divided by 10 and you do it 10 times. Integrating an arbitrary function:

  
float step_size = (end_time - start_time) / num_of_steps;
float value = 0.0f;

for (float curr_time=start_time; curr_time < end_time; curr_time += step_size)
value += f(curr_time)*step_size;
//or for midpoint

value += f(curr_time+step_size/2)*step_size;
//or trapazoid

value += (f(curr_time+step_size)-f(curr_time))/2*step_size+f(curr_time)*step_size;


Share this post


Link to post
Share on other sites
Actually, that all sounds pretty good ... I think you all three have answered my question ... thank you very much ...

Share this post


Link to post
Share on other sites
Well, now, how exactly do I implement "Gaussian Quadrature" in my program? The closest information I found on it was having to do with multiple integrals ...

Share this post


Link to post
Share on other sites
I HATE our ISP.asdfas.dfsajfd;lksafjaslkjdfsa, .

I typed in a very nice reply, hit post reply....web timeout. message lost...this happens all the time...ISP sucks.

Anyway, to summarize.

You DON'T want to use Gaussian Quadrature for time marching problems such as simulation of physics and motion, !!!!! . GQ is not designed for this type of problem, and I should have commented on this before after I read Fruny's post.

The Runge-Kutta method is appropriate for this type of problem, but you probably don't need 4th order. Try a 2nd order Runge-Kutta. It should be just fine, and faster than 4th order. (People always seem to like 4th order RK, but the extra precision may not be that useful. You do get some numerical stability benefits with the higher order RK, but those benefits are insignificant compared to changing to an implicit method.) Alternatively, use a Verlet integrator, but do NOT use the "leapfrog" version of Verlet. Leapfrog is just as problematic as explicit Euler. (You are using explicit Euler currently. There is another Euler technique, called implicit Euler. Its way better, probably even better than the Runge-Kutta, but its much harder to implement---implicit methods always are.)

I had some very nice links, but I didn't save them in my favorites and now, thanks to our lovely ISP, all that is gone. I'm too pissed to look them up again. Try my favorite search engine, www.google.com.

(It might not be the ISP. It might be our Corporate intranet server, which is problematic, .)

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Edited by - grhodes_at_work on December 18, 2001 11:21:04 AM

Share this post


Link to post
Share on other sites
Thanks everyone (sorry about the ISP Graham, I would have loved to read your post). What I find most frustrating is that I have a site with the equations for 4th order Runge Kutta, yet no idea as to how I implement it. In LilBudyWizer''s code, what is "f?" If I was integrating velocity for position then "f" would obviously be the velocity, but how do I find the velocity at (time + step/2)? Seems that I would have to integrate acceleration all over again for velocity ... maybe this is correct ... ?

Basically, how do I transform my crappy way of integrating to this new magical way.

Share this post


Link to post
Share on other sites
quote:
Original post by Dave007
and what about Monte-Carlo integration?


Monte-Carlo isn't really a type of integration. Its a type of simulation that deals with uncertainties and randomness. Basically, you loop over a calculation tens or hundreds or thousands of times, changing the calculation slightly with random numbers to find out how the randomness affects the solution. It would sort of wrap around a numerical integration, if you were interested in representing uncertainties. In the engineering world, it is used to design things (cars, airplanes) that are more robust, that react well even when things are random such as air turbulence, small manufacturing flaws, etc. (Actually, my company develops software called ProFES which implements Monte-Carlo simulation, . http://www.profes.com. web site is outdated).

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Edited by - grhodes_at_work on December 18, 2001 5:15:32 PM

Share this post


Link to post
Share on other sites

  • 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!