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

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

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

  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接口：

//生成查问物体IDglGenQueries(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）