层次结构和状态继承
在 blog 上，我写过好几篇关于场景管理模块的树结构的文章。这些也是我这两年在做游戏引擎中对象管理的思考历程。
通常游戏引擎中会把可渲染对象以树结构储存，这是场景管理模块最常见的作法。顺便说一句，GUI 界面也是用类似的方式。但是，我始终认为，从 gameplay 的层面上来看，游戏逻辑需要关注的对象并不需要用层次结构的方式管理。因为，空间结构上的层次很可能发生变化，从而引起关注的对象的层次路径变化。我们最终关注的那些东西不变，但它们在空间中的位置却会经常改变。
我一直在思考的问题是：为什么一定要用树结构组织可渲染对象？树结构到底带来了什么好处？
最直接的好处是，减少矩阵运算的次数。因为，渲染层最终需要对象在整个世界中的位置，而每个被渲染的部件本身却是逐级组合起来的（为了减少数据重复，我们不能因为一个部件换了个位置，就复制一次），部件只会记录相对整体的一个局部空间变换。如果我们平坦的保存没有可渲染部件，势必在计算它最终被渲染到屏幕时的世界矩阵的时候，需要连乘一长串局部矩阵。而组织成树结构，以一定的次序计算，可以大大减少最终矩阵乘法的数量。
但这一点好处，我认为还没有触及本质。表达空间位置的矩阵，仅仅是可渲染对象的一个属性而已。
层次结构的本质是让属性可以用继承的方式优化储存，并方便批量修改。对于每种属性，会定义一种对应的继承方法。
对于空间矩阵，如果一个对象没有自己的局部矩阵，那么它就继承了父亲的矩阵，如果有，继承的方式就是做 一次矩阵的乘法。修改根节点的空间矩阵，等价于修改了连同它的所有子孙的在空间中的位置。
其实，还有很多属性也需要继承。继承可以避免把相同的属性值复制到相关节点上，也方便了一组对象一起修改。
例如材质，当我们由于种种原因，将一个网格拆分成多个时（可能是因为网格顶点数量过多，也可能是因为它们的贴图不同），多个子网格的材质其实是基本一致的。
还有可使距离，用来控制摄象机距离多远的时候，就不再渲染该组对象。同一个物件，放在室内的时候可视距离比较近，放在室外的时候可视距离较远。
还有一类属性，可能简单到只是一个布尔量，但需要方便的成组改变。我能举出的例子有很多，下面只列出常见的几个：
- 可见标记：我们有时需要临时关闭一组对象的显示，但又不希望删掉这些对象。
- 投射阴影：让标记了的对象投射在阴影图上。
- 接收阴影：在渲染的时候，考虑阴影图的影响。
- 点选标记：被聚焦的时候，采用一种特殊的着色器高亮显示。
- 水中倒影：需要绘制在水面的倒影中。
我觉得在实现的时候可以合并这类布尔量的标记，一起处理比较好。
用一个 64bit 整数保存 32 组状态。高 32bit 表示该状态是自己设置(1) 还是从父亲继承下来(0) 。低 32bit 表示每个状态（0/1) 。
这样，读取第 n 个状态可以简单的用 (state >> n) & 1。
当我们需要从父亲继承状态时，可以使用：
local mask = state >> 32 state = ( parent.state & (mask~0xffffffff) | (state & mask) | (mask << 32)
Comments
之前有一个场景也感到树结构不好用：
UI中，一个ListView中填充不重叠的Cell，Cell有很多部件，渲染次序默认是按hierachy来的，于是一个cell渲染完了再渲染另一个，哪怕这些cell里头每个部件都各自来自同图集。最终DrawCall飙升。
要不然就调整每个部件的order，但手动设置order又会和默认的那套产生穿帮，一处手动处处手动。
如果按绑定器来设计，一个cell其实就是部件跟根节点做了绑定，渲染次序完全可以跟绑定关系不搭嘎。
Posted by: Songs | (12) July 6, 2020 05:51 PM
工匠气息。
Posted by: xxx | (11) June 29, 2020 06:31 PM
我感觉节点树的设计，主要还是因为它比较符合空间事物的一般组织关系。因为大量的物件其实是从属于某个父节点的。例如汽车作为一个父节点，轮胎、方向盘、坐在车上的人等等，在空间位置上都属于汽车的子节点。以节点树结构来组织物体的话，可以将汽车作为一个整体考虑，各种刚体运动变换会直接影响其子节点（轮胎、方向盘、车上的人等等），这很符合人类的认知，也方便管理。
Posted by: walkfish | (10) June 14, 2020 11:47 AM
其实我感觉树是多年来约定俗称的一个用户需求（就像引擎要支持阴影一样）
一些逻辑层的代码可能需要用到树结构，比如主角一个Node，相机一个Node，相机作为主角的Child，我对逻辑不大熟悉，大致描述哈！
Posted by: YuqiaoZhang | (9) June 11, 2020 09:45 PM
@Cloud 理解你的意思。比如另一个实现就是绑定器。把骨骼和武器传入这个类，然后类的内部写更新逻辑。
Posted by: lizhi | (8) June 10, 2020 03:05 PM
@lizhi 列举的需求的本质是：需要方便的指定一个物件的（空间）属性受另一个物件的影响。最直接的方法是在物件自身内设置一个字段描述受谁的影响。
例如，“武器直接放到手骨骼的节点上”其实是说，武器受到了“手骨骼的节点”这个对象的影响。那么在武器对象内标记上“手骨骼的节点”的引用，就足以描述这件事情了。
至于怎么实现，用何种算法，什么数据结构，那是实现层面的工作。
Posted by: Cloud | (7) June 10, 2020 01:52 PM
我觉得树的好处就是方便。比如一个角色上，放个帽子，放个武器，武器直接放到手骨骼的节点上，简单高效。然后武器上挂载个东西，最简单的方法当然是直接把东西放到武器的节点上。其它的方法都会增加代码的复杂度，而且意义不大。
还有比如骨骼，本身就是一个天然的树结构。
Posted by: lizhi | (6) June 10, 2020 01:35 PM
统一parent继承开关听起来不错，以前总是看到零零散散的标记flag
Posted by: Drimoon | (5) June 10, 2020 11:20 AM
云大厉害，长见识了
Posted by: 林冲 | (4) June 8, 2020 09:53 AM
在没有更好的方法前还是会使用树结构
Posted by: yongxinchang | (3) June 8, 2020 08:51 AM
~ 在 lua 中表示 xor
Posted by: Cloud | (2) June 6, 2020 08:16 PM
最后一行(mask~0xffffffff)是什么运算?
Posted by: dwing | (1) June 6, 2020 11:33 AM