Timestepping

[phenomLi]

一些感慨

从开始接触编程到现在，我有一个很强烈的感受就是：当初开始学习的技术，遇到不懂的地方，只要百度一下就能出来一大堆资料，文章和教程，能很快速地解决问题。但是之后发现若向着某个方向越往深走，你能找到的资料就越少，可能要解决的问题只在某个英文文章提了一点，又在某个中文论坛涉及到一两句，你想要窥探整个真相的全貌，就只能靠自己去东拼西凑收集整理理解，但是往往还是触碰不到你想要知道的那个“点”。到最后甚至有些问题只出现在英文论文里，如果不想看英文论文，就只能去GitHub啃源码了，但是说实话啃源码是最痛苦的。

所以说为什么入门是最简单的，因为前人已经帮你开好路填好坑了，你只要照着走就行。到了鲜有人涉及的地方，就要靠自己去摸索了。所以先驱者总是牛逼的。

Timestepping是什么

物理引擎是以离散的间隔时间显示的，简单来说物理引擎就是一个大型循环器，每次循环进行一次物理模拟，每两次循环的时间间隔就是离散的时间间隔。

每次进行一次循环，我们称之为一次Timestepping（有些物理引擎也叫runner或者timer），每进行一次Timestepping称为一帧。这里不是我装逼非要用英文，是因为他这个词我找不到对应的中文翻译，“时间步”？但总感觉怪怪的，像失去了灵魂。下面我一律用Timestepping。

Timestepping之于物理引擎就像血液之于人类一样重要，物理引擎能跑起来就是因为它。通常一次Timestepping只干两件事：更新物理数据（updatePhysics）和渲染（render）。其中updatePhysics就是常说的模拟，是纯计算的阶段，也是最重要的阶段。而render便是将结果可视化的过程。render阶段往往不太重要，很多纯计算的物理引擎都不包含render部分，需要用户自己编写render器。render阶段往往比updatePhysics更耗时。

设计好Timestepping里面的时间分配和调度十分重要，这关系到物理引擎的性能，精确性和稳定性。

设计Timestepping

接下来我会一步步示范如何设计一个稳定的Timestepping。

首先，我们需要先设定好物理引擎的步长（dt），通常是1/60。

const dt = 1/60;

我们需要一种方法来确保我们的物理引擎只在经过特定时间后才运行一次，使用固定的dt值实际上会使物理引擎具有确定性，这被称为固定时间步长（fixed dt）。确定性物理引擎总是在每次运行时做完全相同的事情，前提是给出相同的输入。这点非常重要，因为物理引擎本质也是一个纯函数，给定一个固定输入必定要得固定输出，同样这对于调试物理引擎也很重要，为了精确定位错误，物理引擎的行为需要保持一致。

之后我们就可以写出我们的最简单的Timestepping了：

function timeStepping() {
    // 更新物理
    updatePhysics(dt);
    // 渲染
    render();
}

也许你会说：r u kidding me？这么简单？没错，这就是最基本的框架，该有的两步都有了，而且能用我不骗你（我毕设就是这样干的，能跑起来，就是不稳定）。当然这样有个严重的问题：

如图，timeStepping函数每帧只执行一次updatePhysics和render：

在连续多帧的情况下，一帧对应一次updatePhysics，精度太低，容易造成物理引擎不稳定：

接下我们进行改进：我们记录每帧所需要的时间，根据这个时间，增加updatePhysics的迭代次数，提高精度：

    // 每帧的开始时间
let frameStart = getCurrentTime(),
    // 一帧的长度
    frameDuration = 0,
    // 当前时间
    currentTime = 0;

function timeStepping() {
    // 获取当前时间
    currentTime = getCurrentTime();
    // 计算上一帧长度
    frameDuration = currentTime - frameStart;
    // 更新帧开始时间
    frameStart = currentTime;

    // 根据上一帧长度，按照dt时间更新物理
    while(frameDuration >= dt) {
        // 更新物理
        updatePhysics(dt);
        frameDuration -= dt;
    }
    // 渲染
    render();
}

我们记录上一帧的长度，从frameDuration中取出离散的dt大小的时间块更新物理，直到帧长度大小小于dt。这可以确保传递给物理引擎的dt完全相同。getCurrentTime函数只是伪代码，这取决于你所使用的语言。

但是这同样也有个问题：frameDuration不一定都是dt的倍数，这样通常会导致updatePhysics完成后，剩下的小于一个dt的frameDuration就被浪费了。我们可以引入一个 时间累加器（accumulator） 来解决这个问题。

    // 每帧的开始时间
let frameStart = getCurrentTime(),
    // 一帧的长度
    frameDuration = 0,
    // 当前时间
    currentTime = 0,
    // 时间累加器
    accumulator = 0;

function timeStepping() {
    // 获取当前时间
    currentTime = getCurrentTime();
    // 计算上一帧长度
    frameDuration = currentTime - frameStart;
    // 更新帧开始时间
    frameStart = currentTime;
    // 加到时间累加器
    accumulator += frameDuration;

    // 根据累加器长度，按照dt时间更新物理
    while(accumulator >= dt) {
        // 更新物理
        updatePhysics(dt);
        accumulator -= dt;
    }
    // 渲染
    render();
}

现在所有的updatePhysics都只会消耗accumulator，小于dt的时间会积累起来不会被浪费掉（但是这样也会造成问题，之后会讲到）。

但是这样子一个更加致命的问题来了：现在 updatePhysics的时间 = 上一帧的长度，而 一帧的长度 = updatePhysics的时间 + render的时间。这样会导致每一帧花费的时间越来越长：

这就是所谓的死亡螺旋（spiral of death）。如果这个问题没有解决，物理引擎很快就会崩溃。

要解决这个问题，我们可以限制accumulator的最大值：

    // 每帧的开始时间
let frameStart = getCurrentTime(),
    // 一帧的长度
    frameDuration = 0,
    // 当前时间
    currentTime = 0,
    // 时间累加器
    accumulator = 0;

function timeStepping() {
    // 获取当前时间
    currentTime = getCurrentTime();
    // 计算上一帧长度
    frameDuration = currentTime - frameStart;
    // 更新帧开始时间
    frameStart = currentTime;
    // 加到时间累加器
    accumulator += frameDuration;

    // 限制时间累加器
    if(accumulator > 0.2)
        accumulator = 0.2

    // 根据累加器长度，按照dt时间更新物理
    while(accumulator >= dt) {
        // 更新物理
        updatePhysics(dt);
        accumulator -= dt;
    }
    // 渲染
    render();
}

现在看起来很完美了，但是还是有一个潜在的问题（问题真多。。）：

上面提到，Timestepping每次从accumulator中提取一个dt块，直到accumulator小于dt，这时accumulator会有一点剩余时间会被积累起来。现在假设accumulator每帧都剩下了1/5个dt，那么在第六帧，由于accumulator的积累，物理引擎将会比之前帧执行更多次updatePhysics，这将导致一次微小的渲染抖动。

虽然这是个小问题，但是我们一样可以解决，思路就是利用线性插值（linear interpolation）。什么是线性插值？

假设我们已知坐标 (x0, y0) 与 (x1, y1),要得到 [x0, x1] 区间内某一位置x在直线上的值。如图示：

根据上图我们不难看出有：

我们将这个比值记为α，即插值系数：

这个系数就是从x0到x的距离与从x0到x1距离的比值。而由于x已知，我们可以整理得到y的方表达式为：

回到我们的Timestepping上来。利用线性插值，我们可以在两个不同的时间间隔之间插入（近似）渲染，即渲染两个不同物理更新之间的状态：

    // 每帧的开始时间
let frameStart = getCurrentTime(),
    // 一帧的长度
    frameDuration = 0,
    // 当前时间
    currentTime = 0,
    // 时间累加器
    accumulator = 0，
    // 上一次渲染的时间
    prevRenderTime = 0,
    // 当前渲染的时间
    curRenderTime = 0,
    // 插值系数
    alpha = 0;

function timeStepping() {
    // 获取当前时间
    currentTime = getCurrentTime();
    // 计算上一帧长度
    frameDuration = currentTime - frameStart;
    // 更新帧开始时间
    frameStart = currentTime;
    // 加到时间累加器
    accumulator += frameDuration;

    // 限制时间累加器
    if(accumulator > 0.2)
        accumulator = 0.2

    // 根据累加器长度，按照dt时间更新物理
    while(accumulator >= dt) {
        // 更新物理
        updatePhysics(dt);
        accumulator -= dt;
    }

    // 计算插值系数
    alpha = accumulator/dt;

    // 线性插值
    curRenderTime = prevRenderTime*alpha + curRenderTime*(1 - alpha);

    // 渲染
    render(curRenderTime);

    // 更新上一次渲染的时间
    prevRenderTime = curRenderTime;
}

这时渲染可以以与物理引擎不同的速度运行，这是物理引擎对剩余accumulator的优雅的处理。

到目前位置，Timestepping的设计就基本结束了，我们造出了一个可用的Timestepping，它有一定精度，能优雅处理渲染。但是请注意，这不是唯一的设计，还有其他很多种Timestepping的设计方案，如matter.js用的是一种同时支持固定dt和动态dt的方案，这种方案更简复杂，但我所介绍的是最简单通用的一种。