UE预计算遮挡剔除（PVS）全解析
导语预计算遮挡剔除（PVS）已经是一个20多年的技术，得益于在移动端平台上所展现的综合性能，但在各种新兴的更高效灵活更精细剔除方法中仍有跻身之处。文章解析Unreal 4自带的PVS系统流程，并给出PVS技术的若干前沿方向，供交流学习。
前序
预计算遮挡剔除技术是实时图形学中渲染优化技术的一种方案，在20几年前就已经被应用在早期的3D游戏中，以提升游戏的实时交互性能。现在2020年，灵活的可编程图形管线已经支持更多不同方案的剔除方法，在主机和PC端中成为预计算遮挡剔除技术的替代品。然而在手游时代，在显存带宽和图形API的限制下，预计算遮挡剔除技术仍旧能够在部分应用场景中作为可选的方案之一。Unreal 4引擎也一直保留预计算遮挡剔除技术，给不同需求的场景提供渲染优化支持。
在预计算遮挡剔除技术学习了接近两年，把这一块知识的理论和实践方法前前后后都了解了一遍（其中区域网格划分这一块感觉理解还不足够，考虑之后暂时移除，等学习更充足之后再进行补充）。最近也在公司中做了技术分享，想着还是把它写下来，分享给更多有兴趣的伙伴们，希望可以和大家多交流学习。感谢！
文章的大纲如下：
1. 遮挡剔除技术概览
1.1. 遮挡剔除的目的、方法和分类
1.2. 预计算遮挡剔除技术概览
1.3. 系统预测关系
2. 预计算遮挡剔除技术实现
2.1. 系统流程
2.2. 光线采样
2.3. 运行结果
3. 预计算遮挡剔除前沿方向
3.1. 空间加速结构
3.2. GPU光栅化获取遮挡信息
4. 参考文献
1 遮挡剔除技术概览
1.1 遮挡剔除的目的、方法和分类
一个经典的图形前向渲染管线如图表 1，模型数据以三角形的方式传输到GPU端之后，并在发生绘制调用（DrawCall）时，在顶点着色器中进行顶点变换等操作，得到在标准设备坐标系（NDC）中的顶点之后，在光栅化器中进行光栅化得到像素点之后，在像素着色器进行着色计算，给每个像素确定颜色之后，进行深度测试，确定前后遮挡关系。在流程中，存在大量的像素经过了管线中复杂的计算之后被丢弃，这种造成多此性能浪费的绘制也被称为过度绘制（OverDraw）。在单个模型渲染中，过度绘制可能达到20次以上（一个像素上被重复绘制20次以上，实际上只有最上面的像素会生效），更别说整个场景会由大量的模型共同构成。
图表 1 前向渲染管线
减少过度绘制也自然成为了渲染优化中的一大问题。包括视锥剔除、面剔除和遮挡剔除等，如图表 2。遮挡剔除通过绘制调用发生之前预测对象的遮挡关系，跳过部分不可见的渲染对象来完成。
图表 2 剔除技术示意图
遮挡剔除需要在特定的时机，以特定的粒度进行剔除。根据剔除粒度、遮挡信息的获取、剔除时机和方法等可以被区分为多种方案。剔除的粒度会包括模型、子模型、三角形和像素等；遮挡信息的获取主要分为在线和离线两种方案，描述寻找遮挡关系这个过程是发生在每帧绘制时还是在游戏烘焙阶段。剔除的时机可以发生在CPU端、顶点阶段、像素阶段。细粒度和较早发生的剔除对性能的提升更为明显，但本身剔除也会有开销，需要根据应用场景综合考虑。
剔除的指标包括三个：
剔除优化率：开启剔除之后的性能优化比例剔除正确性：把本来可见的物体错误剔除掉，造成渲染错误剔除开销：执行剔除计算带来的空间和时间开销
遮挡剔除的常见几类方法：
渲染路径：实际上PreZ管线和延迟管线技术是从渲染流程上实现了一个像素级别的遮挡剔除，具体的渲染流程可以查阅更多相关资料。在线剔除方法：配合硬件遮挡查询（Occlusion Query）技术，先用低成本的查询阶段获知绘制所影响的像素量，再决定要不要调用复杂的渲染绘制。软遮挡查询技术（Software Occlusion Culling），在CPU端做一个简易的软光栅化器，结合CPU的SSE指令集快速查询遮挡关系。利用层级深度缓冲（Hierarchical Z Buffer）在GPU中做深度查询，巧妙利用mipmap来降采样深度贴图，使得遮挡查询过程的深度比较能够高效完成。差帧剔除技术，上一帧的深度贴图结合移动矢量（Motion Vector）一起为这一帧提供深度信息参考，可以重用TAA的部分资源。
离线方法：在本文中主要提及的预计算遮挡剔除技术
1.2 预计算遮挡剔除技术概览
预计算遮挡剔除技术根据流程也直接能够分成三块，如图表 3。首先进行空间划分，把场景划分成多个规则的三位网格，对每个网格预先计算好能够看见什么物体，看不到哪些物体，将信息序列化后保存并打包进游戏中。在运行的时候，根据相机当前的位置，读取所在的网格的可见性信息，在CPU设置可见性并提交绘制。
图表 3 预计算遮挡剔除技术总体流程
预计算遮挡关系中系统会离线求解一个潜在可见集（Potential Visible Set），这是一个预测过程，其预测的收敛集合是精确可见集（Extra Visible Set）。
在Unreal 4引擎中，预计算遮挡剔除系统的名字是Precomputed Visibility System，和潜在可见集的缩写一样都是PVS，这个也是特别的巧合。PVS在早期的学术论文中就被用来表示预计算遮挡剔除的这个过程，其实是潜在可见集的缩写。
1.3 系统预测关系
上文说到预计算过程是一个预测过程，他们的预测关系如表格 1。可以看到系统的I类错误和II类错误，其中第I类错误是将不可见的预测为可见，会影响剔除优化率；而第II类错误是将可见的预测为不可见，会导致渲染的时候发生错误，是相比于第I类错误更加严重的错误，需要尽量保证在一个可以接受的范围内。
真实值预测值可见不可见可见预测正确第I类错误不可见第II类错误预测正确
表格 1 系统预测关系表
2 预计算遮挡剔除技术实现
2.1 系统流程
系统分为预计算过程和运行时剔除过程，流程图如图表 4。
图表 4 预计算遮挡剔除系统流程在预计算过程中，需要区域网格划分和可见性判定是最核心的部分。区域网格划分需要找到场景中相机可能达到的区域，并且将区域按照一定的规则划分成网格。系统会先在场景俯视平面上进行等间距划分，如图表 5。之后再根据实际场景在垂直方向上划分。
图表 5 区域网格划分示意图
垂直方向上的划分会更为复杂一些，一方面是场景的地面高度需要确定，如图表 6，另一方面是场景常常包含有多个高度层，如图表 7，例如多个楼层、桥面桥下等，还要考虑跳跃、轻功等会让相机到达更高的位置。因网格数量会与占用空间大小和预计算花费的时间成正比，不同高度级别的区域最好用不同的网格间隔开（一楼和二楼用不同的网格因为可见集的差异性很大），所以在实际项目中使用时这一块需要做深度的定制，提升整体性能。
图表 6 确定地面高度
图表 7 寻找多个高度层
分完三维网格之后就是可见性检测了，这个问题可以描述为：在场景的遮挡物（Occluder）中，求解每个区域网格（Cell）到每个被遮挡物（Occludee）是否可见。这里头的遮挡物和被遮挡物之间并非强关联关系，比如说树木可以作为被遮挡物，用来计算需不需要被剔除，但是树叶本身感觉不能很严实地挡住别人的光线，所以一般不作为遮挡物来影响别的被遮挡物的可见性计算。区域网格一般是轴对齐包围盒AABB，遮挡物是遮挡物本身模型，为了简化计算，被遮挡物会也会采用包围盒OBB甚至轴对齐包围盒AABB来求解。求解的过程会用光线投射来实现，从网格中发射大量光线到被遮挡物中，如果其中有光线能够到达，那么预测这个网格可以见到这个被遮挡物。如图表 8和图表 9。
图表 8 可见性判定为可见
图表 9 可见性判定为不可见
图中左边框框为区域网格，蓝色为遮挡物，绿色为被遮挡物。很容易会有一个疑问，每一对（网格到被遮挡物）的可见性判定，需要采样多少个光线，是否能够确信它们是完全不可见。在系统中采样光线数量会根据大小和距离来判定，但在这种隐式表面的遮挡计算中，无论多少次的光线投射，都无法完全确信不可见，这也是前文中的第II类错误的由来。为了降低这个错误，Unreal 4还采用了很多保守的做法，例如将被遮挡物的模型包围盒扩大1.2倍来计算，如图表 10。还有一个保守方案是在计算的时候用重要性采样（Importance Sampling）策略来补足，在所有光线都判定为不可见之后，将其中最长的前5% 的光线，随机偏转一个小角度，如果能够到达目前长度的120%，认为被遮挡物可见，如图表 11，这个操作相对来说并不是完全无偏的，说不上来为什么需要怎么做，也说不上来和重要性采样有什么擦边。还有一个保守操作就是烘焙完成之后，把每个格子的可见性再“或“给周围的网格。
图表 10 包围盒扩大1.2倍
图表 11 重要性采样
这些操作确实能让系统更加地保守，但也让I类错误不断升高，让遮挡剔除率不断下降。我们希望有更好的做法是在更多的地方保证II类错误的发生概率，而不是拿I类错误的上升来换II类错误的降低。
计算完成之后按每个网格的可见性信息存下来，每个遮挡物用1个bit，那么数据容量会是网格数量乘以被遮挡物数量除以8。实际上如果可见性数据中存在大量的0和大量的1相连，数据压缩就有更大的发挥空间。反过来也可以启发在被遮挡物在排列序号的时候，应该尽量让聚集的模型的序号连在一起。
预计算遮挡剔除系统在运行时的消耗极小，只需要索引出来相机所在的网格，拿到网格的可见集数据，设置渲染器的开关即可完成剔除。这也是这个技术方案的一大优点，可以在手游这种资源吃紧的平台有更好的发挥空间，拿到一个还算过得去的剔除效果。
系统的扩展性还比较高，可以扩展支持流式加载、LOD、花海草海、特效渲染物件和小型的动态物件等，这种都是去做项目适配的时候需要花很多时间的地方。
2.2 光线采样
在前面一节中描述了整个系统的流程，但在如何进行光线采样一部分一笔带过，因为“从一个AABB到一个OBB”的表面采样光线的起始点的这个工作并不简单，所以单独拎出来作为一个小节去描述。
先说一下Unreal 4的做法，如图表 12，在绿色的Cell网格到红色的Occludee网格中心连线，计算Cell的每个面与连线的夹角，大于0认为其为可见面，具体数值作为概率密度函数（PDF），根据PDF进行重要性采样，取其中一个可见面，在面上随机采样点作为光线起点。Occludee亦然，得到起点和终点之后就可以进行光线投射了。
图表 12 连接网格到被遮挡物的中心，判断可见面
但4这个过程其实是有偏差的。我们简化地从二维来看，这样的方式，确定了Cell只有1到2个面能见到Occludee，Occludee也是，但实际上并非如此，如图表 13。Cell的三个面会见到Occludee的一个面。
图表 13 网格的一个面可以见到被遮挡物的三个面
这导致的问题是光线产生自相交，如图表 14，在符合上面的这种采样逻辑的情况下，采样出来的光线穿过了Cell和Occludee本身，如果碰撞的发生点在于Cell和Occludee内，这个光线就会判定为不可见。虽然说还有别的光线，但是这个光线就浪费了。还有就是在极端情况下，这样的逻辑甚至会带来错误。如图表 15，如果黑色是遮挡物，用前面的采样方法算出来的所有光线都会被遮挡，但实际上它们是可见的，如图表 16。
图表 14 光线采样发生自相交
图表 15 极端情况下所有采样到的光线都被遮挡
图表 16 实际上网格到被遮挡物之间是可见的
这种采样本身还会很影响采样的均匀性，可能使得采样点不按照实际使用场景分布，这表明这个过程是一定还有改良空间的。如果想要让每个光线都采样得更有价值，更加均匀，需要从理论上考虑光线应该是怎样分布才更加合理。
我们计算光线投射，是为了模拟在真实场景中相机是否能够看到某一个模型。那么对于相机来说，在整个Cell体积里面均匀采样就可以了，接下来考虑的是，在一个确定的点（不是整个Cell了），怎么样采样Occludee的OBB呢。
答案是视角，如图表 17，从绿色点观看红色OBB时，整个OBB到视角点的角度，就是实际上这个OBB在视角中占用的大小，只需要给定每1°的角想要采样多少个光线即可。那么我们可以通过连接中线，如图表 18，在中线上做两个边角点的垂线，在垂线上均匀采样。而且用这种方法，可以均匀地给每一个物体定义最大光线数量。
图表 17 特定视点下被遮挡物的投影角度
图表 18 连接中点作垂线，从垂线上均匀采样
理论上如此，等到实现的时候发现，问题其实不简单。因为这个场景是三维的，如图表 19。在三维场景中，用一个点去观测一个OBB，投影面会是一个四边形或者六边形，在透视关系下还会显得更加不规则，这个时候去计算立体角的大小，和在立体角中进行采样都会变得很困难。
图表 19 三维场景中的视点对包围盒的投影关系
即使实际上它是有解的，但感觉还还需要时间去做推导，在工程上我需要的只是一个比起Unreal 4现有方案好一些的就可以了，于是我考虑了一个能够更加简单完成的方法，从体积到体积的采样。
首先在Cell中均匀采样点A，从Occludee上采样点B。然后在A到B中间连线，用线与OBB的求交算法分别求解两个交点避免自相交，用这两个交点作为光线的起始点和终止点，如图表 20。虽然这个方法在采样上还不是特别的均匀（密集与两个物体中心区域），但对比起来已经解决了原有方案的很多问题，这个小小的改动没有花费更多的性能，就能让采样到的光线更有价值，结果上看也是可以接受的。
图表 20 从体积到体积之间的光线采样
除此之外，我还在边角采样、改进随机算法、改变光线投射循环退出条件等地方做了小的优化。随机算法改动的改动缘于看到了一个文章说随机采样会产生丛聚现象，如图表 21，而均匀采样则需要提前确定采样数量，不利于最快速退出循环，且对于缩放不友好。低差异序列采样可以很好地解决这些问题，霍顿（Halton）序列的采样顺序很像是每次都去寻找一个“当前最空旷的采样区域”进行采样，而且不需要提前知道总的采样数量，更加适合光线采样过程。
图表 21 随机采样、均匀采样与低差异序列采样
2.3 运行结果
运行结果如图表 22和图表 23，测试场景是大学的一个校区的低多边形风格场景，相机活动区域是64万㎡，场景有2780个模型，三角形的总数量为402K，遮挡物一共是132个。网格数量、剔除时间和剔除率的关系如图表 24，在划分成5000个网格时，可以用1.6MB的空间和320秒的预计算时间（intel i5-4200M八线程并行计算）来换得平均69%左右的剔除率，优化效果是还是比较好的，但具体的优化效果也和场景本身有关系。
图表 22 网格划分结果
图表 23 遮挡剔除运行结果，看不到的被遮挡物用红色标记出来
图表 24 网格数量与预计算时间和遮挡剔除率的关系
在图表 24中也可以看到，PVS的剔除率已经达到了68%~71%这个范围，而本身剔除的收敛极限EVS的剔除率也不会达到100%（不可能把整个场景都剔除了）。所以实际上PVS已经很接近EVS，I类错误在这里影响并不大，它的主要来源是：
使用了区域可见性并集作为视点可见性使用了AABB代替复杂模型进行判定，AABB是肯定会大于模型本身的使用了遮挡物筛选规则，为了预计算效率，很多小的物件不算入遮挡物
而II类错误来源于无法遍历所有的光线，在后面我们会做更详细的推导，如何让II类错误尽量地小。
3 预计算遮挡剔除创新方向
说是创新方向，其实也是一些10年前就被提及的技术。只是在应用上还没铺开，并不算很稳定成熟的方案。还有一些额外的方向，在编写这篇技术文章的时候也还没有完全吃透，也在之后再继续做补充吧。
3.1 空间加速结构
光线投射过程的复杂度是很高的，计算这个过程需要4个循环参与，遍历网格、遍历被遮挡物、遍历多个光线数量和遍历遮挡物，如图表 25。其中最外层循环采用了并行加速，而最内层循环是进行光线投射判定，这个过程可以用空间加速结构去完成，例如NVidia的PhysX库就提供了基于表面启发式（SAH）生成的AABB元素类型的层次包围盒（BVH），可以把O(n)的复杂度降到O(logn)。第三层循环是多个光线，无法进行修改。那么第二层循环是否也可以考虑用BVH或者其他空间加速结构呢？
图表 25 核心遍历算法伪代码截图
Unreal 4确实有这么一个加速计算的设定，将大量的Occludee按照地理位置划分成组（Group），每个网格计算可见性时先对所有的Group进行计算，如果不可见则整组的被遮挡物都可以直接设置为不可见，如图表 26。
图表 26 Unreal 4引擎自带的Group优化
这种按照地理位置分组的加速结构，会比BVH更好吗？在跟踪性能的时候发现，Group本身有开销，但里面的被遮挡物的大小和数量都不固定，这使得Group带来的优化效果不稳定，有一些很好，有一些带来了负优化作用。于是我转用BVH进行实验，企图在第二层循环也达到了(logn)的复杂度，毕竟BVH会更高效。
实验的结果是，在BVH的作用下，算法可以在多造成2%的II错误率上节省40%的预计算时间。2%似乎还能接受，实验到这里头脑发热，想着干脆把最外层循环也改成BVH结构（并行需要改成对BVH树并行），一通实验之后发现算法再多造成5%的错误率下，可以再节省60%的预计算时间。整个算法一路从一开始的6小时多降到了12分钟，再通过BVH神奇操作降到了178秒。
在感受完实验带来的惊喜之后冷静下来，再慢慢整理资料发现，原来单纯用预计算时间去换的话，随着最大光线阈值的不断提高算法的错误率是一个收敛极其缓慢的过程，用40%的时间优化率去换2%的错误率根本不值得。如果不做第一层第二层的BVH，直接运行起来，给与程序这么大的错误率宽容度的话，程序需要的时间仅仅是133秒。也就是BVH的优化是负优化。
负优化是可以有直观原因的：用大的盒子去装几个小的物体的时候，盒子体积本身变大，那么更容易被视角看到，如果被看到了，那么这个结点就会是浪费性能。体积大的盒子还会要求需要更高的最大光线阈值，这使得BVH并不是完全有优的。
图表 27 从网格到模型之间有α概率可见
如图表 27，假定某个Cell中可见到某个Object的比率为α，投射n次光线之后，II类错误率为：
求导得到：
令
可得错误率上限为：
考虑
曲线，如图表 28，
想象一下100个光线就使得这一对的判定错误率小于0.37%了，200个光线就错误率更是低至0.18%，而实际上工程中我用了300~400的光线阈值，容易有一个错觉，就是错误值会很低。实际上，由于区域网格和被遮挡物都有体积大小，计算错误的时候需要计算的是错误期望而不是错误率。体积大的区域网格，会比体积小的区域网格有更大的错误代价，我们应该计算的是类似于以下式子：
其中是上一小节说的投影立体角。换言之，想要计算清楚每个网格到每个被遮挡物应该分配多少个光线，每个BVH结点是否为有优，都需要去计算这个立体角。后来在一篇论文中看到了关于这个光线数量的计算，应该是这篇：《Efficient Occlusion Culling with Occupancy Proportion》。如果还有往这个方向做研究的话还是要去完成这个棘手的问题。
图表 28 光线阈值与错误率上限的关系
3.2 GPU光栅化获取遮挡信息
传统的光线投射方法使用的是CPU计算，但是在遮挡判定这个事情上，明显拥有深度测试的GPU更加适合。在GPU上使用无光照的单色材质对场景中的静态对象进行渲染，将颜色缓冲区取回CPU，逐像素判定颜色，即可得知当前视角下的可见性。更加一般化的，我们的目的是在离线烘焙的时候获得某个区域下所有视角的遮挡信息，使用带有在线剔除方案的GPU渲染方法都是可以的。
GPU光栅化的方法在学术上是比较早期提出的，在《Optimized occlusion culling using five-dimensional subdivision》中描述了它的做法和效果。实验设计上，给每个被遮挡物设置唯一ID，转为RGR565颜色，设置无光照的单色渲染模型，如图表 29。关闭MSAA防止串色，关闭HDR和gamma矫正，关闭天空盒、后处理和各种特效。在特定点渲染一帧到CubeMap上，取回到CPU中进行逐个像素判定颜色，将颜色转换为被遮挡物ID。每个区域网格上采样多个视点的可见性信息，求并集即可作为网格的潜在可见集。这个过程中有两个很重要的参数：
渲染时的缓冲区分辨率，假定最后渲染时的分辨率为2000x2000，烘焙的时候使用分辨率为100x100，那么每个像素点会记录200x200个像素点的信息，这个对II类错误的影响非常大，如图表 30。但如果提升烘焙分辨率，那么PCIE和CPU的开销会很大影响烘焙效率，甚至慢于光线投射方法。另一个是每个网格采样的视点数。光线投射可以在网格中均匀采样光线，但GPU光栅化方法只能在网格中取样少量的视点，很难遍布整个网格，造成渲染错误，如图表 31。视点数量同样会是II类错误和烘焙时间的平衡。
这两个参数的制定使得GPU光栅化方法并非完全优于光线投射的方法，当参数调高时性能差于光线投射，但剔除率较高；当调整参数性能与光线投射平齐时，剔除率高的同时错误率也高，在预计算遮挡剔除中算是一种激进的提出方法。另外这种方法有一个不够灵活的地方，遮挡物和被遮挡物是耦合的，如图表 29中的树木，我们希望它能够作为被遮挡物，但不希望它作为遮挡物挡住后面树木的光线，但在这种颜色渲染的方法中没办法完成。可以采用的另一种灵活高效的方法是在线剔除的Occlusion Query。打开深度绘制，关闭颜色绘制，先绘制所有遮挡物，然后用Occlusion Query查询所有被遮挡物的尝试绘制的像素量。这个过程就不涉及PCIE的大量内存拷贝和CPU的逐个像素判定，可以支持更高的效率绘制，是一个很好的改进方法。
图表 29 场景模型单色渲染材质
图表 30 GPU光栅化的渲染贴图之一
图表 31 左侧网格中采样4个点的可见性，错误将绿色被遮挡物认定为不可见
4 参考文献
知乎：适合于移动平台的预计算遮挡剔除知乎：游戏中遮挡剔除方案总结知乎：浅谈软遮挡剔除知乎：【游戏场景剔除】剔除算法综述知乎：剔除：从软件到硬件GitHub：Unreal4源码Nirenstein S, Blake E. Hardware Accelerated Visibility Preprocessing Using Adaptive Sampling. 2004,Durand F. 3D Visibility: Analytical Study and Applications. Proceedings of PhD Dissertation published 1999, 1999,Cohen-Or D, Chrysanthou Y L, Silva C T et al. A Survey of Visibility for Walkthrough Applications. Ieee T Vis Comput Gr, 2003, 3; 3: 412-431Nirenstein S, Blake E, Gain J. Exact From-Region Visibility Culling. In, edEurographics, 2002. Laakso M. Potentially Visible Set (Pvs). Helsinki university of technology, 2003,Van De Panne M, Stewart A J. Effective Compression Techniques for Precomputed Visibility. In, ed. Rendering Techniques’ 99. Springer, 1999. 305-316Gotsman C, Sudarsky O, Fayman J A. Optimized occlusion culling using five-dimensional subdivision. Computers & Graphics, 1999, 23(5): 645-654.Li B, Wang C, Li L. Efficient occlusion culling with occupancy proportion//2008 International Conference on Computer Science and Software Engineering. IEEE, 2008, 2: 1058-1061.
写得不赖 感谢
[干杯] 666 强悍，膜拜大佬[赞] 有理有据 棒[赞同]
页:
[1]