层次结构和状态继承
在 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