Sign in to follow this  

Fixed Timestepping Interpolation

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

Hello,

I've implemented a timestepping loop much like Gaffers fixed version. But I think my interpolation code is incorrect. I'm at my wits end here, I've debugged and followed log output and I can't find what's wrong. It's very frustrating.

At 2500 fps, everything is silk smooth. At 60 fps, it's noticable jittery. It doesn't matter if I enable VSYNC or not either. At 20 fps it's almost unplayable. I've tested on several different machines and all look the same.

Timestepping looks OK from the logs, with the same time being applied every tick and the occasional remainder accumulator tick. I've tried with TimeGetTime () and GetTickCount (). I haven't tried the performance counter yet.

This is what I've done:


// Init of values
float tickDuration = 100;
float tickSec = tickDuration / 1000.0f;
float accumulator = tickDuration;
int time = getTime ();
int lastTickTime = time;

// This is the actual main loop.
while (true)
{
time = getTime ();
int elapsedTime = time - lastTickTime;
accumulator += elapsedTime;

while (accumulator >= tickDuration)
{
// Tick logic is done here, calculating physics and movement etc.
accumulator -= tickDuration;
}

lastTickTime = time;
float alpha = (float)accumulator / (float)tickDuration;

// Interpolation is done here.
}





I use alpha as the interpolation factor. Is this correct? I expect it to be 0 at the start of each tick, and 1 at the end. I then use it to interpolate between oldPos and newPos on objects.

If anyone can spot any obvious errors in there I would be most grateful.

[Edited by - SymLinked on December 31, 2010 1:19:17 AM]

Share this post


Link to post
Share on other sites
Code looks okay from a quick look. What I would say is that timeGetTime() is not at all accurate unless you call timeBeginPeriod(1) at the start of the program. You need to call timeEndPeriod(1) before the program closes.

QueryPerformanceCounter() is more accurate still, and I believe the multi-core issues have been solved.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aardvajk
Code looks okay from a quick look. What I would say is that timeGetTime() is not at all accurate unless you call timeBeginPeriod(1) at the start of the program. You need to call timeEndPeriod(1) before the program closes.

QueryPerformanceCounter() is more accurate still, and I believe the multi-core issues have been solved.


Thanks for taking a look Aardvajk, I appreciate it.

I do call timeStartPeriod(1), so it's definatly not that. I'll try QPC and see if that helps. I do remember it didn't work so well on battery-running laptops though, because of the CPU throttling being done.. but it's worth a shot.

Share this post


Link to post
Share on other sites
getTime returns 100ths of a second, so your guaranteed granularity is 10 ms from the get-go. That means the maximum theoretical framerate you'll get with that code is 100 FPS, no matter what.

Meanwhile, your while(true) loop is running tens or hundreds of thousands of times a second, only occasionally doing anything useful (when the timer jumps by 1 every 1/100th of a second). That's a lot of wasted 100% busy CPU time...

Also, you snipped a part of the code, so I don't know if this is applicable, but if you interpolate, the remainder accumulator should be reset to 0 at the end, because that time has been "accounted for" -- otherwise, you'll be accounting for a progressively bigger remainder every frame, until the remainder becomes bigger than the duration of one frame, in which case 2 frames will be processed at the same time -- this will inevitably be jittery and cause inaccurate results.

Share this post


Link to post
Share on other sites
Quote:
Original post by kiwibonga
If you interpolate, the remainder accumulator should be reset to 0 at the end, because that time has been "accounted for" -- otherwise, you'll be accounting for a progressively bigger remainder every frame


I don't think that is correct. The whole point of having an accumulator that you constantly subtract from is to carry the error across from one frame to the next.

Share this post


Link to post
Share on other sites
This is probably an issue in your interpolation code. You may be interpolating in the wrong direction (from new to old) or swapped the 2 variables which makes the interpolation be outside these values. Have you tried with a constant moving object and a 1000ms timestep? You'll immediately see if you have interpolation issues.

Share this post


Link to post
Share on other sites
Quote:
Original post by Tiblanc
This is probably an issue in your interpolation code. You may be interpolating in the wrong direction (from new to old) or swapped the 2 variables which makes the interpolation be outside these values. Have you tried with a constant moving object and a 1000ms timestep? You'll immediately see if you have interpolation issues.


Well, of course. I've tried all sorts of different combinations including constant movement and larger timesteps. And it's not interpolating in the wrong direction, that would be worse than jittery obviously.

I've isolated the problem though. It's either timing precision, or the actual render that is rendering at a fluctuating FPS (between 47 and 60 with VSYNC, actually). I'm profiling to see where it might be spending so much time, because it's not waiting for the GPU - that's for sure.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aardvajk
Quote:
Original post by kiwibonga
If you interpolate, the remainder accumulator should be reset to 0 at the end, because that time has been "accounted for" -- otherwise, you'll be accounting for a progressively bigger remainder every frame


I don't think that is correct. The whole point of having an accumulator that you constantly subtract from is to carry the error across from one frame to the next.


No, this is not a fixed framerate application, so the accumulator needs to be "used up" in the interpolation step.

The accumulator in his code will always be between 0 and 99 hundredths of a second after the inner while loop has run. If he kept the accumulator from one run of the loop to the next, he would get just 1 FPS.

In the inner loop (which only runs when accumulator is > 1 second, and which almost never should happen unless there's a huge unexpected delay), he does calculations like this:

Actor.x += Actor.speed_x; // where speed_x is in units/second

In the interpolation code, he's supposed to do this:

Actor.x += Actor.speed_x * alpha; // i.e. speed multiplied by the portion of a second remaining in the accumulator -- his delta t

Having the no-interpolation inner loop saves you the trouble of doing multiplications when there's a delay that causes the program to be several frames behind.

If he's not doing "accumulator = 0" or updating elapsedTime at the end of the interpolation step, his framerate is going to be highly variable, and movement will be very odd...

Share this post


Link to post
Share on other sites
Quote:
Original post by kiwibonga
Quote:
Original post by Aardvajk
Quote:
Original post by kiwibonga
If you interpolate, the remainder accumulator should be reset to 0 at the end, because that time has been "accounted for" -- otherwise, you'll be accounting for a progressively bigger remainder every frame


I don't think that is correct. The whole point of having an accumulator that you constantly subtract from is to carry the error across from one frame to the next.


No, this is not a fixed framerate application, so the accumulator needs to be "used up" in the interpolation step.

The accumulator in his code will always be between 0 and 99 hundredths of a second after the inner while loop has run. If he kept the accumulator from one run of the loop to the next, he would get just 1 FPS.

Not at all: the accumulator is the variable that counts elapsed time, resetting it to 0 for any reason would freeze the game.

The outer loop runs as many times as it pleases (too many times, as already noted: it should be capped to the display refresh rate) and every time accumulator increases a little. Whenever accumulator increases to 100 or more, the simulation advances; every time the loop runs, the interpolation result (past the latest simulation state) is shown and the small or large increase of accumulator provides a reasonable animation.

For example, an object moves at a constant velocity of 17 units per tick, starting from position 0 at absolute time 0: the outer loop runs first for time 0 with accumulator==tickDuration, the simulation update computes two positions (old==0, new==17) and reduces accumulator to 0.
In the first few frames while time < tickDuration the position is interpolated between 0 (exactly, on the first frame) and almost 17 by accumulator increasing from 0 to slightly less than tickDuration.
Sooner or later accumulator >= tickDuration: another simulation update takes place (old position==17, new position==34) and interpolation shows a position slightly past 17.

Maybe you are confused by the OP's code snippet lacking explicit variables for positions (simulated old, simulated new and interpolated) and velocities, and explicit display and waiting calls at the end (using the interpolated positions).
Quote:

If he's not doing "accumulator = 0" or updating elapsedTime at the end of the interpolation step, his framerate is going to be highly variable, and movement will be very odd...

Framerate (determined by the outer "while true" loop) is arbitrary; but simulation timestep (accumulator-=tickDuration) is fixed, which is the whole point.
The only jitter source is inaccurate time measurement, which we cannot do much about, and the only way to improve animation smoothness is exact motion blur.

Share this post


Link to post
Share on other sites
Quote:
Original post by SymLinked
I've isolated the problem though. It's either timing precision, or the actual render that is rendering at a fluctuating FPS (between 47 and 60 with VSYNC, actually). I'm profiling to see where it might be spending so much time, because it's not waiting for the GPU - that's for sure.


Are you already logging all cases of the inner update loop running more than once per screen refresh (jerky large updates due to rendering and/or previous simulation updates taking too long), and making graphs of interpolated positions vs time for objects that move at a constant speed?

Share this post


Link to post
Share on other sites
Quote:
Original post by LorenzoGatti
Maybe you are confused by the OP's code snippet lacking explicit variables for positions (simulated old, simulated new and interpolated) and velocities, and explicit display and waiting calls at the end (using the interpolated positions).


Thanks, I realize my mistake now; I assumed too much about code I couldn't see. Makes perfect sense now.

SymLinked, how do you set your FPS (2500, 60, 20)? Do you just change the TickDuration?

Share this post


Link to post
Share on other sites
Quote:
Original post by LorenzoGatti
Quote:
Original post by SymLinked
I've isolated the problem though. It's either timing precision, or the actual render that is rendering at a fluctuating FPS (between 47 and 60 with VSYNC, actually). I'm profiling to see where it might be spending so much time, because it's not waiting for the GPU - that's for sure.


Are you already logging all cases of the inner update loop running more than once per screen refresh (jerky large updates due to rendering and/or previous simulation updates taking too long), and making graphs of interpolated positions vs time for objects that move at a constant speed?


I do, and the jitter in elapsedTime is every 500 ms or so, while the (running the tick loop more than once) scenario doesn't happen all that often. So it must be something else.

What I didn't do was to look at the data and see if it changes depending on if the renderer is running or not. That might be it.

Share this post


Link to post
Share on other sites

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