Problem with RK4 Integrator
by Demolishun · in Torque Game Engine · 09/23/2006 (7:27 pm) · 11 replies
Here is a version of rigid that attempts to use RK4:
tdn.garagegames.com/wiki/Image:NewRigid.zip
Rotation has been removed until I understand the issues behind the plain jane linear stuff.
The problem:
The object hits the terrain and other objects, but eventually sinks down just a bit and eventually falls through. If I run the normal torque integrator it does what is it supposed to.
Maybe someone can point out where the problem is.
BTW, when I get this done everyone will be welcome to it.
tdn.garagegames.com/wiki/Image:NewRigid.zip
Rotation has been removed until I understand the issues behind the plain jane linear stuff.
The problem:
The object hits the terrain and other objects, but eventually sinks down just a bit and eventually falls through. If I run the normal torque integrator it does what is it supposed to.
Maybe someone can point out where the problem is.
BTW, when I get this done everyone will be welcome to it.
About the author
I love programming, I love programming things that go click, whirr, boom. For organized T3D Links visit: http://demolishun.com/?page_id=67
#2
Here is the article:
www.gaffer.org/integration-basics/
09/24/2006 (12:43 am)
Read the code. This is from an article about creating a more stable and accurate integrator.Here is the article:
www.gaffer.org/integration-basics/
#3
RK4 is more stable, because it uses higher-order information about the problem being integrated.
Where are you getting this higher-order information from, given that the player input is first order? Specifically, "getforce()" doesn't vary over the time step. You could just as well use closed form integration for the time step. Note that this version of RK4 only uses a single data point from the past ("the current state"). The implementation you see would only be useful if the force varied over the step, such as with a calculated spring (which seems to be the simulation you initially got the code from).
Also, it's confusing that you use the same structure for base data and derivatives -- "p" means "position" or "velocity" depending on the place in the code.
09/24/2006 (9:13 am)
I understand what RK4 does. My question is:RK4 is more stable, because it uses higher-order information about the problem being integrated.
Where are you getting this higher-order information from, given that the player input is first order? Specifically, "getforce()" doesn't vary over the time step. You could just as well use closed form integration for the time step. Note that this version of RK4 only uses a single data point from the past ("the current state"). The implementation you see would only be useful if the force varied over the step, such as with a calculated spring (which seems to be the simulation you initially got the code from).
Also, it's confusing that you use the same structure for base data and derivatives -- "p" means "position" or "velocity" depending on the place in the code.
#4
Please give me an example of higher order information. I have no idea what that means. The only inputs into this system is the physics as defined by the updateForces function inside the rigidShape object for the moment. Eventually input from the player will be included, but it will come from the updateForces function. Right now all of that is encapsulated inside "force".
09/24/2006 (12:06 pm)
So your saying this is only usefull if I recalculate the forces in the getForce call?Please give me an example of higher order information. I have no idea what that means. The only inputs into this system is the physics as defined by the updateForces function inside the rigidShape object for the moment. Eventually input from the player will be included, but it will come from the updateForces function. Right now all of that is encapsulated inside "force".
#5
The structure of this will change drastically when I remove the non-class type calls. Everything will be a variable inside the rigid class. I may even make the integrator selectable from script.
09/24/2006 (12:46 pm)
Doesn't Euler integration suffer from error regardless of the order of the data coming in? The way I understand this code is it does a better "curve fit" of sorts to get a value that more closely matches reality. I have looked at bunch of other articles on this RK4 method and most of them show graphs of the improved accuracy of the output. The structure of this will change drastically when I remove the non-class type calls. Everything will be a variable inside the rigid class. I may even make the integrator selectable from script.
#6
The problem is that the integrator has no more data to compare to, because the getforce() function just returns an instantaneous value that does not depend on time. If getforce() took a time, and interpolated the force value between the old value, and the next value, over the time period, then RK4 would be better than Euler.
As it is, if you sum it all out, you will notice that the derivatives come back as the same value for all the sub-steps. Then the weighted sum of the derivatives just add up to the total that you'd get for a forward-Euler step anyway. I suggest you put a breakpoint in and check it for yourself.
The main problem is that, at the T, getforce() may return 0 for time T+dt for the variables c and d. However, then at time T+dt (one step later), getforce() will return non-0 for the variable a -- in effect, you're introducing a discontinuity in the data you supply the integrator, which disables its ability to properly integrate.
09/24/2006 (2:37 pm)
Quote:The way I understand this code is it does a better "curve fit" of sorts to get a value that more closely matches reality.
The problem is that the integrator has no more data to compare to, because the getforce() function just returns an instantaneous value that does not depend on time. If getforce() took a time, and interpolated the force value between the old value, and the next value, over the time period, then RK4 would be better than Euler.
As it is, if you sum it all out, you will notice that the derivatives come back as the same value for all the sub-steps. Then the weighted sum of the derivatives just add up to the total that you'd get for a forward-Euler step anyway. I suggest you put a breakpoint in and check it for yourself.
The main problem is that, at the T, getforce() may return 0 for time T+dt for the variables c and d. However, then at time T+dt (one step later), getforce() will return non-0 for the variable a -- in effect, you're introducing a discontinuity in the data you supply the integrator, which disables its ability to properly integrate.
#7
Now, I am guessing that I need to be checking for impulses from collisions as well during the getForce function. I have it partially working now, but it does not seem to apply enough impulse to prevent going through the terrain.
Thanks for your insight. I will update my progress sometime tonight. It is a mess, but it will be both rigidShape and rigid now that both are being gutted to try and make this work.
09/24/2006 (5:06 pm)
Now I see what you are saying. I have messing around with moving the updateforces and telling the applyimpulse functions to spit out forces. This is really hard to change considering the current code. I think I may rework the physics to be intrinsic to an object class rather than an attachment to it. I think I will have to go back and create a new version of rigidshape that inherits from rigid so they will play better together. Now, I am guessing that I need to be checking for impulses from collisions as well during the getForce function. I have it partially working now, but it does not seem to apply enough impulse to prevent going through the terrain.
Thanks for your insight. I will update my progress sometime tonight. It is a mess, but it will be both rigidShape and rigid now that both are being gutted to try and make this work.
#8
09/25/2006 (8:17 pm)
Okay, I didn't get any further in resolving my issues. So I am rewriting it in its own class that I expect to inherit into a regular torque object that is based upon gamebase. This will provide a foundation for adding physics to the object. Once I get something working I will put it on TDN.
#9
It's done this way primarily for having the ability to properly sequence and apply updates across the network, specifically for control objects.
It's also yet another one of the challenges with real time networked physics--for accurate, responsive networking, you wind up having to accept a much more simplistic physics model, or deal with incredibly agonizing synchronization issues.
09/25/2006 (9:51 pm)
JW hit on something that's inherent in both the Torque Physics and Torque Input models--there is no concept of force, acceleration, or even true "time passing" from tick to tick. Instead, each tick that is processed creates a (sort of) determinstic delta that can then be networked to the clients (and server, in the case of a control object) for replication.It's done this way primarily for having the ability to properly sequence and apply updates across the network, specifically for control objects.
It's also yet another one of the challenges with real time networked physics--for accurate, responsive networking, you wind up having to accept a much more simplistic physics model, or deal with incredibly agonizing synchronization issues.
#10
Ideally, you'd also run collision detection for each of the sub-steps, so that your collision forces are properly integrated, too. At that point, you're using something quite different from the current Torque physics, though :-)
The draw-back is the controller lag, and the actual implementation pain.
09/26/2006 (11:01 am)
An alternative is to accept an input lag of up to one tick. You can build a model where the input is ramped between "on" and "off" over the duration of one tick, so when you integrate, you get consistent derivatives.Ideally, you'd also run collision detection for each of the sub-steps, so that your collision forces are properly integrated, too. At that point, you're using something quite different from the current Torque physics, though :-)
The draw-back is the controller lag, and the actual implementation pain.
#11
JW,
I am going to try and model every collision around a spheroid object to simplify collision processing like you had suggested.
Once I get something working I will check back in.
09/26/2006 (6:25 pm)
Yes, me and my associate have been looking at the "forces" method currently used. I have trying to understand how it works and I am finally came to the conclusion that I will never get to my 100 object goal even with simplified versions of it. I am going to take a different direction and as my friend says, "go one level up" to an energy based system. I see lots of benefits to it in the computational load side. It may be harder to model things initially, but the reduced calculation may get us somewhere near my goal I hope. JW,
I am going to try and model every collision around a spheroid object to simplify collision processing like you had suggested.
Once I get something working I will check back in.
Torque Owner J "hplus" W