本文由@浅墨_毛星云 出品，转载请注明出处。
文章链接： http://blog.csdn.net/poem_qianmo/article/details/78884513
二、裁剪技术 | Culling Techniques
裁剪（Culling）的字面意思是“从大量事物中进行删除”。在计算机图形学中，相对应的就是裁剪技术（Culling Techniques）所要做的工作——“从大量游戏事物中进行删除”。所谓的“大量事物”就是需要绘制的整个场景，删除的是对最终图像没有贡献的场景部分，然后将剩余场景发送到渲染管线。因此，在渲染方面通常使用“可见性裁剪（Visibility Culling）”这个术语。但其实，裁剪也可以用于程序的其他部分，如碰撞检测（对不可见物体进行不十分精确的计算）、物理学计算，以及人工智能（AI）领域。
与渲染相关的裁剪技术，常见的有背面裁剪（Backface Culling），视锥裁剪（View Frustum Culling），以及遮挡裁剪（Occlusion Culling，也常常称作遮挡剔除）。
- 背面裁剪即是将背向视点的物体删除，是一种非常简单直观的操作，只能一次一对个单一多边形进行操作。
- 视锥裁剪是将视锥之外的多边形删除，相对而言，这种操作比背面裁剪稍微复杂。
- 遮挡裁剪，是将被其他物体遮挡的物体进行删除，这种操作在三者中最为复杂，因为其需要聚集一个或者多个物体，同时还需使用其他物体的位置信息。
理论上，裁剪操作可以发生在渲染管线的任何一个阶段，而且对于一些遮挡裁剪算法来说，甚至可以预先计算出来。对于在硬件中实现的裁剪算法来说，有时只需启动/禁止或者设置一些裁剪函数即可。而为了进行完全控制，我们可以在应用程序阶段在（CPU上）实现一些裁剪算法。假设瓶颈位置不在CPU上，渲染最快的多边形就是没有送到图形加速器管线上的多边形，裁剪通常可以使用几何计算来实现，但也不局限于此。例如，某算法也可以使用帧缓冲中的内容。
而理想的裁剪算法预期是只发送所有图元中通过管线的精确可见集(Exact Visible Set ,EVS)。
下图是三种裁剪技术的对比图示。
下文接下来将分别介绍背面裁剪、层次视锥裁剪、入口裁剪、细节裁剪、遮挡剔除等几种裁剪技术。
三、背面裁剪 | Backface Culling
假设你正在观察一个场景中不透明的球体。大约有一半的球体是不可见的。那么，可以从中这个例子里得到一个众所周知的结论，那就是，对不可见的内容不需要进行渲染，因为它们对最终的渲染图像没有贡献。
不需要对球体的背面进行处理，这就是背面裁剪的基本思想。对于一组物体来说，还可以一次性地进行背面裁剪，这也称为聚集背面裁剪（Clustered Backface Culling）。
图14 确定多边形是否背向的两种不同测试。左图所示为屏幕空间的测试情形，三角形和四边形是正向，而七边形是背向。对背向的七边形，无需进行光栅化。
右图为视点空间中背面测试情形，多边形A是背向的，而B和C是正向的。多背向的多边形A，无需进行光栅化。
四、层次视锥裁剪| Hierarchical View Frustum Culling
如上文所示，只需对完全或者部分在视锥中的图元进行渲染。一种加快渲染速度的方法便是将每个物体的包围体与视锥进行比较，如果包围体位于视锥之外，那么便不需要渲染包围体中的几何体。由于这些计算在CPU上进行，因此包围体中的几何体不需要通过管线中的几何和光栅阶段。相反，如果包围体在视锥内或者与视锥相交，那么包围体中的内容就是可见的，所以必须发送到渲染管线中去。
利用空间数据结构，可以分层地来应用这种裁剪。例如，对于层次包围体BVH来说，从根节点进行先序遍历（Preorder Transversal），就可以完成这一任务。
图15 左图所示为一组几何体和相应的包围体（球体），从视点位置使用视锥裁剪来渲染场景。右图所示为层次包围体，视节点的包围体与视锥相交，对子包围体进行遍历测试，左子树的包围体与视锥相交，而其中只有一个子节点与视锥相交，另外一个子包围体体外边，无需发送到管线。根节点中间子树的包围体完全位于视锥内部，可以立即进行渲染，右边的子树的包围体也完全位于视锥内部，所以不需要进一步测试就可以渲染整个子树。
视锥裁剪操作位于应用程序阶段（CPU），这意味着几何阶段和光栅阶段都可以从中受益，对于大场景或者一定的相机视线来说，场景只有一小部分是可见的，只需要将这部分发送到渲染管线。可期望获得一定的加速效果，视锥裁剪技术利用了场景中的空间相关性，因为可以将彼此靠近的物体包围在一个包围体中，而且几乎所有包围体都是以层次形式聚集在一起。
除了层次包围体，其他的空间数据结构同样也可以用于视锥裁剪，包括上文提到的八叉树和BSP树。但是当渲染动态场景时，这些方法便会显得不够灵活,不如层次包围体。
五、入口裁剪 | Portal Culling
对建筑物模型来说，很多裁剪方面的算法可以归结为入口裁剪（Protal Culling）。在这个方向，最早的算法由Airey提出，随后Teller和Sequin，以及Teller和Hanrahan构造出了更高效，更复杂的算法。
入口裁剪算法的基本思想是，在室内场景中，建筑物墙面通常充当大的遮挡物，通过每个入口（如门或者窗户）进行视锥裁剪。当遍历入口的时候，就减小视锥。
使得与入口尽可能紧密贴合。因此，可以将入口裁减算法看作是视锥裁剪算法的一种扩展，且需将位于视锥之外的入口丢弃。
入口裁剪方法以某种方式对场景进行预处理，可以是自动形式，也可以是手动形式，可以将场景分割为一系列单元（Cells），其通常对应于建筑物中的房间或者走廊；链接进阶房间的门和窗口称为入口（Protals）。单元中的每个物体和单元的墙面可以存储在一个与单元关联的数据结构中，还可以将邻接单元和链接这些单元的入口信息保存在一个临接图中。
六、细节裁剪 | Detail Culling
细节裁剪（Detail Culling）是一种通过牺牲质量换取速度的技术。其基本原理是，当视点处于运动的时候，场景中的微小细节对渲染出的图像贡献甚微。，当视点停下来的时候，通常禁止细节裁剪。
考虑一个具有包围体的问题，将这个包围体投射到投影平面，然后以像素为单位来估算投影面积，如果像素的数量小于用户定义的阈值，那么不对这个物体进行进一步处理。基于这个原因，细节裁剪也往往被称为屏幕尺寸裁剪（Screen-Size Culling）。细节裁剪也可以在场景图上以层次形式来实现，几何阶段和光栅阶段都可以从这个算法中受益。
另外，细节裁剪还可以作为一种简化的LOD技术来实现，其中一个LOD是整个模型，另外一个LOD是空物体。
七、遮挡剔除 | Occlusion Culling
遮挡裁剪（Occlusion Culling），也常被称作遮挡剔除。
聊一聊遮挡剔除必要性。不难理解，可见性问题可以通过Z缓冲器的硬件构造来实现，即使可以使用Z缓冲器正确解决可见性问题，但其中Z缓冲并不是在所有方面都不是一个很“聪明”的机制。例如，假设视点正沿着一条直线观察，其中，在这条直线上有10个球体，虽然这10个球体进行了扫描转换，同时与Z缓冲器进行了比较并写入了颜色缓冲器和Z缓冲器，但是这个从这个视点渲染出的图像只会显示一个球体，即使所有10个球体都将被光栅化并与Z缓冲区进行比较，然后可能写入到颜色缓冲区与Z缓冲区。
下图中间部分显示了在给定视点处场景的深度复杂度，深度复杂度指的是对每个像素重写的次数。对于有10个球体的情形，最中间的位置，深度复杂度为10，因为在这个地方渲染了10个球体（假设背面裁剪是关闭的），而且这意味着其中有9次像素写入是完全没有必要的。
像上图这样无聊极端的场景，现实生活中很难找到，但其描述的这种密集性很高的模型的情形，在现实生活中却很常见，如热带雨林，发动机，城市，以及摩天大楼的内部。下图显示了曼哈顿式城市的示例。
从上面给出的示例可以看出，这种用来避免低效率的算法可以带来速度上的补偿，具体可以将这些方法归类为遮挡裁剪算法（Occlusion Culling Algorithms），因为它们都试图裁剪掉被遮挡的部分，也就是被场景中其他物体遮挡的物体，最优的遮挡裁剪算法只选择其中可见得的部分。
有两种主要形式的遮挡裁剪算法，分别是基于点的遮挡裁剪和基于单元的遮挡裁剪。如下图所示。
图20 左图所示为基于点的可见性，右图所示为基于单元的可见性，其中单元是一个长方形，从中可以看出，从视点左边看上去，有些圆被遮挡了，但是从右边看上去，这些圆却是可见的，因为可以从单元的某个位置到这些圆画一些射线，这些射线没有和任何遮挡物相交
下图所示为一种遮挡裁剪算法的伪代码。
有多种不同种类的遮挡剔除算法：
- HardwareOcclusion Queries 硬件遮挡查询
- HierarchicalZ-Buffering 层次Z缓冲
- OcclusionHorizons 遮挡地平线
- OccluderShrinking 遮挡物收缩
- FrustumGrowing视锥扩张
- Virtualoccluder 虚拟遮挡物算法
- ShaftOcclusion Culling 轴遮挡裁剪
- TheHOM algorithm 层次遮挡映射算法
- RaySpace Occlusion Culling 射线空间遮挡剔除
下面将对其中的常见几种介绍。
7.1 硬件遮挡查询 | Hardware Occlusion Queries
现代GPU可以以一种特殊的渲染模式来支持遮挡剔除。通过硬件遮挡查询（Hardware Occlusion Queries），我们能够直接获得所提交的物体是否被绘制到场景中。
简单来说，硬件遮挡查询的基本思想是，当和Z缓冲器中内容进行比较时，用户可以通过查询硬件来找到一组多边形是否可见的，且这些多边形通常是复杂物体的包围体（如长方体或者k-DOP）。如果其中没有多边形可见，那么便可将这个物体裁剪掉。硬件实现对查询的多边形进行光栅化，并且将其深度和Z缓冲器进行比较。
更多细节，可以参考这篇论文：Bittner J, Wimmer M, Piringer H, et al. Coherent hierarchical culling: Hardware occlusion queries made useful[C]//Computer Graphics Forum. Blackwell Publishing, Inc, 2004, 23(3): 615-624.
7.2 层次Z缓冲 | Hierarchical Z-Buffering
层次Z-缓冲算法（Hierarchical Z-Buffering ，HZB）是由Greene等人提出的一种算法，对遮挡剔除的研究有着显著的影响。尽管其在CPU上很少使用，但该算法是GPU上做Z-Culling（深度裁剪）的基础。
层次Z-缓冲算法用八叉树来维护场景模型，并将画面的Z缓冲器作为图像金字塔（也称为Z-金字塔（Z-pyramid）），该算法因此在图像空间中进行操作。其中，八叉树能够对场景的遮挡区域进行层次剔除，而Z-金字塔则可以对单个基元和边界体积进行层次Z缓冲。 因此Z-金字塔可以作为此算法的遮挡表示。
图21 使用HZB算法的遮挡裁剪示例，显示了一个复杂的场景（右下），相应的Z-pyramid(左图)，以及八叉树细分（右上）。通过从前到后遍历八叉树并裁剪遇到的八叉树节点，此算法可以仅访问可见的八叉树节点及其子节点（右上角的节点），的容器只对可见包围体中的多边形进行渲染。在这个例子中，遮挡八叉树节点的裁剪可以将深度复杂度从84，降低到了2.5。
更多细节，可以参考这篇论文：Greene N, Kass M, Miller G. Hierarchical Z-buffer visibility[C]//Proceedings of the 20th annual conference on Computer graphics and interactive techniques. ACM, 1993: 231-238.
7.3 其他遮挡剔除技术 | Other Occlusion Culling Techniques
前人在遮挡剔除方面已经做了大量的工作，但由于GPU的性能早已超过了CPU，所以这些算法中的大部分已经不再受青睐。因此这边只对一些常见的方案做一些简单介绍，至少他们还是值得传递下去的一些知识，因为架构和硬件的不断发展。
而随着多核系统的崛起，CPU端有了额外的资源，但难以直接给渲染本身带来提升，但同时使用单核或多核来执行基于单元的可见性测试或者其他进行方案，也已变得可以想象。
7.3.1 层次遮挡映射算法 | Hierarchical OcclusionMap
层次遮挡映射（Hierarchical Occlusion Map ，HOM)）算法，类似层次Z缓冲算法，是一种启用分层图像空间剔除的方法。但其也不同于层次Z缓冲，因为它提供了使用近似遮挡剔除的能力。 HOM算法的基本思想是，每帧建立一个分层深度缓冲区，用于遮挡测试。并且在每个级别使用不透明度阈值来确定是否有足够的要渲染的对象是可见的。如果只有一小部分的对象是可见的，那么该对象被剔除。但作为一个基于CPU的算法系统，这个算法已经不受欢迎了。
对此算法感兴趣的朋友，可以进一步参考这篇论文： Zhang H, Manocha D, Hudson T, et al. Visibility culling using hierarchical occlusion maps[C]//Proceedings of the 24th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 1997: 77-88.
7.3.2 遮挡地平线算法 | Occlusion Horizons
遮挡地平线（Occlusion Horizons）算法是一种非常简单的、基于点的可见性算法，可以对遮挡物进行融合，在基于点的可见性算法演示方面非常有用。由Wonka和Schmalstieg等人首先提出，并通过图形硬件将其进行了实现，随后Downs等人使用几何计算的方法将其独立开发实现，最早于1995年在电脑游戏中使用。
顾名思义，遮挡地平线算法的基本思想是裁剪掉位于地平线之间和之下的物体。 这种类型的算法经常被用来高效绘制如城市和村庄一样的城市环境。
通过从前到后渲染一个场景，我们可以定位到地平线在哪里进行渲染，而任何在当前地平线之后和之下的物体都可以被裁剪掉。
对此算法感兴趣的朋友，可以进一步参考这篇论文：Downs L, Möller T, Séquin CH. Occlusion horizons for driving through urban scenery[C]//Proceedings of the2001 symposium on Interactive 3D graphics. ACM, 2001: 121-124.
7.3.3 遮挡物收缩与视锥扩张算法 | Occluder Shrinkingand Frustum Growing
上文给出的遮挡地平线算法是基于点的可见性来判断的。有些时候采用基于单元的可见性方法更合适，但基于单元通常比基于点的可见性计算复杂度要高得多。Wonka等人提出了一种称为遮挡物收缩（Occluder Shrinking）的方法，可以使用基于点的遮挡算法来生成基于单元的可见性，根据给定的量来缩小场景中所有遮挡物来达到延伸有效可见点的目的。他们也提出了一种视锥扩张（Frustum Growing）技术，通常与Occluder Shrinking算法一起配合使用。
对此算法感兴趣的朋友，可以进一步参考如下三篇论文：
[1] Wonka P, Wimmer M, Schmalstieg D. Visibility preprocessingwith occluder fusion for urban walkthroughs[M]//Rendering Techniques 2000.Springer, Vienna, 2000: 71-82.
[2] Wonka P, Wimmer M, Sillion F X. Instantvisibility[C]//Computer Graphics Forum. Blackwell Publishers Ltd, 2001, 20(3):411-421.
[3] Wonka, Peter, Occlusion Culling for Real-Time Rendering ofUrban Environments,Ph.D. Thesis, The Institute of Computer Graphics andAlgorithms, Vienna University of Technology, June, 2001. Cited on p. 679
未完待续......
来源：CSDN，作者：浅墨_毛星云
原文：https://blog.csdn.net/poem_qianmo/article/details/78884513
版权声明：本文为博主原创文章，转载请附上博文链接！
