# Interpolation using a sprite's previous frame and current frame

Overview

I'm currently using a method which has been pointed out to me is extrapolation rather than interolation. As a result, I'm also now looking into the possibility of using another method which is based on a sprite's position at it's last (rendered) frame and it's current one.

Assuming an interpolation value of 0.5 this is, (visually), how I understand it should affect my sprite's position....

This is how I'm obtaining an inerpolation value:

public void onDrawFrame(GL10 gl) {
// Set/re-set loop back to 0 to start counting again
loops=0;

while(System.currentTimeMillis() > nextGameTick && loops < maxFrameskip) {
SceneManager.getInstance().getCurrentScene().updateLogic();
nextGameTick += skipTicks;
timeCorrection += (1000d / ticksPerSecond) % 1;
nextGameTick += timeCorrection;
timeCorrection %= 1;
loops++;
tics++;
}

interpolation = (float)(System.currentTimeMillis() + skipTicks - nextGameTick) / (float)skipTicks;
render(interpolation);
}


I am then applying it like so (in my rendering call):

render(float interpolation) {
spriteScreenX = (spriteScreenX - spritePreviousX) * interpolation + spritePreviousX;
spritePreviousX = spriteScreenX; // update and store this for next time
}


Results

This unfortunately does nothing to smooth the movement of my sprite. It's pretty much the same as without the interpolation code. I can't get my head around how this is supposed to work and I honestly can't find any decent resources which explain this in any detail.

My understanding of extrapolation is that when we arrive at the rendering call, we calculate the time between the last update call and the render call, and then adjust the sprite's position to reflect this time (moving the sprite forward) - And yet, this (Interpolation) is moving the sprite back, so how can this produce smooth results?

Any advise on this would be very much appreciated.

Edit

I've implemented the code from OriginalDaemon's answer like so:

@Override
public void onDrawFrame(GL10 gl) {

newTime = System.currentTimeMillis()*0.001;
frameTime = newTime - currentTime;
if ( frameTime > (dt*25))
frameTime = (dt*25);
currentTime = newTime;

accumulator += frameTime;

while ( accumulator >= dt )
{
SceneManager.getInstance().getCurrentScene().updateLogic();
previousState = currentState;
t += dt;
accumulator -= dt;

}

interpolation = (float) (accumulator / dt);

render();
}


Interpolation values are now being produced between 0 and 1 as expected (similar to how they were in my original loop) - however, the results are the same as my original loop (my original loop allowed frames to skip if they took too long to draw which I think this loop is also doing).

I appear to have made a mistake in my previous logging, it is logging as I would expect it to (interpolated position does appear to be inbetween the previous and current positions) - however, the sprites are most definitely choppy when the render() skipping happens.

Edit

I was saving my object's old position during rendering when it should have been saved during logic updating like so:

 render(float interpolation) {
drawSpriteAtX = (spriteScreenX - spritePreviousX) * interpolation + spritePreviousX;
drawSprite(drawSpriteAtX , spriteScreenY);
}

updateLogic(){

spritePreviousX = spriteScreenX; // update and store this for next time
moveSprite();

}


• What language/platform are you using? If it's Flash or JS, there are reasons -- and workarounds -- for timing inconsistencies like this one. Always tag your questions with language/platform, unless purely abstract or design-focused. It may well be that you don't need to do any extrapolation. – Engineer May 22 '14 at 19:09
• Oops - sorry, I usually do but forgot, it's Java (for Android) - I've amended the tags now - thanks! – BungleBonce May 22 '14 at 19:29
• Thanks @LennartRolland no problem, yeah this is for Android devices, unfortunately, I've already read that article many times! I'm now thinking of completely changing my game loop anyway because there seems to be so little good information on interpolation out there (that I can find), plus my current loop caps updates, but renders flat out causing the device to heat up and eating into battery life. I'll see if someone can come up with an answer for this (interpolation) question and in the mean time will post another question that relates to Android Game-loops. Thanks anyway :-) – BungleBonce May 22 '14 at 22:40
• Actually I have used the advice from that article in my android code. I will try to explain what I did in a new answer! – Lennart Rolland May 22 '14 at 22:44

Here is an excellent article on the subject.

The final implementation of the game loop here is very clean and clear;

double t = 0.0;
double dt = 0.01;

double currentTime = hires_time_in_seconds();
double accumulator = 0.0;

State previous;
State current;

while ( !quit )
{
double newTime = time();
double frameTime = newTime - currentTime;
if ( frameTime > 0.25 )
frameTime = 0.25;
currentTime = newTime;

accumulator += frameTime;

while ( accumulator >= dt )
{
previousState = currentState;
integrate( currentState, t, dt );
t += dt;
accumulator -= dt;
}

const double alpha = accumulator / dt;

State state = currentState * alpha +
previousState * ( 1.0 - alpha );

render( state );
}


What you have is a flow that is rendering as fast as possible, but always updating in 0.01s windows (which makes it update at 100 fps). If you wanted the while() loop could be augmented to have a loop count so it updates a maximum of n times before drawing but I'd recommend against this.

The most important thing for you here is the "State state = ..." as this is essentially showing how to do the interpolation. Any code to interpolate between the state at the previous frame and the current state should in some way resemble this. For example, if interpolating the x position of the sprite then you use;

interpolatedX = currX * alpha + prevX * (1.0 - alpha);


If you want you could pass the alpha value through to the render routine so you can perform these interpolations just before rendering.

Keep in mind the alpha value will always be between 0 and 1 as accumulator will be reduced to a value smaller than dt by the above loop. So if you clamp the loop to a maximum number of iterations, don't forget to adjust the alpha value accordingly. I would advise against clamping it though.

## Edit

Had a crack at editing the code in the question. I prefer to do things in seconds so velocities can be expressed as m/s etc. Change the doubles to floats or fixed point if you think it's necessary, but for now I've made it all doubles for simplicity. So I think this should work for you;

double t = 0.0;
double dt = 1 / 60;
double currentTime = System.currentTimeMillis() * 0.001;
double accumulator = 0.0;
double newTime;
double frameTime;

@Override
public void onDrawFrame(GL10 gl) {

newTime = System.currentTimeMillis() * 0.001;
frameTime = newTime - currentTime;

if ( frameTime > (dt * 25) ) // allow a maximum of 25 updates before drawing
frameTime = dt * 25;

currentTime = newTime;

accumulator += frameTime;

while ( accumulator >= dt )
{
previousState = currentState; //Do this is the level classes
SceneManager.getInstance().getCurrentScene().updateLogic(dt);
t += dt;
accumulator -= dt;
}

double interpolation = accumulator / dt;

Log.v("NewTag","Interpolation amount: "+interpolation); //Always 0
Log.v("NewTag","Accumulator amount: "+accumulator);  //Always 0

state = X * interpolation + previousX * (1.0 - interpolation);

render(state);

• Thanks again @OriginalDaemon, just implemented it, it's not rendering anything and is stuck in the while loop, so I'm gonna have a look and see if I can work out what's going wrong! Will report back...... thanks for your help! – BungleBonce May 23 '14 at 16:11
• double check the value of dt. Might need to change the dt = 1 / 60 to 1.0 / 60.0. – OriginalDaemon May 23 '14 at 16:20
• Thanks for your efforts @OriginalDaemon, I finally have the loop working, I seem to be able to control the ticks per second and the interpolation value is indeed now between 0 and 1. However, when applied, the interpolation doesn't seem to make much difference (there is a very slight improvement in the jerkiness but not much of one) with dt*25, 25 is, I assume the amount of frames that can be skipped? (Similar to my maxFramesSkip in my original loop), if have confirmed that the choppiness occurs when frames are skipped. Again, thanks for you help. Much appreciated. – BungleBonce May 23 '14 at 19:40
• 25 is the maximum number of updates that can be added to the update backlog on each call. Since the render calls aren't set to any specific frame rate (unless you call the method at a specific rate) it can't really be expressed as a number of frames to skip. I only used 25 because the original code was doing that, you can adjust to suit your animation. – OriginalDaemon May 23 '14 at 21:34
• Hi @OriginalDaemon, I probably had a mistake in my logging, just re-logged (see edit) and as you can see the position I draw at is indeed in-between the old and current positions. Buy yeah, it definitely goes choppy when the rendering 'skips' and the effect is very noticeable. The other method I was using (extrapolation) keeps things butter-smooth so I'm wondering why this doesn't - it's a shame that method is leaves my collision broken! Are you happy that the interpolation is working as it should in your opinion? Again, thanks :-) – BungleBonce May 24 '14 at 2:20

EDIT: This whole question was rewritten after I discovered that I had misunderstood the original question.

Based on advice from that, my approach was based on an accumulator member variable where each call to render() would add the time since last render() in fractional seconds and then call update() in a loop removing a constant amount of time for each until the accumulator was below 0.0;

Untested example code:

private float lastTime=(float)System.currentTimeMillis()/1000.0f;
private float accumulator=0.0f;
private final float RESOLUTION=1.0f/100; //constant step time for update in fractions of a second.

public void onDrawFrame(GL10 gl) {
final float now=(float)System.currentTimeMillis()/1000.0f;
final float interval=now-lastTime;
accumulator+=interval;
while(accumulator>0.0f){
SceneManager.getInstance().getCurrentScene().updateLogic(RESOLUTION);
accumulator-=RESOLUTION;
}
render(interval);
lastTime=now;
}


Also, you want to look into swap interval or vsync. Android exposes the native refreshrate for the screen(s) through some API that I can't remember. By enabling this you will avoid spending resources rendering frames that will never be drawn to screen. You will also avoid tearing and other artifacts.

• Hi @LennartRolland - thanks but this would update and render flat out would it not? It's essential that I be able to cap the logic updates (in my case to 60 per second), it's also essential that my logic and rendering are uncoupled from each other :-) (So if the device drops rendering frames, it at least carries on updating the logic at 60 ticks per second (it's pretty simple logic taking only a max of 4ms to complete so I don't envisage any device that wouldn't be able to handle 60 updates per second. – BungleBonce May 22 '14 at 20:42
• Running an idle-loop like that is not a good way to delay in modern hardware because it wastes a lot of resources that would be much better spent on actualy useful processing. To get what you want, look into vsync a.k.a. swap interval (opengl.org/wiki/Swap_Interval). To properly handle separate rendering and update, I would recommend reading this article: koonsolo.com/news/dewitters-gameloop – Lennart Rolland May 22 '14 at 22:28
• Ah Sorry! I have misread your code! That is exactly what you are trying to do! I thought I saw a "delay loop" which is NOT a good practice. I will update my answer.. – Lennart Rolland May 22 '14 at 22:31
• Thanks @LennartRolland - I will give it a try. Just a couple of questions - I don't quite understand what the 'interval' value is you're passing to the render() call. And, if I'm reading it correctly, this loop uses a variable delta which is passed to the logic routine? I currently use a fixed delta (which I'd like to stick to) so final dt = 1f/TickPerSecond which is passed to my logic routine (doesn't change). Can this be adapted to use a constant value? (Unless of course, I'm misunderstanding) - I'll also look into VSync - I was under the impression we had no control over than in 'droid! – BungleBonce May 22 '14 at 23:17
• 1. The interval is simply the time since last rendering took place, so if rendering is slow this will be a large number. I pass it to the render() simply because tehn the rendering can use it to apply some adaptive LOD or similar to reduce rendering time. 2. The update() is called with step that is guaranteed to never go above the resolution you selected. You COULD just skip this and instead do final float step=interval. This would result in constant time being passed to update(). The accumulator would then just cary over the remainder to the next frame. – Lennart Rolland May 22 '14 at 23:55

It has come to my attention that nobody has taken notice that in the Gaffer "fixed timestep" method tutorial's sourcecode he actually uses a "rk4 intergrator". The math shown in this question, is Euler intergration.

A different intergrator is required because the rendering can only be precise in Euler intergration if it truly recieves a fixed timestep, this, is not the case with the game loop being shown. Hence, also causing objects to "stutter" or to move further than intended. (Physics engines such as Box2D etc, do this by default I believe, and thus preventing the choppy movement.)

For further info, about Game Physics intergrators, here is a link to an article also written by Gaffer, which uses RK4 intergrator as an example.

• Thank you @RandomDeveloper this is interesting. I will go back and read the article again. I'm a bit confused though as I was under the impression my loop was utilising a fixed timestep!? What would be the best way forward changing as little code as possible? Thank you! – BungleBonce May 31 '14 at 18:03
• Well given the fact you are most likely using gaffers fix your timestep method, and most likely a linear interpolation function in the form of: renderPosition = interpolate(previousPosition, currentPosition, alphaValue); You can basically fix the remaining problems by providing for example an interpolate_rk4 function. Personally I'd start using a simpler method and see if that works, for example Verlet Intergration. Like seen here: subprotocol.com/verlet-js – RandomDeveloper Jun 1 '14 at 14:38
• A good explanation about how Verlet Intergration works, and when it is and is not useful for games can be found here: lonesock.net/article/verlet.html I'd like to add that the problems are highly related to floating point value math, and differencing frame rates(thus inconsistent delta values). Since the delta value is not consistent, Eular aka linear interpolation will fail. I hope I managed to clear some things up, I'm not used to this, but I figured this information should be out there @user22241 :) – RandomDeveloper Jun 1 '14 at 14:42