低性能手机也能跑得动？《明日之后》手游中大量的建筑物、车辆、石头等遮挡物，如何能被快速计算，以低功耗完成遮挡剔除的？在GDC2023的核心会场（Core concept）中，网易游戏的资深引擎程序Tao介绍了《明日之后》所使用的创新高性能软光栅遮挡剔除方案（SOC）。借助SOC方案，在低端手机平台（如 iPhone 6s）上，游戏每帧仅需要约1.5ms的消耗，能够完美适配动态场景，美术可以放心创造复杂精巧的场景而不用担心性能问题！
以下是演讲实录（根据现场英文演讲内容翻译整理）：本次演讲将跟大家分享我们是如何在《明日之后》项目中，实现移动平台的高性能软光栅遮挡剔除方案的。演讲主要分为 3 个部分：轻量级软光栅遮挡剔除方案、优化剔除管线和离线生成遮挡网格。首先介绍下背景信息。《明日之后》是一款开放世界多人TPS手游。玩家要在末日世界中生存，探索废弃荒芜的城市、危险重重的森林，山脉和海洋，还要对抗怪物，收集资源以及建造营地。先介绍下演讲中涉及的术语。
遮挡剔除（Occlusion Culling）是指当一个物体被其他物体遮挡时，不对其进行渲染。遮挡物（Occluder）是一些选定的大型物体，可以遮挡视线中的其他物体，就像这里的帐篷。被遮挡物（Occludee）是场景中的所有可以被遮挡物遮挡的物体。
剔除率（Culling rate ）是一种用于评估剔除算法有效性的指标，剔除率 = 剔除掉的物体或面片数 / 总的物体或面片数。错误遮挡（False Occlusion）指由于剔除算法的误判，导致可见物体被错误遮挡的情况。这种情况下，剔除算法错误地认为某些物体或面片是不可见的，从而导致它们可能突然消失。
一、优化动机由于《明日之后》是款手游，遮挡剔除可能会对移动平台的性能产生较大的影响。在常规场景中，60%以上的对象可以被剔除，意味着这些物体不用渲染，从而帮助我们节省大量的时间。然而，要设计针对移动平台的遮挡剔除解决方案，需要满足很多条件。首先要满足的是高剔除率，以及无错误遮挡——这意味着没有可见对象被错误剔除。该解决方案必须支持静态对象和动态对象，而且占用的包体较小。另外，也是非常关键的一点是，它得跑的很快。对于计算能力较弱的移动平台，这个要求非常的有挑战性。这里有一个表格，包含常见的遮挡剔除解决方案，潜在可视集合 （Potential Visible Set， 以下简称 PVS ）、硬件遮挡查询、以及软件遮挡剔除，简称SOC。可以看到，PVS不支持动态对象渲染，而硬件遮挡查询则导致出现了错误遮挡。
SOC 方案满足了我们的大部分要求，但是它的结果严重依赖于遮挡网格的质量，而且它在移动平台上运行太慢了。但我们最终还是选择使用 SOC 解决方案，但是需要做一些努力来解决这些问题。我们的目标是，尽可能提升 SOC 解决方案的速度，所以我们必须针对移动平台优化算法，同时使用高质量的遮挡网格。我们的方案这里就要提到我们的高效软件遮挡剔除解决方案。该方案由 3 个部分组成，一个用于剔除的轻量级soc 算法，即图表中的绿色部分；一个用于组织数据的优化管线，即黄色部分，以及用于生成高质量遮挡网格的离线生成器，即蓝色部分。
在接下来的演讲部分，我会逐一解释以上三个部分。二、剔除算法（Occlusion Mesh Generator）让我们从第一部分开始，剔除算法。该算法有 2 个目标。先是对选定的遮挡物光栅化，计算出深度值，存储在深度缓冲区中，接着使用这个深度缓冲区来做深度测试，判断被遮挡物的可见性。
2.1 传统SOC方案和轻量级SOC方案对比传统SOC方案作为对比，我简单介绍一下传统的“带遮罩的软件遮挡剔除方案”（Masked Software Occlusion Culling，MSOC），它是Intel在2016年提出的解决方案，也是现在PC和主机上的主流SOC实现方案。
传统软件遮挡剔除方案（MSOC）流程图
该算法针对支持 AVX 的 CPU 进行了优化，具有分层深度缓冲区。它会收集遮挡物的三角形信息（wedge），然后使用“边缘填充光栅化算法”来检查并标记给定遮挡物三角形的覆盖像素， 再然后使用’启发式丢弃'算法，来更新深度缓冲区信息，从而得到新的深度值。接着计算被遮挡物的屏幕矩形区域，对深度缓冲区进行遮挡查询。轻量级SOC方案接下来，再看看我们的轻量级SOC 软件遮挡剔除算法。蓝色标记的步骤是我们与 MSOC 不同的地方。可以看到框架非常相似，但是在细节上进行了优化。
我们的轻量级SOC 软件遮挡剔除算法流程图
我们的算法也使用 SIMD 指令进行了优化。在移动平台上，SIMD 通常用Arm Neon技术实现。我们沿用了分层深度缓冲区的想法，但做了一些小的调整。在对遮挡物光栅化部分，我们在准备阶段上进行了很大的改动：不再使用背面剔除（BackfaceCulling），优化了顶点排序，并且在楔形信息收集阶段增加了一个额外的预排序步骤。准备之后，我们仍然使用边缘填充光栅化进行覆盖检测，但不再使用“启发式丢弃”过程，深度信息更新则回落到使用简单的写入方式。在对被遮挡物进行可见性查询，我们在查询之前添加了一个“Early Out（尽早退出循环或函数）”步骤。我将在后面的演讲内容观众详细介绍我们的算法，重点介绍我们创新的部分。2.2 深度缓冲区和深度值存储深度缓冲区结构我们使用分辨率很低的深度缓冲区，比如 256x160。如图所示，整个缓冲区被分成 4 个 bin。每个 bin 进一步被划分为80 个图块。每个图块又分为 4 个子图块。图块由 8*4 的像素块组成， 每个图块共享一个深度值。最后，每个图块包含 128 个像素，对应一个 m128i；4 个深度值对应一个 m128，可以看成是4个float32。
深度缓冲区结构
存储深度值在存储深度值方面，我们也有一个小技巧。我们注意到深度值仅用于 Z 测试，所以真正重要的是相对大小。因此，我们使用反向Z (Reversed-Z) 投影来提高深度缓冲区精度。这也是常见的做法。通过进一步修改投影矩阵，将远平面投影设置为0，可以更方便地设置深度缓冲区。最终的投影矩阵如下图所示。参数'c'可以是任何正实数。可以看到矩阵中只有4个非零项，比原始矩阵少1 个非零项，也就意味着投影速度加快了。实际上，如果你使用SIMD (Single Instruction Multiple Data，即单指令流多数据流)会快得多。
投影矩阵
2.3 楔形信息收集阶段（Wedge Collecting Phase）接下来是处理过程。在对遮挡物进行处理时，首先会经过楔形收集阶段。我们使用上文中所示的修改后的投影矩阵，将遮挡物投影到楔形板中。对于每个三角形, 我们只存储 1 个深度值，即只存储最远、最保守（即最严格）的深度值。然后，当所有遮挡物都完成投影时，按照深度值对楔形内的物体进行排序。我们为什么要进行这种排序呢？与 MSOC 中的启发式搜索方法类似，都是为了确保后续深度缓冲区的深度值更新。使用排序而不是“启发式丢弃”法，是因为我们考虑到了两个因素：准确性和速度。排序的准确性排序的结果准确性更高。“启发式丢弃”，顾名思义， 是一种启发式算法，结果不稳定。在下图中，我们可以看到使用“启发式丢弃”法 时，沿着阴影边界的一些像素丢失了，而使用排序时，结果则显示正常。不要低估这个小问题。由于我们使用的是极低的分辨率，这可能会极大的影响剔除率。
“启发式丢弃”时边缘像素的丢失
排序的渲染速度而渲染速度则取决于需要处理的遮挡物三角形数量。
从上图中可以看出，三角形面数较多时，“启发式丢弃法”（橙线）效率更高，三角形面数较少时，则排序法速度更快。在我们的解决方案中，输入的三角形面数非常少，甚至低于 4000。因此，排序法是更为合理的方案。2.4 准备阶段（Preparation Phase）接下来是准备阶段。计算信息首先，我们来计算信息，方便后续进行边缘填充算法。需要计算的信息包括屏幕的楔形边界框以及每条边的斜率等。所有输入的三角形都被视为双面，并且按批次打包，通过 SIMD 指令批量进行处理。为了有效地从打包的SIMD数据中找到三角形的指定边，我们需要将信息打包在一些指定的图案中。实际上，我们会将三角形顶点排列成 2 个指定的图案，如下图所示。因此，我们通过对顶点进行排序来形成三角形。排序有 3 个目标：
逆时针V0 的 y 值最小识别出哪个顶点的 y 值居中
相比MSOC，我们需要完成的目标更多（“将顶点设置为逆时针方向”，这是一个额外的需求），但我们通过最终使用比 MSOC更少的指令数完成了所有的目标，只用到了 22 条SIMD 指令。这其中的关键点在于，要意识到这个额外的目标事实上使我们放开了手脚，因为不必保留原始顶点顺序。代码如下所示。我们通过简单比较找到顶点v0，计算出与其相邻的两个点v1和v2的向量，对这两个向量进行叉积运算，最后将v1和v2按照顺时针的方向排序。
2.5 光栅化阶段（Rasterization Phase）接下来是光栅化阶段，也是最终的处理阶段。在这个阶段，我们将屏幕的楔形光栅化，存储到深度缓冲区中。其中包括两个步骤：覆盖检测和深度更新。与 MSOC 一样，我们在覆盖检测部分使用了“边缘填充光栅化”算法。主要原理是是为每一行找到最左边和最右边的像素，接着填充之间所有的像素。
接着我们要更新深度缓冲区中的深度值。由于前面的排序，深度值的更新非常简单，即当子图块被完全覆盖的时候，记录当前的深度值。现在我们已经完成了遮挡物的部分，获得了深度缓冲区，接着再处理被遮挡物。在这部分中，我们将被遮挡物的 AABB 投影到屏幕空间中，执行简单的碰撞测试，得到早期剔除结果，再通过深度测试查询可见性。这个方法很简单——也就意味着很快：如果投影面积太小，则被遮挡物将不可见。如果离相机过近，那么被遮挡物将是可见的。实际上，我们可以跳过大约 50% 的被遮挡物查询。这是我们的轻量级软件遮挡剔除算法的性能数据。在对遮挡物光栅化时，每个三角形只需花费 0.4 微秒。对遮挡物进行可见性查询，每个被遮挡物花费 0.56 微秒。还可以看出，“Early Out”有效地降低了可见性查询的成本，绕过了几乎 50% 的被遮挡物。
三、优化剔除管线（Optimized Culling Pipeline）接下来到剔除管线的部分。剔除管线需要组合多个剔除模块，以及所有相关数据的组织，包括遮挡物和被遮挡物，并输出报告结果。下图是一个典型的剔除管线实现方法。
因为过于简单明了，几乎很少人关注它在电脑和主机平台上的应用情况。然而在移动平台上，我们发现管线本身的消耗很大。在旧版本的引擎中，渲染5000 个被遮挡物需要 1.5ms 的时间，留给 SOC 的空间很小。因此，我们需要加速渲染管线。3.1 降低缓存丢失率3.1.1 数组遍历首先，我们考虑如何有效地判断被遮挡物。有两个选择：直接使用普通的数组来管理场景中的物体，或者，空间加速结构。数组如果我们选择使用数组，策略非常简单：遍历所有被遮挡物来进行判断。这个场景中有5个遮挡物，每次Cache Fetch可以存储3个物体到缓存，则可以看到，需要进行5次可见性查询和2次Cache Fetch。
空间加速结构而如果使用空间加速结构，例如 边界体层次结构 （Bounding Volume Hierarchy （BHV））或 八叉树（Octree）等方法，就能减少查询次数。如下图，我们添加 2个父级包围体积（ Parent Bounding Volume（PBV）），V1和V2，一旦被判断为不可见，比如V2，它的所有子级包围体积，C，D，E，都可被设为不可见，无需进一步测试。因此，我们可以减少 1 次可见性查询。但此时，我们访问内存的方式，相比数组来说，更加的随机。在这种情况下，我们需要3次Cache Fetch，比使用数组多一次。那么你可能会好奇，如果将数组中的子项和父项放在一起，是否可以减少缓存预取的性能消耗呢？实际上，该方案下内存访问将是线性的，确实可以减少消耗。但是此时维护加速结构的开销会显著增加，考虑到被遮挡物移动的情况下，会需要我们去做更多的工作来维持结构。
两者对比结合我们的实际情况，在我们的解决方案中，剔除查询的消耗较低，而且游戏中的被遮挡物数量不是那么大，因此跳过的查询次数，无法抵消缓存未命中的消耗，更不用说维护加速结构的额外成本了。所以，使用数组显然是更好的选择。由于缓存行（cache line） 的大小通常是固定的。数据结构越小，Cache Fetch次数越少。所以，我们希望最小化被遮挡区的数据大小。我们在数据结构中仅存储了相关的数据，并使用尽可能低的数据精度。此外，我们使用位域来最小化布尔值和枚举值 。通过对数据进行组织和优化，我们获得了约0.3毫秒的时间性能提升。3.1.2 函数调用下一个要解决的问题是函数调用时出现的缓存未命中。由于虚函数调用导致缓存未命中（cache miss）时，会产生显著消耗。我们先来看看这些缓存未命中是如何发生的。当调用一个普通函数时，CPU 处理器需要加载该函数的指令。如果指令没有存储在指令缓存中，就会发生缓存未命中。调用虚函数时，处理器首先需要加载虚表(vtable)指针，然后加载vtable指针引用的函数地址。而加载地址时，有可能会发生缓存未命中。因此最糟糕的情况就是在调用函数时，多了两次缓存未命中。此外，使用虚函数时，CPU很难预测下一条指令，导致指令执行效率降低。
因此，我们决定删掉所有的虚函数调用，简化操作，解决缓存未命中问题。这个修改本身并不复杂，但我也有一些小小的建议，来使你更快的完成这类修改：你可以将数据和指令分开存放，这样可以方便地访问数据，也可以通过函数实现面向对象的指令部分；其次，还可以使用不同的数组来存储不同类型的遮挡物信息，并调用特定的通知函数。通过上述方式，我们获得了0.5ms 的性能提升。3.1.3 可见性过滤下一个问题是可见性过滤器。什么是可见性过滤器呢？在一个渲染管线中，一个被遮挡物需要经过多次检测，才能判断为可见。这个过程是多个过滤器的级联，包括逻辑设置、视体剔除，以及软件算法执行遮挡剔除等等。这个过滤器有两种常见的实现方式。第一种方法是标记可见性。已标记为不可见的遮挡物将跳过后续测试。第二种方法是使用一个额外的数组来保存过滤后的遮挡物。第一种方法的缺点是不可见的遮挡物占用了缓存行。而第二个方法则会导致不必要的数据复制消耗。那么哪个方案更好呢？取决于实际情况。在我们的项目中，大约 80% 的对象会被视体剔除过滤掉，因此复制操作并不频繁。在这种情况下，我们发现使用“过滤”方法效率更高，可节约0.05ms。3.2不要光栅化低遮挡的三角形
让我们根据上面这张图来分析可见部分。上图中，你可以看到，这个遮挡物，不仅隐藏了被遮挡物，还隐藏了一部分自身——我们称之为自遮挡（Self Occlusion）。此外，平行于观察方向的部分几乎没有遮挡效力。对场景来说，左边的遮挡物和右边的遮挡物具有相同的遮挡效果，但右边的面数显著低于左边，因此对左边这个遮挡物进行完整的光栅化，算对算力的浪费。为了解决这个问题，我们将遮挡网格分成多个部分，只光栅化有效部分，也就是我们说的“可见部分”。可见部分信息是离线渲染的。我们先给定一个遮挡网格，根据三角形的法线和位置对三角形进行聚类，将网格分成几个部分。然后我们从不同的角度拍摄快照，并计算每个部分的可见尺寸大小。
在这张图中，有一个部分只是一个线段，或者说是平面。绿线和红线表示不同的观察方向。0表示在这个视图中方向，完全不可见，可能是被其他部分遮挡了。这里的 1 是指投影后，这个部分在视线中占1平方米大小。这里的单位是平方米。通过汇总所有信息，每个部分都可以用一个视锥体来描述其可见范围。假设我将阈值设为1，视锥体的大小和形状应该能够包含所有可见尺寸等于或大于1平方米的物体。所以我们得到如图所示的锥体。在运行时，会使用视锥体来进行可见性测试。如果在运行时，视角方向在可见锥体之外，那么被观察物体的可见尺寸一定小于某个阈值，这部分将被视为不可见。而我们只对那些可见的部分进行光栅化——使用我们的轻量级软件遮挡剔除算法。在实践中，大约 50% 的遮挡三角形可以跳过光栅化过程，并且不会对渲染效果产生严重影响。性能数据显示如下，可以看到需要光栅化的三角形数量从1539降到了874。
四、用于生成高质量遮挡网格的离线生成器（High-quality Occlusion Mesh Generator）有了一个高效的剔除管线后，接下来我们要为其提供高质量的遮挡体。因此需要打造用于生成高质量遮挡网格的离线生成器。为什么遮挡网格如此重要？首先，为了在低端手机上，为了实现在 2ms内完成整个剔除渲染过程，我们需要将遮挡网格的三角形面数设置为4000，这是一个极低的面数要求。与此同时，还要保证遮挡网格是高质量的。否则，即使只是轻微的网格裂缝和偏差，也会导致剔除率急剧下降到35%，偶尔还会出现错误遮挡。想象一下，常见场景下，画面可能有 100 万个三角形，而被遮挡物的三角形数量可能达到 10 万个。然而，我们只需要渲染4000个三角形，可以实现同样的遮挡效果。听起来似乎是不可能完成的任务，但是我们做到了。先简要介绍一下我们的网格生成器。
我们首先通过体素化和填充来对模型进行平滑处理，接着从中过滤出有效的聚类，再将每个聚类中的数据或对象转换为三角形网格来进行渲染。由于体素化模型不适合表示斜坡或曲面，我们将原始遮挡物按法向方向切割成子模型，再分别进行处理，最后再合并所有子模型的结果。4.1 平滑过程（Smoothing）在生成高质量的简化遮挡网格的过程中，我们遇到了很多挑战。在这其中，最难的一点，就是如何去平滑一个3D Mesh。我们尝试了很多方法，最终找出了这个解决方案。平滑Mesh如下图所示，我们的想法是尽可能多地填充体素化模型，得到平滑的Mesh，接着进行提取。
而问题是，如何在确保进行平滑操作后，还不会产生错误遮挡。我们需要用数学公式来描述“无错误遮挡”的约束条件。因此，我们提出了可视函数的概念。可视函数接下来是算法部分，我尽量讲的简单点，避免大家睡着：）。可见性函数的定义很简单，是指从一个任意位置，沿着一条任意方向，去观察一个任意物体，如果物体可见，那么函数结果为 True，反之为 False。那么我们可以这样描述“无错误遮挡”约束条件：对于任意被遮挡物，在任何位置或任意视线方向，如果在使用简化遮挡网格时，可见性函数为假，则在使用原始网格时，可见性函数也应该为假。如果函数为真，那么说明该物体可以被看到，但如果使用简化网格看不到它，说明物体被错误遮挡了。
这个约束条件仍然很难使用，因为“任意”的条件太多了，所以我们决定通过近似来简化这个条件。简化“任意位置”首先，我们简化“任意位置”， 将任意位置替换为“near 和 far”，其中 near 表示AABB网格的扩展，而“far”表示无穷大。范围如下：
紧接着，对于“任意方向”，我们将其简化为几个指定的观察方向，在实践中，我们选择 3 条轴和其中线：
最后，我们还要定义“任意被遮挡物”，这相对复杂一些。我们提出了“重要体素”的概念：重要体素是那些已经存在了静态物体的地方，以及动态物体中心部分可能出现的地方。然后，我们将约束条件中的“任意被遮挡物”替换为“任意重要体素”。下图具象说明了什么是重要体素。图中有一个预设的动态对象和一个遮挡物。我们让动态物体在遮挡物内部徘徊，而红色的体素就是中心部分可能出现的地方，也就是重要体素。
我们将约束条件被简化为：对于任意重要体素，在 near 和 far 的位置，沿任何指定的方向观察，如使用简化遮挡网格时，可见性函数为假，则使用原始网格时，可见性函数也必须为假。
通过约束（Constraint）平滑Mesh有了约束（Constraint）后，我们的平滑过程就很清晰了。如流程图所示，我们需要遍历所有空的体素，尝试进行填充，并检查约束是否仍然成立。
但是这个遍历过程很耗时，所以在实践中，我们使用启发式的方法，再通过约束来判断可填充的体素。这个方法的思路是找到 2 个彼此不可见的重要体素，则它们之间的体素一定是可以安全填充位置，因为它们不会干扰重要的体素。这种启发式方法要快得多，结果也可以接受。以下图为例，Voxel SA 和 SB 位于重要体素 IA 和 IB 之间，而 IA 和 IB 看不到对方。所以SA 和 SB 是安全体素。
这样一来平滑过程就变得简单。在设置可见性函数约束后，我们得出所有安全体素，进行填充，并得到填充的体素网格。4.2 筛选聚类（Filtering）接着，我们需要提取它的有效遮挡部分。我们首先沿着其中一个轴对体素网格进行切片。然后对于每个切片，我们将相连的体素划分为簇，计算簇与簇之间的遮挡关系。然后我们选择遮挡关系高于给定阈值的簇。
理论上讲，一个簇的遮挡关系可以通过下面的公式来计算得到，但是这个过程很慢。因此我们最终没有使用这个方案，这就里不再详细说明这个公式。
我们同样提出了一种启发式方法。我们首先找到满足这样条件的重要体素：当它被原始模型包围时，可见性函数的返回值为假，当它被所有当前选择的簇包围时，其可见性函数的返回值为真。接着标记可以遮挡这些重要体素的簇，将标记的数量作为遮挡信息的近似值。在实践中，这种启发式方法与基准真相（ ground truth） 相比，计算速度快10 倍，并且结果也很棒。4.3 转化为三角形（Triangulating）而选中簇之后，接下来就是将它们转换成三角形。我们使用了常见的做法。首先，我们先提取出边界信息，并将孔洞与边界相连接，从而将每个簇转换为边缘循环。
然后，我们通过经典的道格拉斯-普克算法（Ramer-Douglas-Peucker）算法沿边缘曲线循环简化。之后，我们使用经典的切耳法（Ear Clipping）算法对多边形进行三角剖分，从而得到结果。
对于方形遮挡物，这样处理后的结果已经可以接受。但是我们还有许多斜面和曲面的遮挡物。
解决这个问题的思路很简单。我们从原始模型中分离出斜坡和曲面，形成一个独立的子模型。用前面的提到方法简化它们，接着将所有部分的结果结合起来，并将它们之间的间隙焊接起来，得到最终的遮挡网格。现在我们得到最终的结果，就是一个简化的高质量遮挡网格，如下面的案例。
这座教堂有 75240个三角形，而简化的遮挡网格使用了不到900个三角形。你可以看到凹凸不平的墙壁被平滑了，塔尖被自动移除，因为塔尖基本不具备遮挡效果。
而这里的圆形体育场，原来有大约 10k 个三角形，简化后只剩下 900 个三角形。可以看到到生成器对于曲面非常有效。我们的生成器生成的最终简化遮挡网格大约是原始三角形数量的5%，并且不会产生任何错误遮挡效果。总结下表显示了从高端到低端的不同机型的性能数据，可以看到我们在2ms 内剔除了 65% 的对象。
以Iphone 6s为例，我们的 SOC 算法可以在1ms 内减少 65% 的绘制调用，而不会发生任何错误遮挡。对于整个剔除解决方案，时间是1.5ms，总剔除率约为 91%。针对移动平台的高效软件遮挡剔除解决方案，需要综合考虑各个方面。如：
使用轻量级 SOC 算法来适配移动平台。构建缓存友好和多线程运行的剔除管线。用于高质量的遮挡网格的生成器。生成器可以基于可见性函数来制作。
这就是我们在《明日之后》中所实现的解决方案，这不是一项简单的任务。没有我们出色的开发团队，就无法实现这套解决方案。感谢大家倾听！
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.