云风的 BLOG

每个可以容纳别的对象的对象，可以在自身拥有一系列的挂接点（一个相对于自身的变换矩阵）。对象都是挂接在另一个对象的挂接点上。挂接点是编辑时产生的静态数据，通常不允许在运行时改变。但对象可以改变自身相对挂接点的矩阵变换。例如，整个场景有一个根节点，所有运行时的对象都是挂接在这个根节点的默认挂接点（一个单位矩阵）上。这样，每个对象都是由一系列的 slot matrix + local matrix 决定最终的 world matrix 。

最终，我们用来描述对象在场景中的空间信息的组件 transform ，包含了这么一些属性：

• world matrix ：最终在世界空间中的矩阵
• base matrix ：父亲自身局部空间中的矩阵
• scale ：自身相对 base matrix 的缩放
• rotation ：自身相对 base matrix 的旋转
• translation ：自身相对 base matrix 的位移
• parent id ：受哪个对象的影响
• slot name ：挂接在哪个挂接点上

其中，world matrix 和 base matrix 都是运行时逐级计算出来的。scale rotation translation 均是可选项，默认就是相对于挂接点的原点：scale 为 1 ，rotation 为不旋转，translation 为 0 。parent id 和 slot name 决定了空间层次信息。

对于可以容纳和影响别的对象的对象，还会有一个编辑时产生的静态数据，记录了每个 slot name 对应的变换矩阵。如果是运行时需要动态调整相对父对象的位置，挂接点可以省略，默认为单位矩阵，相对变换由 SRT 决定；如果运行时固定位置，在编辑时就生成好，那么相对位置记录在 slots 结构中，对象只需要记录 slot name ，而省略 SRT 的值。

slot 的变换矩阵和对象自身的 SRT 分离，增加了这个结构的弹性。我们可以复用 slots 这份静态数据：例如在编辑时生成后层次结构的预制件。然后，运行时还可以通常对对象自身的 SRT 进行调整。去掉 slots 的设计可以进一步简化数据结构，但是，也失去了一些空间和时间上的优化空间，这点，后面会再谈谈。

这里没有记录每个对象的孩子，这给计算每个对象最终的 world matrix 造成了一定的困难。最为粗暴的方法是，渲染每个对象的时候，依据 parent id 和 slot name 向上回溯每级对象，把矩阵乘起来。不过，相对于渲染的高频率，其实修改场景中对象的 SRT 是相当低频的，每次修改的数量也远远少于场景对象的总数。为了低频低量的操作，每个渲染帧对所有的对象进行复杂的处理无疑是很浪费的。为了避免中间节点的重复计算，我们还需要把当前帧计算过的节点做上标记，这也增加了数据结构的复杂度，过多的标记判断是省不掉的开销。

传统上还有另一种方法减少遍历。那就是在修改一个对象时，将所有的孩子都置入更新集。那么，每帧只需要遍历受影响的对象。不过这依赖数据结构中有孩子的关联信息，我们这次的设计中没有，我也不想加上。况且，我不太喜欢在修改数据时，还有隐式的额外操作（标记孩子）。

我们现在的 ECS 框架有能力遍历出某个类型的组件，以及这类组件中当前帧被修改的子集。但，遍历无法保证次序。而在这个案例里，次序是有必要的。我希望父亲被先处理，因为孩子的空间信息需要利用父亲的计算结果。兄弟之间的次序则不相关。

所以，最直接的方法是先遍历再排序，再依次处理。传统的方法中，在对象中记录下所有的孩子，也正是为了方便确定处理次序。当没有这个直接信息时，我们还是可以做拓扑排序来达到一样的效果：简单的数据结构（只记录父结点） + 独立的算法步骤 （先排序，再遍历平坦的数组）。

我们用 ( parent , id ) 这样一对表达父子关系的 id 来表示一个待处理的对象，把它放入一个数组，可以表示出一组层次结构数据。对这样一组 id 对进行拓扑排序是一个纯粹的算法问题，用 Lua 实现很简单，也可以留到以后用 C 优化一遍。不过需要留意的是，拓扑排序并不算廉价，它的时间复杂度是 O(n + m) 。

为了减少 n 的规模，我们在排序阶段不处理场景中的所有叶子节点。叶子节点全部留到渲染阶段，在渲染前判断父亲的 world matrix 是否改变，来决定自身是否需要重新计算 world matrix 。

对于非叶子节点，我每帧采用如下的算法：

1. 遍历所有被修改过的对象，这些均为一定需要重新计算 world matrix 的，置入更新集。
2. 遍历所有未被修改过的对象，分别设于更新集、待更新集、不变集其中的一个。所有节点均有一个默认归属集合供子节点使用。根节点默认进入不变集，其余节点默认进入待更新集。遍历过程中，根据父节点归于父节点所在集合。即：父节点在不变集，自己就加入不变集；父节点在更新集，自己就加入更新集；父节点未确定，就进入父节点的默认归属集。
3. 对待更新集进行一次拓扑排序。
4. 遍历待更新集，依次检查其父亲是否在更新集内，如果在则把自身加入更新集。由于这次遍历是有序的，所以不会再有遗漏。
5. 对最终的更新集做一次拓扑排序。

注意：这里进行了两次拓扑排序，可能有较大的开销，所以我们可以考虑进一步的优化：

1. 将每帧最终的更新结果保存下来。这是一个排过序的结果。
2. 上面的步骤 1 中，只有当修改过的对象不在上一帧的结果中，才需要做后续步骤。
3. 如果略过了后续步骤，那么更新集使用上一帧保留的集合。但在处理时剔除当前帧不需要变更的对象，但设定一个对象数量阙值，保留一定的对象在这个集合中，不将集合完全清理干净。防止不同的帧交错修改不同的对象。

因为大多数情况下，我们只会修改固定的少量对象的空间信息，大多数对象在场景中都是固定的。所以，一旦易变的对象的处理次序被 cache 下来，接下来的几帧修改的对象都在相同的集合中，这个遍历次序也就被 cache 了下来。也就是说，大多数情况下，只需要做步骤 1 。

至此，我们得到了更新次序，可以循序计算每个对象的 world matrix 。如果当前帧没有重新计算过父亲，且父亲没有更换，那么 base matrix 就可以保持，只需要把 SRT 乘上去，得到 world matrix ；如果父亲在当前帧被重新计算，则需要根据 parent id 和 slot name 重新算出 base matrix 。

最后还有一点优化：

在编辑场景时，一组对象可能构成复杂的空间结构。一旦编辑好，我们可以为这组对象生成一个预制件，并标记为运行期层次结构不可修改。这是一种非常常见的情况。这样，对于预制件来说，内部可以是一颗复杂的有层次的树；但是对外，所有的插槽则是平坦化的。

对于预制件内部的层次树，由于数据是静态的，我们更容易用 C 的数据结构来储存，并用 C 库来做计算。这块，我挑选了成熟的开源骨骼动画库来实现，用和骨骼系统一致的数据结构来表达。然后，我们可以把它作为一个整体放在运行期的场景节点上。这样，运行期的场景树规模要小的多，放在 Lua 中的管理规模就小了很多。更适合用 Lua 弹性管理。