How to tell whether an expression is independent from frame rate?

Question

I'm working on a videogame where part of the logic involves increasing a value each render frame (a render frame is equivalent to a simulation step where the result is drawn on the screen).

Frames can have varying time steps between them, commonly named "delta time".

I am wondering if there is a general approach to determining whether the expression that updates the value is "pinned" to real time, meaning that running one frame with delta time x is equivalent to running n frames with delta times adding up to x.

I have thought about this extensively for a few days now, but haven't reached the clean generalization I think would be possible to reach.

Say every frame we update value a with the following expression:

a = a + (b - a) * d

This is a commonly used formula for linear interpolation, where b is a constant that can be interpreted as a target value, and d is another constant between 0 and 1 that represents the fraction of distance to cover.

Now as you can see in the link I shared above I have calculated that to do this independently from frame rate one has to replace the factor d with an expression that involves delta_time:

a = a + (b - a) * (1 - d^delta_time)

I did this by expressing this process as a recursive sequence:

S(0) = a
S(n) = S(n-1) + (b - S(n-1)) * d

Then making it non-recursive (I don't think there's a standard approach for this, just expanding the expression and looking for patterns such as series with known formulas for the sum of the first n elements).

Once I reached a non-recursive form, I replaced n with t / delta_time, as the number of frames elapsed is equivalent to time elapsed divided by the time between frames. Then, I introduced delta_time into the expression in order to cancel it out, and translated that change into a change in the d constant.

I am not happy with this approach however.

I am now trying to formulate the problem in some other way, seeing if it gives me some clues as to a clean generalization.

What I'm looking for is a simple rule, a way to express that:

Given an expression S(delta_time) which calculates how much to increase a value by each frame, an increase of x in delta_time should be equivalent to running one iteration with delta_time = x.

I would also be interested in a solution that would provide assurance in terms of varying time step between frames - so not just agnostic to different delta_time over n frames, but agnostic to any delta_time between each subsequent frame. I think this may have no importance mathematically, but I'm not sure.

Could someone help elucidate me? I feel I'm at the edge of my mathematical ability.

Thanks!

Answer 1

One way we can formalize this is to say we have a function \$f\$ that takes some input game state \$ {\bf x}_0 \$ and a timestep \$ \Delta t\$ and transforms it into the resulting game state \$ {\bf x}_1 \$ exactly that much time in the future:

$${\bf x}_1 = f({\bf x}_0, \Delta t)$$

As you say in the "Another Perspective" section at the bottom of your article, we want to check whether the result of evaluating this function twice is the same as evaluating it once for the combined timestep (at least for infinite-precision real numbers). That is, does it obey this identity:

$$ f\left( f({\bf x_0}, \Delta t_1), \Delta t_2 \right) = f( {\bf x}_0, \Delta t_1 + \Delta t_2)$$

I asked about this on the Math StackExchange, and learned that a function with this property is called a flow.

We can test for this property by expanding out the two sides using some algebra, and check if we get the same expression both ways. For the exponential ease-out function you showed...

$$ f(a, \Delta t) = a + (b - a)\left(1 - d^{\Delta t}\right)\\ f(a, \Delta t_1 + \Delta t_2) = a + (b - a)\left(1- d^{\Delta t_1 + \Delta t_2}\right) $$

For this case, composition over two subsequent steps expands out to...

$$\require{cancel} \begin{align} &f\left( f(a, \Delta t_1), \Delta t_2 \right)\\ &= f\left(a + (b - a)\left(1- d^{\Delta t_1}\right), \Delta t_2 \right)\\ &= \left[a + (b - a)\left(1- d^{\Delta t_1}\right) \right] + \left(b - \left[a + (b - a)\left(1- d^{\Delta t_1}\right) \right]\right)\left(1 - d^{\Delta t_2}\right)\\ &= a + (b- a)(1 - d^{\Delta t_1}) + (b-a)(1 - d^{\Delta t_2}) - (b -a)(1 - d^{\Delta t_1})(1 - d^{\Delta t_2})\\ &= a + (b - a)\left(1 - d^{\Delta t_1} + 1 - d^{\Delta t_2} - (1 - d^{\Delta t_1})(1 - d^{\Delta t_2})\right)\\ &= a + (b - a)\left(1 \cancel{- d^{\Delta t_1} + 1 - d^{\Delta t_2}} \cancel{- 1 + d^{\Delta t_1} + d^{\Delta t_2}} - d^{\Delta t_1 + \Delta t_2}\right)\\ &= a + (b - a)(1 - d^{\Delta t_1 + \Delta t_2})\\ &=f(a, \Delta t_1 + \Delta t_2) \end{align}$$

So the composed form is equal to the single evaluation with summed time arguments, and we've proven this function has the desired "flow" property.

---

If you're looking for a relatively easy test to apply to a given function, without having to find a route to simplify the algebra to check the identity as shown above, then a numerical simulation is a great quick-and-dirty check:

Open up Google Sheets or the spreadsheet software of your choice. Pick a timestep, and make a column of values going up by that step. Next to them, use your step formula with that timestep and drag it down to see the sequence of values it produces. Repeat this for a different timestep (say half or double the initial choice). Then compare the values they give you, or graph the two curves. If they give diverging values at the same timestamp, the formula does not preserve framerate independence.

I show an example of that approach in this answer, to prove that some formulas being purported as "framerate independent" were not.

Because of the compounding of errors from one step to the next, the wrong formula will tend to reveal itself very quickly when you do this! And this directly tests the situation we care about in games: whether a run simulating discrete steps at 30 fps and 60 fps (for example) will see the same result.

Note that even when we use a function with this flow property, the results we get can still vary slightly at different framerates due to accumulated rounding error in the intermediate values. So when you need exact consistency for fairness or deterministic simulation, you need to fix your timestep.

Answer 2

You are asking the difference between a mathematical derivative and a discrete derivative:

Given an expression S(delta_time) which calculates how much to increase a value by each frame, an increase of x in delta_time should be equivalent to running one iteration with delta_time = x.

I would also be interested in a solution that would provide assurance in terms of varying time step between frames ...

Yes, you can be assured the produced value is the best estimate possible, by virtue of the definition of a derivative: the denominator is delta t.

The error factors only include precision errors.

agnostic to any delta_time between each subsequent frame

No such general exact solution could exist.

Delta time has an unstable variance(outside of a RTOS).

The theoretical mathematical value is the best estimator.

Bottom Line

It can never be exact, only close.

Final comment

I am wondering if there is a general approach to determining whether the expression that updates the value is "pinned" to real time, meaning that running one frame with delta time x is equivalent to running n frames with delta times adding up to x.

As close as accumulated precision will allow.

Answer 3

I am wondering if there is a general approach to determining whether the expression that updates the value is "pinned" to real time, meaning that running one frame with delta time x is equivalent to running n frames with delta times adding up to x.

Yes.. If the expression's variables that are multiplied by delta-time are constant (they can not change from frame to frame) then running one frame with delta time x is equivalent to running n frames with delta time x*n.

In your example, you provided the expression:

a = a + (b - a) * d

If (b-a), the value multiplied by d, is constant (as in it can not change from frame to frame) then running it ten times for delta-time-d is the same as running it once for delta-time-10d (floating point precision ignored). This is the only case where this is true.

However, if (b-a) is varying from frame to frame, then EVERY different delta-time you choose to run under will produce a different outcome, because of that varying.

For example, in physics simulation, a simple first-derivative velocity approach, if velocity is changing because of acceleration, produces noticably different results based on what the actual delta-time experienced happens to be, and the method used of computing the new velocity value.

This is why typically, in a physics simulation, a 2nd order differential equation is used to compute motion, because given an acceleration, it will not only compute the current velocity given an acceleration over some given delta-time, but it will also provide an integrated average velocity (and thus motion delta) over the delta-time based on how much the velocity was changing during the previous delta time. This 2nd order differential equation of motion will accurately produce the same results whether it's 10x-delta-d or 1x-delta-10d - but ONLY if the acceleration over that time is constant!

If the acceleration over that time is changing, then you are back to your delta-t mattering, because of the changes to acceleration... unless the acceleration is changing with a constant 3rd derivative, and you use a 3rd order differential equation of motion.

Are you seeing a pattern?

It's turtles turtles turtles all the way down.

Answer 4

Your conclusion assumes a fixed delta-time: u^deltatime​ Which is an invalid statement if delta-time varies across steps. Almost a given on modern systems.

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

Each of your options explores/describes the same formula with different parameter options.

A true "Frame Rate Independent Lerp" fixes, makes constant, the a and b parameters at the start, as a1 and b1 and scales alpha to a normalized time period(called nt ),0 to 5 seconds becomes 0 - 1 by multiplying by 1/5, so for this example, nt = 0.2 :

if(sum_time < 1)
{
      sum_time += elapsed_time * nt; // this calculation may run into lower epsilon and become zero for long periods on fast computers use doubles not floats
      if(sum_time > 1)
            sum_time = 1; // eliminate overshoot, breaks linearity for the last step, due to precision errors
      current_value = a1 * (1 - sum_time) + b1 * sum_time;
}

By fixing the start and end values (a1,b1) the result is linear and bound to the range [a1,b1].

For long period lerps:

if(sum_time < 1)
{
      sum_time += elapsed_time; 
      if(sum_time > 1)
            sum_time = 1; // eliminate overshoot, breaks linearity for the last step, due to precision errors
          st =sum_time  * nt; 
// this calculation may still run into lower epsilon and become zero for long periods on fast computers for the first iterations, but will stabilize after 'sum_time  * nt' grows above epsilon.
// although the start time may be delayed(non-linear for the first steps), the outcome is the same linear movement over time.
      current_value = a1 * (1 - st) + b1 * st;

That is the entire article as it relates to the title.

Ease in

Allowing a​​ to vary with a fixed b1​​ over iterations produces an easing effect, smooth exponential motion given a fixed(usually small) alpha value.

Recursive analysis

You have described the differential equation of X​​ as: X(n+1) = X(n) + DX/DT​

There are three ways to treat this equation in a discrete manner Forward Euler, Backward Euler and Crank-Nicolson ie Mid-Point. Since DT, delta time is unknown in the future, Forward Euler can be eliminated, unless delayed by a step. By storing the previous calculated point Crank-Nicolson is the best stable solution.

---

Is the geometric series/exponential curve special in this scenario? Or can other curves be made independent from frame rate?

Any and all curves including non-linear differential equations are expressed independent from frame rate by definition and could be expressed.

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?

No. You are changing the parameters on the fly.