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

Question

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;                         
//Game updates per second
final int ticksPerSecond = 60;
//Amount of time each update should take        
private final int skipTicks = (1000 / ticksPerSecond);
float dt = 1f/ticksPerSecond;
private double timeCorrection;

Answer 1

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.

Answer 2

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.