Interpolation using a sprite's previous frame and current frame

Question

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();

}

Answer 1

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);

Answer 2

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

The definite resource on the subject is this article: http://koonsolo.com/news/dewitters-gameloop

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.

Answer 3

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.