Lol Engine - Blog
http://lolengine.net/blog
The Lol Engine Blogen-USTrac 1.2.2Lol Engine/chrome/site/logo.png
http://lolengine.net/blog
Damping with delta-timesamSun, 03 May 2015 00:24:03 GMT
http://lolengine.net/blog/2015/05/03/damping-with-delta-time
http://lolengine.net/blog/2015/05/03/damping-with-delta-time<p>
Just a quick tip on how to convert usual damping code to something framerate-independent.
</p>
<p>
Most of us have probably, at some point, written code resembling this:
</p>
<div class="wiki-code"><div class="code"><pre>// Perform velocity damping
velocity -= velocity * 0.01f;
</pre></div></div><p>
… or probably the more correct:
</p>
<div class="wiki-code"><div class="code"><pre>// Per-second damping coefficient
float const D = 10.0f;
// Damp velocity according to timestep
velocity -= velocity * D * delta_time;
</pre></div></div><p>
Yet this is not fully framerate-independent; results are slightly different at 30fps and 60fps, and more importantly, spikes in the framerate cause lots of weird artifacts, causing developers to attempt to fix the situation by clamping <code>delta_time</code>, which is not ideal.
</p>
<h2 id="Theexponentiationmethod">The exponentiation method</h2>
<p>
Here is one way to fix it: assume that the code works correctly at 60 fps. This means that each frame, <code>velocity</code> is effectively multiplied by <code>1 - D / 60</code>.
</p>
<p>
After one second, <em>i.e.</em> 60 frames, <code>velocity</code> has been multiplied by <code>(1 - D / 60) ^ 60</code>.
</p>
<p>
After two seconds, it has been multiplied by <code>(1 - D / 60) ^ (60 * 2)</code>.
</p>
<p>
After <code>N</code> seconds, it has been multiplied by <code>(1 - D / 60) ^ (60 * N)</code>.
</p>
<p>
So, there, we have a formula that tells us what happens after <code>N</code> seconds, and it’s a continuous function. We can therefore choose <code>N</code> as we like, and especially <code>N = delta_time</code>:
</p>
<div class="wiki-code"><div class="code"><pre>// Per-second damping coefficient
float const D = 10.0f;
// Damp velocity (framerate-independent)
velocity *= pow(1.f - D / 60.f, 60.f * delta_time);
</pre></div></div><p>
Which can be conveniently rewritten as:
</p>
<div class="wiki-code"><div class="code"><pre>// Per-second damping coefficient
float const D = 10.0f;
// Exponentiation base for velocity damping
float const D2 = pow(1.f - D / 60.f, 60.f);
// Damp velocity (framerate-independent)
velocity *= pow(D2, delta_time);
</pre></div></div><h2 id="Usewithlerp">Use with lerp</h2>
<p>
The same method can be adapted to uses of linear interpolation such as this one:
</p>
<div class="wiki-code"><div class="code"><pre>// Perform velocity damping
velocity = lerp(velocity, target_velocity, K * delta_time);
</pre></div></div><p>
Which we replace with:
</p>
<div class="wiki-code"><div class="code"><pre>// Damp velocity (framerate-independent)
velocity = lerp(velocity, target_velocity,
1.f - pow(1.f - K / 60.f, 60.f * delta_time));
</pre></div></div>mathstipcodephysicsUnderstanding basic motion calculations in games: Euler vs. VerletsamTue, 13 Dec 2011 23:39:41 GMT
http://lolengine.net/blog/2011/12/14/understanding-motion-in-games
http://lolengine.net/blog/2011/12/14/understanding-motion-in-games<p>
During the past month, I have found myself in the position of having to explain the contents of this article to six different persons, either at work or over the Internet. Though there are a lot of articles on the subject, it’s still as if almost everyone gets it wrong. I was still polishing this article when I had the opportunity to explain it <a class="ext-link" href="http://gamedev.stackexchange.com/q/21037/5864"><span class="icon"></span>a seventh time</a>.
</p>
<p>
And two days ago a coworker told me the source code of a certain framework disagreed with me… The kind of framework that probably has three NDAs preventing me from even thinking about it.
</p>
<p>
Well that framework got it <strong>wrong</strong>, too. So now I’m mad at the entire world for no rational reason other than the ever occurring realisation of the amount of wrong out there, and this article is but a catharsis to deal with my uncontrollable rage.
</p>
<h2 id="Asimpleexample">A simple example</h2>
<p>
Imagine a particle with position <code>Pos</code> and velocity <code>Vel</code> affected by acceleration <code>Accel</code>. Let’s say for the moment that the acceleration is constant. This is the case when only gravity is present.
</p>
<p>
A typical game engine loop will update position with regards to a <strong>timestep</strong> (often the duration of a frame) using the following method, known as <strong>Euler integration</strong>:
</p>
<div class="wiki-code"><div class="code"><pre>Particle::Update(float dt)
{
Accel = vec3(0, 0, -9.81); /* Constant acceleration: gravity */
Vel = Vel + Accel * dt; /* New, timestep-corrected velocity */
Pos = Pos + Vel * dt; /* New, timestep-corrected position */
}
</pre></div></div><p>
This comes directly from the <a class="ext-link" href="http://en.wikipedia.org/wiki/Acceleration"><span class="icon"></span>definition of acceleration</a>:
</p>
<img src="http://lolengine.net/tracmath/00005492b5e2abc9714eda7a54cac6863bda1944.png" alt="\[a(t) = \frac{\mathrm{d}}{\mathrm{d}t}v(t)\]
\[v(t) = \frac{\mathrm{d}}{\mathrm{d}t}p(t)\]
" /><p>
Putting these two differential equations into Euler integration gives us the above code.
</p>
<h2 id="Measuringaccuracy">Measuring accuracy</h2>
<p>
Typical particle trajectories would look a bit like this:
</p>
<blockquote>
<p>
<img src="http://lolengine.net/raw-attachment/blog/2011/12/14/understanding-motion-in-games/euler-integration.png" crossorigin="anonymous" />
</p>
</blockquote>
<p>
These are three runs of the above simulation with the same initial values.
</p>
<ul><li>once with maximum accuracy,
</li><li>once at 60 frames per second,
</li><li>once at 30 frames per second.
</li></ul><p>
You can notice the <strong>slight inaccuracy</strong> in the trajectories.
</p>
<p>
You may think…
</p>
<blockquote>
<p>
<img src="http://lolengine.net/raw-attachment/blog/2011/12/14/understanding-motion-in-games/derp.png" style="float:left" crossorigin="anonymous" /> “Oh, it could be worse; it’s just the expected inaccuracy with different framerate values.”
</p>
</blockquote>
<p>
</p><div style="clear:both;"></div><p>
</p>
<p>
Well, no.
</p>
<p>
<strong>Just… no.</strong>
</p>
<p>
<img src="http://lolengine.net/raw-attachment/blog/2011/12/14/understanding-motion-in-games/no-rage.png" style="float:right" crossorigin="anonymous" />
</p>
<div style="text-transform: uppercase; font-weight: bold; font-size: 1.1em;" class="wikipage"><p>
If you are updating positions this way and you do not have a really good reason for doing so then either you or the person who taught you is a fucking idiot and should not have been allowed to write so-called physics code in the first place and I most certainly hope to humbly bestow enlightenment upon you in the form of a massive cluebat and don’t you dare stop reading this sentence before I’m finished.
</p>
</div><p>
</p><div style="clear:both;"></div><p>
</p>
<h2 id="Whythisiswrong">Why this is wrong</h2>
<p>
When doing <a class="ext-link" href="http://en.wikipedia.org/wiki/Kinematics"><span class="icon"></span>kinematics</a>, computing position from acceleration is an <strong>integration</strong> process. First you integrate <strong>acceleration</strong> with respect to <strong>time</strong> to get <strong>velocity</strong>, then you integrate <strong>velocity</strong> to get <strong>position</strong>.
</p>
<img src="http://lolengine.net/tracmath/731cc93e3ef1153741555f5d34eea544b63a07fc.png" alt="\[v(t) = \int_0^t a(t)\,\mathrm{d}t\]
\[p(t) = \int_0^t v(t)\,\mathrm{d}t\]
" /><p>
The integral of a function can be seen as the <strong>area</strong> below its curve. So, how do you properly get the integral of our velocity between <code>t</code> and <code>t + dt</code>, <em>ie.</em> the green area below?
</p>
<p>
<img src="http://lolengine.net/raw-attachment/blog/2011/12/14/understanding-motion-in-games/accurate-integral.png" crossorigin="anonymous" />
</p>
<p>
It’s <strong>not</strong> by doing <code>new_velocity * dt</code> (left image).
</p>
<p>
It’s not by doing <code>old_velocity * dt</code> either (middle image).
</p>
<p>
It’s obviously by doing <code>(old_velocity + new_velocity) * 0.5 * dt</code> (right image).
</p>
<h2 id="Andnowforthecorrectcode">And now for the correct code</h2>
<p>
This is what the update method should look like. It’s called <strong>Velocity Verlet integration</strong> (not strictly the same as <em>Verlet integration</em>, but with a similar error order) and it <strong>always gives the perfect, exact position</strong> of the particle in the case of constant acceleration, even with the nastiest framerate you can think of. Even at two frames per second.
</p>
<div class="wiki-code"><div class="code"><pre>Particle::Update(float dt)
{
Accel = vec3(0, 0, -9.81);
vec3 OldVel = Vel;
Vel = Vel + Accel * dt;
Pos = Pos + (OldVel + Vel) * 0.5 * dt;
}
</pre></div></div><p>
And the resulting trajectories at different framerates:
</p>
<blockquote>
<p>
<img src="http://lolengine.net/raw-attachment/blog/2011/12/14/understanding-motion-in-games/verlet-integration.png" crossorigin="anonymous" />
</p>
</blockquote>
<h2 id="Furtherreadings">Further readings</h2>
<blockquote>
<p>
<img src="http://lolengine.net/raw-attachment/blog/2011/12/14/understanding-motion-in-games/derp.png" style="float:left" crossorigin="anonymous" /> “Oh wow thank you. But what if acceleration is <em>not</em> constant, like in real life?”
</p>
</blockquote>
<p>
</p><div style="clear:both;"></div><p>
</p>
<p>
Well I am glad you asked.
</p>
<p>
<a class="ext-link" href="http://en.wikipedia.org/wiki/Euler_method"><span class="icon"></span>Euler integration</a> and <a class="ext-link" href="http://en.wikipedia.org/wiki/Verlet_integration"><span class="icon"></span>Verlet integration</a> are part of a family of iterative methods known as the <a class="ext-link" href="http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods"><span class="icon"></span>Runge-Kutta methods</a>, respectively of first order and second order. There are many more for you to discover and study.
</p>
<ul><li>Richard Lord did this nice and instructive <a class="ext-link" href="http://www.richardlord.net/presentations/physics-for-flash-games"><span class="icon"></span>animated presentation</a> about several integration methods.
</li><li>Glenn Fiedler also explains in <a class="ext-link" href="http://gafferongames.com/game-physics/integration-basics/"><span class="icon"></span>this article</a> why idiots use Euler, and provides a nice introduction to RK4 together with source code.
</li><li>Florian Boesch did a <a class="ext-link" href="http://codeflow.org/entries/2010/aug/28/integration-by-example-euler-vs-verlet-vs-runge-kutta/"><span class="icon"></span>thorough coverage</a> of various integration methods for the specific application of gravitation (it is one of the rare cases where Euler seems to actually perform better).
</li></ul><p>
In practice, Verlet will still only give you an approximation of your particle’s position. But it will almost always be a <strong>much better</strong> approximation than Euler. If you need even more accuracy, look at the <a class="ext-link" href="http://mathworld.wolfram.com/Runge-KuttaMethod.html"><span class="icon"></span>fourth-order Runge-Kutta (RK4)</a> method. Your physics will suck a lot less, <em>I guarantee it</em>.
</p>
<h2 id="Acknowledgements">Acknowledgements</h2>
<p>
I would like to thank everyone cited in this article, explicitly or implicitly, as well as the commenters below who spotted mistakes and provided corrections or improvements.
</p>
rantcodephysics