关于算法:游戏场景剔除之剔除算法综述

这是一篇对于剔除算法的综述，来总结罕用剔除算法的实现原理和过程。

在游戏运行中，引擎渲染出数以万计的物体，场景复杂度往往是数千万面的级别，同时还须要解决千计盏灯光和数百种材质。因而，如何无效地缩小不必要的绘制就显得分外重要。本文就游戏引擎中用到的各种剔除技术进行概述，会较少波及细节，感兴趣的同学能够去看文末的参考文献，文献中会有相干剔除算法的原理和具体实现。

咱们将分为以下四个方面来介绍：

1. 场景剔除工作原理
2. 罕用剔除算法
3. 总结

4. 参考文献

   ---

一、场景剔除工作原理

对于场景物体的剔除个别分为可见性剔除和遮挡剔除：

1. 可见性剔除
可见性剔除通过判断物体与相机的间隔（间隔剔除）或者是否在相机的视锥体内（视锥体剔除）来对物体进行剔除。

如图所示，不在相机视锥体外部的物体将被剔除不进行渲染。

2. 遮挡剔除
遮挡剔除则是在相机可见范畴内通过判断物体是否被其余物体遮挡来对物体进行剔除。遮挡剔除有基于整个物体是否被遮挡的剔除（如 Hiz、硬件遮挡查问等），也有基于像素级别的遮挡查问（如 Early Z）。

图中蓝色虚线的物体被相机后方的物体遮挡，并将剔除不进行渲染。

二、罕用剔除算法

本文将大抵介绍以下剔除算法的原理和实现过程：

1. 间隔剔除
2. 视锥体剔除
3. Occluder 剔除（软件剔除）
4. 视口剔除
5. 反面剔除
6. 遮挡查问（Occlusion Query）
7. Early Z Culling
8. Hiz Culling
9. PVS

1. 间隔剔除
剔除阶段：应用程序阶段。

通过物体和相机的间隔进行判断物体是否被剔除，原理比较简单，剔除效率也绝对较高。在 UE4 中能够通过物体属性设置剔除的最大间隔和最小间隔（如下图）：

2. 视锥体剔除
剔除阶段：应用程序阶段。

即简略判断一个物体是否位于视锥棱台内。裁剪的根据次要是依据摄像机的视线（field of view）以及近裁减面和远裁剪面的间隔，将可视范畴外的物体排除出渲染。

上图中 1 为近裁剪屏幕，2 为裁剪截面体，3 为远裁剪立体。

在实践中，因为模型往往是比较复杂的，很难准确计算它和视锥体的交加，因而个别是用轴对齐突围盒（AABB），有向突围盒（OBB）或者突围球（BSphere）代替模型自身进行相交计算。

视锥体剔除是缩小渲染耗费的最无效伎俩之一，能够在不影响渲染成果的状况下大幅缩小渲染波及到的顶点数和面数。

3. Occluder 剔除（软件剔除）
剔除阶段：应用程序阶段。

这个计划的思路是，首先利用 CPU 结构一个低分辨率的 Z -Buffer，在 Z -Buffer 上绘制一些场景中较大的遮挡体：

在结构好的 Z -Buffer 上，绘制小物体的突围盒，而后执行相似于 Occlusion Query 的操作，查问以后物体是否被遮挡：

因为是纯 CPU 的，集成起来也比较简单，同时不会有 GPU Stall 的问题。毛病是须要美术指定一些大的遮挡体，对 CPU 性能有肯定的耗费。在 UE4 中通过物体 Actor 的 LOD For Occluder 设置遮挡体。

4. 视口剔除
剔除阶段：投影变换之后屏幕映射之前。

产生在几何阶段（Geometry Stage）前期，投影变换之后屏幕映射之前，是渲染管线的必要一环。只有当图元齐全或局部存在于标准立方体外部的时候，才将其返送到光栅化阶段。其中，对于齐全位于标准立方体外部的图元，则间接进行下一阶段；齐全处于标准立方内部的图元则齐全被舍弃；局部处于标准立方体外部图元，则会依据视口进行对应的裁剪，在这一过程中可能会产生新的顶点。通过视口剔除能够将视口外的图元舍弃掉，减小光栅化阶段的耗费。

5. 反面剔除
剔除阶段：在光栅化阶段进行。

当咱们察看场景中对象时，个别只能以肯定角度来察看，那么对象的某些面咱们是看不到的，例如你察看一个立方体，最多只能同时看到 3 个面，有时只能看到 1 个面，而咱们绘制时如果不采取剔除反面的措施，则要绘制 6 个面，其中包含一些咱们基本看不到的面。对于立方体这个面较少的几何对象，性能开销不显著，然而对于简单的模型，开启反面剔除则能明显改善渲染性能。反面剔除，就是早点抛弃对观察者来说是反面的片元的一种办法。

剔除的基本原理是先断定多边形的朝向，并和以后的察看方向进行比拟。OpenGL 中设置反面剔除相干函数：
glFrontFace(GL_CW)；设置顺时针或者逆时针为侧面
glCullFace(GL_BACK)；设置剔除侧面或者反面

反面剔除在光栅化阶段进行，执行在 Vertex Shader 之后，在 Fragment Shader 片元着色器之前。

6. 遮挡查问（Occlusion Query）
剔除阶段：在深度测试时失去待剔除物体，在应用程序阶段执行。

参考步骤和代码：
https://www.cnblogs.com/mazhe…

简略来说，Occlusion Query 容许你在绘制命令执行之前，向 GPU 插入一条查问，并且在绘制完结之后的某个时刻，从 GPU 将查问后果回读到零碎内存里。这条查问命令失去的是某次 DrawCall 中通过 Depth Test 的 Sample 数量，当这个 Sample 的数量大于 0 时，就示意以后模型是局部可见的，否则以后模型齐全被遮挡。

OpenGL 中实现 API 接口：

// 生成查问物体 ID
glGenQueries(GLsizei n, GLuint *ids);

// 开始遮挡查问
glBeginQuery(GL_SAMPLES_PASSED, 1);

// 完结遮挡查问
glEndQuery(GL_SAMPLES_PASSED);

// 依据 Sample 值 param 是否大于 0 判断查询号为 id 的物体是否被遮挡
glGetQueryObjectiv(GLenum id, GLenum pname, GLint *param);

对于简单的场景，一个不言而喻的优化策略就是用突围盒代替模型自身去做渲染，为了更加准确，咱们也能够用多个紧贴的突围盒或者绝对原模型更简略的 Proxy Mesh 去做 Occlusion Query。基于这些 API，咱们就能够失去一个比较简单的遮挡剔除策略：

1. 首先为这些物体生成查问对象 ID，并调用 glGenQueries；
2. 调用 glBeginQuery 开始遮挡查问；
3. 渲染突围体；
4. 调用 glEndQuery 完结遮挡查问；
5. 调用 glGetQueryObjectiv，依据 ID 提取遮挡查问的后果，并依据后果绘制相应的物体；
6. glDeleteQueries 删除 ID，回收资源。

Occlusion Query 的另一个毛病（也是最致命的毛病）是，它须要将查问后果回读到零碎内存里，这就意味着 VRAM->System RAM 的操作，走的是比较慢的 PCI-E。

为了解决这个问题，比拟罕用的的办法是让 CPU 回读前一帧的 Occlusion Query 的后果，用来决定以后帧某个物体是否 Visible，对于相机静止较快的场景，用上一帧的后果可能会导致出错，但因为个别是用突围盒，自身就是激进的剔除，所以总体来说影响不显著，UE4 默认应用的就是这样的遮挡剔除计划。

7. Early Z Culling
剔除阶段：在光栅化阶段后，片元 Shader 执行前。

咱们晓得传统的渲染管线中，深度测试是产生在 Pixel/Fragment Shader 之后的。然而，如果咱们认真想下，在光栅化的时候咱们曾经晓得了每个片断（Fragment）的深度，如果这个时候咱们能够提前做测试就能够防止前面简单的 Pixel/Fragment Shader 计算过程。

提到 Early- Z 就必须提对应的 Late-Z：在图形管线中，逻辑上 Depth Test 和 Stencil Test 是产生在 Pixel Shader 的执行之后的，因为 Pixel Depth 在 Pixel Shader 阶段还有可能被批改，所以 Pixel Shader->Depth Test 的流程程序就是 Late-Z。但因为 Pixel Depth 批改的需要非常少（基于深度混合的 Impostor 和某些粒子成果），所以绝大部分状况下，Pixel Depth 在 Rasterization 之后、Pixel Shader 执行之前就能够被确定下来，如果咱们可能把 Depth Test 放在 Pixel Shader 之前，对那些没通过 Depth Test 的像素不执行 Pixel Shader，就可能肯定水平上缩小 SM 的压力，这就是 Early- Z 这个优化策略的初衷，当初曾经是 GPU 的标配了。默认在 Pixel Shader 里没有批改 Depth 的操作时，这个优化就会开启。

UE4 在 Prepass 中生成 EarlyZ Depth，而后在光栅化后执行 EarlyZ Culling。

8. Hiz Culling
剔除阶段：在几何 Shader 失去待剔除物体，在顶点 Shader 执行。

参考步骤和代码：
https://github.com/nvpro-samp…

Hiz Culling 同样是基于 GPU 但不同于 EarlyZ Culling 的剔除算法，Hiz Culling 应用几何着色器学生成对应物体的突围盒，而后依据物体的突围盒抉择对应层级的 Depth Map。利用 Depth Map 对应像素值对突围盒进行剔除，失去物体可见性并作标记。为了防止 GPU 返回标记到内存而造成工夫耗费，通常应用 Transform Feedback 将此数据流式传回到顶点 Shader 中，也就是常应用的 2 -Pass。

具体算法过程如下：
（1）拿到上一帧场景深度 Buffer，利用深度 Buffer 结构分层深度图像，咱们将其称为 Hi-Z map。这些分层的深度图是对深度缓冲区进行 Mip-map 失去，其中 Mip 级别 i 中的每个像素蕴含 Mip 级别 i - 1 中的对应像素块的最大深度。

（2）将以后待绘制的场景物体分为两个汇合：
汇合 1，上一帧已有的物体汇合（这里不肯定和上一帧已有物体数量雷同，有可能上一帧在相机可视范畴而以后帧不在等状况）；
汇合 2，以后帧新增的待渲染物体。

（3）解决汇合 1：在构建 Hi-Z map 后，依据汇合 1 物体的突围盒大小取对应级别的 Hi-Z map 深度图，并通过比拟物体的突围盒深度值和存储在对应深度图深度信息来执行遮挡剔除，通常咱们比拟突围盒六个顶点深度值与对应地位四周的四个像素的深度值判断物体是否被遮挡。

（4）依据（3）剔除的后果绘制汇合 1，更新深度 Buffer。

（5）解决汇合 2：利用新的深度 Buffer 建设 Mipmap 深度图，对汇合 2 进行剔除。

（6）绘制汇合 2 中物体，更新深度 Buffer。

值得注意的是：咱们对剔除的判断是在几何 Shader 中进行，实现物体可见性判断后，利用 Transform Feedback 将可见性数据流传回到顶点 Shader 中，这样能够防止数据从 GPU 写回到内存。

9. PVS
剔除阶段：应用程序阶段。

像其余剔除办法一样，预计算可视性体积用于实现中小型场景的性能优化，通常用于因为硬件问题而使动静遮挡剔除受到限制的挪动平台。预计算可视性体积依据玩家或摄像机的地位，将 Actor 地位的可视性状态存储在场景中。

因为预计算可视性是在线下生成的，因而能够省去用于硬件遮挡查问的渲染线程工夫，但代价是会减少运行时内存和照明构建工夫。基于这一点，倡议仅在玩家或摄像机可拜访区域搁置体积来放弃可视性剔除。

规范 PVS 分为两步：
1、先求解繁难模型：减面，枚举模型上每个顶点，找到一个点使得删除该顶点，模型变形最小，不停地寻找并删除影响最小的点直到模型变形超过肯定阀值。最终求解出繁难场景模型，为第二步计算做筹备。

2、划分成小的三维格子，在格子外面平均或随机选取 N 个采样点作为摄像机地位，每个采样点 360 度全方向做肯定数量的射线进来，和场景中的模型判断交点，求解出该采样点的 PVS，而后合并格子里 N 个采样点的后果为该格子的 PVS。有离线计算好的，也有实时计算摄像机四周空间未计算格子的，等摄像机挪动到那里时曾经计算好了，无外乎精度不同。理论绘制时将所在格子的 PVS 提取进去再做一次视锥剔除就行。

三、总结

本文次要对以后引擎罕用的一些剔除算法做了综述。剔除的实质是耗费大量的计算剔除尽可能多的物体，如果场景物体不简单或者说相互遮挡不多，此时用一些计算简单的剔除算法反而可能使帧率升高。因而，须要依据不同的状况抉择适合的剔除办法，例如对于有大量植被实例场景能够思考设置间隔剔除，场景中有比拟大的遮挡物则能够思考 Occluder 剔除，在手机平台咱们能够思考基于预计算剔除 PVS 等，通过这些剔除算法来晋升游戏场景帧率。

四、参考文献

1. https://docs.unrealengine.com…
2. https://blog.csdn.net/game_fe…
3. https://zhuanlan.zhihu.com/p/…
4. https://www.intel.com/content…
5. https://bazhenovc.github.io/b…
6. https://developer.nvidia.com/…
7. https://www.gamedev.net/artic…
8. https://gameinstitute.qq.com/…
9. https://www.khronos.org/openg…
10. https://www.rastergrid.com/bl…
11. https://zhuanlan.zhihu.com/p/…
12. https://www.zhihu.com/questio…

这是侑虎科技第 1224 篇文章，感激作者 Mangoo 供稿。欢送转发分享，未经作者受权请勿转载。如果您有任何独到的见解或者发现也欢送分割咱们，一起探讨。（QQ 群：793972859）

作者主页：https://www.zhihu.com/people/…

再次感激 Mangoo 的分享，如果您有任何独到的见解或者发现也欢送分割咱们，一起探讨。（QQ 群：793972859）