On Frame Rate Independence

The Problem

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 delta_time:

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 n with:

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 n with 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 d by 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 d into 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.

Note that d should be a value between 0 and 1.

Generalizing

Formalizing

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

Where 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 b and d):

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

Removing recursion

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-2), S(n-3)), and noting patterns - such as a series that can be replaced by a formula for the sum of its first n terms.

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

and

(1 - d)^3 * S(n-3)

The first pattern is a geometric series - which has the following formula for the sum of the first n terms:

a + ar + ar^2 + ... + ar^(n-1) = a * (1 - r^n) / (1 - r)

So with 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) becomes:

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)

And now 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 delta_time:

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 b and delta_time change 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.

Another perspective

What is the deeper underlying meaning of frame rate independence?

It may be put this way: any step with delta_time of k should be equivalent to any number of steps whose delta_time adds up to k.

We can simplify this into:

Any step with delta_time of k should be divisible into two steps with delta_times i and j where 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 delta_time d, and values k, i, and j such that k = i + j:

f(a, k) = f(f(a, i), j)

I found out by asking on the game development stack exchange that this is equivalent to flow.