« December 2018 | Main

January 09, 2019

粒子系统的设计

因为需要为我们的 3d engine 添加特效系统的模块,我最近读了一篇文章:Efficient CPU Particle Systems 。文章的作者为很多 MMO / MOBA 游戏设计过粒子系统,其中最有名的是上古卷轴 Online 。所以我认为他的实践很有参考价值。

文章很长,夹杂着设计思路,优化,算法实现,渲染实现。对于我来说,由于过去我做过好几版粒子系统,所以读起来不太费力,很多细节可以直接略过,我今天写一篇 blog 把我认为文章中对我最有参考价值的部分列出来。

首先,我们是否需要做一个基于 gpu 的粒子系统?文章的结论是,各有利弊。如果单从性能角度去考虑,GPU 未必更好,尤其是对于 MMO 类发射器很多,每个发射器发射的粒子片并没有多到上千片的情况, GPU 粒子的优势并不明显。

我觉得,对于移动平台来说,把计算负担加在 CPU 或 GPU 上对性能和功耗的考虑也是一种权衡。基于 GPU 的粒子系统会增加一些开发复杂度,但并不算太复杂(bgfx 就在 examples 里给出了一个 gpu 粒子的范例);但 CPU 带来的灵活度的确能带来不少好处。另外,粒子系统的核心计算环节是天生能用多核并行计算的,且计算规模可裁剪(动态砍掉部分效果并不影响业务逻辑),我们不必过于考虑性能问题。

另外,我也读过一些相关的讨论,部分效果,尤其是粒子需要和场景做交互时,可能更适合放在 GPU 中计算。不过大多能找到一些替代方案,不用太担忧。

所以,我认可文章作者的方向,也打算先只给我们的引擎设计一个基于 CPU 的粒子系统。


作者花了很大篇幅谈内存管理。其实这部分并没有太多新的东西,几乎所有商用级别的引擎,粒子系统都很重视这块。用固定内存区维护固定上限数量的粒子片,固定数量的发射器,等等。这有几个明显的好处:

对大规模的计算,内存 cache 友好。基于 CPU 的粒子系统在合理的内存布局设计时,即使是同样的算法,可以带来成倍的计算性能提升。

限制粒子片的物理上限,可以极大的减少运行期的误用。不会因为不小心使用让内存爆掉。对业务逻辑也没有什么影响。最多是粒子发射器无法发射新的粒子,画面效果出错,但不影响其它部分。

内存管理部分作者给出了很多具体代码,我个人认为有少量动态数组部分还可以改进,去掉动态特性。尤其是时间线管理的部分应该做成可共享的固定模板。因为很多数据结构只需要在编辑期才有动态性需求,运行期都是固定的。

我倾向于在运行期用一个 C 模块和简单的 C 数据结构去管理粒子及发射器;而在编辑期,则用 lua 结构管理发射器会更具弹性。我们只需要编写一个 lua 结构到 C 结构的列集函数,在每个编辑修改操作后转换一下即可。

文章中还混杂了多线程管理和渲染流程的具体实现。这对我们的引擎设计是多余的。我想把线程管理和渲染流程从粒子系统模块中剥离出去,只设计一个纯计算模块。


文章中把粒子特效系统的原型设计分为两个层面,其一是基本粒子系统,作者称之为 bread and butter 。即仅仅用简单的多个发射器发射矩形粒子片就可以实现出来的效果:火焰、烟雾、雨、尘埃、雪、火花。

其二是为具体效果定制出来的粒子系统。所以涉及动态构建网格的效果都属于这部分,而每种特定效果都是需要特定编程的。例如:光束、刀光拖尾、闪电、更复杂的天气,等等。

后一种效果文章没有谈,只集中讨论了基本粒子系统的设计。我也想在第一步只在我们的引擎中实现基本部分。

这部分其实只涉及粒子发射器的定义,发射器按预先设定好的参数喷射出粒子,每片粒子在发射出的那一刻,就决定了所有的初始参数。之后,粒子系统每帧按这些参数更新粒子就可以了。在粒子片被构造出来的那一刻开始,整个粒子生命周期的状态变化过程就已经决定了,甚至没有任何随机量。所有随机环节都是在发射器发射时决定的。这样非常适合并行计算。我们可以用多线程,用 SIMD 优化。

btw, 在很多年前,我们第一次设计 3d 粒子系统时犯过过度设计的错误。当时我们实现了一个发射器去发射发射器的特性。现在看来是多余的,增加了许多无谓的复杂度。简单算法支撑的粒子系统一样可以做出丰富的效果。


这篇文章提出了另一个关键点是时间线的基础数据结构。他称为 AnimatedValue 。很多简单的粒子系统对一些参数,例如颜色参量,只提供了 StartColor 和 EndColor 两个控制量明显是不够用的(比如著名的 cocos2d 自带的粒子系统模块)。我们需要用一个时间线,提供任意个关键帧,用一条曲线去描述参数的变化。

另外,就是需要给发射器提供足够多的控制参数。这部分怎么多都不会浪费。

特效设计师总会充分利用这些参数,反复调整,设计出你一开始都想象不出来的效果。我所理解的特效设计师的工作就是在拿到新的特效引擎后,调调这个,改改那个,看看会得到什么结果,反复组合让这些参数之间产生化学反应。引擎设计者和特效师都无法一开始预知能做出什么,所以很难预先提出需求:“我需要这么一个参数”。我们只需要提供更多更多的参数可以调节。

好在这篇文章的作者已经实现过好多商用的粒子系统,他给出的参数列表让我们有个参考标准。他给出了发射器的数据结构定义 ,我个人觉得这是这篇文章对我价值最大的东西。不过我有一点不太赞同的地方:我觉得应该把发射器固有的模板数据和动态变化的数据字段分开,前者应该由多个实例共享。例如在场景中如果有 10 个相同的火把,我认为它们的发射器模板是同一个才对,随粒子系统更新而变化的量才应该分开。而目前作者把它们全部放在了 ParticleEmitter 类中。


最后,作者还对编辑器的设计提了点建议:虽然一个表格式数据输入界面和一个组件节点连线式的图形编辑界面本质上没啥区别;但是美术的思考模式决定了他们就喜欢后一种。所以我们应该尽可能地做成那样让美术更好的理解粒子系统如何工作。

January 08, 2019

一种 16 倍抗锯齿字体渲染的方法

昨天读了几篇文章,讲解了一种新的抗锯齿字体渲染的方法

我觉得颇有意思,就试着实现了一版 CPU 版本,想看看针对中文的效果。虽然最后觉得这个算法对游戏领域的实用性不大,不过还是挺有启发的。这里写写我对这个算法的理解,以及我所理解的算法局限性。

原文讲解的非常细致,还配了不少图片,我就不再重复了,只简单说两句。

我认为发明这个算法的动机是 “Our UI has a lot of smooth animation, text should be able to move smoothly across the screen.” 这是过去很多传统字体渲染算法很难解决的。

当我们输出的文字略微偏移 1/4 个屏幕像素时,通常会糊掉。但是这个算法则可以尽可能地保留信息。

因为这个算法的本质是把 16 倍大的字形,以黑白二值位图的形式保存在一个每像素 16bit 的贴图中。和传统的保存字形位图的方式不同,它不储存字体抗锯齿后的灰阶图片,而是一个 bit 保存一个像素。贴图的一个图素保存了 4x4 共 16 个像素。把 16 个点阵像素压缩到贴图的一个图素中带来的并不仅仅是压缩的好处,更重要的是,可以让 gpu 做采样时,可以一次拿出更多的字形信息,方便做抗锯齿处理。

我们在纹理采样时,从贴图上采到的一个图素其实包含了 16 个字形像素的信息。如果我们采样 4 次,就可以拿到 16x16 = 256 像素的位图。然后,计算出真正采样的范围,统计这个采样区域 bit 1 的个数,就可以精确的算出灰阶。

相比传统储存方法,偏移部分像素,就只能通过简单的混合算法求出平均灰阶,这种储存方法相当于推迟了字型抗锯齿计算灰阶的时机。

我做了一个简单的动画,让一个 23 像素高的 “好”字在一个像素范围内轻微位移转圈,我们可以看到,好字的包围盒并没有扩大,但肉眼明显能感知到字的移动。

我们把好字的半像素位移展开, X Y 方向各移动 1/4 1/2 3/4 像素,得到 16 个字,是这样的:

放大点可能看的更清楚:

如果我们把灰阶改成类似微软 ClearType 的方法,利用液晶屏 RGB 三个子像素,可以做到更清晰。这部分工作我懒得做了。


但我认为,这个方法对于目前游戏并没有太大意义。因为用 GPU 实现过于复杂,而收益(文字移动平滑这个特性)并不大。

而且算法本身有个弱点,原文并没有解决。那就是当字体放大或缩小时,其实贴图到帧缓冲的算法就不再是 1:1 的关系。如果按原文的方法 4x4=16 像素的窗口去采样,结果是不对的。如果最终显示的文字比原始字型点阵要小,就应该用大于 4x4 的采样窗口;如果要放大原始点阵,则应该用更小的采样窗口。

这个方法的极限可以把字形放大 4x4 倍而不失真。当你需要输出 4x4 倍大的文字时,其实每次只应该在贴图上采样一个 bit (1x1 窗口)。

用 CPU 可以勉强解决这个缩放问题,GPU 来做也未尝不可。我构想的方法是另外做一种带 mipmap 的纯色贴图,不同的 mipmap 层填充不同的颜色通道,比如第一层用纯红,第二层用纯绿,然后根据采样的颜色结果的红绿比例,可以推测出贴图到帧缓冲的映射比。

对英文来说,缩放问题并不麻烦。只要可以快速生成需要的大小的贴图(这也是原文第三篇讨论的话题),加上合适的 cache 即可;但是中文字形太多,我们就需要太大的 cache 。这也是我认为该算法(对中文)并不实用的原因之一。