[HN Gopher] Fixing the iterative damping interpolation in video ...
___________________________________________________________________
Fixing the iterative damping interpolation in video games
Author : ux
Score : 117 points
Date : 2024-05-18 12:24 UTC (1 days ago)
(HTM) web link (blog.pkh.me)
(TXT) w3m dump (blog.pkh.me)
| chrisjj wrote:
| Nice, but ...
|
| > So there we have it, the perfect formula, frame rate agnostic ,
|
| ... worth noting what happens on a frame time spike.
| ux wrote:
| A frame time spike is covered by the overshooting point: it
| will basically land further down the curve, which means a point
| converging toward the B target.
| chrisjj wrote:
| In monoticity guaranteed even if the next frame is short?
| ux wrote:
| As the delta time converges to 0, the lerp coefficient is
| going to converge to 0 as well, meaning it won't move. Said
| differently, if time stops the interpolation as well. You
| may enter into the realm of floating point accuracy issues
| at some point with low values, but I'm curious of what
| specific scenario you have in mind here?
| chrisjj wrote:
| OK, so that's confirmed Yes.
|
| Thanks.
| kibibu wrote:
| Alternatively, you could fix your timestep, decoupling your
| physics from your display refresh entirely.
|
| https://gafferongames.com/post/fix_your_timestep/
| mort96 wrote:
| Which is hard to do well and has its own set of drawbacks.
| nightowl_games wrote:
| Hard disagree. It's not hard to do well. The draw back is
| less than 1 frame of input latency. If your game uses a
| physics engine or is networked you are forced to use a
| constant update rate, ie: 30 or 60hz. The draw backs to
| linking the physics update rate to the monitor refresh rate
| are enormous and untenable in a networked game.
| mort96 wrote:
| I don't personally care much about a frame or two of
| latency (some do though, and for some genres that'll be a
| big deal); however I care about animation smoothness. If
| the monitor refresh rate is 144Hz and physics tick rate is
| 60Hz, you'll need some form of interpolation, which is hard
| to do well especially since the refresh rate isn't a
| multiple of tick rate.
| magicalhippo wrote:
| > you'll need some form of interpolation, which is hard
| to do well
|
| Due to non-constant accelerations?
| kibibu wrote:
| Some games use a 120hz physics sim even if they're capped
| to 60hz display refresh.
| Matheus28 wrote:
| This would still be needed for UI animations and lerpings that
| aren't tied to the actual gameplay
| markisus wrote:
| Unfortunately you cannot extend this approach much beyond this
| simple example if you are writing a physics simulation. There is
| no known closed form solution, for example, for the famous three
| body problem, so a some sort of numerical integration is
| absolutely required. At that point, you should just decouple the
| numerical integration timestep from the monitor refresh rate, or
| mandate a refresh rate that will be acceptable to the player.
| mort96 wrote:
| You can do that, but it has serious drawbacks. You can:
|
| * Run physics at such a high rate that sampling it at 30 or 60
| or 144 or 260 hertz is fine, like running physics at 1kHz. This
| is appropriate for certain kinds of very realistic physics sim
| style games, but usually undesirable due to performance.
|
| * Run physics at some fixed, sane rate (somewhere between 20
| and 100 Hz probably), and then do rendering separately,
| interpolating between positions for refresh rates higher than
| the physics tick rate. This can be hard to make feel good on
| refresh rates which aren't clean multiples or divisors of the
| tick rate, but ensures that physics behaves identically
| independent of frame rate.
|
| * Couple rendering and physics and run at a fixed frame rate
| (60 FPS). This will work okay for many players but a whole lot
| of people will be angry at you that your game is choppy on
| their fancy high refresh monitor, and if you don't change
| monitor mode to change the monitor's refresh rate, a 144Hz
| screen will sometimes refresh twice and sometimes thrice per
| game frame, meaning nothing will ever seem smooth even by 60
| FPS standards.
|
| * Couple physics and frame rate but allow the delta time to
| vary (maybe running physics 2 or 3 times per frame if the frame
| rate is really low). I'd say this produces the best results for
| any given refresh rate, and it's relatively simple to
| implement, but it causes physics to behave slightly differently
| with different frame rates, and it's prone to bugs like the one
| discussed in this article.
|
| It's not an easy decision, there is no good rule of thumb. I
| tend to prefer the last option I listed for my games, but I'm
| aware that it has drawbacks. But "just decouple physics from
| rendering" is certainly not the straightforward rule of thumb
| you seem to suggest it is. (EDIT since this post seemed more
| negative than I meant: running at a fixed time step is a good
| solution and very appropriate for many games, I'm not saying
| your suggestion is bad)
| gnuser wrote:
| In godot (compile main daily) I am running 120 tick rate but
| have found some interesting optimizations happen there and
| above (240) and am seriously temped to just make 240 my
| default (but I need to do more server load tests as I'm
| planning to scale)
| mort96 wrote:
| 240Hz has issues too though, it means that there's on
| average 1.66 physics ticks per screen refresh on a 144Hz
| screen. In practice that means that an object moving at,
| say, 0.1 meter per tick will have moved 0.1 meters in some
| frames and 0.2 meters in other frames, which leads to
| choppy animation. That's why I mentioned tick rates in the
| kilohertz; sometimes having 10 ticks between frames and
| sometimes 11 ticks isn't a big deal, but sometimes having 2
| and sometimes 1 is noticeable (and obviously if some frames
| have 1 tick and some have 0 ticks between them, that's a
| disaster (unless you do interpolation which is a different
| can of worms)).
|
| Now running physics at 240Hz or even 120Hz might still be
| the right choice for your game, especially when taking into
| account human factors and time constraints, it's just not a
| panacea
| schiffern wrote:
| For 144 and 240 Hz, the LCM (least common multiple) would
| be 720 Hz. At 144 Hz that's 5 ticks per frame, and at 240
| Hz it's 3 per frame.
|
| https://www.calculatorsoup.com/calculators/math/lcm.php
| kibibu wrote:
| > will have moved 0.1 meters in some frames and 0.2
| meters in other frames
|
| Not if you interpolate based on previous position. This
| means you accept up to 16ms display latency, but the
| trade off is smooth motion.
| mort96 wrote:
| That's why I wrote this part:
|
| > unless you do interpolation which is a different can of
| worms
| markisus wrote:
| Thanks for bringing up the intricacies involved. I shouldn't
| have used the word "just" as it implies that the solution is
| easy.
| jprete wrote:
| I think the real problem with the OP's straw-proposal
| interpolation method is that it's stateless and doesn't need to
| be. I would instead record the start position, then interpolate
| along a function F(t) to the end position. F(0)=0, F(1)=1,
| F'(0)=F'(1)=0 just so the ends aren't jerky. The curve can even
| overshoot 1 to give the animation some bounce.
|
| I'm sure somewhere on the Internet somebody's written down some
| good choices of curve; hopefully someone else knows what to
| search for.
|
| (I don't know what to do if another change interrupts the first
| but it's a rare case and can probably be handled imperfectly.)
| v21 wrote:
| > (I don't know what to do if another change interrupts the
| first but it's a rare case and can probably be handled
| imperfectly.)
|
| This kind of lerp trick, while imperfect, is useful in exactly
| these sort of situations. It allows you to smooth movement even
| if the target point is changing at at arbitrary intervals (note
| too that it works okay generalised to multiple dimensions). And
| the statelessness is very useful too - I don't think the feel
| is great and it's not very controllable, but being able to just
| add some damping to the movement without having to track
| animation states or anything like that is super useful.
| 10000truths wrote:
| > I don't know what to do if another change interrupts the
| first but it's a rare case and can probably be handled
| imperfectly.
|
| Extract the position (p0) and velocity (v0) vectors at the
| moment of interruption, and derive a new function F(t) that
| meets the constraints {F(0)=p0, F'(0)=v0, F(1)=p1, F'(1)=0}.
| jayd16 wrote:
| Wouldn't you just want to sample a normalized curve and apply
| that? What is the use case where you want to use this iterative
| call, care about frame accuracy, but can't afford curve data?
|
| With the explicit curve you have more control in the exact
| damping, too.
| meindnoch wrote:
| Exponential decay has the special property that it can be
| calculated from the current state with no additional data
| needed. With other kinds of interpolation curves, you need to
| additionally store the time the animation started.
| jayd16 wrote:
| Sure, but when is that relevant?
| manmtstream wrote:
| When the end state changes over time, or there is no
| defined duration.
| spoiler wrote:
| Stated dabbling with game dev very recently so I'm
| curious about this!
|
| Couldn't we get the delta, or for some animations use
| modulo arithmetic? Maybe mix in some gradient noise into
| the animation to make it seem organic to break the
| looping.
| Ono-Sendai wrote:
| Proposed solution is too expensive with ln and exp calls.
| ux wrote:
| Only the exp call happens in the processing loop. The ln is in
| the conversion function, it's not supposed to land in the code.
| ncruces wrote:
| Now write the formula in terms of expm1 for numerical stability,
| and express the constant in terms of "half life" measured in
| seconds to make it intuitive instead of magical.
| ncruces wrote:
| Seriously guys, don't write: a = lerp(a, B, 1.0
| - exp(-delta * RATE2))
|
| Write: a = lerp(a, B, -expm1(-delta * RATE2))
|
| This is precisely the situation where you really want to use
| expm1: https://www.johndcook.com/blog/cpp_expm1/
|
| And (as pointed in the above) if you're worried about the
| slowness of it, just Taylor expand it to x+x2/2.
|
| Finally, unless division is too costly, do: a =
| lerp(a, B, -expm1(delta / -T))
|
| Where T is the "time constant" (which you can intuitively
| express in time units, like seconds):
| https://en.wikipedia.org/wiki/Exponential_smoothing#Time_con...
|
| It's not the half-life (sorry) but it's still a lot more
| intuitive as a parameter.
| ux wrote:
| That's some very good recommendations you made here. I'm
| adding all 3 at the end, thank you.
| BoingBoomTschak wrote:
| Don't most modern video games run a physics thread at fixed rate
| in addition to the rendering one?
|
| I remember Quake 3 still having that issue, but that was in
| '99...
| nightowl_games wrote:
| Game dev here. Hardly any serious game developer uses lerp like
| that. I prefer a quadratic friction when I write custom friction,
| ie: a constant force away from velocity, and simply ensure it
| doesn't go past the zero point. More controllable. Box2Ds
| friction uses something like v = v * 1/(1+damping*delta_time),
| which is a good method as well.
|
| Keep in mind it's best practice to run your game logic at a
| constant update rate and render an interpolated state between the
| current and previous game logic frame, meaning that if your game
| logic is frame rate dependent, you can still run it smoothly on
| any monitor.
| 05 wrote:
| > run your game logic at a constant update rate and render an
| interpolated state between the current and previous game logic
| frame
|
| But if graphics frame rate is higher you won't be able to
| interpolate until the next logic frame is ready, - wouldn't
| that increase latency?
| marcosdumay wrote:
| It will keep latency constant, at right the amount you tested
| the game with.
| stephc_int13 wrote:
| Constant update rate is a must, and can even be tweaked to
| minimize input latency if you are using a custom engine.
|
| Using two frames to interpolate at render time is adding one
| frame of latency.
|
| It is possible to do it on a single frame, extrapolating
| instead of interpolating, but you have to use a simple but
| uncommon trick to make it robust.
|
| The latency gain is not a full frame but some sizeable fraction
| of a frame, I think it is worth it for some games.
| bschwindHN wrote:
| What is the simple but uncommon trick?
| bavell wrote:
| Some sort of Kalman-esque algo?
|
| https://en.wikipedia.org/wiki/Kalman_filter
| omoikane wrote:
| All the frame rates in this post appears to refer to physics
| frame rates, but Godot makes the distinction between physics and
| display frame rates, and have separate callbacks for each:
|
| https://docs.godotengine.org/en/stable/tutorials/best_practi...
|
| Because physics frame rate is fixed (configured under project
| settings), I suspect developers would be able to get away with
| using the common lerp() formula and not having to worry about
| varying (display) frame rates.
| refulgentis wrote:
| I was bit confused how a formula that depends on a constant frame
| rate works with variable refresh rate. Then the author commented
| that you don't need to calculate the quantity that depends on
| frame rate in code. https://news.ycombinator.com/item?id=40401211
|
| I'm really lost, but alas have ~0 experience with 3D about 15
| years into a career.
|
| Ignoring variable frame rate: 1. Doesn't the frame rate depend on
| the display hardware?
|
| 2. Can you know the frame rate at runtime?
|
| Variable frame rate: 3. What quantity do you use for frame rate
| for variable frame rates?
___________________________________________________________________
(page generated 2024-05-19 23:02 UTC)