« 让 lua 运行时动态切换操作系统线程 | 返回首页 | 群星的经济系统 »

场景层次结构的管理

今年上半年的时候,就想把我们游戏引擎中场景层次结构管理模块的设计记录一下。每次想写的时候都在做小调整。直到最近,算法和数据结构才稳定下来。今天做一个记录。

游戏里的场景对象,通常以树结构保存。这是因为,每个对象的空间状态,通常都受上一级的某个对象影响。

从管理角度讲,每个对象最好都能知道它可以影响其它哪些对象;且必须知道它被哪个对象影响。所以,这会用到一个典型的树结构。尤其在做编辑器时,树结构还会直接呈现在编辑界面上。不过,我认为在运行时,从父对象遍历到子对象的需求并不是必要的,需要时可以额外记录。从数据上考虑,父亲记住孩子和孩子记住父亲,是重复了同一种关系信息。如果不需要记住孩子的兄弟次序,那么在核心数据结构中,我们只需要让孩子记住父亲就足够了。

去掉冗余信息可以简化数据结构、减少维护成本、避免犯错误。尤其对于 ECS 架构,我希望所有对象都是平坦的,在场景对象组件上,一个 parent id 可以最少的构造出场景的层次结构出来。

每个可以容纳别的对象的对象,可以在自身拥有一系列的挂接点(一个相对于自身的变换矩阵)。对象都是挂接在另一个对象的挂接点上。挂接点是编辑时产生的静态数据,通常不允许在运行时改变。但对象可以改变自身相对挂接点的矩阵变换。例如,整个场景有一个根节点,所有运行时的对象都是挂接在这个根节点的默认挂接点(一个单位矩阵)上。这样,每个对象都是由一系列的 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 弹性管理。

Comments

其实云凤可以参考一下NVIDIA的Scenix
https://developer.nvidia.com/scenix-download
http://on-demand.gputechconf.com/gtc/2013/presentations/S3032-Advanced-Scenegraph-Rendering-Pipeline.pdf
http://on-demand.gputechconf.com/gtc/2015/presentation/S5148-Markus-Tavenrath.pdf
https://github.com/nvpro-pipeline/pipeline
以及Pixar的USD(Universal Scene Description)
https://graphics.pixar.com/usd/docs/index.html

@judadeshu
云大说了,这样的目的是为了让对象都平坦,方便后期管理。
在以前ECS没流行起来之前,大家都用树结构,最后管理还是没那么方便,程序里各种嵌套也很烦。
写底层都有的坏毛病,希望内存对象之类的,都是可预测可管理的。有一种"sir, everything is under control."全局观。

明白了,这个设计是将场景对象的逻辑层级关系(hierarchy)与相对变换(world matrix)进行了分离。这个理解是正确的吗?

如果是正确的,那么下一个问题是,为什么要对场景进行这样的设计呢?

从编辑器使用者的角度来看,Unity那种将两者统一的设计,应该是更符合用户的直观感受的?(即对象的world matrix = parent matrix + local matrix)

任何化简模式都是有一定代价的,个人偏向于记录一下子结点,而不是每次都排序。
如果嫌弃建立双向关系,对系统简介设计有干扰,可以用对系统打Patch的模式,对树建立临时children cache。
再用dirty flag来判断是否需要重新场景里,刷新父子关系。

每个容器都可以有若干的孩子,每个孩子都有一个空间变换。我们可以给它们分别起不同的名字,就是 slot name 。而新的节点是用这个名字绑在上面的。

例如,你有一张桌子,桌子上有个位置可以摆个盘子。这个盘子相对整体的位置就是一个 slot 。运行时摆什么盘子都可以。

这个描述对象之间相对关系的数据结构:若干 slots (name : matrix) 是一组不变的数据,其实就等同于动画系统中的骨骼数据。场景中放很多张桌子,它们也可以共享同一个这个结构。但是不同的桌子却可以摆放不同的盘子。

云风大大好,我想请教一下slot name的设计用意是什么呢?文章中的解释没有看得特别明白。
在我现在的理解中,slot name与parent id好像都是用来构造层级结构的,不知道是我哪个地方理解出了问题?

点赞

对,我搞错了时间复杂度。

拓扑排序的时间复杂度O(n + m)就足够了m是边数,对于一个树来说,m < n。

如何判断兄弟节点之间的层级问题呢

写得好!

我觉得过度的精简, 害怕冗余和犯错, 感觉反而会加大编程的难度和不必要的复杂度

Post a comment

非这个主题相关的留言请到:留言本