# How does interpolation actually work to smooth out an object's movement?

I've asked a few similar questions over the past 8 months or so with no real joy, so I am going make the question more general.

I have an Android game which is OpenGL ES 2.0. within it I have the following Game Loop:

My loop works on a fixed time step principle (dt = 1 / ticksPerSecond)

loops=0;

while(System.currentTimeMillis() > nextGameTick && loops < maxFrameskip){

updateLogic(dt);
nextGameTick+=skipTicks;
timeCorrection += (1000d/ticksPerSecond) % 1;
nextGameTick+=timeCorrection;
timeCorrection %=1;
loops++;

}

render();


My intergration works like this:

sprite.posX+=sprite.xVel*dt;
sprite.posXDrawAt=sprite.posX*width;


Now, everything works pretty much as I would like. I can specify that I would like an object to move across a certain distance (screen width say) in 2.5 seconds and it will do just that. Also because of the frame skipping that I allow in my game loop, I can do this on pretty much any device and it will always take 2.5 seconds.

Problem

However, the problem is that when a render frame skips, the graphic stutter. It's extremely annoying. If I remove the ability to skip frames, then everything is smooth as you like, but will run at different speeds on different devices. So it's not an option.

I'm still not sure why the frame skips, but I would like to point out that this is Nothing to do with poor performance, I've taken the code right back to 1 tiny sprite and no logic (apart from the logic required to move the sprite) and I still get skipped frames. And this is on a Google Nexus 10 tablet (and as mentioned above, I need frame skipping to keep the speed consistent across devices anyway).

So, the only other option I have is to use interpolation (or extrapolation), I've read every article there is out there but none have really helped me to understand how it works and all of my attempted implementations have failed.

Using one method I was able to get things moving smoothly but it was unworkable because it messed up my collision. I can foresee the same issue with any similar method because the interpolation is passed to (and acted upon within) the rendering method - at render time. So if Collision corrects position (character now standing right next to wall), then the renderer can alter it's position and draw it in the wall.

So I'm really confused. People have said that you should never alter an object's position from within the rendering method, but all of the examples online show this.

So I'm asking for a push in the right direction, please do not link to the popular game loop articles (deWitters, Fix your timestep, etc) as I've read these multiple times. I'm not asking anyone to write my code for me. Just explain please in simple terms how Interpolation actually works with some examples. I will then go and try to integrate any ideas into my code and will ask more specific questions if need-be further down the line. (I'm sure this is a problem many people struggle with).

edit

Some additional information - variables used in game loop.

private long nextGameTick = System.currentTimeMillis();
//loop counter
private int loops;
//Amount of frames that we will allow app to skip before logic is affected
private final int maxFrameskip = 5;
final int ticksPerSecond = 60;
//Amount of time each update should take
private final int skipTicks = (1000 / ticksPerSecond);
float dt = 1f/ticksPerSecond;
private double timeCorrection;

• And the reason for the downvote is...................? – BungleBonce Aug 21 '14 at 19:09
• Impossible to say sometimes. This looks to have everything a good question should have when trying to solve a problem. Concise code snippet, explanations of what you've tried, research attempts, and clearly explaining what your problem is and what you need to know. – Jesse Dorsey Aug 21 '14 at 19:28
• I wasn't your downvote, but please clarify one part. You say the graphics stutter when a frame is skipped. That seems like an obvious statement (a frame is missed, it looks like a frame is missed). So can you better explain the skipping? Does something weirder happen? If not, this might be an unsolvable problem, because you can't get smooth motion if the framerate dips. – Seth Battin Aug 21 '14 at 19:29
• Thanks, Noctrine, it just really irks me when people downvote without leaving an explanation. @SethBattin, sorry, yes of course, you are right, the frame skipping is causing the jerkiness, however, interpolation of some sort should sort this out, like I say above, I've had some (but limited) success. If I'm wrong, then I guess the question would be, how can I get it running smoothly at the same speed across various devices? – BungleBonce Aug 21 '14 at 19:33
• Carefully reread those documents. They don't actually modify the location of the object in the rendering method. They only modify the apparent location of the method based off of its last position and its current position based on how much time has passed. – AttackingHobo Aug 21 '14 at 19:34

There are two things crucial to get motion appearing smooth, the first is obviously that what you render needs to match the expected state at the time at which the frame is presented to the user, the second is that you need to present frames to the user at a relatively fixed interval. Presenting a frame at T+10ms, then another at T+30ms, then another at T+40ms, will appear to the user to be juddering, even if what is actually shown for those times is correct according to the simulation.

Your main loop seems to lack any gating mechanism to make sure that you only render at regular intervals. So sometimes you might do 3 updates between renders, sometimes you might do 4. Basically your loop will render as often as possible, as soon as you've simulated enough time to push the simulation state in front of the current time, you'll then render that state. But any variability in how long it takes to update or render, and the interval between frames will vary as well. You've got a fixed timestep for your simulation, but a variable timestep for your rendering.

What you probably need is a wait just before your render, that ensures that you only ever start rendering at the start of a render interval. Ideally that should be adaptive: if you've taken too long to update / render and the start of the interval has already passed, you should render immediately, but also increase the interval length, until you can consistently render and update and still get to the next render before the interval has finished. If you have plenty of time to spare, then you can slowly reduce the interval (i.e. increase the frame rate) to render faster again.

But, and here's the kicker, if you don't render the frame immediately after detecting that the simulation state has been updated to "now", then you introduce temporal aliasing. The frame being presented to the user is being presented at slightly the wrong time, and that in itself will feel like a stutter.

This is the reason for the "partial timestep" you'll see mentioned in the articles you've read. It's in there for a good reason, and that's because unless you fix your physics timestep to some fixed integral multiple of your fixed rendering timestep, you simply cannot present the frames at the right time. You end up either presenting them too early, or too late. The only way to get a fixed rendering rate and still present something that's physically correct, is to accept that at the time the rendering interval comes around, you will most likely be mid-way between two of your fixed physics timesteps. But that doesn't mean that the objects are modified during rendering, just that the rendering has to temporarily establish where the objects are so that it can render them somewhere in between where they were before and where they are after the update. That's important - never change the world state for rendering, only updates should change the world state.

So to put it into a pseudocode loop, I think you need something more like:

InitialiseWorldState();

previousTime = currentTime = 0.0;
renderInterval = 1.0 / 60.0; //A nice high starting interval

subFrameProportion = 1.0; //100% currentFrame, 0% previousFrame

while (true)
{
frameStart = ActualTime();

//Render the world state as if it was some proportion
// between previousTime and currentTime
// E.g. if subFrameProportion is 0.5, previousTime is 0.1 and
// currentTime is 0.2, then we actually want to render the state
// as it would be at time 0.15. We'd do that by interpolating
// between movingObject.previousPosition and movingObject.currentPosition
// with a lerp parameter of 0.5
Render(subFrameProportion);

//Check we've not taken too long and missed our render interval
frameTime = ActualTime() - frameStart;
if (frameTime > renderInterval)
{
renderInterval = frameTime * 1.2f; //Give us a more reasonable render interval that we actually have a chance of hitting
}

expectedFrameEnd = frameStart + renderInterval;

//Loop until it's time to render the next frame
while (ActualTime() < expectedFrameEnd)
{
//step the simulation forward until it has moved just beyond the frame end
if (previousTime < expectedFrameEnd) &&
currentTime >= expectedFrameEnd)
{
previousTime = currentTime;

Update();
currentTime += fixedTimeStep;

//After the update, all objects will be in the position they should be for
// currentTime, **but** they also need to remember where they were before,
// so that the rendering can draw them somewhere between previousTime and
//  currentTime

//Check again we've not taken too long and missed our render interval
frameTime = ActualTime() - frameStart;
if (frameTime > renderInterval)
{
renderInterval = frameTime * 1.2f; //Give us a more reasonable render interval that we actually have a chance of hitting
expectedFrameEnd = frameStart + renderInterval
}
}
else
{
//We've brought the simulation to just after the next time
// we expect to render, so we just want to wait.
// Ideally sleep or spin in a tight loop while waiting.
timeTillFrameEnd = expectedFrameEnd - ActualTime();
sleep(timeTillFrameEnd);
}
}

//How far between update timesteps (i.e. previousTime and currentTime)
// will we be at the end of the frame when we start the next render?
subFrameProportion = (expectedFrameEnd - previousTime) / (currentTime - previousTime);
}


For this to work all objects being updated need to preserve the knowledge of where they were before and where they are now, so that the rendering can use it's knowledge of where the object is.

class MovingObject
{
Vector velocity;
Vector previousPosition;
Vector currentPosition;

Initialise(startPosition, startVelocity)
{
currentPosition = startPosition; // position at time 0
velocity = startVelocity;
//ignore previousPosition because we should never render before time 0
}

Update()
{
previousPosition = currentPosition;
currentPosition += velocity * fixedTimeStep;
}

Render(subFrameProportion)
{
Vector actualPosition =
Lerp(previousPosition, currentPosition, subFrameProportion);
RenderAt(actualPosition);
}
}


And let's lay out a timeline in milliseconds, saying rendering takes 3ms to complete, updating takes 1ms, your update time-step is fixed to 5ms, and your render timestep starts (and remains) at 16ms [60Hz].

0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33
R0          U5  U10 U15 U20 W16                                 R16         U25 U30 U35 W32                                 R32

1. First we initialise at time 0 (so currentTime = 0)
2. We render with a proportion of 1.0 (100% currentTime), which will draw the world at time 0
3. When that finishes, actual time is 3, and we don't expect the frame to end till 16, so we need to run some updates
4. T+3: We update from 0 to 5 (so afterwards currentTime = 5, previousTime = 0)
5. T+4: still before the frame end, so we update from 5 to 10
6. T+5: still before the frame end, so we update from 10 to 15
7. T+6: still before the frame end, so we update from 15 to 20
8. T+7: still before the frame end, but currentTime is just beyond the frame end. We don't want to simulate any further because to do so would push us beyond the time we next want to render. Instead we wait quietly for the next render interval (16)
9. T+16:It's time to render again. previousTime is 15, currentTime is 20. So if we want to render at T+16, we are 1ms of the way through the 5ms long timestep. So we are 20% of the way through the frame (proportion = 0.2). When we render, we draw objects 20% of the way between their previous position and their current position.
10. Loop back to 3. and continue indefinitely.

There's another nuance here about simulating too far ahead of time, meaning the user's inputs might be ignored even though they happened before the frame was actually rendered, but don't worry about that until you're confident that the loop is simulating smoothly.

• NB: the pseudocode is weak in two ways. Firstly it doesn't catch the death-spiral case (it takes longer than fixedTimeStep to Update, meaning the simulation falls ever further behind, effectively an infinite loop), secondly the renderInterval never gets shortened again. In practice you want to increase the renderInterval immediately, but then over time shorten it gradually as best you can to within some tolerance of the actual frame time. Otherwise one bad/long update will saddle you with a low framerate forever. – MrCranky Sep 1 '14 at 21:19
• Thanks for this @MrCranky, indeed, I've been struggling for ages on how to 'limit' rendering in my loop! Just couldn't work out how to do it and wondered if that might be one of the issues. I'll have a proper read through this and give your suggestions a try, will report back! Thanks again :-) – BungleBonce Sep 3 '14 at 0:59
• Thanks @MrCranky, OK, I've read & re-read your answer but I can't understand it :-( I tried to implement it but it just gave me a blank screen. Really struggling with this. previousFrame and currentFrame I assume relates to the previous and current positions of my moving objects? Also, what about the line "currentFrame = Update();" - I don't get this line, does this mean call update(); as I can't see where else I'm calling update? Or does it just mean to set currentFrame (position) to it's new value? Thanks again for your help!! – BungleBonce Sep 5 '14 at 16:34
• Yes, effectively. The reason why I put in previousFrame and currentFrame as return values from Update and InitialiseWorldState is because to allow for the rendering to draw the world as it is part-way between two fixed update steps, you need to have not only the current position of every object you want to draw, but also their previous positions. You could have each object save both values internally, which gets unwieldy. – MrCranky Sep 8 '14 at 8:11
• But it's also possible (but much harder) to architect things so that all the state information needed to represent the current state of the world at time T is held under a single object. Conceptually that's much cleaner when explaining what information is around in the system as you can treat the frame state as something produced by an update step, and keeping the previous frame around is just about retaining one more of those frame state objects. However I might rewrite the answer to be a bit more like you'd actually probably implement it. – MrCranky Sep 8 '14 at 8:15

What everyone has been telling you is correct. Never update your sprite's simulation position in your render logic.

Think of it like this, your sprite has 2 positions; where the simulation says he is as of the last simulation update, and where the sprite is rendered. They are two completely different coordinates.

The sprite is rendered at his extrapolated position. The extrapolated position is calculated each render frame, used to render the sprite, then thrown away. That's all there is to it.

Other than that, you seem to have a good understanding. Hope this helps.

• Excellent @WilliamMorrison - thanks for confirming this, I was never really 100% sure that this was the case, I now think I'm on my way to getting this working to some degree - cheers! – BungleBonce Sep 6 '14 at 16:48
• Just curious @WilliamMorrison, using these throw-away coordinates, how would one mitigate the problem of sprites being draw 'embedded in' or 'just above' other objects - the obvious example, being solid objects in a 2d game. Would you have to run your collision code at render time also? – BungleBonce Sep 11 '14 at 1:09
• In my games yes, that's what I do. Please be better than me, dont do that, it is not the best solution. It complicates render code with logic it shouldnt be using, and will waste cpu on redundant collision detection. Itd be better to interpolate between the second to last position and the current position. This solves the problem as you're not extrapolating to a bad position, but does complicate things as you are rendering one step behind the simulation. Id love to hear your opinion, which approach you take, and your experiences. – William Morrison Sep 11 '14 at 3:46
• Yeah it's a tricky problem to resolve. I have asked a separate question regarding this here gamedev.stackexchange.com/questions/83230/… if you want to keep an eye on it or contribute something. Now, what you suggested in your comment, am I not doing this already? (Interpolating between previous and current frame)? – BungleBonce Sep 11 '14 at 12:37
• Not quite. You're actually extrapolating right now. You take the most current data from simulation, and extrapolate what that data looks like after fractional timesteps. I'm suggesting you interpolate between the last simulation position, and the current simulation position by fractional timesteps for rendering instead. Rendering will be behind the simulation by 1 timestep. This ensures you'll never render an object in a state the simulation didn't validate (ie. A projectile won't appear in a wall unless the simulation fails.) – William Morrison Sep 12 '14 at 2:01