游戏编程模式笔记——第十八章 脏标记模式

“将工作推迟到必要时进行以避免不必要的工作。”

动机

许多游戏都有一个称之为场景图的东西。这是一个庞大的数据结构，包含了游戏世界中所有的物体。渲染引擎使用它来决定将物体绘制到屏幕的什么地方。
许多场景图是分层的。场景中的一个物体会绑定在一个父物体上。在这种情况下，它的变换就依赖于其父物体的位置，而不是游戏世界中的一个绝对位置。
想象我们的游戏中有一艘海盗船在海上。桅杆的顶部是一个瞭望塔，一个海盗靠在这个瞭望塔上，抓在海盗肩膀上的是一只鹦鹉。这艘船的局部变换标记了它在海中的位置。瞭望塔的变换标记了它在船上的位置，等等。
这样，当一个父物体移动时，它的子物体也会随之变动。如果在船移动时我们必须手动调整船上所有物体的变换来防止相对滑动，那会是一件很头疼的事情。
但是要真的将海盗绘制到屏幕上，我们需要知道它在世界中的绝对位置。我们将相对于父物体的变换称为这个物体的“局部变换”。为了渲染一个物体，我们需要知道它的“世界变换”。

局部变换和世界变换

计算一个物体的世界变换是相当直观的——只要从根节点沿着它的父链将变换组合起来就行。
鹦鹉世界变换 = 船的局部变换 x 瞭望塔的局部变换 x 海盗的局部变换 x 鹦鹉的局部变换

我们每帧都需要世界中的每个物体的世界变换，这会成为代码中影响性能的关键所在，保持它们及时更新是棘手的，因为当一个父物体移动，这会影响它自己和它所有的子物体等的世界变化。
最简单的途径是在渲染的过程中计算变换。每一帧递归地遍历场景图，计算它们的世界变换并立刻绘制它。
但是这是对我们宝贵的CPU资源是一种可怕的浪费。许多物体并不是每一帧都移动，但每一帧都要重计算它们的世界变换是一种多大的浪费。

缓存世界变换

一个明显的解决办法是将它“缓存”起来。这看起来很美好，当一个物体确实移动了，简单的方法就是立即刷新它的世界变换。但是不要忘了继承链！当一个父物体移动时，我们需要重计算它的世界变换并递归地计算它所有子物体的世界变换。问题的关键是一个世界变换可能依赖于好几个局部变换。由于我们再每个这些变换时都立刻重计算，所以最后当一帧内有好几个关联的局部变换改变时，我们就将这个变换重新计算了好多遍。

延时重算

我们通过将修改局部变换和更新世界变换解耦来解决这个问题。这让我们在单次渲染中修改多个局部变换，然后在所有变动完成之后，在实际渲染器使用之前仅需要计算一次世界变换。
要做到这点，我们为每个物体添加一个”flag”。”flag”和”bit”在编程中是同义词——它们都表示单个小单元数据，能够储存两种状态中的一个。我们称之为”true”和false”，有时也叫”set”和”cleared”。我会交叉地使用它们。
我们在局部变换改动时设置它。当我们需要这个物体的世界变换时，我们检查这个flag。如果它标记为”set”了，我们计算这个世界变换，然后将这个flag置为”clear”。这个flag代表，”这个世界变换是不是过期了？”由于某些原因，传统上这个”过期的”被称作”脏的”。也就是”脏标记”，”Dirty bit”也是这个模式常见的名字。但是我想我会坚持使用那种看起来没那么”污秽”的名字。
只需要一个简单的位数据，这个模式为我们做了不少事：

• 它将父链上物体的多个局部变换的改动分解为每个物体的一次重计算。
• 它避免了没有移动的物体的重计算。
• 一个额外的好处：如果一个物体在渲染之前移除了，那就根本不用计算它的世界变换。

脏标记模式

一组原始数据随时间变化。一组衍生数据经过一些代价昂贵的操作由这些数据确定。一个脏标记跟踪这个衍生数据是否和原始数据同步。它在原始数据改变时被设置。如果它被设置了，那么当需要衍生数据时，它们就会被重新计算并且标记被清楚。否则就使用缓存的数据。

使用情境

相对于其他模式，这个模式解决一个相当特定的问题。同时，就像大多数优化那样，仅当性能问题严重到值得增加代码复杂度时才使用它。
脏位标记涉及两个关键词:”计算”和”同步”。在这两种情况下，处理原始数据到衍生数据的过程在时间或其他方面会有很大的开销。
当使用这个模式做同步时，派生数据通常在别的地方——也许在磁盘上，也许在网络上的其他机器上——光是简单地把它从A移到B就很费力。
这里也有些其他的要求：

• 原始数据的修改次数比衍生数据的使用次数多。衍生数据在使用之前会被接下来的原始数据改动而失效，这个模式通过避免处理这些操作来运作。如果你再每次改动原始数据时都立刻需要衍生数据，那么这个模式就没有效果。
• 递增地更新数据十分困难。我们假设游戏的小船能运载众多的战利品。我们需要知道所有东西的总重量。我们能够使用这个模式，为总量设置一个脏标记。每当我们增加或者减少战利品时，我们设置这个标记。当我们需要总量时，我们将所有战利品的重量加起来并清除标记。但是一个更简单的方法是保持一个动态的总量。当我们增加或者减少物品时，就从总量上增加或者减去这个物体的重量。像这样保持衍生数据更新时，这种方法要比使用这个模式要好。

这些要求听起来让人觉得脏标记很少有适合使用的时候，但是你总能发现它能帮上忙的地方。

使用须知

即使当你有相当的自信认为这个模式十分适用，这里还是有一些小的瑕疵会让你感到不便。

延时太长会有代价

这个模式把某些耗时的工作推迟到真正需要时才进行，而到有需要时，往往刻不容缓。但是，我们使用这个模式的原因是计算出结果的过程很慢。
当工作量大到需要一个能够察觉时间才能完成时，如果游戏直到玩家想要看到结果时才开始计算，这会导致一个不友好的视觉卡顿。
另外一个延时的问题是如果某个东西出错，你可能完全无法工作。当你将状态保存在一个更加持久化的形式中时，使用这个模式，你问题会尤其突出。就像文本编辑器，许多程序都仅在文档关闭或者程序退出时才会自动存盘。如果你意外的将电源线揽踢出，那么你的工作就付之东流了。

必须保证每次状态改动时都设置脏标记

当你获取缓存数据时，棘手的问题是缓存失效——当缓存和原始数据不同步时，什么都不正确了。在这个模式中，它意味着当任何原始数据变动时，都要设置脏标记。
在一个地方忘记了，你的程序就会不正确地使用失效的衍生数据。这会导致玩家的困惑和十分难以追踪的bug。当你使用这个模式时，你需要小心，在任何改动原始数据的地方都要设置脏标记。
一个解决问题的方法是将原始数据的改动封装起来。任何可能的变动都通过单一API入口来修改，你可以在这里设置脏标记，并且不用担心会有遗漏。

必须在内存中保存上次的衍生数据

这个模式会在空间和时间上做平衡。当返回内存中之前计算的数据时，会避免对未修改数据的重计算，这在内存便宜而计算费时的情况下是合算的。当内存比时间更加宝贵时，在需要时计算会比较好。

示例代码

class Transform
{
public:
    static Transform origin();
    
    Transform combine(Transform& other);
};

这里我需要的唯一操作就是”combine()”，这样我们可以通过组合父链中所有的局部变换来得到它的世界变换。它还有一个方法用来得到一个“原始”的变换——一个简单的单位矩阵表示没有移动、旋转或者缩放。
接下来我们来定义场景图中的物体类。这是我们运用这个模式之前的基础。

class GraphNode
{
public:
    GraphNode(Mesh* mesh) : mesh_(mesh), local_(Transform::orign()) {}
private:
    Transform local_;
    Mesh* mesh_;

    GraphNode* children_[MAX_CHILDREN];
    Int numChildren;
};

每一个节点包含一个局部变换，描述它相对于父物体的位置。它还有一个mesh，代表这个物体的真正图元（我们允许”mesh_”为”NULL”来处理只是为了组合子物体的不可见节点）。最后每个节点都包含一个可能为空的子物体集合。
有了这个，一个“场景图”是一个单一的根节点”GraphNode”，它的子节点(子子节点，等等)就是世界中的所有物体。

GraphNode* graph_ = new GraphNode(NULL);
// Add children to root graph node...

为了绘制一个场景图，我们需要做的就是遍历节点树，从根节点开始，通过正确的世界变换为每个节点图元调用下面的方法。

void renderMesh(Mesh* mesh, Transform transform);

未优化的遍历

我们通过基本的遍历并动态计算世界坐标来渲染场景图。它不会进行优化，但是却很简单。我们为“GraphNode”添加一个新方法。

void GraphNode::render(Transform parentWorld)
{
    Transform world = local_.combine(parentWorld);
    if(mesh_) renderMesh(mesh_, world);
    
    for(int i = 0; i < numChildren_; i++)
    {
        children_[i]->render(world);
    }
}

这样为了绘制整个场景图，我们从空根节点开始渲染就可以了:

graph_->render(Transform::orign());

让我们“脏”起来

这份代码做了正确的操作——在正确的地方渲染图元——但并不高效。它每帧都在每个”node”上调用”local_.combine(parentWorld)”。让我们看脏标记模式是如何修正这点的。

class GraphNode
{
public:
    GraphNode(Mesh* mesh) : mesh_(mesh), local_(Transform::origin()),dirty_(true) {}
    // Other methods...

private:
    Transform world_;
    bool dirty_;
    // Other fields...
};

“world“成员缓存了上次计算了的世界变换，”dirty“成员就是脏标记。注意，这个标记用”true”初始化。当我们创建一个新节点时，我们没有计算过它的世界变换。
我们需要这个模式的唯一理由是物体能够移动。

void GraphNode::setTransform(Transform local)
{
    local_ = local;
    dirty_ = true;
}

这里有一个微妙的假设，if检查要比矩阵乘法快。然而在现代CPU上可能会导致分支预测错误，数据局部性模式可以帮助我们避免这些问题。
当一个父节点移动时，它所有的子节点的世界坐标都失效了。但是这里，我们不设置它们的脏标记。我们能做到这点，但是这需要递归而且缓慢。相反我们在渲染时做点聪明的事。

void GraphNode::render(Transform parentWorld, bool dirty)
{
    dirty |= dirty_;
    if(dirty)
    {
        world_ = local_.combine(parentWorld);
        dirty_ = false;
    }
    if( mesh_ ) renderMesh(mesh_, world_);
    for(int i = 0; i < numChildren; i++)
    {
        children_[i]->render(world_, dirty);
    }
}

这里的技巧就是”dirty”参数。如果父链中它之上的任何物体标记为脏，则它被置为”true”。在我们递归的时候用相同的方式通过“parentWorld”渐进地更新世界变换。”dirty”参数跟踪父链变换是否改变。
最终结果就是我们想要的：修改一个节点的局部变换只是几条赋值语句，渲染世界时只计算了自上一帧以来最少的变动的世界变换。
注意，这里技巧能奏效是因为”render()”是”GraphNode”中唯一需要实时世界变换的操作。如果其他操作访问它，则我们需要做一些不同的操作。

设计抉择

这个模式是相当特定的，所以只需要注意几点。

何时清除脏标记

当需要计算结果时

• 当计算结果不使用时，它完全避免了计算。当原始数据变动的频率远大于衍生数据访问的频率时，优化效果更显著。
• 如果计算十分耗时，会造成明显的卡顿。把计算工作推迟到玩家需要查看结果时才做会影响游戏体验。这在计算足够快的情况下没什么问题，但是一旦计算十分耗时，则最好提前开始计算。

在精心设定的检查点
有时，在游戏的过程中有一个时间点十分适合做延时计算工作。比如游戏存档。

• 这些工作并不影响用户体验。不同于之前的选项，当游戏忙于处理时你可以通过其他东西分散玩家的注意力。
• 当工作执行时，你失去了控制权。这和之前一点有些相反。在处理时，你能轻微地控制，保证游戏优雅的处理。

你“不能确保”玩家真正到达检查点，或者达到任何你设定的标准。如果他们迷失了或者游戏进入了奇怪的状态，你可以将预期的操作进一步延迟。

在后台
通常，你可以在变动的时候启动一个固定的计时器，并在计时器到达时处理之间的所有变动。

• 你可以调整工作执行的频率。通过调整定时器的间隔，你可以按照你想要的频率进行处理。
• 你可以做更多冗余的工作。如果在定时器期间原始状态的改动很少，那么你最终可以处理大部分没有修改的数据。
• 需要支持异步操作。在后台处理数据意味着玩家可以同时做其他事情。这意味着你需要线程或者其他并发支持，以便能够在游戏进行时处理数据。
  因为玩家有可能同时与你现在处理的原始数据交互，所以你也要考虑并行数据的安全性。

脏标记追踪的粒度多大

想象一下我们的海盗游戏允许玩家建造和定制他们的海盗船。船会自动线上保存以便玩家在离线之后能恢复。我们使用脏标记来决定船的哪些甲板被改动了并需要发送到服务器。每一份我们发送给服务器的数据包含了一些船的改动数据和一份元数据，该元数据描述这份改动是在什么地方发生的。
更精细的粒度
你将甲板上的每一份小木块加上脏标记。

• 你只需要处理真正变动了的数据，你将船的真正变动的木块发送给服务器。

更粗糙的粒度
另外，我们可以为每一个甲板关联一个脏标记。在它之上的每份改动将整个甲板标记为脏。

• 你最终需要处理未变动的数据。当在甲板上放置一个酒桶时，你需要把整个甲板上的数据发送给服务器。
• 存储脏标记消耗更少的内存。添加10个酒桶在甲板上只需要一个位来跟踪他们。
• 固定开销花费的时间要更少。当处理修改后的数据时，通常有一套固定的流程要预先处理这些数据。在这个例子中，就是标识船上哪些是改动了的数据。处理块越大，处理块越小，也意味着通用开支越少。