Introduction
Hello, I’m Glenn Fiedler and welcome to the second article in my series on game physics.
At this point we have a working physics simulation, and we want to get it up on the screen. How do we do it?
As we discovered in the previous article, physics simulation is performed by starting at some initial state (position, velocity etc), then integrating the equations of motion over time to advance the physics state forward in small time steps. The trick to showing this physics simulation animating on screen is to simply take a physics step, then draw the object. If we repeat this process over and over, we show the physics state animating over time.
Stepping forward in time
First thing we need to do is choose the timestep to advance the simulation ahead each time we draw the object. The easiest way to do this is to step your physics ahead by a fixed amount of time each step.
For example you could step ahead 1/100th of a second each frame:
float t = 0.0f;
float dt = 0.01f;
while (!quit)
{
integrate(state, t, dt);
render(state);
t += dt;
}
The problem is that you can never really be sure exactly what framerate the simulation is running at. Some computers render at 60hz, and others render at 75 or 85hz. Slower computers may only be able to render at 30hz.
This means that if you fix the framerate to a constant delta time each frame, your simulation will seem to run faster or slower, depending on how fast the computer is able to render your scene.
One way to fix this is to use a high resolution timer to get the current time value each time you update the physics. Then you can work out the time in seconds between the current physics integrate call and the previous one, and pass this time in as dt as follows:
float t = 0.0f;
float currentTime = time();
while (!quit)
{
float newTime = time();
float dt = newTime - currentTime;
currentTime = newTime;
integrate(state, t, dt);
t += dt;
render(state);
}
This last method looks pretty good. If the game is running at 60fps then each dt will be passed in as 1/60th of a second to the simulation, and if the game is running on a slower computer it will pass in 1/30th of a second for 30fps. No matter how fast or slow the computer is, your simulation will always run at the correct speed.
But there is a huge problem with doing it this way which I will now explain!
Fix your timestep or explode
The problem is this. We are using numerical integration so the results of the integration depend on the size of the timestep. This is even true for advanced integrators like RK4. The larger the timestep the less accurate the results. So if you develop your simulation running at 60fps then at some point during your game the framerate drops to 10fps then all bets are off.
This may not seem like a big deal, but consider that in physics simulation, a small change in timestep can cause huge differences in behavior. If you have a series of really stiff spring constraints for shock absorbers in a car simulation then tiny changes in dt can actually make the simulation explode.
So ideally what we want is the best of both techniques. We want to choose a single dt so that every time the simulation runs it is stable and behaves exactly the way it was intended. At the same time we want the simulation to run at the same perceived speed irrespective of the display framerate. These two requirements seem completely at odds, and they are, unless we can decouple the physics and display framerates.
Free the physics
What needs to be done is to advance the physics simulation ahead using a fixed dt but make sure that it keeps up with the display framerate so that the simulation appears to run at the same speed. For example, if the display framerate is 50fps and the simulation is designed to run at 100fps then we need to take two physics steps every display update to keep the physics in sync.
But its not always this easy. What if the display is running at 60fps? Even trickier, what if the display framerate is 200fps? In this it would seem that we need to take half a physics step each display update. But we always need to step forward in discrete dt sized steps, so the best we can do is one physics update every two display updates. What if the display framerate fluctuates between 40 and 60fps? Ouch.
If you think about exactly what is required to keep the physics update in sync with the display update while only ever taking discrete timesteps of size dt you will see that its not trivial. But now I will share with you a trick that makes it very easy to implement correctly.
The trick is to use a time accumulator. Each update you add the display deltaTime from your high resolution timer into this accumulator. Then, while there are whole increments of your dt available you run a physics step and subtract the physics step dt from the accumulator. Effectively the timer produces time and the physics update consumes it in discrete dt sized chunks.
float t = 0.0f;
const float dt = 0.01f;
float currentTime = time();
float accumulator = 0.0f;
while (!quit)
{
float newTime = time();
float deltaTime = newTime - currentTime;
currentTime = newTime;
accumulator += deltaTime;
while (accumulator>=dt)
{
integrate(state, t, dt);
t += dt;
accumulator -= dt;
}
render(state);
}
This code handles both undersampling and oversampling correctly which very is important. Undersampling is where the render framerate is lower that the physics framerate, eg. 20fps display when physics runs at 60fps. Oversampling is where you have an insanely high framerate (or you are viewing physics in slow motion) where one physics frame accumulates over several display updates. Note that the “sampling” here applies not to the physics steps, but to the renderer sampling state and drawing it on the screen.
There is one final thing that you need to be careful of when using this technique. Now that our physics simulator is smart enough to step any large deltaTime passed to it in small dt increments, make sure that you clamp the deltaTime passed in from the timer to some maximum value like 0.25 seconds. Why? Well if you alt-tab away from your physics simulation in windows then come back to it 10 minutes later, you’ll be waiting a long time for it to catch up the last 10 minutes of physics in 1/100th of a second increments…
The final touch
So it seems that all is well. Our simulation is stable and framerate independent but there is still one last thing to do before it is perfect. Consider what will happen if the display framerate is 55fps and the physics is running at 60fps. Basically the time accumulator will have to alternate between taking one and two physics steps each display update to make sure that it keeps up. This irregular amount of physics steps taken per update causes a subtle but visually unpleasant stuttering of the physics simulation on the screen.
Even worse, if you have an oversampling case, say in slow motion mode (1/10th speed) your effective display framerate would be 600fps if your display is actually updating at 60fps. Assuming the physics is also running at 60fps the accumulator would only do one physics step every 10 display updates. This means that objects animate in discrete jarring steps every 1/6th of a second. This looks pretty dodgy but the good news is that there is a way to make sure that everything runs smoothly all of the time.
The solution is to interpolate between the previous physics state and the current state based on how much time is left in the accumulator. This will add a latency of up to dt to your physics simulation, but the visual results are definitely worth it. Here is how to implement it:
float t = 0.0f;
const float dt = 0.01f;
float currentTime = time();
float accumulator = 0.0f;
State previous;
State current;
while (!quit)
{
float newTime = time();
float deltaTime = newTime - currentTime;
currentTime = newTime;
accumulator += deltaTime;
while (accumulator>=dt)
{
previousState = currentState;
integrate(currentState, t, dt);
t += dt;
accumulator -= dt;
}
const float alpha = accumulator / dt;
State state = currentState*alpha + previousState*(1.0f-alpha);
render(state);
}
This looks pretty complicated but here is a simple way to think about it. After the deltaTime has been added to the accumulator and the physics steps of size dt have been performed, if the physics and display fps are not integer multiples of each other, then some time will remain in the accumulator. This remainder is effectively a measure of just how much more time is required before another whole physics step can be taken. For example, a remainder of dt/2 means that we are currently halfway between the current physics step and the next one. A remainder of dt*0.1 means that the update is 1/10th of the way between the previous and current states.
We can use this remainder value to get a blending factor between the current physics state and the previous state simply by dividing by dt. This gives an alpha value in the range [0,1] which is used to perform a linear interpolation between the two physics states to get the current state to render. This interpolation is easy to do for single values and for vector state values. You can even use it with full 3D rigid body dynamics if you store your orientation as a quaternion and use a spherical linear interpolation (slerp) to blend between the previous and current orientations. I’ll show you how to do this in the next article.
If you implement this interpolation technique you ensure that there will not be any visual stuttering when your display and physics framerates are out of sync. It will also perfectly handle the undersampling case so your objects will move smoothly when you view your simulation in slow motion or ten years from now on a really fast computer.
Conclusion
Time stepping seems so simple, yet it contains many subtleties that you must understand to implement it perfectly. I hope you can use the techniques presented in this article to improve time stepping in your physics simulation. Certainly if you follow exactly what is presented here you can decouple your display and physics framerates for determinism and stability, and at the same time, ensure that your physics animates perfectly smoothly on screen. It really is the best of both worlds.
Click here to download the source code for this article.
Finally, for what it is worth, I recommend using this time stepping technique for all game systems. Pick a framerate that is appropriate for your game code (say 60fps), then decouple your entire game engine update to run at this fixed framerate. Why bother? Well the same stability and reliability reasons that drove us to do this for physics apply to game code too. Running your game code at different delta time values usually produces different results. By choosing a fixed framerate for all your systems you can ensure that your game behaves consistently independent of framerate. I’ve certainly seen enough bugs in game code that only show up at low framerates in my time. There is no need for this to happen, just fix your time step and be done with it already.
71 responses so far ↓
1 Andrew Ladenberger // Sep 14, 2006 at 12:00 pm
Great article! Best article I’ve read on this important subject. Very nice and clean implementation too.
Do not worry about your difficulties in Mathematics. I can assure you mine are still greater
-Albert Einstein
2 Phillip // Sep 15, 2006 at 11:05 am
Excellent articles on game physics. I’m starting to do some research on network-based state machines/physics and they were quite helpful.
3 JC // Sep 29, 2006 at 8:17 pm
Thanks so much for posting this! After trying to figure this out after many hours, I was able to quickly
come up to speed thanks to this article. Excellent work!
4 pTymN // Oct 13, 2006 at 9:44 am
Also, fixed internal framerates help when you do networked games.
5 Ruud van Gaal // Nov 21, 2006 at 10:06 am
Given the last interpolation trick with ‘alpha’ blending between states, you’d think that for physics-intensive programs it may be important to really catch up with realtime. I.e. after the while(accumulator>=dt) loop finishes, do a new deltaTime calculation with a new time() call and re-enter the while loop if deltaTime is bigger than some threshold.
I’ve noticed with my car simulator that the physics can take up quite a bit of CPU time, making the last alpha blending call a bit useless if you’re already straying away from the actual time.
6 Paul // Nov 28, 2006 at 10:04 am
Excellent article and very helpful to my current situation. Thanks for taking the time to explain this in terms that non-mathematician games programmers can have a half chance of understanding.
7 Manu // Dec 29, 2006 at 7:36 pm
Thank you very much!
(really!)
This solves all my problems
8 Phil // Jan 12, 2007 at 7:20 am
Very nice article. I’m curious about a possible optimization though. Rather than doing the physics in a While loop, why not calculate how many physics updates you have time for and run them in a For loop? Obviously if the framerate is fluctuating this is less accurate, but this way - because you know when you’re going to end - you need only capture the state on the last run through. Since you only do multiple physics updates when the system is struggling to keep up, knocking out the requirement to capture the state before and after each update might save you time and help you keep up, no?
9 Glenn Fiedler // Jan 12, 2007 at 11:18 pm
well, i’m not sure if that will work - there are certainly other strategies for doing updates, but if you want to use this one, you need to be very careful to follow the accumulator/while loop logic very closely
its quite intricate and is doing a lot more than it looks like it is…
yes, it is possible to get into a “spiral of death” with physics when using this technique, when you are heavily CPU bound
so in general this technique is great when you are renderbound and simulation is cheap and reasonably predictable.
to take it even further, you can run the main physics loop entirely on a separate thread which actually runs (in real time) at the number of frames per second the physics should run (say 100hz) and the render thread just reads latest physics state and interpolates, completely independent of physics
this way you are never doing two or more physics updates per-update, so processing is more evenly distributed
in addition, if you gather the input for you simulation on the physics thread, you sample the joystick or keyboard at regular 100hz intervals, which leads to better behavior of your physics
consider this, “fix your timestep version 2.0″
cheers
ps. another option i should mention is just plain framelocking, just pass in delta time as 1/60th of a second every frame, no matter what the real time value is. yes, your simulation will slow down in real time, but you’ll get the stability benenfits of fixed delta time updates — this is a good technique when you are mostly simulation bound, but it breaks down when you want synchronize with display refresh to get everything perfectly smooth
10 Matt // Jan 16, 2007 at 3:01 am
I thought I could get by without fixed timestep, however some testers were having issues with the game I’m working on - which were fixed by a fixed timestep. Thanks for writing the article, it saved me tons of time messing around.
11 Romz // Feb 9, 2007 at 5:15 pm
Hello, great article! I’v implemented your technique but I’d like your advice about (mega)oversampling.
My project doesn’t do much things so the framerate is insanely high with my PC (3000fps), and the timer of my engine (Ogre) gives me a deltaTime of 0, because it’s has a precision of 1 milisecond, so 1/3000 = 0.00033s = 0.33ms (that’s why I got 0).
I already had this problem with the SDL timer and I guess a QueryPerformanceCounter or any other high precision timer have the same limitation. So I thought putting some ugly Sleep() in the code to obtain a valid deltaTime. How do you think it’s possible to do something about this ?
And even I if want to fix the display framerate, the problem is the same (adding 0 to any accumulator, so it’s never time to update).
Thank you !
12 Glenn Fiedler // Feb 10, 2007 at 12:13 pm
use a higher resolution timer, 1ms resolution is next to useless, and is the root cause of your problem
use QueryPerformanceCounter directly!
13 Romz // Feb 11, 2007 at 5:53 pm
Everything is now working perfectly, and the interpolation part makes a noticable difference ! Thanks a lot
14 andre krause // Feb 13, 2007 at 6:16 am
i have to thank you, too! i’m using your accumulator code in my game project, too.
currently, i’m running under win32 and have a high-res timer. but - i want to port it to linux. under linux, there is apparently no reliable way to get any sort of highres timers. so. what now?
is it possible to somehow calc the mean framereate (e.g. measure number of frames rendered in 1 second) for the whole physics+graphics loop, and then calc the needed number of physics step?
for example:
whe have 20 fps, and physics needs 100Hz
so we would need to do
100/20 = 5 physics loops every frame? is this right?
15 Glenn Fiedler // Feb 13, 2007 at 10:34 am
ok, under linux there are a few options for high res timers:
see http://pixeltoaster.googlecode.com/svn/trunk/PixelToasterUnix.h
and look at the code for the “UnixTimer” class (two different techniques are presented)
both should give you good precision
cheers
16 Leigh McRae // Feb 21, 2007 at 8:33 pm
Very nice article. I was using this method for a game and it actually caused a very subtle bug. When playing very large in game cut scenes, the audio would become out of sync with the animations. I tracked the problem down to delta time accumulating error. The solution instead was to keep a simulation time and a real time. Then the loop is something like:
while ( (time() - simTime)>=dt )
{
simTime += dt
}
You still get error but it’s less. It also works with a crappy timer
Leigh
17 Jose Gregoris // Jun 19, 2007 at 7:27 am
Hi
Very nice article.
Now, I want to ask a question.
I’m using NewtonGameDynamic and Genesis3D .
I implemented the GameLoop without the “The final touch”, and I have the problem that you comment:
The final touch
So it seems that all is well. Our simulation is stable and framerate independent but there is still one last thing to do before it is perfect. Consider what will happen if the display framerate is 55fps and the physics is running at 60fps. Basically the time accumulator will have to alternate between taking one and two physics steps each display update to make sure that it keeps up. This irregular amount of physics steps taken per update causes a subtle but visually unpleasant stuttering of the physics simulation on the screen.
My problem is, I don’t understand like I can use the interpolation of the article for my system.
You use OpenGL and it is easy to use the value of the interpolation for rendering the point directly.
Newton uses callback to transform the objects 3D.
My callback is this:
VehicleChassis(Class)>>transform: pBody from: pMatrix
| chassis matrix |
chassis := NewtonRigidBody userDataFrom: pBody.
matrix := NewtonMatrix fromBytes: pMatrix.
“Relocate the GenesisActor”
chassis actor pose: matrix asGeXForm3d.
^NULL
I take the matrix that Newton sends me and I relocate my objects directly.
Would I have to interpolate the matrix before relocating my objetos3D?
Advance thank.
KIKO
PD: Perhaps you could enlarge the example using an engine
18 Glenn Fiedler // Jun 19, 2007 at 9:46 am
sure, well you just need to buffer the position/orientation coming out of newton’s callbacks, then at render time (later in the frame - dont do it within the callback), render an interpolated value
19 Jose Gregoris // Jun 20, 2007 at 7:51 am
Hi Glenn
Thank you for their attention.
I have a question more.
Suppose you, that I update the physics with a dt=0.016 that is the minimum that NewtonGD requires.
The range is of (1/60.. 1/1000) for NewtonGD.
I would update the physics X times before the render, you suppose 16 times.
With a smaller dt=0.01 I would be update the physics more times, you suppose 25 times.
My question is:
Should I have a buffer the position/orientation coming out of newton’s callbacks of variable size?
For example: 16 for dt=0.016 or 25 for dt=0.01.
Is this correct?.
if it is this way.
How I do make to manage after the update of the physics the render?
I implement the solution with 2 variables (currentMatrix previousMatrix), but I have the problem of the stuttering
I am really confused
Advance thank
20 Glenn Fiedler // Jun 21, 2007 at 10:38 pm
i think you should try a simple example first, and get your head around it — its not hard! but becomes complex when introducing middleware and “its way of doing things”
here is what i think you need to do with newton, always update it at 60fps (~16.7 ms per frame), but interpolate between according to render rate, as described in the article above
so newton is always creating state for you on integer frame numbers, exactly 1/60th of a second apart, while your renderer is not always doing this, it is working on arbitrary dt, — so you interpolate between the two nearest integer frame samples to find the position/orientation of your body at the render time
cheers
21 Gregoris jose // Jun 23, 2007 at 12:17 pm
Hi Glenn
Thank you again.
Excuse that I insist once more. I will try to explain again, what I don’t understand and I will accompany him with my code.
You wrote:
There is one final thing that you need to be careful of when using this technique. Now that our physics simulator is smart enough to step any large deltaTime passed to it in small dt increments, make sure that you clamp the deltaTime passed in from the timer to some maximum value like 0.25 seconds. Why? Well if you alt-tab away from your physics simulation in windows then come back to it 10 minutes later, you’ll be waiting a long time for it to catch up the last 10 minutes of physics in 1/100th of a second increments…
Well, Let us suppose the stage.
deltaTime=0.016 for physics update.
accumulator=0.25 .
while (accumulator>= deltaTime)
{
accumulator -= deltaTime;
NewtonUpdate(deltaTime).
}.
The amount of times that NewtonUpdate () it is called it is: 15 times.
On the other hand, Newton calls 15 times to the callback:
“void PhysicsSetTransform (const NewtonBody* body, const dFloat* matrix). “
In my buffer I have 15 matrix. OK.
Now, is time of render. OK.
In this point is where I don’t know that I should make.
If my buffer would have 2 matrix, it would be easy to interpolate its values. But with 15 matrix?.
If I make an interpolation between the first and the last matrix, this it would not be correct. Right ?.
I implement this last and it doesn’t work. I continue having stutterer problems.
Could you explain a little more, how do I have to make the render?.
My code in Smalltalk:
GenesisMainWindow>>onIdle
“Private - Processes onidle messages.”
[thisApplication peekMessage)not ] whileTrue:[ self application update.
thisApplication peekMessage ifTrue:[^true]].
“application = GenesisSpaceManager”
GenesisSpaceManager>> update
self isReadInputTime ifTrue:[ self readInput].
self physicsManager update . “Perform physics update”
“This is the site where I don’t know that I have to make”
self updateVehicle . “Set the position/orientation with the matrix of Newton callback”
self render.
PhysicsManager>>update
|now elapsed|
now := Time millisecondClockValue.
elapsed := (now - self lastPhysicsUpdate) / 1000.0.
(elapsed > 0.25) ifTrue:[elapsed:=0.25] .
accumulatedTime:=accumulatedTime + elapsed.
[accumulatedTime >= 0.016] whileTrue:[newtonWorld update: 0.016.
accumulatedTime:=accumulatedTime - 0.016 ].
self lastPhysicsUpdate:Time millisecondClockValue.
GenesisSpaceManager>>render
(engine beginFrame:self camera clearScreen: true) ifTrue:[
engine render: aWorld with:self camera time:0].
(engine endFrame).
Advance thank you
KIKO
PD: Sorry for my english.
PD2: I hope not to drain their patience
22 Cazy // Jun 26, 2007 at 1:46 pm
I am very impressed by the quality of the article too. I’ve read a few more on the subject but none was this clean and eloquent.
One comment though. The interpolation function in your code looks like this:
State state = currentState*alpha + previousState*(1.0f-alpha);
My calculations (and intuition) say it should be:
State state = currentState*(1.0f+alpha) - previousState*alpha;
Am I wrong? Can you double-check your math?
Best regards, Cazy.
23 Glenn Fiedler // Jun 26, 2007 at 8:41 pm
i’m certain its correct, why dont you download the example source code, switch the math around and try it?
ps. i always find it intuitively wrong too, and its always tricky to get it the right way around when i code it fresh… but its right i tells ya!
24 Glenn Fiedler // Jun 26, 2007 at 8:45 pm
#21 - you seem to be a bit fuzzy on exactly what to interpolate. please read the article again and study the example source code that comes along with the article, the answer *is* in there
once you have the concepts straight, then perhaps try to “refactor” the example source it into a form more like newton (with callbacks on update), then you should get it!
(hint, you’ll need a circular buffer indexed by frame # — or at least, store the last 2 previous state values for each object)
cheers
25 Glenn Fiedler // Jun 26, 2007 at 8:59 pm
#22 ok, cazy i’ll prove it via logic, just because i’m feeling a bit evil now
first, take the “left over” bit of time that doesnt fit exactly into our chosen fixed “DeltaTime”
this is basically, currentTime modulus DeltaTime, but in the article i implement it by taking our deltaTime value (the real value from the time), and increasing our currentTime value in whole frame increments
maybe a better way to do this would be to forget about floating point time, and just have “frame” and “accumulator”:
to update time:
const float FrameRate = 60.0f; const float DeltaTime = 1.0f / FrameRate; int frame = 0; float accumulator = 0.0f; while ( true ) { accumulator += GetDeltaTimeFromTimer(); // note: delta time in seconds while ( deltaTime >= DeltaTime ) { frame++; accumulator -= DeltaTime; // (simulate frame) } }the code above may be a bit clearer than the code in the article
ok, so each time through the loop, we know two things:
* our frame number (integer)
* our current accumulator (in seconds)
to calculate alpha, lets take the accumulator value, which will be (by definition) in the range [0, DeltaTime)
note the “)” at the end, it cannot actually equal DeltaTime, it can just approach it (if it did equal DeltaTime, we’d just iterate through the loop once more, and subtract DeltaTime getting it to be zero)
ok, so we need a blend factor. lets call this “alpha”
we want blend in [0,1], so we just take accumulator and divide it be DeltaTime - note that this actually generates a value in the range [0,1)
but what does “alpha” mean? which value of alpha means “100% previous frame” and which side means “100% current frame” ?
to work this out, just look at accumulator:
if we are *exactly* on the previous frame value, accumulator will be zero, and so will alpha
if we are say, 90% near the end of the frame, accumulator will be 9/10ths of the way towards DeltaTime, so alpha will be 0.9
so clearly, if alpha is 0 - we wish to have 100% previousFrame, if alpha is 1 we want 100% of currentFrame
so, the correct interpolation is:
or if this makes it a bit clearer:
(note that if alpha = 0, 1.0f-alpha = 1.0f, which gives 100% previous state)
cheers!
26 Cazy // Jun 26, 2007 at 10:46 pm
The answer is here: “The solution is to interpolate between the previous physics state and the current state based on how much time is left in the accumulator. This will add a latency of up to dt to your physics simulation, but the visual results are definitely worth it.”
Yes, your math is the correct one for the interpolation function. Sorry for the missunderstanding. Although I was calling it interpolation I was actually talking about extrapolation. The extrapolation gives a real time estimate of the state. If you add (CurrentState-PreviousState) to the interpolation formula, you get the extrapolation formula.
Can you tell me the reason why interpolation is better than extrapolation? They are both just linear estimates of nonlinear physics behaviour. I know there is a reason, I just don’t know it.
Best regards, Cazy.
27 Glenn Fiedler // Jun 26, 2007 at 10:49 pm
interpolation is between two known values, so its “perfect” - just lagged by up to one frame
extrapolation is jerky and is predicting ahead, thus gets it wrong, and has to snap and pop to correct
trust me you want interpolation
take the example source code and change it to extrapolation, and let me know how it goes! - maybe it’ll be good for you, i’m conservative so i prefer interpolation
cheers
28 Cazy // Jun 27, 2007 at 12:03 pm
What confused me is that the actual current time is currentTime + acumulator, so it’s outside the (previousTime, currentTime) interval. But after thinking it trough I realised that what you’re doing is shift the fraction alpha back one inteval. This is complelty legal, as the game loop uses a fixed time step. So CurrentState could be vweyt well named NextState and PreviousState could be named CurrentStep.
Thank you for your time, reading your article and replies was very informative. One other question though (feel free to ignore it): why do you initialize currentTime to 0? Isn’t that going to give a wrong deltaTime the first time the game loop is entered?
Best Regards, Cazy.
29 Glenn Fiedler // Jun 27, 2007 at 8:30 pm
good point, fixed!
30 Gregoris jose // Jul 1, 2007 at 5:15 pm
Hi cheers
I cannot make him to work still, but I think that I am very close.
At the moment, I don’t use QueryPerformanceCounter .
I wanted to ask to you.
How much can this affect in the problem?.
At the moment I has a undersampling problem.
My fps fluctuates between 29 and 35.
Advance thank you
KIKO
31 Glenn Fiedler // Jul 1, 2007 at 5:34 pm
chances are, the precision of your timer is probably too low - upgrade to QueryPerformanceCounter and see how it goes
32 Darklawl // Sep 28, 2007 at 4:38 pm
Great article which nicely describes a solution for a “common” problem!
33 sydd // Nov 3, 2007 at 7:29 am
Great article!
I read your atricles printed, id be happy if the would be a printer-friendly version of your stuff too
34 Glenn Fiedler // Nov 3, 2007 at 6:02 pm
i’m using wordpress - dont think it supports that, but if you cut & paste the article text into word i think you’d get something nice to print, — could probably even cut & paste into an email app, then print the email, whatever
35 Barend // Nov 4, 2007 at 5:40 am
Indeed a good article on an important topic. However, I don’t agree with your use of deltaTime. This value relies on the accuracy of time(). Even if it’s a high-res timer, the accumulator accumulates inaccuracies over time.
Related to that, I don’t agree with “keep the physics update in sync with the display update”. If it’s a simulator, then shouldn’t the physics be the driving factor? And the display updates follow? Accuracy first?
I propose getting rid of deltaTime and accumulator, and introducing a variable nextPhysicsTime to store the time at which the physics should be updated again. You update the nextPhysicsTime by simply adding dt, which is more accurate than an accumulator that relies on time().
What i’m saying is, the physics time should be synched with real time directly.
This code is pre-”final touch”:
float t = 0.0f;
const float dt = 0.01f;
// absolute time we should do the next physics update(s)
float nextPhysicsTime = time();
while (!quit)
{
while (time() >= nextPhysicsTime)
{
integrate(state, t, dt);
nextPhysicsTime += dt;
t += dt; // not sure what t is
}
render(state);
}
36 Glenn Fiedler // Nov 4, 2007 at 5:23 pm
dude, you totally missed the point of the article - read it again
37 Barend // Nov 5, 2007 at 5:17 am
Ok, cool. I do get the point. It is to untie physics from rendering, and to get each update to do updates for a fixed amount of time. There are many reasons for doing that.
When I look at your code again, I see that your deltaTime IS correct, even if time() is not accurate. I’m sorry about the mistake.
I still think the code can be simplified. There is no need to have currentTime, assumulator, endTime etc. You can do the same by having 1 variable nextPhysicsTime and incrementing this by dt on each update.
For what it’s worth, the Java code below produces perfectly smooth animation, if v-refresh is equal to the target fps. If not, it would need your interpolation code.
Dude.
long period = 1000000000L/60; // 60 is target fps
long nextUpdateTime = System.nanoTime();
while (running) {
while (System.nanoTime() >= nextUpdateTime) {
update(…);
nextUpdateTime += period;
}
paintScreen(…);
}
38 Glenn Fiedler // Nov 5, 2007 at 1:10 pm
you are right, and i dont code it the way explicitly mentioned in the article here, its just the easiest way to explain it to folks
if you use floating point values to store time values, you are a bloody idiot!
basically, i use 32bit integer vales to represent time, and do all the calculations in 64bit integers
but, i dont want to do a tutorial about fixed point mathematics also… =)
cheers
39 DrPadawan // Nov 27, 2007 at 3:44 am
>…and do all the calculations in 64bit integers
What’s the sake of doing everything in fixedpoint? Is that to only avoid floating value de-normalization and accuracy degradation problems?
On the other hand, as I know (at least on x86) floats are faster to multiply than integers. Division is not faster, but while doing division, CPU can perform integer operations in parallel (except integer multiplication).
40 Naveen Nattam // Jan 9, 2008 at 11:31 am
I just wanted to give a huge thanks to you Glenn. Your method helped me out incredibly! I have way more control over my physics simulation in my app now! Thanks again!
41 Cyde Weys // Mar 10, 2008 at 9:00 pm
Thanks for the great article. You have the optimal solution here that I really wish I had known about when I was screwing around with physics simulation Java applets back in high school. The animation was just never quite right.
42 Glenn Fiedler // Mar 21, 2008 at 10:49 am
dr. Padawan - i’m just saying that time should fundamentally by an integer quantity, not anything else!
If you use floating point numbers for time, your time value will get less accurate the longer your program runs for
If you use fixed point, its the same accuracy forever, provided you intelligently handle wrap around (this is not too hard…)
cheers
43 Macguffin // May 5, 2008 at 11:41 am
Hi Glen,
That’s an excellent article. Thanks!
44 David // May 21, 2008 at 6:49 pm
Hi Glenn,
Thank you for this article, as a beginner in game development this is a great help and I will definitely make my game loop like this.
I also like the way you separate your window code from your game code, it makes everything so much more clean.
I got a question though, when I run your example I can still see the dot stuttering from the moment it goes left for the second time and the stuttering stays until it slows down in the middle.
Is that normal? Am I being too picky? Do you have the same effect when you run it or your computer?
Anyway, again, thanks a lot for this.
Regards
David
45 Dunge // Aug 11, 2008 at 4:46 pm
I was reading your article and tough it was perfect, but I just though “integrate” meant the physics update/game logic/input pooling and I though it was working this this, but after checking the source code, integrate is really a mathematical integration, and I don’t quite understand what it is doing there. I also don’t quite understand the constants used in the function, and what are x and b are supposed to mean in your State structure..
46 Bob // Aug 11, 2008 at 5:50 pm
For the Windows alt-tab issue, the other solution is to run the physics code even when the renderering code isn’t happening. This should free up the CPU time being used for graphics, and given the technique in the article wouldn’t need to run perfectly smoothly anyway.
This is especially important in multiplayer games where you can’t just automatically pause the game.
47 Damian Nikodem // Aug 14, 2008 at 7:01 pm
Whilst a intresting article on this topic I did find one flaw though.
In the past where I have had to write such code I have always used a MVC model to map physics to display and control.
Creating a model that runs in its own thread (regardless of system speed.) allows the simulation to be easily sped up ,slowed down and paused, as well as giving it the ability to be decoupled from the render speed..
If a simulation (i.e. snooker ball) it would also be advisable to create a full physics object model so it then becomes possible to run in reverse. (e.g. so drag, etc. can be applied in reverse).
48 guest // Aug 30, 2008 at 8:23 am
>>”This code handles both undersampling and oversampling correctly which very is important. ”
not really,
unless somehow you can make your physics calculations in zero amount of time.. but, you seem to know that and call it “spiral of death”
..i’m just saying you should remove word “undersampling” from the same sentence with word “correctly”
but then,
if we only deal with oversampling and, as you suggest, design application for certain fixed time step - that practically means we only deal with cases with extra time or just enough time i.e low-end specs ..and so, why not just sleep() or run empty loop till the right time comes.. say we design app to sync with 60Hz, so we do something like this:
while( dt < 1/60 )
getTimeSinceLastFrame( dt );
// dt= 1/60; <– might as well put this here
..then, continue as normal, as if it was on the low-end spec computer i.e. dt=1/60
in that case,
you dont really need all the interpolation stuff nor the other stuff to fix the problems with former ..simply, there is no need to render more frames than you already designed your app to work on - use that extra time to render additional features for high-end machines on high-detail video setting
49 Glenn Fiedler // Aug 30, 2008 at 9:57 am
yes, what i mean specifically by undersampling and oversampling is this, imagine if you had some time scale factor that you could applied to real delta time, before you fed it into the system described in this article
when i say it handles it correctly, i mean that you can represent everything from super-speed to super-slowmo (of course, super speed will have a higher sim cost due to more sim loops per visible frame), but at least its theoretically correct
i shipped this technique in “freedom force” from irrational games, note that it has that “super-slomo” on the right mouse click - we implemented that using the system described in this article
cheers!
50 abaraba // Aug 30, 2008 at 4:55 pm
>>”..but at least its theoretically correct”
not really,
unless there truly is such thing as ‘correct theory’ that does not work in practice
>>i shipped this technique in “freedom force” from irrational games..”
then it is an example how it does not work - scrolling speed goes from fast at the edges of the map to slow and jerky depending on the scene complexity and number of moving objects
not that it matters much as i see the game scored “Outstanding” 9.3 on IGN, congratulations!
cheers,
http://www.geocities.com/ze_aks/
51 Glenn Fiedler // Aug 30, 2008 at 6:15 pm
i fail to see how the game not making framerate has anything to do with the time stepping algorithm - although perhaps its the lowpass over delta time that shipped in freedom force, which is most certainly theoretically in-correct
as to oversampling / undersampling i believe we are most likely talking about two different things, or you failed to understand the concept in the article properly
i’m not sure which it is yet
cheers
52 Anonymous // Aug 31, 2008 at 7:18 am
ok, let me understand undersampling..
- how did you test undersampling while developing “freedom force”?
- what would be the best way to observe the effects of undersampling in “freedom force”, how to put the game in extreme case scenario where effect is most obvious?
cheers
53 Glenn Fiedler // Aug 31, 2008 at 8:54 am
oversampling is what happen when you go into super-slomo on the right click menu (change the option from pause to super-slomo first)
undersampling is what happens when your display is capable of rendering faster than 60Hz, and you disable vsync (the game runs physics internally at 60Hz…)
cheers
54 Glenn Fiedler // Aug 31, 2008 at 8:56 am
importantly, the “sampling” is the renderer displaying a frame - not the physics running, so it may be the opposite of what you have in your head (i assume that you are thinking that sampling is a physics step)
55 abaraba // Aug 31, 2008 at 5:27 pm
1.) in the article:
>>”Undersampling is where the display framerate is lower that the physics framerate, eg. 50fps when physics runs at 100fps.”
2.) and now this:
>>”undersampling is what happens when your display is capable of rendering faster than 60Hz, and you disable vsync (the game runs physics internally at 60Hz…)”
slower, faster..
which one is it then?
56 Glenn Fiedler // Aug 31, 2008 at 5:29 pm
could be an error there, i’ll have a quick read over the article again and check it in my head
57 Glenn Fiedler // Aug 31, 2008 at 5:32 pm
ok so here is the bit from the article:
“Undersampling is where the display framerate is lower that the physics framerate, eg. 50fps when physics runs at 100fps. Oversampling is where you have an insanely high framerate (or you are viewing physics in slow motion) where one physics frame accumulates over several display updates.”
this appears to be slightly incorrect, or at least poorly written, here is what i meant:
1. undersampling = display framerate is lower than the simulation framerate, eg. render at 10fps, but you are simulating at 50fps
2. oversampling = display framerate is significantly higher than simulation framerate, eg. 200fps when your sim is at 60fps, alternatively in a “super-slomo” mode where you scale time to make simulation time go slower, while keeping the display rate up.
i’ll fix the article up now
58 Glenn Fiedler // Aug 31, 2008 at 5:34 pm
fixed! (i think!)
59 abaraba // Aug 31, 2008 at 9:16 pm
undersampling,
everything i say/said concerns only “undersampling”, as you define it..
anyway,
let’s return to this question then:
- what is the practical case scenario of undersampling you’re trying to account for with your algorithm?
- when do we observe such case and how is it different with undersampling on/off?
..in other words,
- what hardware, driver settings, game setting or whatever else circumstances will lead to occurrence of undersampling in, say “freedom force”?
cheers
60 Glenn Fiedler // Aug 31, 2008 at 10:00 pm
ok you’re kindof missing the point here, the idea is that you can fix the simulation rate to some FPS, and then render at another, at any rate (from below the sim rate, to above it) and it will be smooth
undersampling and oversampling are not specific points or “features” here, its just my way of explaining that the algorithm works in both cases
maybe i should turn this around, what is your actual question here? what exactly are you proposing that is better than this? as far as i can tell you are just advocating for a vsync or framelock type approach to X fps, and of course thats fine, provided that you know what that FPS is — in console platforms thats fine, but on PC it could be 60Hz, 75Hz, 80Hz, 120Hz… etc.
thats the point of this whole trick, you can pick your sim rate, then stick to that, even when the render FPS varies from machine to machine (or even when its non-vsynced, with different render time frame to frame…)
cheers
61 abaraba // Sep 3, 2008 at 5:20 pm
..my message seem to be too long or something, so the rest of it is here: http://www.geocities.com/ze_aks/test/sampleTest.html
float accum= 0.0;
float nowTime= 0.0;
float lastTime= 0.0;
float deltaTime = 0.0;
float simDT, anmDT;
float STEP= 1.0f / 400;
int cnt, fpsTensor= 60;
while( theBeatGoesOn )
{
nowTime= getCurrentTime(RTN_SECONDS);
accum+= deltaTime= nowTime - lastTime;
anmDT= deltaTime - simDT;
simDT/= cnt; lastTime= nowTime; cnt= 0;
while( accum >= STEP )
{
cnt++;
stepSimulation( STEP );
accum-= (simDT >= STEP)? simDT+(STEP*anmDT*fpsTensor) : STEP;
}
simDT= getCurrentTime(RTN_SECONDS) - lastTime;
renderScene();
}
62 Glenn Fiedler // Sep 3, 2008 at 9:14 pm
uh, i’m not trying to delete your messages, it just appeared to me that the first two ones you posted looked quite similar, so i just deleted the first (i thought they were duplicates)
you seem to have some bee in your bonnet? i’m not really sure why… you seem to disagree with this technique or not like something about it, i still can’t understand from your comments or your site exactly what this is, so…
perhaps i should the key points of this technique clear so we are on the same page
the technique described in this article is applicable when:
1. you are render bound, not simulation bound
2. when due to simulation or networking reasons, you wish to step forward with a constant dt (you may never vary this dt)
3. you *also* want to display this at some other rate, not equal to the simulation rate, that may vary or be different from computer to computer (eg. display rate)
if you have #1 and #2, but not #3, then you can use a framelocking or VSYNC approach which is common on consoles. on PCs however #3 comes into play and this technique is a good one, provided you are not simulation bound! so for example, you need to have fast enough simulation code if you want to sim @ 60FPS, and your render rate can drop to 10FPS, that you are able to simulate 6 frames 10X a second, now… thats the same as rendering 1 frame every 60th of a second, 6 times in a row, so you see… this actually is quite feasible
NOW, your main beef with this technique seems to be that you are simulation bound and you are concerned about spiral of death. sure! this is true, and you should be aware of this, but remember this technique is designed for cases where you are not simulation bound. if it takes longer than 1/60th of a second for you to simulate 1/60th of the second in real time, then no technique is going to save you - you must either slow down, skip frames or reduce simulation quality. these are all out of scope with this article
regarding oversampling and undersampling, these points in the article only refer to one thing - the interpolation between two simulation states to get a smooth render state that avoids temporal aliasing, i’m not talking about having to do too many simulation samples per frame causing spiral of death, since this article assumes you are not simulation bound and would not encounter that case
63 Glenn Fiedler // Sep 3, 2008 at 10:06 pm
importantly please note that the technique you present violates #2, since you integrate at the end of the step to remove the extra bit of time remaining after stepping n times dt
this entire article is predicated on the fact that a truly fixed simulation dt from frame to frame is desirable, thats why its called “Fix your Timestep”, literally meaning fix your timestep to a constant dt. in many cases, this can be important for general reliability of game code, for determism and for networking of your simulation code
but, if your game does not require fixed dt, then by all means the technique you are using is quite fine, its also *much* easier to implement because there no need to interpolate between two render states and so on
cheers
64 Anonymous // Sep 4, 2008 at 2:51 am
we agree,
i dont really say anything is “wrong”, its a bit like this:
a = b / c;
so i say,
it maybe fine to assume c is never zero, but would it not be better if we, just in case, handle that somehow, just like we are supposed to do with all other exceptions and “errors”
i didnt meant to criticize algorithm,
dont see any other way to do it, i only ask if we maybe ignore too much by not taking simulation cost into account, even if for only to soften couple of glitches when CPU does get overloaded
>>”..since you clearly do not value having a truly fixed dt from frame to frame”
my algorithm is identical to yours, but only with addition that it handles the case where - simulation cost is near or greater than rendering cost - it handles it “more softly” without “spiraling to death”
sorry for the bee,
its very long story that funny enough does not have anything to do with you, i take back everything that i said through the wrong hole.. can i do that?
regardless of everything,
id really like to know how much time in a modern game, say “Mercenaries 2″ is spent doing physics and how much on rendering and everything else? and how does it compare on PS2 vs PS3 vs Xbox vs low-end PC?
cheers
65 Glenn Fiedler // Sep 4, 2008 at 8:02 am
your technique is not identical to mine, from your source code you appear to not be interpolating between two render states, instead you are integrating the remaining dt in the accumulator at the end of the frame - this violates the desired constraint of this article, that you are always stepping forward with a fixed dt
as to what mercs2 does, it is very CPU intensive and has a wide range of simulation loads, so it does not use the technique from this article. it either framelocks to 30fps, or simulates at native render rate with variable dt when it has to tear
66 Anonymous // Sep 4, 2008 at 11:08 am
>>”your technique is not identical to mine.. this violates the desired constraint of this article, that you are always stepping forward with a fixed dt”
i do step every time in fixed STEP of 1/400
stepSimulation( STEP );
variable STEP, that you call dt, never changes in the code
could be as well like this
stepSimulation( 1.0f/400 );
so, if you change :
accum-= (simDT >= STEP)? simDT+(STEP*anmDT*fpsTensor) : STEP;
to
accum-= STEP;
..you get your algorithm, identical.. with few more variables and one more time read
thanks for the info,
i would have no idea how to go about figuring that one out!
cheers
67 Glenn Fiedler // Sep 4, 2008 at 11:30 am
its not the same algorithm because of this line:
accum-= (simDT >= STEP)? simDT+(STEP*anmDT*fpsTensor) : STEP;
plus i don’t see where you are interpolating render state between two sim states - are you doing that? do you understand why we need to do that?
do you understand what temporal aliasing is and why we need to do the interpolation?
cheers
68 Glenn Fiedler // Sep 4, 2008 at 11:32 am
ok perhaps i should mention another constraint, relevant only to networking - it is desirable that time steps forward in chunks related to real time, its not acceptable for the game to “slow down” you appear to be using this to compensate for low framerate, but you must understand that in a network game this is highly undesirable - you need the deltaTime interpreted as the same amount of sim time to step forward on both computers
69 Glenn Fiedler // Sep 4, 2008 at 11:37 am
so i first mentioned the properties of this technique here:
1. you are render bound, not simulation bound
2. when due to simulation or networking reasons, you wish to step forward with a constant dt (you may never vary this dt)
3. you *also* want to display this at some other rate, not equal to the simulation rate, that may vary or be different from computer to computer (eg. display rate)
lets add another one:
4. it is important for simulation delta time to match the real delta time coming in from the timer
#4 is important for networked games, because you cannot just have the client and server making different decisions about how to simulate a given deltaTime, the game will get out of sync
its also very design dependent whether or not it is appropriate to slow the game down if it is in fact becoming simulation bound (such that simulation of t seconds takes longer than t seconds to compute)
the conclusion here is that when you write a game that has to run at X fps, it is your responsibility to ensure that your physics simulation takes < 1/X seconds to calculate
this is well accepted in the game industry, and basically “common sense” for game programmers
although perhaps i will add a section describing the pros and cons of the technique, and the base assumption of not being simulation bound
cheers
70 Anonymous // Sep 4, 2008 at 6:47 pm
>>”plus i don’t see where you are interpolating render state between two sim states - are you doing that? do you understand why we need to do that?”
>>”do you understand what temporal aliasing is and why we need to do the interpolation?”
no, im not doing that,
- i understand interpolation is some kind of “final touch” thing and not required for code to -
>> “handles both undersampling and oversampling correctly which very is important. ”
so i do not see of what relevance is that in regard to the problem of undersampling and “spiraling to death”?
actually more i look at it - it more feels “out of the place”… what is “State”, in what units is it, if i use Physics library like Havok, PhysX or Bullet what does “State” correspond to?
cheers
71 Glenn Fiedler // Sep 5, 2008 at 8:41 am
you keep missing the point here, when i discuss over and undersampling in this article - i am talking only about THE INTERPOLATION, you are talking about spiral of death, and I disagree because in this case the game is not simulation bound and that cannot happen
end of discussion!
Leave a Comment