摘 要

消隐是指将场景中不可见的物体剔除，减少渲染开销的过程，而高效率的消隐对于游戏和三维图形处理等领域来说是一个非常重要的课题。特别是在现代大型虚拟场景中，渲染所占的开销极大，影响用户了的交互体验，这就需要有高效的消隐算法来降低硬件渲染的压力。传统的消隐算法只适应特定的场景，在复杂多变的大型场景下表现不佳，无法满足实际应用的需要。因此，对消隐算法的改进和研究愈发重要。

本文为了解决在大场景下的消隐问题，从基本理论出发，基于高效的遮挡表示形式和分层深度缓冲结构，对已有的消隐算法进行了多方面的优化和改进。利用基于区域的层次遮挡图结构来表示累积投影，从而在高分辨率的精度下有着媲美低分辨率的运行效率。经测试，本文实现的消隐算法只有很低的内存开销，相比于传统单一的消隐算法，支持多层级的深度缓冲和快速的剔除查询。在处理较大场景数据时，平均消隐效率高达96%，计算速度相比提升1倍以上。

关键词：计算机图形学；消隐；三维图形；大场景

Abstract

The elimination of hidden objects is the process of eliminating the invisible objects in the scene and reducing the overhead of rendering, and the efficient hiding is a very important topic in the fields of game and 3D graphics processing. Especially in modern large virtual scenes, the overhead of rendering is very expensive and affects the user's interactive experience. This requires a high efficient hidden algorithm to reduce the pressure of hardware rendering. The traditional hiding algorithm only adapts to specific scenarios, and performs poorly in complex and large-scale scenes, which can not meet the needs of practical applications. Therefore, it is more and more important to improve and study the algorithm.

In order to solve the problem of hiding in large scenes, based on the efficient occlusion representation and layered deep buffer structure, the existing hidden algorithms are optimized and improved in many aspects. We use the region based hierarchical occlusion graph structure to represent the cumulative projection, thus achieving a high resolution accuracy comparable to low resolution operation efficiency. After testing, the algorithm implemented in this paper has only a low memory cost. Compared to the traditional single hidden algorithm, the algorithm supports the multi-layer depth buffer and fast elimination of query. When dealing with large scene data, the average hidden efficiency is as high as 96%, and the computation speed is increased by more than 1 times.

Key Words：Computer Graphics；Hidden Surface Removal；Three-Demensional Graphics；Large Scene

目 录

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外研究现状 2

第2章 消隐方案设计 5

2.1 消隐算法的分类和选择 5

2.1.1 GPU辅助 5

2.1.2 完全 GPU 5

2.1.3 完全 CPU 6

2.2 视锥剔除 6

2.3 场景管理 8

2.4 深度缓冲 9

第3章 算法流程与实现 10

3.1 算法概述 10

3.1.1 问题分解 10

3.1.2 算法流程 12

3.2 场景数据获取与处理 14

3.2.1 数据的准备 14

3.2.2 数据的传输 14

3.3 实时遮挡体选择 14

3.3.1 Z平面 15

3.3.2 距离准则 15

3.3.3 时间相干性 16

3.4 三角形覆盖 17

3.5 分层深度缓冲 18

3.5.1 深度缓冲的更新 19

3.5.2 深度测试 20

第4章 测试结果 22

4.1 测试环境 22

4.1.1 场景图和空间层次 22

4.1.2 遮挡图 22

4.1.3 活动层次 23

4.2 深度缓冲可视化 23

4.2.1 深度数据处理 23

4.2.2 渲染深度数据 24

4.3 测试结果 24

4.3.1 城市场景 24

4.3.2 运行效率对比 25

4.3.3 帧率对比 26

4.3.4 准确度对比 27

第5章 总结与展望 28

参考文献 29

致谢 32

绪论

研究背景及意义

动态元素在现代游戏的环境和实时图形应用上越发普遍，用户可以更加自由的在虚拟世界中进行交互。这些动态元素在一定程度上增加了用户的代入感，提高了用户的体验，使他们更容易沉浸在虚拟世界中，但同时也给图形渲染带来了巨大的压力。

在图形流水线中，渲染的效率直接和当前所有的三角形几何绘制调用的数量有关，在复杂的大场景中，单次渲染的代价可能相当昂贵，从而极大影响用户的交互体验。当大型模型的交互渲染超过硬件系统的性能极限时，就必须采取措施减少每帧渲染图元的数量，而且这种减少不应该引入太多的视觉伪影，使得图元数量降低到图形硬件可以以交互速率处理的水平。

为了尽可能减少GPU渲染的压力、提高渲染效率、降低功耗，对场景消隐算法的研究也在逐步深入。场景消隐算法是基于一个事实，即如果观察者看不到对象，则不必呈现对象，只需要绘制可见的或者部分可见的对象。由于多种原因，场景中对象对于观看者可能是不可见的，例如观察者不能看到视场外的对象，也不能看到的封闭对象的内部。消隐算法就是用于确定3D场景中哪些表面或者三角形几何从某个角度看不可见， 对于不可见的物体，就可以直接从渲染的列表移除。

传统的基于预计算可见性检测的算法，例如潜在可见集、选择性光栅算法等愈发不能满足现今游戏引擎的需要。而基于软光栅的分层深度缓冲算法则显现出更大的优势。这类算法利用深度缓冲区在GPU渲染指令前进行可见性计算，对剔除大场景中的动态元素更加有效，消隐准确度也极高，但性能却不能令人满意。

消隐算法准确度和性能是天平的两端，在实际的大多是系统中都在寻求一个平衡点。一些做法是通过降低缓冲区分辨率，牺牲一定的准确度来提升性能。为了弥补过度的准确度损失，需要对场景中遮挡体的网格进行内包围盒计算。然而计算网格内包围盒是一个比较困难的工作，通常需要对网格进行体素化处理来确定体素是否在内包围盒内。有些体素具有二义性，会导致剔除计算出错，这就给设计模型的美术人员带来了诸多的限制和不便。

单一的消隐算法的运用很难在实际复杂场景中有很好的表现，因此本文综合多种消隐算法的优点，利用更高效的分层缓冲区数据结构，实现了一套实时大场景消隐的方案。这套方案的核心在于将一个数据块作为计算的基本单位。一个数据块用位掩码抽象表示了32x8像素区域的覆盖情况，从而可以在高缓冲区分辨率的情况下达到近似地分辨率的效率。这种数据结构对CPU友好，可以用SIMD指令加速计算，内存消耗低并且提升了消隐算法的计算和查询效率。

国内外研究现状

计算机图形系统需要正确显示可见的表面，这使得隐藏表面去除即可见表面确定成为计算机图形学中的一个基本问题。Sutherland定义了消隐算法的基本特征^[1]。给定几何模型和视角参数，隐藏表面算法计算出哪些表面或者部分表面对观察者可见。至今为止，消隐算法的研究主要分为三个阶段。

第一个阶段主要是对基本图元的研究，仅考虑比较简单的几何体之间的遮挡关系。其中比较有代表性的是Newell提出的深度排序算法^[2]。其核心思想是对基本图元进行排序，然后对其进行由后向前的渲染，从而确定正确的可见性。Fuchs利用二进制空间划分(BSP)，对多边形进行组织，从而加速了深度排序的过程^[3]。在此之上，Naylor描述了一种将目标空间中的三维BSP树投影到屏幕空间中二维BSP树的算法，对其进行优化和改进^[4]。

但是总体而言，使用BSP进行深度排序的一个最大问题在于，当多边形在树中注册时，常常需要分割多边形，对于个多边形的场景，最坏情况下可能需要生成个新的多边形。即使最坏情况在实际使用中很难出现，但是分割多边形涉及计算多边形的交点，可能会导致某些数值精度问题，不具有数值鲁棒性。

第二个阶段主要是研究全局可见性，预计算三维场景中任意观察者位置和视角下的可见性信息，并将其存储在特殊的数据结构中，在运行时，根据当前点从数据结构中取出对应的可见性信息。方位图作为其中的一个典型代表，被广泛的运用于当时的计算机视觉应用中^[5]。方位图用于描述观察者在空间中移动的变化，而这些变化被称为视觉事件。三维空间被细分为常数方位的体积空间，通过视觉事件发生的边界进行分隔，这个细分的对偶被称为方位图。针对凸或者非凸多面体，Plantinga提出了在平行投影或者透视投影下生成方向图的算法^[6]。该算法中额外引入了一个称为ASP的复杂数据结构来储存数据。Chang在透视投影下提出了非凸多面体的另一种方位图算法^[7]。由于模拟全局漫反射光线的形状因子计算需要获得物体对间的可见性信息，Teller引入了一种保守的支持两个物体之间可见性查询的算法，支持获得物体对之间被阻挡的对象列表^[8]。Pocchiola利用可见复合体存储二维全局可见性^[9]。

虽然在全局可见性这个问题上有许多优化性的方法，但是其在复杂模型交互显示的应用中，受到了算法复杂度的限制。在最坏情况下，复杂度高达。尽管在实践中很少出现最坏的情况，但受限于硬件性能，即使是复杂度低的多的，交互式图形也很难处理。此外，预计算的过程中存在较高的误差，也无法支持场景中的动态物体，一般来说，对于静态小场景来说，预计算全局可见性然后运行时查询可见性数据库是一种可行的方案。

目前，消隐算法的研究处于第三个阶段。之前的研究更多的侧重于生成具有正确可见性关系的图像上，但对于具有海量多边形的大型场景来说，是非常低效的，因为它们必须显式的遍历和处理场景中的每个多边形以生成可见性解决方案。目前的研究则关注于可见性剔除算法，寻求快速检测和去除未被观察者看到的大部分场景，从而加速渲染。由于大场景的复杂性，对消隐算法的优化研究细分为多个方向。

在空间管理方面，Stich提出了层次包围体结构，以加速复杂模型的渲染^[10]。每个物体都赋予一个包围体，它的形状简单，空间上包含物体，轴对其包围盒是最常用的包围体之一。使用形状规则的包围体替代对象本身大大加速了可见性的确定，如果对象的包围体不可见，则对象本身也不可见。然而，如果包围体积部分可见，不能保证对象部分可见，因为包围体通常比对象占据的空间更大。在层次结构中，叶子节点是对象的包围体，根节点包围整个场景。使用层次包围结构的优点在利用了模型的空间相干性，即靠近的对象往往同时可见或者不可见，从而在可见性测试中以分层的方式加速测试。如果非叶包围体被确定为完全不可见的，那么它所有的后代包围体都必须如此，因此该节点可以直接被剔除，不需要进行额外的测试。在另一方面，如果非叶包围体仅部分可见，那么其子包围体可能由于其较小的空间范围而又完全隐藏的机会，对此，需要执行进一步可见性测试^[11]。Madera为了更好地对物体近似，使用了球形包围体^[12]。但是，球形包围体不同于普通的方形包围体，虽然增加了对物体的近似程度，但不利于计算。因此，一种改进做法是利用贴合包围盒(OBB),该种包围体在局部坐标系下建立，因此和对象本身的变换属性无关^[13]。

在深度测试方面，Greene等人首次提出了一个基于深度的层次结构，在每个层次上具有保守的值^[14]。这项理论的提出，切实的带来了巨大影响，但时刻计算整个深度结构是不实际的。张寒松学者在1997年SIGGRAPH会议上介绍了分层遮挡图，根据他们创建层次的方法来进行近似的消隐测试^[15]。Morein提出了一个更可行的方案，仅有一个层次，最大深度值以块的形式储存和计算^[16]。当三角形保守估计的最小值大于深度块中的最大值时，三角形和深度块重叠的部分就可以被剔除，这使得实现上更为方便，在一定程度上也改进了效率。Akenine-Moller和Strom对这个方案进一步改进^[17]。在不考虑深度和模版测试的情况下，如果三角形保守估计的最小深度小于块中的最大深度时，三角形可以平凡的覆盖这个块，并且读取操作可以省去。为了可以对场景中动态对象进行处理，Aila和Miettinen定义了一个剔除系统^[18]。这个系统称为动态可视集（dPVS），成为动态物体消隐的理论基础。硬件遮挡查询的领域逐渐成熟，利用预测性渲染仅在遮挡查询成功的情况下执行渲染指令和近似匹配查询，可以在第一个图元可见的时候就终止查询操作，能更好的将之前可见的交错对象同时剔除。Valient提出在一个全分辨率的深度缓冲中进行渲染，然后保守的将它缩小从而加速消隐测试^[19]。Pelss计算来自保守遮挡盒内部凸体积，然后剔除完全包围在体积中的物体^[20]。Boulos提出了一种改进的深度金字塔的结构^[21]。2014年，Stein和Limper利用一种空间数据结构加速了可见性的计算^[22]。Morphet改进了基于区域的消隐算法，提高了渲染流水线的效率^[23]。也有一些学者提出相关的近似算法，例如Akenine-Moller基于GPU生成的深度来加速深度缓冲区的构建^[24]。这些近似算法依赖于对前一帧的深度缓冲进行降采样和重投影，用空洞填充策略来填充缺失的数据。可能会错误的剔除可见的对象，并且建立在帧与帧之间变化较小的前提下，处理含有快速移动的动态对象场景特别麻烦，所以目前对近似的算法的研究比较缓慢。

在软件光栅化方面，早在90年代末就开始蓬勃发展，但由于后来GPU的出现，近年来只有少数的论文涉及到CPU光栅化。这些论文中的大部分在讨论一般的显示算法或者面向GPU特定解决方案，并不能以原来的形式应用于CPU。在这个问题上，近几年一些学者提出了三角形遍历算法的优化，并引入了新的栅格化模型。Olano等人提出了一种全新的方法，他们是利用二维齐次坐标系简化三角形扫描转化的计算量，从而进行快速实时渲染^[25]。该做法避免了昂贵的裁剪测试并且可以比以前的实现更快的渲染同质三角形。杜慧敏等学者提出了一种中点三角形光栅化遍历算法，减少了遍历点的数量，提高了图形加速的效率^[26]。Royer等人研究并比较了三种不同的三角形遍历算法的性能，并在Matlab中对其进行仿真^[27]。实验结果表明，在实现关键图像处理算法时，可以对重要区域性能进行权衡。Tsao给出了一种基于边缘的平铺扫描三角形算法^[28]。在这种方案中，参数插值和光栅化的基本计算可以用通用共享硬件来执行，以降低渲染的成本。通过流水线和调度的硬件共享设计技术，该算法能够在合理的硬件成本下满足图形应用的实时要求。Bethel基于区域的半空间理论提出了一种多线程软件光栅算法，充分利用了CPU的性能，使得计算效率得以提高^[29]。

总体来看，虽然目前对消隐算法的研究有多方面的突破，取得了一定程度上的进展，但面对实际中的复杂的大型场景，尤其是静态物体和动态物体混合，观察者视角变换频繁的情况下，单一方向的优化改进并不能满足实际应用的需要，而是需要多维度的综合考量。

消隐方案设计

消隐方案的设计对消隐效率来说影响巨大，在本章中将对消隐算法中几个关键部分进行设计和比较，着重于消隐过程中核心问题的理论和分析。

消隐算法的分类和选择

目前的主流消隐算法主要分为三大类，GPU辅助、完全GPU和完全CPU。不同类别的消隐算法其适用的范围和应用的场景差别巨大，因此选择合适类别的消隐算法是至关重要的。

GPU辅助

生成遮挡体的深度缓冲的代价是很高的，而且占用较多的系统资源，GPU辅助类算法就是利用GPU来进行这些操作。深度缓冲重投影技术就是最有代表性的应用，其主要原理是将前一帧的深度数据重新投影以匹配当前帧，利用对包围盒的软光栅来快速得知一组网格是否被遮挡。

这类算法的优点是用过去的计算来避免产生全新的深度缓冲区，集成到现有的游戏引擎中也比较简单，也没有要求将网格分类成遮挡体和非遮挡体。但同时也存在着缺点，每次执行重新投影时，都会收到伪影的影响。同时，快速移动的物体和突然的相机变化也会极大的降低消隐过程的效率。

更近一步的，GPU不仅可以用于深度缓冲区的生成，也可以用于遮挡查询本身。例如虚幻4引擎仅依赖于CPU通过分层深度缓冲区结合GPU遮挡查询来实时的动态消隐,即将一组网格的包围盒发送到GPU检查可见性。虽然GPU硬件遮挡查询的结果较优，但是有着结果延迟的问题。在不影响GPU流水线的情况下，引擎读取到的查询数据至少落后于实际渲染一帧，当摄像机快速移动时，剔除结果存在一定的误差。

完全 GPU

另一类解决开放场景中大量增长的几何数据的算法是将所有可见性计算和是否渲染的抉择委托给GPU处理。CPU和GPU之间的同步代价是高昂的，会极大降低CPU流水线的性能，因此在理想状态下GPU应该独立的处理所有的剔除和渲染。这类算法通过修改内部引擎渲染流水线使得GPU尽可能不依赖于CPU。其中有代表性的是网络集群渲染技术，将几何细分成集群，这样GPU可以独立的在单独的批次中对这些集群进行剔除和光栅化处理。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：