When working on iterative simulations - such as games - we frequently want to animate a value over time.
There are two ways to go about this:
- Calculate the current value given a starting value and time elapsed (an animation curve)
- Update the value given the time since the last step (such as moving forward at a given speed)
Option 2 does not require keeping track of starting value nor time elapsed. It is especially attractive when we don’t have an end in sight - meaning no fixed duration.
It allows us to build an iterative process that does something indefinitely.
A common use case is applying lerp (linear interpolation) every frame to move a value
a towards a value
b over time:
lerp(a, b, d) = a + (b - a) * d
Where the factor
d is a value between 0 and 1 representing the fraction of distance to cover.
We can run lerp iteratively like so:
a = lerp(a, b, d)
This means using the last frame’s result as the starting value for the next frame.
An issue becomes apparent - this process is entirely dependent on frame rate. Running this at 30fps will cause a slower change in real time than running it at 120fps.
A common workaround is to multiply the factor
d by the time elapsed since the last frame
a = lerp(a, b, d * delta_time)
While this helps, it is not a real solution - as we will see below.
The problem we are interested in is: how can we know whether an iterative process is independent from frame rate?
We can begin by thinking about lerp specifically - and how we can make it independent from variations in
delta_time (the time between simulation steps).
Iterative lerp is an exponential curve
When running lerp iteratively, we reduce the distance to the target value by a factor
d each frame. The fraction of remaining distance is thus
1 - d. After
n iterations, the fraction of remaining distance is
(1 - d)^n.
For example, with
d = 0.1, after 3 iterations we will have
0.9 * 0.9 * 0.9 = 0.729 of the remaining distance.
This means we can express the resulting value at frame
f(n) = b - (b - a) * (1 - d)^n
Which shows the underlying curve is exponential.
Making lerp frame rate independent
We can relate the number of iterations
n to the elapsed time
t, given a constant
delta_time representing the time between iterations:
n = t / delta_time
This means we can update the
f(n) expression we saw above to
f(t) by replacing
t / delta_time:
f(t) = b - (b - a) * (1 - d)^(t / delta_time)
If you plot this function with varying values for
delta_time, you will see that an iterative lerp with a constant factor
d is dependent on frame rate (which is kind of obvious).
The previously mentioned common solution of multiplying the factor
delta_time will not entirely solve this issue:
f(t) = b - (b - a) * (1 - (d * delta_time))^(t / delta_time)
If you plot this function, you will see that varying
delta_time still has an effect, albeit smaller.
To negate the effect of variations in
delta_time, we have to cancel it out of the equation. We can do this by turning the factor
1 - d^delta_time:
f(t) = b - (b - a) * (1 - (1 - d^delta_time))^(t / delta_time) = b - (b - a) * (d^delta_time)^(t / delta_time) = b - (b - a) * d^t
Our frame rate independent iterative lerp should then look like:
a = lerp(a, b, (1 - d^delta_time))
We can also reason that
d now means “fraction of distance remaining after 1 second”, because at
t = 1,
b - (b - a) * dˆt becomes
b - (b - a) * d.
d should be a value between 0 and 1.
The reasoning we used above can be formalized, so we can hopefully apply it to any iterative process.
The main idea is to start with a recursive sequence:
S(0) = a S(n) = f(S(n-1))
a is a constant representing the starting value, and function
f can be anything you do in code (as long as you can express it mathematically).
We will use lerp as an example from here on out. It can be expressed as the following function (with constants
f(x) = x + (b - x) * d
Once you have a function
f, you can expand it in the sequence:
S(0) = a S(n) = S(n-1) + (b - S(n-1)) * d
The next step is to somehow make the sequence non-recursive. This is not straightforward and there is no clear path, but a good general approach is to expand
S(n-1) backwards a few steps (into
S(n-3)), and noting patterns - such as a series that can be replaced by a formula for the sum of its first
S(0) = a S(n) = S(n-1) + (b - S(n-1)) * d = S(n-1) * (1 - d) + db = (S(n-2) * (1 - d) + db) * (1 - d) + db = ([S(n-3) * (1 - d) + db] * (1 - d) + db) * (1 - d) + db
Now that we have quite a long expression, we can reorganize it a bit:
S(n) = ([S(n-3) * (1 - d) + db] * (1 - d) + db) * (1 - d) + db (start by reversing it to make it easier to read left-to-right) = db + (1 - d) * (db + (1 - d) * [db + (1 - d) * S(n-3)]) = db + (1 - d) * db + (1 - d)^2 * db + (1 - d)^3 * S(n-3)
We can see two patterns above:
db + (1 - d) * db + (1 - d)^2 * db
(1 - d)^3 * S(n-3)
The first pattern is a geometric series - which has the following formula for the sum of the first
a + ar + ar^2 + ... + ar^(n-1) = a * (1 - r^n) / (1 - r)
a = db and
r = (1 - d) we can change it into the following:
db + (1 - d) * db + (1 - d)^2 * db = db * (1 - (1 - d)^n) / (1 - (1 - d)) = db * (1 - (1 - d)^n) / d = b * (1 - (1 - d)^n)
The second pattern can be dealt with through a simple replacement:
(1 - d)^3 * S(n-3) = (1 - d)^n * a
Note that eventually the remaining
S(n-3) term will become
a, which is the starting value of the sequence.
So by adding back together the the two patterns,
S(n) = b * (1 - (1 - d)^n) + (1 - d)^n * a = b - (b * (1 - d)^n) + (1 - d)^n * a = b + (1 - d)^n * (a - b)
S(n) is no longer a recursive expression:
S(n) = b + (1 - d)^n * (a - b)
Turning frames to time
The next step is to evaluate the expression as a function of time, not iterations (or frames elapsed).
We can use the following expression to convert frames
n to time
t, given a constant time between frames
n = t / delta_time
We can now change the expression to:
S(t) = b + (1 - d)^(t / delta_time) * (a - b)
The effect of variations in
delta_time should now become clear. In this case, we can compensate for it by adjusting the
d constant in order to cancel
delta_time out of the expression:
d = (1 - u^delta_time) S(t) = b + (1 - (1 - u^delta_time))^(t / delta_time) * (a - b) = b + (u^delta_time)^(t / delta_time) * (a - b) = b + u^t * (a - b)
Which as we saw before, is equivalent to running lerp iteratively as follows:
a = lerp(a, b, (1 - u^delta_time))
Questions at this point
- Is the geometric series/exponential curve special in this scenario? Or can other curves be made independent from frame rate?
- Is there a way to guarantee that an iterative process will be independent of frame rate even when
delta_timechange between iterations?
Regarding question 2, we know that keeping track of starting value and time elapsed allows us to make something 100% frame rate independent. It basically allows us to skip the whole recursive sequence reasoning and jump into evaluating a function based on time. Maybe that is a clue on arriving at an answer.
What is the deeper underlying meaning of frame rate independence?
It may be put this way: any step with
k should be equivalent to any number of steps whose
delta_time adds up to
We can simplify this into:
Any step with
k should be divisible into two steps with
k = i + j.
Because if a step is divisible into two, we can keep dividing arbitrarily into any number of steps.
This can be expressed mathematically as:
Given a function
f(a, d) that updates a state
a given a
d, and values
j such that
k = i + j:
f(a, k) = f(f(a, i), j)