Improved Lerp Smoothing.

September 29th, 2017| Posted by admin
Categories: Uncategorized | Tags:

A Useful Snippet:

A lot of game developers will recognize this line of code:

value = lerp(value, targetValue, 0.1);

It’s super useful, and can be used for all sorts of things. With a higher constant, it’s a good way to smooth out jittery input from a mouse or joystick. With a low constant, it’s a nice way to smoothly animate a progress bar or a camera following a player. It will never overshoot the target value even if it’s changing, and it changes the speed based on how far away it is so it will always quickly converge on the target. Pretty good for a one liner!

BUT!

Unfortunately it has a couple problems that are often ignored. The first is that it’s highly dependent on framerate, but is usually applied per frame anyway. The second is that the lerp constant that you need to use is really hard to control. It’s not uncommon to start adding a lot of zeros to the front of the lerp constant to get the desired smoothing amount. Assuming 60 fps, if you want to move halfway towards an object in a second you need to use a lerp constant of 0.0115. To move halfway in a minute, you need to use 0.000193. On the other end of the spectrum if you use a lerp constant of 0.9 you will run out of 32 floating point precision within 7 frames, and it will be exactly at the target value. That’s a little wacky.

Fortunately, with a little math, both issues are easy to fix.

The Math

Don’t feel bad about skipping this section if you don’t care about the math. The solution at the end works just fine without understanding why. ūüėČ

Think of it another way. Say you are lerping by 0.9 each frame. That means you are leaving (1 - 0.9) = 0.1 = 10% of the remaining value. After 2 frames, there will be (1 - 0.9)*(1 - 0.9) = 0.01 = 1% of the remaining value. After 3, (1 - 0.9)*(1 - 0.9)*(1 - 0.9) = 0.001 = 0.1%. After n frames you’ll have (1 - 0.9)^n of the remaining value. Let’s graph that and see what it looks like.

An exponential curve.

You can see that this example does close in on the target very¬†quickly. Also, since it’s a continuous function, we can figure out what the value between frames would be.¬†This is how you fix the framerate issue, but we’ll get into that more later.

Since floating point numbers have limited precision, you’ll eventually run out and you’ll “arrive” at the target value exactly. Floats can store ~7 significant digits, and doubles ~16. Here’s a quick snippet of Ruby code to test that out.

value = 0.0
target = 1.0
alpha = 0.9
100.times do|i|
  value = (1 - alpha)*value + alpha*target
  puts "#{i + 1}: #{value == target}"
end

And the output?

1: false
2: false
... (more false values)
15: false
16: false
17: true

It shouldn’t be too surprising that precision runs out after the 16th iteration. (1 - 0.9)^17 is quite small. 1e-17 to be exact. That is so small, that in order to store 1 - 1e-17 you would need 17 significant digits, and doubles can only store 16! More interestingly, no matter what your starting and ending values are, it will always run out of precision after 16 iterations. Most game engines use floats instead of doubles, and those can only store ~7 significant digits. So you should expect precision to run out after only the 7th iteration.

What about for other constants? (Keep in mind I’m using doubles, and floats would run out in half as many iterations.) For 0.8 you run out of precision after ~23 iterations, ~53 for 0.5. With constants less than 0.5 it sort of breaks down and something curious can happen. Say you keep lerping with a constant of 0.5. Eventually, you will run out of precision and the next possible floating point number after value will be target. When you try to find the new value half way between, it will cause it to round up to target instead. If you use a constant smaller than 0.5, it will round down to value instead. Instead of “arriving” at target, it will get stuck at the floating point number immediately before it. Interesting, but not all that important since with a few exceptions it’s not a good idea check floating point numbers for equality anyway. Anyway¬†for a constant of 0.4, the value gets stuck at ~70 iterations, or ~332 for 0.1.

So really all you are doing by repeatedly lerping is evaluating an exponential curve. We can use this knowledge both to fix the framerate independence issue, as well as make the values used more reasonable.

Improved Version:

Let’s replace the simple lerp constant with an exponential function that involves time, and see how it works.

// exp() works just as well, probably with little to no measurable performance difference.
value = lerp(target, value, exp2(-rate*deltaTime))

In this version, rate controls how quickly the value converges on the target. With a rate of 1.0, the value will move halfway to the target each second. If you double a rate, the value will move in twice as fast. If you halve the rate, it will move in half as fast. Couldn’t be easier.

Even better, it’s framerate independent. If you lerp this way 60 times with a delta time of 1/60 s, it will be the same result as lerping 30 times with 1/30 s, or once with 1 s. No fixed time step required nor the jittery movement it causes. However, do keep in mind that if your target value is changing over time (such as one object following another) you won’t get the exact same behavior. It’s close enough for many uses though.

Conversion:

So this new version is framerate independent, and easier to tune. Now how do you convert your old lerp() statements into the new ones without changing the smoothing coefficients that already work so well at 60 fps? Math to the rescue again. The following formula will can convert them: rate = -fps*log2(1 - coef). (Note: Use log() instead of log2() if you are using exp() instead of exp2() in your lerp expression.)

Performance:

I’ve never actually tested it! On the other hand, I’ve never run into issues with it. I’m also pretty sure most CPUs have instructions for computing log2() and exp2() nowadays. Computing exp() is only a couple instructions then. Different systems/languages/VMs vary, but I would not worry about it.

Going Further:

I have on few occasions considered going a step further and putting rate on a logarithmic scale too. The advantage is if you are adjusting the rate value through a UI. Halving or doubling a number by typing it in is easy, but not when dragging a slider with the mouse. You would also have to be very careful not to adjust the rate to be negative. Putting it on a logarithmic scale makes the problem go away. Dragging a certain amount to the left would always mean halve the rate, and dragging the same amount to the right would always mean to double the rate.

value = lerp(target, value, exp2(-exp2(logRate)*deltaTime))

No comments yet.