Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

What is the best pattern to create a system that all the objects positions to be interpolated between two update states?

The update will always run at the same frequency, but I want to be able to render at any FPS. So the rendering will be as smooth as possible no matter the frames per second, whether its lower, or higher than the update frequency.

I would want to update 1 frame into the future interpolate from the current frame to the future frame. This answer has a link that talks about doing this:

Semi-fixed or Fully-fixed timestep?

Edit: How could I also use the last and current speed in the interpolation? For example with just linear interpolation, it will move at the same speed between positions. I need a way to have it interpolate the position between the two points, but take into consideration the speed at each points for the interpolation. It would be helpful for low rate simulations like particle effects.

share|improve this question
2  
ticks being logic ticks? So your update fps < rendering fps? –  The Communist Duck May 26 '11 at 20:45
    
I changed the term. But yes logic ticks. And no, I want completely free the rendering from the updating, so the game can render at 120HZ or 22.8HZ and the updating will still run the same speed, provided the user meets the system requirements. –  AttackingHobo May 26 '11 at 20:52
    
this might be realy tricky since while rendering all your object positions should stay still (changing them during render process may cause some undifined behavior) –  Ali.S May 26 '11 at 21:14
    
Interpolation would calculate the state at a time between 2 already calculated update frames. Isn't this question about extrapolation, calculating the state for a time after the last update frame? Since the next update is not even capculated yet. –  Maik Semder May 26 '11 at 21:19
    
I think that if he has only one thread updating / rendering, it can't happen to re-update just rendering position. You just send positions to the GPU and then re-update. –  zacharmarz May 26 '11 at 21:20

2 Answers 2

up vote 20 down vote accepted

You want to separate update (logic tick) and draw (render tick) rates.

Your updates will produce the position of all objects in the world to be drawn.

I will cover two different possibilities here, the one you requested, extrapolation, and also another method, interpolation.

1.

Extrapolation is where we will compute the (predicted) position of the object at the next frame, and then interpolate between the current objects position, and the position that the object will be at next frame.

To do this, each object to be drawn must have an associated velocity and position. To find the position that the object will be at next frame, we simply add velocity * draw_timestep to the object's current position, to find the next frame's predicted position. draw_timestep is the amount of time that has passed since the previous render tick (aka the previous draw call).

If you leave it at this, you'll find that objects "flicker" when their predicted position didn't match the actual position at the next frame. To remove flickering, you can store the predicted position, and lerp between the previously predicted position and the new predicted position at each draw step, using the elapsed time since the previous update tick as the lerp factor. This will still result in poor behavior when fast moving objects suddenly change location, and you might want to handle that special case. Everything said in this paragraph are the reasons why you don't want to use extrapolation.

2.

Interpolation is where we store the state of the last two updates, and interpolate between them based on the current amount of time that has passed since the update before last. In this setup, each object must have an associated position and previous_position. In this case, our drawing will represent at worst one update tick behind the current gamestate, and at best, at the exact same state as the the current update tick.


In my opinion, you probably want interpolation as I've described it, as it's the easier of the two to implement, and drawing a tiny fraction of a second (e.g. 1/60 second) behind your current updated state is fine.


Edit:

In case the above isn't enough to allow you to perform an implementation, here is an example of how to do the interpolation method I've described. I won't cover extrapolation, because I can't think of any real-world scenario in which you should prefer it.

When you create a drawable object, it will store the properties needed to be drawn (i.e., the state information needed to draw it).

For this example, we will store position and rotation. You may also want to store other properties like color or texture coordinate position (i.e. if a texture scrolls).

To prevent data from being modified while the render thread is drawing it, (i.e. one object's location is changed while the render thread draws, but all others have not been updated yet), we need to implement some type of double buffering.

An object stores two copies of it's previous_state. I will put them in an array and refer to them as previous_state[0] and previous_state[1]. It similarly needs two copies of it's current_state.

To keep track of which copy of the double buffer is used we store a variable state_index, which is available to both the update and draw thread.

The update thread first computes all properties of an object using it's own data (any data structures you want). Then, it copies current_state[state_index] to previous_state[state_index], and copies the new data relevant for drawing, position and rotation into current_state[state_index]. Then it does state_index = 1 - state_index, to flip the currently used copy of the double buffer.

Everything in the above paragraph has to be done with a lock taken out on current_state. The update and draw threads both take out this lock. The lock is only taken out for the duration of the copying of state information, which is fast.

In the render thread, you then do a linear interpolation on position and rotation like so:

current_position = Lerp(previous_state[state_index].position, current_state[state_index].position, elapsed/update_tick_length)

Where elapsed is the amount of time that has passed in the render thread, since the last update tick, and update_tick_length is the amount of time that your fixed update rate takes per tick (e.g. at 20FPS updates, update_tick_length = 0.05).

If you don't know what the Lerp function above is, then checkout wikipedia's article on the subject: Linear Interpolation. However, if you dont know what lerping is, then you probably aren't ready to implement decoupled update/drawing with interpolated drawing.

share|improve this answer
    
+1 the same must be done for orientations/rotations and all other states that change over time, i. e. like material animations in particle systems etc. –  Maik Semder May 27 '11 at 5:56
    
Good point Maik, I just used position as an example. You need to store the "velocity" of any property you wish to extrapolate (i.e. the rate of change over time of that property), if you want to use extrapolation. In the end, I really can't think of a situation where extrapolation is better than interpolation, I only included it because the asker's question requested it. I use interpolation. With interpolation, we need to store the current and previous update results of any properties to interpolate, like you said. –  Olhovsky May 27 '11 at 12:05
    
This is a restatement of the problem and the difference between interpolation and extrapolation; it is not an answer. –  user744 May 27 '11 at 12:27
    
Joe Wreshnig: I thought I gave enought to perform an implementation. But alright, I'll explain how to do linear interpolation in my answer, although the link in my answer to wikipedia's article would probably be sufficient, or you could just use the Lerp function in whatever library you have access to. In any case, this certainly was not just a "restatement of the problem". –  Olhovsky May 27 '11 at 12:33
1  
In my example I stored position and rotation in the state. You can just store velocity (or speed) in the state as well. Then you lerp between speed in the exact same way (Lerp(previous_speed, current_speed, elapsed/update_tick_length)). You can do this with any number you want to store in the state. Lerping just gives you a value between two values, given a lerp factor. –  Olhovsky May 27 '11 at 19:15

This problem requires you to think about your definitions of start and finish a little differently. Beginning programmers often think of change in position per frame and that is a fine way to go in the beginning. For the sake of my response, let's consider a one dimensional answer.

Let's say you have a monkey at position x. Now you also have a "addX" to which you add to the monkey's position per frame based on the keyboard or some other control. This will work as long as you have a guaranteed frame rate. Let's say that your x is 100 and your addX is 10. After 10 frames, your x += addX should accumulate to 200.

Now, instead of addX, when you have a variable frame rate, you should think in terms of velocity and acceleration. I will walk you through all of this arithmetic but is is super simple. What we want to know is how far you want to travel per millisecond (1/1000th of a second)

If you are shooting for 30 FPS, then your velX should be 1/3rd of a second (10 frames from the last example at 30 FPS) and you know that you want to travel 100 'x' in that time so set your velX to 100 distance / 10 FPS or 10 distance per frame. In milliseconds, that works out to 1 distance x per 3.3 milliseconds or 0.3 'x' per millisecond.

Now, everytime you update, all you need to do is figure out the time elapsed. Whether 33 ms have passed (1/30th of a second) or whatever, you just multiply the distance 0.3 by the number of milliseconds passed. This means that you need a timer that gives you ms (millisecond) accuracy but most timers give you this. Simply do something like this:

var beginTime = getTimeInMillisecond()

... later ...

var time = getTimeInMillisecond()

var elapsedTime = time-beginTime

beginTime = time

... now use this elapsedTime to calculate all of your distances.

share|improve this answer
1  
He doesn't have a variable update rate. He has a fixed update rate. To be honest, I really don't know what point you're trying to make here :/ –  Olhovsky May 27 '11 at 17:37
1  
??? -1. That is the entire point, I am having a guaranteed update rate, but a variable render rate, and I want it to be smooth with no stuttering. –  AttackingHobo May 27 '11 at 17:39
    
Variable update rates do not work nicely with networked games, competitive games, replay systems, or anything else that relies on the game-play being deterministic. –  AttackingHobo May 27 '11 at 17:42
1  
Fixed update also allows easy integration of pseudo-friction. E.g. if you want to multiply your speed by 0.9 each frame, how do you figure out how much to multiply by if you have a fast or a slow frame? Fixed update is sometimes greatly preferred -- virtually all physics simulations use a fixed update rate. –  Olhovsky May 27 '11 at 17:48
2  
If I used a variable frame rate, and set up a complex initial state with lots of objects bouncing off of each other, there is no guaranty that it will simulate exactly the same. In fact it will most likely simulate slightly differently each time, with small differences at the start, compounding over a short time into completely different states between each simulation run. –  AttackingHobo May 27 '11 at 18:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.