首页 > 计算机论文 > 基于GPU的大规模复杂场景渲染的优化算法研究与实现计算机论文

基于GPU的大规模复杂场景渲染的优化算法研究与实现

发布时间:2017-04-21      文章来源:论文无忧网

基于GPU的大规模复杂场景渲染的优化算法研究与实现
摘要
目前,在电影、虚拟现实、电子游戏等领域方面,需要大规模的对场景进行渲染,增加游戏体验感和电影特效。所以在对于图形硬件处理方面的技术发展十分迅速。图形处理技术的快速的发展,能够能观众带来更好的观影体验和更加炫酷的游戏画面。但是,随着用户的需求不断增加,现阶段对图形的处理技术已经不能够很好的满足用户的需求。这时,硬件方面的处理已经到了瓶颈,就需要利用软件来改善对于图形方面的处理,用新的方法来满足用户的需求。
国内已经有很多人在从事利用软件来渲染大型复杂场景的研究工作,关于渲染图形的算法也在不断被推出。目前得到市场认可的算法主要有实例化技术、LOD算法、遮挡剔除算法等。本人参照了目前市场上已经得到的一些算法的优点,将这些算法进行优化,并将其中的优点进行结合,设计出了一套新型且高效的算法来进行对大型复杂场景的渲染。
本文提出的算法并没有采用传统的硬件遮挡查询算法,而是通过对软件利用遮挡剔除算法,来达到对大型复杂场景进行渲染的目的。对于这种算法,在这里称作层次遮挡算法。对于这种算法,对于遮挡图的构建是算法的关键所在。在设计算法中,需要在数据中找到不适合作为遮挡的物体,并将这些物体进行清除。在数据库完成后,便需要设计算法的运行过程了。算法在运行时,需要从数据库中取出一些遮挡物数据,将这些数据进行整合,并划分层次。最后便需要利用自己设计出的层次遮挡图来进行遮挡剔除计算。
遮挡剔除算法和视点依赖算法的结合,需要通过一个可见物体数组。利用算法来对大型复杂场景进行处理时,需要计算出该物体在不同的视角中所有的可见性。在算法运行过程中,需要利用算法在数据库取出所需要的单个数据,并就该数据与之前计算出数据的物理间距对于物体进行计算,计算出符合物理的合适LOD。在计算完成后,需要将计算出合适LOD写入进渲染场景的三角形序列中进行渲染处理。
本文在对大型场景渲染方面拿森林场景作为例子,在如何对大型森林哥进行渲染方面提供理论基础。本文能够证明,在对大型森林场景进行渲染时,使用本算法能够比市面上通用的遮挡剔除算法和LOD算法效率更高,效果更好。对于越复杂的场景,越能体现该算法对比于遮挡剔除算法和LOD算法等的优势。
 
 
 
 
关键词:大型复杂场景;遮挡剔除算法;LOD算法
 
 
 
目录 
 
第一章绪论.............................................................................................................................. 1
1.1  选题背景及选题意义 ............................................................................................... 1
1.2  国内外研究现状 ........................................................................................................ 2
1.3  主要研究内容 ............................................................................................................. 3
1.4  论文章节安排 ............................................................................................................. 4
第二章 大规模复杂场景优化渲染相关技术................................................................. 6
2.1  空间数据结构 .............................................................................................................. 6
2.2  剔除算法 ....................................................................................................................... 8
2.2.1  背面剔除(Backface Culling) ........................................................................... 9
2.2.2 视景体剔除(View Frustum Culling) .............................................................. 10
2.2.3  遮挡剔除(Occlusion Culling).......................................................................... 11
2.3 LOD算法........................................................................................................................... 13
2.3.1  离散型LOD算法(Discrete LOD) ................................................................. 13
2.3.2  连续型LOD算法(Continuous LOD) .......................................................... 14
2.3.3  视点依赖LOD算法(View-dependent LOD) ........................................... 14
2.4 GPU技术的发展 ............................................................................................................ 15
2.5  本章小结 ....................................................................................................................... 16
第三章基于GPU的混合场景渲染管线............................................................................ 17
3.1  硬件遮挡查询的缺点 ................................................................................................. 17
3.2  混合场景渲染管线 ...................................................................................................... 17
3.2.1  剔除处理流程 ............................................................................................................ 18
3.2.2 LOD处理流程................................................................................................................. 19
3.3  本章小结........................................................................................................................... 20
第四章软件实现的层次化遮挡剔除.................................................................................... 21
4.1  构建层次遮挡图 ............................................................................................................ 21
4.1.1  视景体剔除 ................................................................................................................. 22
4.1.2  遮挡物选择 ................................................................................................................. 22
4.1.3  构建层次遮挡图 ........................................................................................................ 24
4.2  用层次遮挡图进行遮挡剔除 ..................................................................................... 26
4.2.1  层次遮挡图重叠测试 ............................................................................................... 26
4.2.2  深度比较 ...................................................................................................................... 28
4.3  本章小结 ......................................................................................................................... 29
第五章并行化的视点依赖LOD算法.................................................................................. 30
5.1 预处理阶段 ....................................................................................................................... 30
5.1.1  生成空间单元 ............................................................................................................. 31
5.1.2  可见度计算 .................................................................................................................. 31
5.1.3  叶子随机排序 .............................................................................................................. 33
5.2  运行时阶段 ...................................................................................................................... 33
5.2.1 LOD选择............................................................................................................................ 33
5.2.2  生成三角形序列 ......................................................................................................... 34
5.3  本章小结 .......................................................................................................................... 35
第六章实验结果与分析........................................................................................................... 36
6.1  实验环境 .......................................................................................................................... 36
6.2  实验结果分析 ................................................................................................................. 36
6.3  本章小结 .......................................................................................................................... 40
第七章总结与展望..................................................................................................................... 41
7.1  总结 .................................................................................................................................... 41
7.2  工作展望 ........................................................................................................................... 42
参考文献........................................................................................................................................ 43
攻读硕士学位期间取得的研究成果...................................................................................... 45
致谢................................................................................................................................................. 46
 
 
 
 


第一章 绪论

1.1选题的背景及意义     

目前好莱坞的电影特效在全球可谓是首屈一指,就拿《少年Pi的奇幻漂流》作为例子。在这部电影中有这么一个场景。主人公Pi和他的伙伴帕克在站在帆船之上,这时有成千上万只飞鱼从海水中飞跃而出。这部电影,让观众们印象最深的就是这个场景。现在,类似这样的场景在虚拟现实、电影和电子游戏等领域中出现的非常多。在体育竞技类游戏中,通过对画面的渲染可以营造出有满场的观众在为球赛而欢呼呐喊。在角色扮演游戏中,可以渲染出玩家们相互厮杀、热血奋战的场景。在模拟现实游戏中,可以对都市繁荣的生活进行渲染,还能够对广阔无边的森林进行渲染。在通过计算机技术对于虚拟场景进行渲染有一个共同点,需要渲染的对象需要具有共同性。对于同类物体,进行单一渲染,然后作用在相同物体上,就能迅速完成对多个物体的渲染。本文这里研究出来的算法,也是针对于由多个同类物体构成的大型复杂场景。
现在,大型复杂场景的渲染已经在电影、虚拟现实、电子游戏等方面得到了运用。在国内外,也有着大量的研究人员在从事着相关工作的研究。这些研究的核心在于对大型复杂场景渲染时需要有真实感和实时性。
真实感主要是指渲染出来的场景让人看到要尽可能的认为真实。例如在对大型森林进行渲染时,要给玩家一种真正生活在森林中的感觉。然而要尽可能地做到让观众感觉是真实的,在技术上无疑是复杂的。为了满足用户的需求,计算机需要通过细致的纹理和精细的网络来表现出所需要渲染场景中物理的具体特征。除了描述出物体简单的物理特征外,计算机还需要通过对光线、动画等方面的模拟来描述物体的动态特征,这样才能让观众的感受尽可能的真实。由于仅仅渲染一个物体就需要描述物体大量的特征,在进行多个物体同时渲染时,对于计算机的计算量无疑是个很大的要求。无论是硬件方面还是软件方面,都需要得到新的突破。
实时性主要是指用户能够实时与所处的场景进行交流。用户在场景中的位置随时可能发生变化,在进行场景渲染时,需要做到随着用户的变化,场景的渲染也需要实时进行变化,带给用户良好的用户体验。为了满足这一要求,计算机需要能够随时检测用户的数据,并针对用户的数据对场景进行反馈。在对于实时性的测量上,一般用帧率(FPS)作为范围。对于场景来说,帧数越高,代表着该场景所具有的实时性就越强。
在某种程度上来说,实时性和真实感是具有矛盾的。假设计算机的计算能力为某一常量,计算机通过计算,营造出了高度满足用户真实感的场景。相应的,该场景的计算复杂度相对较高,对计算机的计算能力消耗较大,计算机留在对场景实时性设计的计算能力就越少,这样计算机设计出的场景的实时性就越差。那么如何既保证场景的真实性足够高,又能够减少计算机计算场景每帧所需要的时间呢,这是一个重要的难题,也就本文这里的研究主题:基于GPU的大规模复杂场景的渲染优化算法。
在计算机图形学上存在着一个重要的研究方向,那就是对于大型复杂场景优化渲染的研究。现在,在图形硬件技术上面的发展十分迅速,从而使得CPU在并行计算速度方面已经远远地低于GPU。计算机已经有越来越多的图形计算已经不在CPU中处理了,而是通过GPU进行处理。随着计算机GPU的计算能力的逐步加强,计算机在对于简单场景的渲染计算上,全部通过GPU。这样既能够减少CPU的运行负担,又能够加快对于场景的渲染速率。但是随着用户的需求不断增加,计算机需要进行对大型复杂场景进行渲染。仅仅通过GPU的计算能力进行渲染是远远不够的,那么如何解决对于大型复杂场景的渲染一直是计算机图形学研究上的一个难点,也是一个研究热点。本文就是通过利用目前所具有的软硬件技术基础,设计出了一个更加高效的对大型复杂场景渲染的算法。
 
1.2 国内外研究现状
   对于大型复杂场景渲染的研究已经成为了国内外一个热门。目前,剔除算法是市场上一种比较常见的加速场景渲染速度的一项技术,但是剔除算法在某种程度上具有一定的局限性。剔除算法的工作原理是通过剔除掉对最终显示画面没有作用的物体来达到减少渲染场景计算量的问题。对于一个场景来说,除了最终显示的场景之外,场景之中还存在着很多被遮挡的物体以及位于用户视线之外的物体。在进行场景渲染时,需要将那些物体在渲染对象中剔除掉。刚才所说的被遮挡的物体叫做遮挡剔除算法,剔除位于用户视线之外的物体叫做视景体剔除算法。这两种算法目前是国内外研究的热门,已经有大量的专业人士在相关权威杂志上发表了关于这两种算法研究的论文。
    目前,由U.Assarsson等人在杂志上发表了一篇论文,上面提到了一种关于视景体剔除的优化算法。这个算法相比于之前的视景体算法来说,在速率上有了很大的提升。主要在于设计该算法时,考虑到了帧与帧之间是具有连续性的,利用这种特性能够加快剔除视景体的速率。在同一个包围体当中,如果前一帧是处在当前平面之中,那么它的下一帧就极有可能还在处在这个平面当中。那么在进行处理一帧一帧的画面时,利用帧与帧之间存在这样的特性,就能够很好的解决算法的时间复杂度,从而提高了算法的执行效率。帧与帧之间的空间相关性在某种程度上来说,并不是绝对的。1993年,在SIGGRAPH会议上,著名学者N.Greene
等人提出一个名叫Hierarchical  Z-buffer的经典算法。算法在设计上高效地利用了时间相关性和空间相关性,从而使得整个算法在执行效率上非常高。算法通过建立八叉树等形式,在对算法的设计上,利用时间相关性建立一个空间维度,来很好地表现该算法的优势。但是,当时在提出这个算法时存在了一个很大的缺陷。就是使用该算法需要很高的硬件配置,不然在算法运行过程中可能存在各种各样的问题。在2004年,J.BIttne等人在这个算法上加以了改进,提出了一个CHC算法(Coherent Hierarchical Culling)。这个算法继承了Hierarchical  Z-buffer算法在于时间相关性和空间相关性方面的优点,并且在硬件需求上得到了改进。该算法能够很好地利用CPU和GPU的空闲时间进行工作,使得整体算法在较低硬件配置的计算机上仍能正常工作。这个算法的提出,得到了广大计算机研究者的高度认可。2006年,M.Guthe等人在CHC算法上再次做了改进,提出了一个叫NOHC(Near Optimal Hierarchical Culling)的算法。该算法既满足CHC算法在时间、空间相关性的优点,对硬件的需求上也并没有那么高,并且在物体的可见性上做出了突破。该算法抛弃了CHC算法中查询消耗计算机计算能力较大的物体的缺点,而是通过查询对场景显示有关的画面来加强算法执行效率。
    在遮挡剔除算法中主要用到包围体层次。包围体的实质就是将同个空间中的物体包含在一个维度的空间当中,这样能够最大限度的减少算法的空间复杂度,从而加强算法的执行效率,减少算法运行所需要的时间。在包围体层次中,是由叶子节点、内部节点、根节点共同构成的。叶子节点主要起到能够包围单一个体的作用。内部节点主要起到能够包围与目标物体物理位置相近位置节点的作用。而根节点主要是能够包围场景中所有存在的物体
目前在市场上还有一种算法和遮挡算法一样流行,那就是LOD(Level of Detail)算法。该算法主要是通过对于场景中不同物体的相对位置的计算,来表现出对于物体的渲染。在对物理渲染时,也需要对位置进行渲染,在某种程度和上来说,就是对整个场景进行渲染。近些年来,国内外在于LOD算法上面的研究主要体现在,将LOD算法在GPU上进行运行。
在2002年,由CO'Sullivan等人提出了一个名叫ALOHA(Adaptive Level of Detail for Human Animation)的架构。这个架构的提出,解决了场景渲染在运动细节和几何细节上面的难题。该算法主要是通过对于细节进行预设定来达到目的。在2006年,由 PH Ciechomski 等人提出了一种新型的骨骼剔除方法。通过剔除场景中的一些不必要的骨骼,来达到加快算法速率的目的。在2010年,由Rafael Rodriguez等人提出了一种剔除相关动画来减少场景行为计算量的方法。在2011年,由Peng C等人提出了并且实现了一种基于GPU上面的整体渲染的系统。该算法简化了LOD算法在网络运算以及网格表现上面的运算时间。在2012年,有F.J. Perales等人在研究前人算法后,进行整合,提出一个新的基于GPU上面的算法。该算法在渲染速度、渲染效率、渲染质量等方面上都有了很大的突破。
使用LOD算法与剔除算法相配合能够很好地解决在与渲染场景速率方面的问题。但是在两者结合上,还存在了一定地技术难题。如何做到让两种算法高效的结合,现如今也是计算机图形学上的一个重要的研究领域。
在2009年,由C.LAUTERBACH等人在杂志上发表了一篇论文,该论文提出一个新型的算法。该算法划分了一定的空间层次,减少了计算机在执行算法时所需要的计算量和系统中所占用的内存。在2010年,由J.Pantaleoni等人提出了一个构想。他们构想可以对SAH(Surface Area Heuristic)算法进行优化,减少物体微粒在空间复杂度上的相关性,提高整个算法的执行效率,减少计算机的计算量,提高计算机的工作效率。在2011年,由K.Garanzha等人在J.Pantaleoni的新算法再做出了改变,从而有了HLBVH变体算法。
 
 
1.3 主要研究内容
本文主要研究基于GPU的大规模复杂场景的优化算法。在研究前,本文分析了国内外的研究形式,点出了目前已经有哪些学者提出了对场景渲染有着突破性的算法和构想。本文所提出的算法结合了LOD算法和遮挡剔除算法的优点,在一定地程度上加快对于大型复杂场景的渲染速率。在于硬件方面,该算法利用了CPU和GPU在空闲时刻的运算能力,使得整个计算机在使用该算法时并不需要一定的硬件配置需求。对于LOD算法所拥有的处理物体相对位置的优点,以及遮挡剔除算法中能够剔除遮挡物体以及视野外物体的特性,该算法都会包含。所有在算法执行效率,以及时间复杂度上具有相当的优势。目前,虽然国内外已经有很多学者在尝试着将这两种算法进行组队,但是根据相关权威杂志判断,目前,在于两种算法的结合上并不能够让人满意。大多数的结合算法并没有结合两种算法的优点,并且有些算法甚至不能够解决LOD算法和遮挡剔除算法所存在的缺陷。本文设计的算法,基于目前需要设计基于在GPU上运行的算法,本算法在设计后进行了大量的实验,确定了该算法确实结合了LOD算法和遮挡剔除算法的优点。
该算法区别了传统的场景优化算法,将目前计算能力强大的GPU计算能力以及LOD算法和遮挡剔除算法高效的运行能力相结合。并且,该算法摒弃了利用高硬件来运行算法的缺陷,使得整个算法对于硬件方面的要求并不是太高。
在算法执行时主要分为两个部分:预处理阶段和运行时阶段。第一部分,预处理阶段所需要的任务是将本来的数据库生成为一个全部储存遮挡物的数据库。并且会将本来的场景数据库中的数据与新生成的遮挡物数据库中的数据想结合。算法利用 了帧与帧之间的连续性。考虑到了帧与帧之间是具有连续性的,利用这种特性能够加快剔除视景体的速率。在同一个包围体当中,如果前一帧是处在当前平面之中,那么它的下一帧就极有可能还在处在这个平面当中。那么在进行处理一帧一帧的画面时,利用帧与帧之间存在这样的特性,就能够很好的解决算法的时间复杂度,从而提高了算法的执行效率。帧与帧之间的空间相关性在某种程度上来说,并不是绝对的。再就是运行时阶段,算法在运行时会记录每一帧时所产生的所有数据,并将这些数据进行整理。将不是场景渲染所需要的数据进行剔除,提高算法的执行效率。在利用LOD算法具有的特性,来设计物体相对位置的动态,将物体定在一个网络的位置,并在网络上详细的记录物体的动态数据。
本文在讲解该算法的时候,便于理解,运用了几百个面片构成的大型森林场景作为例子来进行说明。利用该算法,不仅仅只是实现了对于大型森林场景的实时渲染,并且在算法效率上,只对比于LOD算法或者是遮挡剔除算法,在速度上都有了很大的提高。
 
 
1.4 论文章节安排
第二章主要会就大型复杂场景渲染所需要的相关技术进行介绍。
第三章主要会就大型复杂场景的渲染管线进行介绍。
第四章主要会就如何利用软件来实现对于层次化遮挡提出算法进行介绍。
第五章主要会就在算法上实现可视化并行计算,利用LOD算法的特点来实现该算法。
第六章主要会就本算法进行实验的结果进行分析,并且得出相应结论。
第七章主要就是对全文的总结,以及对于未来的展望。
 
 
 
 
 
 
 
 
 
 
 
第二章 大规模复杂场景优化渲染相关技术
本章主要阐述了一些喜闻乐见的大型场景的渲染算法,这些算法包括了LOD算法等一系列常见的场景渲染算法,其中的剔除算法有很多种,有背面的剔除算法,还有其它方面的剔除算法,LOD算法也有一些分类,主要是按照粒度的尺寸进行分类的,具体不加以介绍。还要一个算法就是空间结构的算法分类,这种算法的分类分为BSP树、八叉树等等一系列结构。
2.1 空间数据结构
对于一个算法设计来说,空间数据结构的设计无疑是十分重要的。并且在对于大型复杂场景的渲染上,优化算法主要也是在空间数据结构的基础上进行的。物体在空间中的位置按照一定的顺序和规律进行储存,并将这些数据存放在数据库中,就构成了空间数据结构。在对物体空间数据的存储上需要按照一定的层次来进行。在算法方面,空间数据结构还需要考虑到对于空间物体是否被遮挡、是否被重叠,物体和物体之间是否产生了碰撞等。
在通常情况下,在空间数据结构的设计上主要采用了层次化结构来进行设计。在层次结构上会有高低层等方面的问题,还会存在嵌套层次等方面的问题。这能够提高算法在空间复杂度上的执行效率。
目前,主要的空间数据结构有八叉树(Octrees)、BSP树(Binary Space Partitioning Trees)、四叉树(Quad Trees)、包围体层次(Bounding Volume Hierarchies)等空间层次。在进行场景空间层次的划分上面,要使得场景和场景之间的空间层次不相重叠。使得场景能够按照不同的层次进行划分,分出不同的区域来进行小型的场景渲染。对于计算机来说,进行大型空间场景渲染所需要的时间远远高于若干个小型空间场景组合成的场景。
下面将就本文所采用到的包围体层次的空间数据结构在进行详细的介绍。
包围体层次是目前得到广泛运用的一种空间数据结构。然而,包围体的实质就是将同个空间中的物体包含在一个维度的空间当中,这样能够最大限度的减少算法的空间复杂度,从而加强算法的执行效率,减少算法运行所需要的时间。在包围体层次中,是由叶子节点、内部节点、根节点共同构成的。叶子节点主要起到能够包围单一个体的作用。内部节点主要起到能够包围与目标物体物理位置相近位置节点的作用。而根节点主要是能够包围场景中所有存在的物体。
 
图 2-1 层层嵌套的包围体结构
 
利用包围体空间层次能够很大限度上起到加快对大型复杂场景的渲染速度。这里拿一个例子进行相应的说明。判断场景中的某一个物体是否已经和场景中的另外一个物体相互碰撞。对于这个问题,利用一般的算法是这样判断的。需要将该场景中的每一个物体都与该物体进行碰撞检测的测试。那么,这样的算法存在什么样的问题呢?如果在检测事务场景中只存在了几个或者几十个物体。那么该算法的运行速率还算是可以的。但是对于那种场景中具有几万或者几十万物体的场景呢,那么对于物体碰撞的计算所需要的时间就是十分漫长了。针对于这类问题,利用层次化包围体算法来进行计算就是十分有必要的了。首先将需要检测的物体于该包围体中所具有的根节点做碰撞测试。如果返回值为0,那么可以判断出,该物体并没有与该场景中的任何个体发生碰撞。如果返回值为1,则做该物体与该根节点下的内部的子树节点做碰撞测试。按照这个逻辑,将测试范围逐步缩小,最后便可以得出了该物体到底与该场景中的物体是否发生碰撞,与该场景中的哪个物体发生了碰撞。这样就简化了算法,加快了算法的执行效率,减少的需要等待的时间。
在包围体层次空间数据结构算法的运用上并不仅仅只适合与静态场景的检测,在动静场景的检测上,该算法也具有相当大的优势。对于一个在场景中移动的物体来说,需要不断的对目标体进行判断,判断目标体是否还处在该场景中。如果该物体一直在该场景当中,那么可以遵照对于静态场景的判断来进行。首先需要将检测的物体于该包围体中所具有的根节点做碰撞测试。如果返回值为0,那么可以判断出,该物体并没有与该场景中的任何个体发生碰撞。如果返回值为1,则做该物体与该根节点下的内部的子树节点做碰撞测试。按照这个逻辑,将测试范围逐步缩小,最后便可以得出了该物体到底与该场景中的物体是否发生碰撞,与该场景中的哪个物体发生了碰撞。这样就简化了算法,加快了算法的执行效率,减少的需要等待的时间。如果该物体已经没有处在该场景当中,那么需要对物体所处的场景再进行重复判断,再进行上面的静态判断。但是,这样的方式使用次数过多,会造成整个层次逐步失衡,整个算法的效率逐步降低。
2.2 剔除算法
剔除算法的工作原理是通过剔除掉对最终显示画面没有作用的物体来达到减少渲染场景计算量的问题。对于一个场景来说,除了最终显示的场景之外,场景之中还存在着很多被遮挡的物体以及位于用户视线之外的物体。在进行场景渲染时,需要将那些物体在渲染对象中剔除掉。刚才所说的被遮挡的物体叫做遮挡剔除算法,剔除位于用户视线之外的物体叫做视景体剔除算法。剔除算法目前已经被广泛的在人工智能、物理计算、碰撞检测等方面得到课应用。剔除算法是一个总分,具有的可以分为遮挡剔除算法、视景体剔除算法、背面剔除算法。如下图2-2所示,就是一个背面剔除所展示的背视点多边形情况。在设计背面剔除时,要考虑到多个方面的问题,合理的设计算法,才能做到整个算法具有高度的执行效率。目前剔除算法已经有大多数被一些硬件来实现了,但是在某些部分来说,这并不是有如何的高效。在利用软件来设计该算法,能够更好的实现算法的优势。
图2-2  常见的三种可见性剔除
 
在某种程度上来说,理想化的剔除算法将会只是发送一些可见集合(Exact Visible Set,EVS)到相对应渲染管线上。加快对于大型复杂场景的渲染速率。在于硬件方面,该算法利用了CPU和GPU在空闲时刻的运算能力,使得整个计算机在使用该算法时并不需要一定的硬件配置需求。对于LOD算法所拥有的处理物体相对位置的优点,以及遮挡剔除算法中能够剔除遮挡物体以及视野外物体的特性,该算法都会包含。所有在算法执行效率,以及时间复杂度上具有相当的优势。用户在场景中的位置随时可能发生变化,在进行场景渲染时,需要做到随着用户的变化,场景的渲染也需要实时进行变化,带给用户良好的用户体验。为了满足这一要求,计算机需要能够随时检测用户的数据,并针对用户的数据对场景进行反馈。这样在对于剔除算法上也提出了新的要求。要保证场景所具有的潜在集合存在,保证对可见物体进行渲染得到的画面具有一定的精确性。
对于剔除方面,市面上得到认可的主要是:遮挡剔除算法、视景体剔除算法、背面剔除算法。
 
 
2.2.1 背面剔除
在对于背面剔除方面,其实质在于剔除物体的背面。对于一个场景来说,每个物体都具有两个部分:一是能够被用户看到的可视化的部分,二是无法被用户可视的背面部分。在一个场景中,物体的背面部分是相当之多的。那么为了提高算法的执行效率,减少计算机的计算能力,剔除物体的背面是十分有必要的。对于一个物体来说,显示在用户面前的就是可视化的部分,而对于物体的渲染也是对于物体可视化方面的渲染。然后物体的背面,存在场景之间,这就消耗了计算机的计算能力。从而在计算物体的实时位置上,以及带给用户的真实性上都会存在一些问题。这样就会对用户的体验感造成一定程度上的影响,对于物体的背面部分,根本不需要发送到渲染管线中进行渲染。对于场景中其他的一些不透明的物体来说,对于其背面的部分,也是需要被剔除,根本不需要再做出任何处理,在这些处理上,只会浪费计算机的计算能力和计算资源、而不会给用户带来更好的体验感。另外,对于场景中的建筑物来说,使用背面剔除也是十分有必要的。对于一个建筑物来说,显示在用户面前的就是可视化的部分,而对于物体的渲染也是对于物体可视化方面的渲染。然后物体的背面,存在场景之间,这就消耗了计算机的计算能力。从而在计算物体的实时位置上,以及带给用户的真实性上都会存在一些问题。这样就会对用户的体验感造成一定程度上的影响。
     在对于交互图形的处理上也应该做到对重叠部分进行剔除。对于一个物体来说,它的背面并不是一成不变的,而是随着用户的走动,它所显示的背面在不断地发生改变。那么在不同的场景中,在进行背面剔除时都需要做出相应的判断,判断到底物体的背面处在哪个地方,这样才能更好地进行剔除处理。
在进行剔除处理时,还有一个判断,便是对于一个物体它到场景中另外物体,以及场景法线所构成的向量的乘积。若乘积为正,则说明该视点为物体的可视化视点,需要被渲染。若乘积为负,则说明该视点为物体的不可视化部分,需要被剔除,不做渲染。如果做出渲染处理,只会浪费计算机的计算能力和计算资源、而不会给用户带来更好的体验感。另外,对于场景中的建筑物来说,使用背面剔除也是十分有必要的。对于一个建筑物来说,显示在用户面前的就是可视化的部分,而对于物体的渲染也是对于物体可视化方面的渲染。然后物体的背面,存在场景之间,这就消耗了计算机的计算能力。从而在计算物体的实时位置上,以及带给用户的真实性上都会存在一些问题。这样就会对用户的体验感造成一定程度上的影响。
背面剔除算法已经被设计出有很多年了,也已经得到了市场的广泛认可。对于背面剔除算法的实现,Direct X和Open GL都有与之相关的实现算法的函数。在对场景实现渲染时,只需要调用那些函数,就能够对场景实现背面剔除渲染。
 
 
2.2.2视景体剔除
     对于一个场景来说,视景体剔除是十分有必要的。剔除算法在某种程度上具有一定的局限性。剔除算法的工作原理是通过剔除掉对最终显示画面没有作用的物体来达到减少渲染场景计算量的问题。对于一个场景来说,除了最终显示的场景之外,场景之中还存在着很多被遮挡的物体以及位于用户视线之外的物体。在进行场景渲染时,需要将那些物体在渲染对象中剔除掉。在视景体剔除方面,这里利用XNA框架来进行说明。该框架主要是通过投影矩阵来对不同顶点的投影来进行计算。
     对于投影的模型,大致是被切断的金字塔形状。对于这个图形,下面会作为详细的描述。如图2-3所示,是视景体剔除图。
 
     图2-3 视景体剔除图
对于视景图剔除算法擦在2002年,由CO'Sullivan等人提出了一个名叫ALOHA(Adaptive Level of Detail for Human Animation)的架构。这个架构的提出,解决了场景渲染在运动细节和几何细节上面的难题。该算法主要是通过对于细节进行预设定来达到目的。在2006年,由 PH  Ciechomski 等人提出了一种新型的骨骼剔除方法。通过剔除场景中的一些不必要的骨骼,来达到加快算法速率的目的。在2010年,由Rafael Rodriguez等人提出了一种剔除相关动画来减少场景行为计算量的方法。
      对于视景图剔除来说,只有处在观影体内的物体才会被渲染。如果对观影体外的物体进行渲染,只会浪费计算机的计算能力和计算资源、而不会给用户带来更好的体验感。另外,对于场景中的建筑物来说,使用背面剔除也是十分有必要的。对于一个建筑物来说,显示在用户面前的就是可视化的部分,而对于物体的渲染也是对于物体可视化方面的渲染。然后物体的背面,存在场景之间,这就消耗了计算机的计算能力。从而在计算物体的实时位置上,以及带给用户的真实性上都会存在一些问题。这样就会对用户的体验感造成一定程度上的影响。所以在视景图外的物体,不需要经过渲染总线。
       对于视景体和包围体相交或者是包围体在视景体之类时,需要将物体发送到渲染总线中进行渲染,因为这时候的物体是可见的。包围体的实质就是将同个空间中的物体包含在一个维度的空间当中,这样能够最大限度的减少算法的空间复杂度,从而加强算法的执行效率,减少算法运行所需要的时间。在包围体层次中,是由叶子节点、内部节点、根节点共同构成的。叶子节点主要起到能够包围单一个体的作用。内部节点主要起到能够包围与目标物体物理位置相近位置节点的作用。而根节点主要是能够包围场景中所有存在的物体。
目前,主要的空间数据结构有八叉树(Octrees)、BSP树(Binary Space Partitioning Trees)、四叉树(Quad Trees)、包围体层次(Bounding Volume Hierarchies)等空间层次。在进行场景空间层次的划分上面,要使得场景和场景之间的空间层次不相重叠。使得场景能够按照不同的层次进行划分,分出不同的区域来进行小型的场景渲染。对于计算机来说,进行大型空间场景渲染所需要的时间远远高于若干个小型空间场景组合成的场景。
算法利用了帧与帧之间的连续性。考虑到了帧与帧之间是具有连续性的,利用这种特性能够加快剔除视景体的速率。在同一个包围体当中,如果前一帧是处在当前平面之中,那么它的下一帧就极有可能还在处在这个平面当中。那么在进行处理一帧一帧的画面时,利用帧与帧之间存在这样的特性,就能够很好的解决算法的时间复杂度,从而提高了算法的执行效率。帧与帧之间的空间相关性在某种程度上来说,并不是绝对的。再就是运行时阶段,算法在运行时会记录每一帧时所产生的所有数据,并将这些数据进行整理。将不是场景渲染所需要的数据进行剔除,提高算法的执行效率。
 
 
2.2.3遮挡剔除
1993年,在SIGGRAPH会议上,著名学者N.Greene等人提出一个名叫Hierarchical  Z-buffer的经典算法。算法在设计上高效地利用了时间相关性和空间相关性,从而使得整个算法在执行效率上非常高。算法通过建立八叉树等形式,在对算法的设计上,利用时间相关性建立一个空间维度,来很好地表现该算法的优势。但是,当时在提出这个算法时存在了一个很大的缺陷。就是使用该算法需要很高的硬件配置,不然在算法运行过程中可能存在各种各样的问题。但是利用Z-buffer能够很好地解决遮挡剔除问题。如图2-4是10 个球体的渲染效果相当于 1 个球体的渲染效果详细展示图。
 
图2-4 10 个球体的渲染效果相当于 1 个球体的渲染效果
 
对于遮挡剔除算法来说,需要剔除掉场景渲染所不需要的那个部分。对于场景不要的部分,根本不需要再做出任何处理,在这些处理上,只会浪费计算机的计算能力和计算资源、而不会给用户带来更好的体验感。另外,对于场景中的建筑物来说,使用背面剔除也是十分有必要的。对于一个建筑物来说,显示在用户面前的就是可视化的部分,而对于物体的渲染也是对于物体可视化方面的渲染。然后物体的背面,存在场景之间,这就消耗了计算机的计算能力。从而在计算物体的实时位置上,以及带给用户的真实性上都会存在一些问题。这样就会对用户的体验感造成一定程度上的影响。
目前,针对遮挡剔除的情况大致可以分成两个方面:
1.在渲染物体的同时需要同时开启对于遮挡方面的查询。
2.对于被查询的物体,如果返回值为1,则这个物体应该被渲染。
针对遮挡剔除的渲染,首先需要将检测的物体于该包围体中所具有的根节点做碰撞测试。如果返回值为0,那么可以判断出,该物体并没有与该场景中的任何个体发生碰撞。如果返回值为1,则做该物体与该根节点下的内部的子树节点做碰撞测试。按照这个逻辑,将测试范围逐步缩小,最后便可以得出了该物体到底与该场景中的物体是否发生碰撞,与该场景中的哪个物体发生了碰撞。这样就简化了算法,加快了算法的执行效率,减少的需要等待的时间。如果该物体已经没有处在该场景当中,那么需要对物体所处的场景再进行重复判断,再进行上面的静态判断。
对于遮挡渲染来说,并不能够剔除掉所有的不可见的物体,因此在某种程度上来说,也是存在着缺陷的。
 
 
2.3LOD算法
本节阐述的内容包括LOD算法的一些专业术语。LOD算法的产生可以从1976年的一篇文章说起,这篇文章是J Clark写的,当时发表在ACM通讯杂志中,在那个时代计算机的发展不是很迅速,计算机笨重且昂贵,计算机的图形处理的运行只能通过专业人员进行调控,当时的硬件并不是很先进,所以当时产生的LOD算法大不同于现如今的LOD算法,然而,算法的核心还是不变的,算法的分类可以分为离散型的LOD算法,还能分为视点依赖的LOD算法,这一算法会在第五章进行详细的介绍,下面进行的只是简单的说明,还有一种LOD算法是连续型的LOD算法。接下来就对这三种算法进行简单的介绍和讲解。
2.3.1离散型LOD算法
离散型的LOD算法是一种比较流行的算法,出现的时期是1976年,提出这个算法的是JClark,这个算法是很重要的一种算法,在一些特殊的领域还在受到广泛的使用,这个算法的主要思想就是通过预处理阶段对物体进行处理,产生各异的LOD,通过一个不统一的标准进行LOD的选择,并用该LOD表示物体。这个标准的制定主要是通过一些客观的因素决定的。虽然标准不同,但是还是有一定的规律可言,一般来说,视点近的物体能够使用最开始的LOD,距离视点远的物体则使用简化的LOD,这是因为距离越远,网格的复杂程度就越小,需要的图形就越少,虽然距离变远,但是物体的实际视觉效果没有受到很大的影响。然后通过这两个极端的标准来合理的选择不同距离时需要使用的LOD。离散型的LOD算法就是通过这种方式进行保证视觉效果的,在这个保证的同时,还能够保证渲染的程度和速度。
离散型的LOD算法有很大的优点,但是也有一定的局限性,优点方面,在物体的网格化处理阶段是在第一阶段完成的,在第二阶段只需要进行相应的LOD选择,用来表示物体,离散型的LOD算法优点有很多,不能够具体的进行阐述,在局限性方面,离散型LOD算法在特定的情况下会出现失真的问题,局限性也有很多方面,具体不一一进行举例。
2.3.2连续型LOD算法
这种算法在第一阶段产生的不是传统LOD算法产生的LOD模型,而是一些特定的数据结构,这种数据结构在运行阶段能为算法提供合适的LOD模型,这种连续型的LOD算法是一种更加紧密的算法,产生的LOD模型更加的精确,从视点产生的多边形比传统的离散型LOD算法要少了,分配的多边形更加的合乎情理,分配到不同的网格的多边形也很合适,这样的LOD算法在一定程度上保证了场景的真实程度,也将场景的空间复杂程度大大的降低,连续型的LOD算法的适用范围也很广泛。
在2002年,由CO'Sullivan等人提出了一个名叫ALOHA(Adaptive Level of Detail for Human Animation)的架构。这个架构的提出,解决了场景渲染在运动细节和几何细节上面的难题。该算法主要是通过对于细节进行预设定来达到目的。在2006年,由 PH Ciechomski 等人提出了一种新型的骨骼剔除方法。通过剔除场景中的一些不必要的骨骼,来达到加快算法速率的目的。在2010年,由Rafael Rodriguez等人提出了一种剔除相关动画来减少场景行为计算量的方法。在2011年,由Peng C等人提出了并且实现了一种基于GPU上面的整体渲染的系统。该算法简化了LOD算法在网络运算以及网格表现上面的运算时间。在2012年,有F.J. Perales等人在研究前人算法后,进行整合,提出一个新的基于GPU上面的算法。该算法在渲染速度、渲染效率、渲染质量等方面上都有了很大的突破。
2.3.3视点依赖LOD算法
该算法能够帮助程序在使用的过程中根据现在的视点进行选择合适的LOD模型,该算法产生的LOD模型是不均匀的,各个不同场景产生的多边形依据不同的距离得到不同的多边形数量,距离远则多边形少,反之多边形就多;还有就是场景的外部区域的多边形要比内部的区域多。这种算法和连续型的LOD算法比较起来更加的精细,很好的利用多边形和视点位置的关系将资源的分配合理的进行管理,更好的将场景进行展现,给人一种全新的真实感。
2.4GPU技术的发展
在现今社会,随着科技的不断进步,人们对图形处理器的要求也不断的提高,图像处理器的技术在不断的发展和进步,也使得GPU的计算速度逐渐的提高,现在的GPU不同于以前的GPU,不再只用于图形的处理,还用于非图形相关的计算,也就是说,不是图形相关的计算也能够在GPU上进行计算。
图形处理器的发展历程可以分为几个阶段,具体的阶段下面进行详细的介绍:
第一个阶段是1991年之前,这个阶段还不存在图形处理器这个概念,由于当时的人们对图形的需要并不是很大,所以不注重图像处理器的发展。很多的程序使用都是通过命令行的方式进行实现的。
第二个阶段就是1991年到2001年,微软公司设计开发的Windows操作系统得到了广泛的使用,在世界受到了极大的欢迎和推广,这个趋势极大的激励了图形处理器的发展,S3 graphics公司首先设计出了世界上第一个图形处理器,这个图形处理器虽然不够成熟,但是被称为GPU的始祖和基本设计模型。
第三个阶段就是2001年到2006年,这个阶段是图形处理器发展的里程碑阶段。当时的硬件设备正在突飞猛进的发展,硬件设备的先进促使显卡的性能达到了极大的提升,当时出现的可编程处理器也受到了极大的关注,当时出现的第一款能够支持可编程的GPU产品就是这个GeForce,硬件也被加入了很多的辅助功能,其中就有着色功能,这个功能使得图形处理器不再是一个单调的处理器,而是能够让用户自己进行编程的处理器,这使得3D游戏的开发和设计得到了很大的进步。
在这个阶段,出现了很多经典的图形处理器,也产出了很多先进的图形处理技术,其中比较重要的处理技术就是GPU技术,了图形处理器的高效处理能力,于是开始开发GPU的通用计算能力,将一些科学问题通过着色功能进行编程实现,然后放置图形处理器的着色其中进行运行,将运行得到的数据放置内存。在设计图形处理器的时候主要是为了计算图形的相关数据,所以对通用计算的方面不是很注重,在进行通用计算的使用时需要对相关的图形计算构架进行修改和转换,这就需要编程人员对着色器算法足够的熟悉。
第四个阶段是2006年至今,在这个阶段,图形处理器的注重点开始从图形的处理转移到通用计算的需求。在这一阶段,NVIDIA公司设计开发了一种GPU产品,这种产品标识着GPU进入通用计算的时代,这个GPU产品就是GeForce系列的图形处理器。这个产品的统一着色器没有其他的分类。它将顶点着色器和像素着色器的特点相结合。这种着色器可以进行2中着色器的功能,着色器的功能不会被很充分的得到运用,所以会把着色器的功能更多的运用到通用计算的方面,这样就使得通用计算的效率得到了很大的提升。所以说这种着色器的存在使得图形处理器不仅是图形处理的高效工具,还是通用计算的强大工具,为此,NVIDIA公司还特意的开发了CUDA语言,苹果公司还特意的开发了能够帮助图形处理器的通用语言。
图形处理技术的通用计算功能的实现使得GPU的并行计算得到了实现,现在的算法,是专门为了改造GPU进行并行计算的,这些算法之间的联系很紧密,没有很好的并行性,所以需要对一些算法进行合理的改进,有的算法联系并不是很紧密,所以不需要进行改进,可以直接的使用在GPU的通用计算功能上,而且还会大大的提升算法的速度和能力。
2.5本章小结
本章节的主要内容是阐述了一些喜闻乐见的大型场景的渲染算法,这些算法包括了LOD算法等一系列常见的场景渲染算法,其中的剔除算法有很多种,有背面的剔除算法,还有其它方面的剔除算法,LOD算法也有一些分类,主要是按照粒度的尺寸进行分类的,具体不加以介绍。还要一个算法就是空间结构的算法分类,这种算法的分类分为BSP树、八叉树等等一系列结构。在章节的最后还额外的对GPU的发展历程进行了相关的介绍,介绍了GPU的一些改进过程和具体的GPU产品等等。
 
 
 
 
 
 
 
 
 
 
 
 
第三章  基于GPU的混合场景渲染管线
3.1  硬件遮挡查询的缺点
遮挡剔除算法的发展一直到现在已经有了很多的研究和经验,经过了上个世纪到现在的不断探索和进步,现在的遮挡剔除算法已经不再是以前那样简单的实现遮挡剔除算法,而是在探究如何从硬件层面实现算法的高效性。现今发展较为先进的主要有CHC++算法和NOHC这两个硬件遮挡剔除算法。
对于硬件遮挡剔除算法而言所使用的工具,即硬件遮挡查询来说,其虽然能够使得非常高效的实现硬件遮挡剔除算法,但是其在某些层面也存在着许多的不足之处。因为硬件遮挡查询工具在运行的时候是采用的异步的工作模式,使得其对系统的资源占用不够高效,甚至在一定的程度上导致应用程序的崩溃。具体造成这种情况的原因就是在进行物体渲染之前必须得出物体的可见性情况,这就造成了CPU必须等待遮挡查询的结果,造成了CPU和GPU的利用率的低下。为了缓解这种异步工作所带来的低效性和不稳定性,因此就需要将这些异步工作时的空闲时间进行填补和利用,但是现今许多改进的相关技术又在查询功能上变得十分的复杂。
对此的解决办法就是使用OpenGL3.0来进行渲染工作,将遮挡查询等待的时间利用,实现系统的并行工作,从而提高遮挡剔除算法的高效性。具体的原理即为,首先对遮挡查询等待时长进行条件判断,当等待时长过长时直接对当前查询的物体进行渲染,使得系统空闲时间得以利用。但是对于这个等待时长的限定也需要进行详细的考量,当等待时长过短则会使得多数的物体都将直接进行渲染,使得遮挡剔除算法变得没有实际的意义,但是等待的时长过长也会也会使得加入的条件渲染没有很好的效果。
硬件遮挡剔除算法在运转的过程中造成CPU中断的现象也使其难以与其他的渲染算法共同结合起来。造成这种现象的具体原因就是其在算法完成时,最后的返回结果值还必须判断其可行性,使得,这也在一定的程度上造成了其工作的效率。
3.2  混合场景渲染管线
为了使得硬件遮挡剔除算法的低效性和难以结合性得到解决,在本系统的设计和开发中将层次遮挡图的算法与LOD算法共同结合,打造一个基于GPU的混合渲染管线,使得其在复杂的大规模场景下的渲染效率和渲染效果更好。如图3-1所示即为场景渲染管线的详细显示图:
 
图3-1基于GPU的混合场景渲染管线具体的实现过程为:
首先进行渲染的预处理过程。在这个过程中需要对场景数据库进行LOD预处理数据,并且将其组织为包围体层次,使得其成为一个空间数据结构,最后根据场景数据库的数据内容产生一个附带的遮挡物数据库以进行后续的处理。
然后进行的就是渲染处理的运行过程。在这个过程中需要将不可见的场景使用剔除算法进行剔除处理,使得得到的场景中的内容均为可见的部分,接着对其进行LOD选择,最后将得到的细节层次传送带进行渲染的管线对其进行后续的渲染过程。
3.2.1 剔除处理的详细流程
在整个流程过程中首先在预处理阶段首先根据遮挡物的具体情况从遮挡物数据库中产生一个附带的遮挡物数据库,并且在生成的时候将其设定为包围体层次的空间数据结构的形式。
而在运行的过程则进行剔除算法的计算,在进行剔除处理的过程中也分为了两个部分,首先进行的是层次遮挡图的构建过程,在构建完成之后再进行下一步对遮挡进行剔除。如图3-2即为剔除处理过程的详细显示图:
 
图3-2运行时剔除处理流程
在进行剔除算法运算过程的第一个步骤的过程中还分为了三个过程来完成遮挡图的构建,依次进行视景体的剔除过程、遮挡物的选择过程以及遮挡图的构建。在第一个过程需要对预处理得到遮挡物数据库和场景数据库中无关的数据,即将干扰视景体的其他物体剔除掉。然后进行的遮挡物选择的过程中在遮挡物数据库中进行寻找,直到匹配到与当前视景体相符合的遮挡物。接着进行遮挡图的构建过程,将得到的遮挡物进行渲染,最终经过了渲染之后得到的就是原始的遮挡图了。原始遮挡图得到之后也并不代表算法的第一阶段最终完成,还需要将其进行迭代计算后,得到迭代的层次遮挡图的一个集合然后再进行遮挡剔除过程。
在遮挡剔除处理的第二个阶段,即对遮挡物进行剔除处理。具体的就是对场景按照迭代得到的层次遮挡图进行剔除,在剔除的过程中还需要经过重叠测试,重叠测试的过程中主要是测试层次遮挡图与包围体的投影的重叠情况,得到物体的可见性情况,当重叠情况严重的时候就需要进行进一步的深度测试,深度的测试可以得到更加细致的重叠情况,以确定物体是完全重叠或者是可见。
3.22 LOD处理的详细流程
LOD的处理过程也与遮挡物剔除处理流程相似,也分为了两个流程。在第一个过程中预处理,在第二个过程中进行算法的运行过程。如图3-3即为LOD处理流程的详细显示图:
 
图3-3 LOD处理流程
具体的过程为:
在LOD处理的预处理节点过程分为了三个子过程,在第一个过程中首先将物体划分为许多的空间单元,在不同的单位中使用算法来得到不同角度的采样数据,然后得到物体的可见性程度。不同的空间单元即OBB树中的叶子在得到了可见性的程度后接着就进行算法的随机排序,最终得到随机的叶子排序结果。
预处理过程完成后就可以对其进行LOD处理了,在运行过程中会根据预处理得到的物体进行LOD选择,从而得到LOD因素。LOD因素是根据物体在预处理得到的可见性的程度来决定视点的叶子表示数目的,最后算法即可根据叶子的表示情况,将表示的叶子的随机数进行写入,得到一个三角形序列。通过处理后的结果即可以进行后续的渲染处理过程。
3.3本章小结
在本章的内容中主要对混合渲染管线的主要内容进行了介绍,并且在之前对传统的硬件遮挡查询方法的缺陷进行了叙述,在对产生缺点的原因进行分析,在得到原因之后就选择了更为完善的软件层面的层次遮挡图算法,并且结合LOD算法,通过构一个混合的渲染管线使得系统在进行非常复杂的场景的渲染工作的时候也能非常高效的运作下去。
 
 
 
 
第四章 软件实现的层次化遮挡剔除
由于硬件的遮挡算法的不完善性,其在算法运行过程的异步性导致的CPU等待时间大大减低的工作的效率,并且在后续的返回值的检验过程造成CPU中断的现象使得其在应用上不能很好的实现遮挡剔除。因此在本文中采用优化过的层次遮挡图算法这一软件层面的算法来实现遮挡剔除的过程。
层次图剔除算法大致原理即将需要进行剔除处理的场景进行划分,使得场景中的遮挡物和被遮挡物分离开来,分别并入不同的集合之中。当遮挡物集合被划分出来之后就可以进行层次遮挡图的构建过程,层次遮挡图的构建过程是整个层次图剔除算法的核心步骤,在进行最后的剔除测试的时候就是利用层次遮挡图来对其场景中的遮挡物进行剔除处理的。层次化剔除算法的过程主要包含了遮挡图的构建以及剔除这两个计算部分。
对于层次遮挡图的构建这一核心来说,其在构建的过程主要的原理即将不同分辨率的投影进行一个集合的过程,通过这种不分辨率的投影使得集体的遮挡效果得以被记录下来。物体的可见性在层次遮挡图的算法运行过程中被分为了两个测试过程,即为重叠和深度的测试过程。重叠测试过程是真个层次遮挡剔除算法中至关重要的一个过程,通过这个测试可以将遮挡物与被遮挡物的投影覆盖情况进行一个衡量,然后得出其遮挡物是否完全的将被遮挡物进行遮挡的可能性。如果可能完全重叠遮挡的时候就需要进行深度的测试过程,在深度测试过程会进行进一步的估计缓冲环节。只有经过了这两个测试之后才能得出物体的可见程度。
在层次遮挡剔除算法的剔除过程中之中包含了两个重要的数据库的生成和利用,并且这两个数据库在空间数据结构方面均为包围体层次。第一个数据库即为场景数据库,场景数据库即为场景中的遮挡物的数据的一个空间划分集合。而第二个数据即遮挡物数据库,其产生的阶段为预处理时将场景数据库进行了相关处理之后得到。
在下面的叙述中将对层次化剔除算法的两个部分进行详细的介绍。
4.1构建层次遮挡图
对于层次遮挡剔除算法的一个核心的环节,构建层次遮挡图的过程中需要进行三个阶段,通过这三个阶段后最终才能得到需要的层次图。这三个阶段分别为视景体的剔除过程、遮挡物的选择过程以及遮挡图的构建。如图4-1即为构建层次遮挡的过程详细显示图:
 
 
图 4-1构建层次遮挡图过程
由上图的详细流程可以得知在进行层次遮挡图构建的时候首先需要进行了的就是视景体的剔除。视景体的剔除需要算法首先将遮挡物数据库之中的对视景体有干扰的其他遮挡物剔除掉。对于视景体之中的遮挡物将构成一个遮挡物的集合,算法就是根据这些遮挡物生成的帧时间和帧的相干性等因素来进行筛选,最终得到符合算法需要的遮挡物。而原始遮挡图就是根据这些筛选出来的遮挡物然后进行渲染到帧缓冲之中最终得到的。在得到的原始的遮挡图之后就可以进行层次遮挡图的生成了。由于原始的遮挡图在颜色上仅有黑色和白色所构成,因此很容易就能判断出白色的部分为没有遮挡的像素点,而黑色的部分即为有遮挡物的像素点。然后根据原始的遮挡图的分辨率进行一步的构造以得到不同层次的遮挡图,最后这些不同分辨率的遮挡图共同组成层次遮挡图。
层次遮挡图构建过程中三个阶段的详细原理以及介绍如下:
4.11视景体的剔除阶段
在视景体的剔除过程中首先是根据算法中的剔除算法来对遮挡物数据库之中的对视景体有干扰的其他遮挡物进行剔除,排除掉干扰的遮挡物。在剔除的过程中为了使得算法的运行速度更快,效率更高采用了结合包围体的层次的方式。通过对包围体的根节点与视景体之间的覆盖和相交情况进行判断来得出遮挡物是否处于视景体之内。具体过程是对根节点进行逐个的扫描和测试,如果当视景体与根节点完全相互重叠的时候即可判断所有的子节点都与视景体都重叠,因此可以得出遮挡物处于视景体之内。当视景体与根节点没有相交情况出现的时候即可判断所有的子节点都与视景体都没有相交,因此可以得出遮挡物处于视景体之外。但是也存在着视景体与根节点既不完全相离也不完全包含的情况,这种情况下就需要对当前根节点下的所有子节点记性逐个的扫描,从而得出那些与视景体相离的子节点,再将这些子节点剔除之后即可得到完全剔除了外围的遮挡物的视景体。如下图4-2即为视景体剔除的详细过程显示图:
 
图4-2视景体剔除
4.1.2遮挡物的选择阶段
在遮挡物的选择过程中算法会对当前状态下处理的每一帧中视点进行定位,然后再根据这个视点的详细情况来在遮挡物数据库中选择与之匹配的一个遮挡物集合。这个集合在最大的程度上对场景中的可见物进行概括,最好的情况就是包含了所有的可见物,这种最好的情况下就可以直接对场景进行渲染即可得到完美的渲染场景。但是在一般状态下为了保障算法运作的效率,在一定的时间内得到最符合需求的工作质量和数量,不会采取完全集合的选择和渲染的方式,而是采用尽可能接近完全选出遮挡物的方式来找出匹配场景遮挡物的遮挡物集合。
1)在选择之前必须要得到遮挡物的数据库才行,因此在预处理阶段首先要构建遮挡物数据库,这个数据库的具体构造时选择的遮挡物的标准如下:
(1)复杂程度:由于过于复杂的遮挡物在进行渲染时会耗费大量的资源,使得渲染的效率变得很低,不利于工作时的效益,因此尽量选择几何复杂度适中后者简单的遮挡物。
(2)冗余程度:对于多余的遮挡物,比如时钟这样的遮挡物,在遮挡物数据库的选择中也应该排除掉。
(3)大小:遮挡物过小并且离视点很远时不利于遮挡物的剔除,因此在遮挡物数据库的选择中遮挡物在大小上不能过小。
2)遮挡物集合的选择过程需要参考许多的因素。首先在选择算法上选择Z-plane 算法,通过算法对当前状态下处理的每一帧中视点进行定位,然后再根据这个视点的详细情况来在遮挡物数据库中选择与之匹配的一个遮挡物集合。
在遮挡物的选择过程的具体标准有两个,第一个即为遮挡物的复杂度,另外一个即为视点与遮挡物之间的距离的长短。由于视点变化时由于角度会变化因此得到的二维遮挡物的复杂程度以及距离都会相应的发生改变,为了使得选择更具合理性,在选择之前设定视点与遮挡物中心之间的距离作为参考距离,并且设定一个L值作为遮挡物的多边形的参考值。当算法对数据库内的所有物体进行逐个筛选的时候会根据这个参考的距离从短到长进行遍历,当遮挡物的总多边形数超过了参考的L值之后就停止遮挡物的选择。由于算法的局限性也有出现选择不够完善的时候。例如在下图4-3的遮挡物集合的选择详情显示图之中,由于在距离变化的过程中多边形总数超过了设定的L值的时候还未选择到遮挡物A和B,而其他四个遮挡物则会被则会被选择进入遮挡物数据库之中。这就导致了遮挡效果的降低。
 
图4-3遮挡物集合的选择
4.1.3层次遮挡图的构建阶段
层次遮挡图的构建是根据遮挡物数据库中挑选出来的集合来进行构造的。在这个阶段将调用GPU来完成算法的所有过程。详细流程如下:
由于不透明的物体在进行投影时,其会在屏幕空间上留下不透明的投影,而透明的物体或者空白的情况下所得带的投影则为透明的,通过这样的原理就可以使得最终的遮挡图的像素显示。而遮挡图就是对屏幕区域上不透明的区域和透明区域的一个记录,最终得到的遮挡图的像素显示中黑色像素块即为空间中不透明的区域,而白色的像素块即为空间中透明的区域。也可以说将投影中不透明的区域占所有的屏幕区域的比率即透明度作为遮挡图生成的标准。遮挡图的组成部分即像素块根据遮挡图的不同分辨率和大小,其也可能是由不同大小的标准像素块所组成,例如3*3或者是5*5的形式组成。最后,经过了渲染流程之后就能得到对应的原始遮挡图。在得到了原始的遮挡图之后也就完成了层次遮挡图的初步创建。
原始遮挡图还不能直接用于层次遮挡剔除算法的剔除处理,其还必须经过两个方面的测试之后得到最后的层次遮挡图。层次遮挡图的构建过程即根据原始遮挡图来进行逐层的构造,越往上构造所得到的遮挡图的分辨率就越低,通过这样的方式使得进行重叠测试的时间大大的缩短,提高了测试效率。如图4-4即为层次遮挡图的构建详细显示图:
 
图4-4层次遮挡图的构建
如上图所示,分辨率最高的图片为原始遮挡图,其编号为0,依次往上遮挡图的分辨率越低,编号也相应增加。在层次遮挡图中,分辨率最高的原始遮挡图在构造时采取黑色和白色结合的显示形式,然后为了使得往上更低分辨率的层次遮挡图显示更加准确,其每一块像素均由紧挨着的下层高一级的层次遮挡图按照对应比例的像素块的黑白比例平均而来,因此其在色彩上回出现灰色的情况。
在进行逐层的层次遮挡图的构造过程中,首先会对原始的遮挡图进行一个划分,使得其分为均匀的等分像素块,然后以每两个像素块为单位进行灰度的平均值计算然后得到上一层遮挡图的单个像素块的颜色。最后将所有经过了灰度平均值计算后的像素块结合到后一起就完成了一层的遮挡图的构造。再经过了逐次叠加之后即可得到最终的所有遮挡图,共同构成最后的层次遮挡图。
在进行每一层的像素块的灰度值的平均计算时都是独立进行了,因此得到的上一层的各个像素块之间本身不具有相关性,所以在进行运算时就可以采用并行运算的方式提升运算效率。具有的算法设计即将每一个像素块的灰度值的平均计算时将这一层中的所有计算分散到GPU的不同线程上去计算,通过这样的并行并发运算模式提高GPU的利用率和处理效率,使得层次遮挡图的构建过程的时间大大缩短。
在进行灰度的平均值的计算的时候所采用的算法的代码实现过程如下图所示:
 
4.2用层次遮挡图进行遮挡剔除
在遮挡剔除的环节中主要是利用层次遮挡图来将场景中的遮挡物以及被遮挡物的相互关系来进行计算的过程。在这个过程中将有两个阶段,分别为重叠测试和深度测试,这两个阶段将分别从二维层面和一维的层面来进行剔除计算。
4.2.1 层次遮挡图重叠测试
在这个阶段中主要的过程是将场景中的遮挡物在二维平面上的像素投影以及被遮挡物投影的关系经过重叠的测试来得出其相互之间的关系。重叠测试的具体依据为,当前者的投影与后者的投影在重叠测试的时候没有任何的重叠情况时候或者仅仅有部分相互重叠的情况,则说明被遮挡物没有完全被遮挡,在一定程度上是可见的,因此可以进行后续的渲染过程。但是如果发现两者在屏幕上的像素投影存在完全重叠的情况,也不能直接确定被遮挡物是完全不可见的,还需要经过在一维平面上的深度测试之后才能得出被遮挡物的可见性程度。
在进行重叠测试的时候如果为了保障测试的极度精准性,则需要对投影的像素点进行全面的逐个扫描测试,但是这样带来的结果就是算法的时间复杂度会变得非常高,算法的计算效率也就变得更低,从实际的效益来说并不合适。
为了兼顾算法的精确度和实际的效益,在进行重叠测试的过程中采用了更为简洁的方法。这个方法的具体过程就是将物体的投影转化一个包围的长方形来进行估。包围长方形是根据每一个遮挡物在二维屏幕上的投影来进行一对一的计算的,因此在一定程度上能够很好的反应其实际的透明度。包围长方形的值则是根据物体在二维平面上的投影的极限边缘值来进行设置的,在范围上要比投影的实际范围大,但是因为在对长方形这种简单的多边形进行遍历重叠测试时的计算量大大缩小,因此能够在很大程度上提高了重叠测试的效率。
在进行重叠测试的过程中为了使得物体的重叠测试过程更加的快速,在进行测试的过程中选取像素块大小与物体投影中的长方形包围体的大小最为接近的遮挡图,使这样在进行遮挡物剔除的时候就能够快速进行对照匹配完成剔除过程。之所以不选择从最上层和最下层的遮挡图来进行重叠测试,主要的原因是,当选择最下层的原始遮挡图的时候将会对场景投影中的所有长方形包围体进行测试,这不仅仅会耗费大量的系统资源,也使得层次遮挡剔除变得没有任何的意义。但是当选择从最上层的分辨率最低的层次遮挡图来进行重叠测试的话,很有可能由于长方形包围体与遮挡图中的像素块的大小相差太大,无法完成重叠测试,因此就需要进行逐层的递进运算,这也使得算法的运算效率大大的降低。因此在重叠测试中采取最接近的匹配方式来完成重叠测试的运算。
在层次遮挡图的层次图匹配选择完成之后即可进行重叠测试。在这个过程中将使用递归计算的方式来将场景中的遮挡情况与层次遮挡图中的所设定的长方形包围体进行比较和计算。当这两者的像素点在重叠测试的过程中没有重叠的情况,所有的重叠部分的像素块透明度均为100%,则可以得出被遮挡物体没有被遮挡,是可见的。如果当这两者的像素点在重叠测试的过程中出现完全重叠的情况,所有的重叠部分的像素块透明度均为0%,则可以得出被遮挡物体被完全遮挡,是不可见的。另外如果当这两者的像素点在重叠测试的过程中出现部分重叠的情况,不同重叠部分的像素块的透明度不均匀,这种情况可能为被遮挡物仅为部分遮挡,需要进行进一步的测试,但是在再次的测试之前需要将透明度为100%的没有被遮挡部分剔除掉之后再进行重叠测试,如此反复直到出现透明度为0%或者100%的情况。
为了使得算法的计算效率更高,在进行重叠测试的时候也设定了一个透明度的阈值,使得重叠测试过程中可以当重叠部分的像素块的透明度达到这个阈值的时候将其认定为未被遮挡。能够这样设定的原因是因为在本身分辨率较低的层次遮挡图中的遮挡效果会放大,在透明度很低的情况下已经很难再在接下来的迭代测试中找到透明度为0%的像素块。算法的这个设定成为保守提前终止,具体的实现代码如下图所示:
 
4.2.2层次遮挡图深度测试
因为在进行遮挡剔除的过程中仅仅进行重叠测试还不能够很好的保障重叠测试之后得到的完全被遮挡物体的深度情况,其只能反映遮挡物和被遮挡物之间的二维平面关系,在一维平面上的深度关系就需要通过深度测试来进一步反映。对于深度测试方法的详细介绍如下:
1. Single-Z-plane
在进行深度测试的时候所采用的第一个方法即为Z平面算法,这个算法的主要原理就是通过利用Z平面来将可能存在的遮挡物与被遮挡物进行一个分离的过程,由于Z平面的深度值已经非常大,几乎所有的遮挡物的深度值均不可能比它大,所以可以认为在分离后处于该平面之后的物体即可认为比遮挡物的深度值要大的多,因此就可以将被遮挡物分离出来,处于平面之上的即为遮挡物。由于Z平面算法只能够进行粗略的计算,在进行深度测试的时候采用深度估算缓冲可以得到更为精确的结果。
2. 深度估算缓冲
深度估算缓冲的过程也与重叠测试过程中采用的保守估计的方式相类似,其比Z平面算法计算的精度要更高一些。在这个估算的过程中会将整个平面进行划分,然后分别对不同的区域进行比较。
   在进行深度估算缓冲之前首先需要对场景中的每一帧图片都进行构造,使得遮挡物的投影的像素块被确定。在进行这个过程的时候将对场景的每一帧的遮挡物投影都进行扫描和确定,由此造成的计算量也会大大增加,使得算法的效率变低。因此在实际的运用过程中也采用长方形包围体的方式来进行深度值的衡定。通过这样的方式使得进行深度估算缓冲的速度大幅提升,使得算法的效益更高。首先进行像素块深度值的判断,当其有更改时就需要进行更改前后的比较,在确定深度值的更改后再进行深度测试,如果保持原本的值则直接进行深度测试。在所有的像素区域都经过了遍历计算之后即完成了深度估算缓冲的所有过程。
深度估计缓冲估计与重叠测试一样,也可以进行保守估计来提高实际的工作效益。通过设定一个深度值的阈值,使得在进行深度估计缓冲的时候,达到或者超过这个阈值的则可以直接保守认定其即为物体没有被遮挡物所遮挡,可以直接进行渲染的处理。
由于深度测试在一定程度上需要更大的计算量,因此在计算时会花费比较大的时间和系统资源。为了使得深度测试能够保障一定的精确性的同时能够有着更高的效率,在进行深度缓冲估计预算时采用较为合适的分辨率,而不是最高的分辨率来进行测试。在进行这个过程的时候将对场景的每一帧的遮挡物投影都进行扫描和确定,由此造成的计算量也会大大增加,使得算法的效率变低。因此在实际的运用过程中也采用长方形包围体的方式来进行深度值的衡定。通过这样的方式使得进行深度估算缓冲的速度大幅提升,使得算法的效益更高。
当物体在重叠和深度的测试过程中的存在不通过的情况即可认为其是可见的,反之,当两项测试均通过时则可以认为其是被遮挡的,需要进行剔除处理。
4.3本章小结
在本章的内容中主要对系统所采用的层次遮挡图剔除算法的实现过程进行了详细的描述。在这个算法中则主要包含了遮挡图的构建以及剔除的过程。遮挡图的构建中需要经过视景体的剔除、遮挡物集合的选择以及层次图的构造。而剔除过程则进行了重叠测试和深度测试这两个过程。通过这些过程的实现以及协调配合共同实现了在软件层面的层次遮挡图剔除算法。
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
第五章 并行化的视点依赖 LOD 算
LOD是一种很常见的帮助进行可行化的视点定位算法,这种算法的使用主要是由几个重要的部分组成,其中就有网格简化的算法部分,为了对物体进行合理的可行化视点的改进,需要使用不同的网络格式算法,因为不同的物体的各种性质不同,所以需要不同地算法进行操作。本文章的内容主要是通过大型的森林场景为例子进行场景渲染的操作,通过这个森林场景的渲染来验证本文作者提出的场景渲染算法的优点性。下面为了介绍网格简化算法,特意采用森林的树模型进行合理的操作。
树状模型的网格化设计是一个不同于一般物体的网格化设计,树形的网格化设计要对不同的树枝形状的物体进行网格化设计,但是这种树枝形状的网格化设计不适合使用一般的折叠方式,本文介绍的算法对树形模型进行网格化设计的时候,采用的是通过不同的视点进行树形模型的算法设计,利用该树形的不同视点进行合理的分析和采样,再通过详细的电眼和对结果的分析进行考证,最终得到了相应的LOD模型。
该算法的组成部分主要分为两个部分,具体的介绍如下所示:
预处理阶段,在这个阶段,算法需要将树模型的各个空间进行分割,然后使用方盒进行圈点包围,形成不同的空间单元,在这之后,算法在利用不同的视点进行对不同的空间单元相关的可视化的样本采集,最后得到不同的空间单元相关的一些有用数据。完成了数据的收集之后,再对各个不同的空间单元中的树叶进行详细的分析,进行随机的采样调查。
在该算法的运行阶段,通过分析每一个帧数的相关算法的具体情况,选择不同的LOD模型,在利用各个不同的空间单元中的一些调查数据来确定不同的视点到空间单元的距离,还要计算各个不同的视点到空间单元的角度,在完成这个计算之后,结合在上一阶段中得到的一些数据,计算出LOD因素。这个因素可以用来确定不同的空间单元中的树叶数量,最后,使用上一阶段统计得到的树叶分析数据,将由LOD因素得到的树叶表示方式进行树叶三角形的设计,将这个三角形的数据保存在算法的数组中,再由算法进行数据的传输,传输到渲染管线中去。
从实现的方面进行讲解,可以说每一个空间单元的相关分析都是与其他空间单元无关的,所以说GPU的并行实现是可以用来很好的进行该算法的实现。下面是一些相关细节的解释。
5.1预处理阶段
这个阶段分为三个步骤。
第一个步骤,算法对树形模型进行空间单元的产生,使得空间单元能够将树形模型的叶子包括进去。
第二个步骤,要通过算法将各个单元的相关数据进行计算出来,并记录各个单元的数据,用于计算叶子的可视化程度。
第三个步骤,将不同的空间单元的叶子进行合理的分配,再进行数据的排序。
5.1.1生成空间单元
生成空间单元是预处理阶段一个重要的组成部分,也是整个算法的重要部分,在进行空间单元的生成过程中中需要注意多个问题,第一个就是要注意树形模型中的叶子分布的情况,还有就是要注意叶子的类型。这两个因素是决定空间单元生成过程中能否正常的进行操作。算法需要达到的目的就是要保证使得各个空间中的叶子最多,还要保证空间单元的空间最小,这个算法的目的之一就是要将物体用空间单元的模式进行紧密的包围,空间单元的数量决定了GPU的计算能力。
空间单元的生产是利用OBB进行实现的,根据不同的深度数据,得到合适的空间单元,要想得到OBB树,就要通过该算法得到一个树形包围体,再对树形模型进行空间的分析和划分,将空间单元切割成两个空间子单元,然后将这个空间单元作为子单元的父亲节点,最后得到的就是一个通过递归算法实现的OBB树。具体如图5-1所示:
 
5.1.2可见度计算
在进行空间单元的生成之后,需要进行可见度的计算,这就需要使用不同的视点进行相关的数据计算,从而得到空间单元的可见度。这个可见度的计算是很重要的,空间的可见度决定了空间单元的叶子数量的表示方式,要想很好的得到树形模型的具体形态,就要对树形模型进行全方位的监控和分析。具体如图5-2所示:
 
这个可见度的计算方法主要是通过特定的函数进行的,这个函数有几个变量:cell是空间单元,camID表示摄像头,函数的返回值表示可见度。要想确定空间单元中的叶子数量,就需要从某个视点进行观察,而这个可见度就是其中一个决定性的因素。该算法需要单独的对每个空间单元进行可见度的计算,所以处理阶段的时间复杂度就是O(ncelk*ncameras),其中的几个变量表示的含义有:Ncelk 表示的是空间单元的数量,Ncameras表示的是摄像头的数量。
具体的空间单元可见度的计算公式是:
 
从每一个视点进行观察,各个空间单元的叶子数量会被不同的设备进行多次的渲染,一共渲染了4次,第一次是为了保证能够得到空间单元的像素,第二次也是为了进一步的得到与像素有关的数据,第三次是为了填充各个空间单元的缓冲程度,所以需要对所有的空间单元进行整体的渲染,第四次的渲染需要重新对现在的空间单元进行渲染,进而就算出从当前视点观察到的空间单元的像素,通过可见像素和当前视点的可见像素,就能够算出当前空间单元的可见因素。这个计算的具体实现算法如下:

 
5.1.3叶子随机排序
在预处理阶段,需要对叶子的数量进行计算,得到各个空间单元的叶子数量之后,还要对各个空间叶子数量进行相关的随机存储,存储的顺序是随机的,随后在利用这个存储的叶子数量进行特定的排序,保证在运行阶段能够随机的使用叶子数据。
5.2运行时阶段
算法的运行阶段有两个重要的部分,第一个重要的部分就是要选择合理的LOD算法,第二个重要的部分就是要生成三角形序列。在预选阶段,该算法中的遮挡删除算法的功能就是将不可见的树排除在树模型之外,因此该算法能够在树的数组中挑选出相关的数据进行LOD模型的设计,在这个阶段,视点是会不断变化的,所以需要根据具体的情况进行相关的LOD模型的改变。再收集不断变化的LOD模型之后,得到动态的LOD模型,最终得到一个三角形序列,发送给渲染管线。
5.2.1 LOD的选择
在进行渲染的过程中,有的图形不需要进行渲染操作,所以需要设计合理的算法来选择合适的LOD模型,为了得到视点依赖的效果,算法设计了一个特别的函数,这个函数中有几个变量,有LODcell——factor,这个变量是决定了空间单元在特定视点的叶子数量,能够影响它的因素有空间单元的可见度,还有空间单元到视点的深度等等。
空间单元的可见度能够直接的通过算法计算得到,空间单元的可见程度就是距离现在视点最近的三个视点相关因素的加权平均和,计算的公式是:
 
具体的解释通过图形进行表示,如图5-3所示:
 
函数dist将树和视点的相对位置映射到特定的范围,这个函数包括了两个LOD,分别是最大的和最小的LOD,具体的计算公式是:
 
所以说,空间单元的LOD模型主要还是有空间的可见度和距离决定的,算法为各个空间单元都设计了一个LOD模型,最终再存储到相关的缓冲区中,这个操作的时间复杂度的计算由空间单元的数量决定。
5.2.2生成三角形序列
为了得到细节层次的叶子数量,就需要算法生成相应的三角形序列,在LOD模型的选择阶段,这个三角形序列是该阶段重要的影响因素,决定了叶子的数量选取。
在预处理的阶段,空间单元被分配了随机的叶子数量,并进行了随机的排序,在运行阶段,需要使用特定的函数变量进行空间单元的表示,叶子数量的表示主要是Nleaversell,叶子的数目是不确定的随机的,因此可以很简单的通过空间单元产生的随机叶子数量作为当前观察到的叶子数量,并用该叶子数量来表示整个空间单元。
由于GPU具有并行能力,所以能够保证算法产生相应的索引表,这个索引表是由叶子的数量组成的,因此需要在算法的设计中对空间单元的叶子数量进行地址的计算,具体的地址计算方式如图5-5所示:
 
该算法的代码实现主要是对地址进行上扫描,在对地址进行下扫描,在计算出空间单元地址的偏移量之后,系统就会为空间单元提供寻址的索引表,最后将三角形序列存储到合适的地址中,最后将三角形序列发送到渲染管线中。
5.3本章小结
本章节阐述了依靠视点进行LOD算法实现的过程,介绍了算法实现的两个阶段,预处理阶段和运行阶段。
预处理有三个步骤,分别是划分空间单元、计算可见度、对叶子进行随机排序。
运行阶段主要是为了计算LOD因素,这个计算需要可见因素和视点位置,在得到LOD因素之后通过算法的相关操作得到空间单元的叶子表示方式,得到叶子的三角形序列,传送到渲染管线进行渲染操作。
第六章 实验结果与分析
6.1实验环境
实验使用的硬件环境主要是:CPU采用的是Intel core i5 6500,核心数量是四核,生产工艺是14纳米,核心的类型是skylake,接口的类型是LGA 1151。
采用的GPU是GTX 960,显存的大小是2G。
实验机器采用的操作系统是win10。
6.2实验结果的分析
本实验使用的场景是大型的森林场景,使用的测试方式是利用横向和纵向的对比进行分析,得出算法的渲染效果。
在横向的对比中,需要进行测试的数据主要是渲染的帧数和三角形序列的数量,具体的测试方式分为几个方面,一个是只使用LOD算法进行相关的计算,二是通过选择了剔除函数的算法,三是利用LOD算法和剔除算法的结合进行计算,四是利用普通的算法进行计算,不使用LOD算法也不使用剔除算法。
横向的对比采用的数据包括1000棵树, 5811个序列三角形,空间复杂度为5811000具体如图6-1所示:
 
图6-1由5811000个三角形构成的大规模森林场景
在实验测试中,算法设计的层次遮挡图如图6-2所示:
 
图6-2 层次遮挡图
横向的数据对比表如图6-3和图6-4所示:
 
图6-3帧率比较
 
图6-4三角形总数比较
从图6-2能够得到以下结论,就是LOD算法结合提出算法得到的方法能够恨到的提升森林场景的渲染程度和速度。这种方法得到的渲染帧数远高于其他的渲染方式,比第一种渲染方式提升了7倍,比第二种方式提升了1.5倍,比第四种方式提升了17倍。所以说剔除算法比LOD算法要高效。
从6-3图中能够得到以下结论,剔除算法和LOD结合的方式可以避免97%的无用三角形被渲染,第一种方式只能避免70%,第二种只能避免95%。
因此得到总的结论就是剔除算法和LOD算法结合的方式是一种最有效的渲染方式,能够很大程度的提升渲染效率,大大的避免无用三角形占用资源。
纵向对比应用的场景也是森林场景,不过空间复杂度更加大,场景具体的数据有1000棵树,49207个三角形序列,复杂程度是49207000个三角形序列。具体的表现如图6-5所示:
 
纵向对比主要是为了测试渲染的加速比,加速比是经过渲染后的帧数和未经算法渲染的帧数之比。
在经过不同场景的算法渲染之后得到了不同的帧率,具体如图6-6所示:
 
图6-6场景渲染帧率对比
由图可知6-1的渲染加速比为17.46。
由图可知6-4的渲染加速比为29.95。
所以说,越复杂的场景,该算法体现的效率越高,渲染的效果越明显。
6.3本章小结
在横向的对比中,需要进行测试的数据主要是渲染的帧数和三角形序列的数量,具体的测试方式分为几个方面,一个是只使用LOD算法进行相关的计算,二是通过选择了剔除函数的算法,三是利用LOD算法和剔除算法的结合进行计算,四是利用普通的算法进行计算,不使用LOD算法也不使用剔除算法。从对比的图表可以得到的结论就是LOD算法结合剔除算法的方式在渲染帧率以及剔除效率上都比其他三种方式要好。
在纵向对比中,纵向对比主要是为了测试渲染的加速比,加速比是经过渲染后的帧数和未经算法渲染的帧数之比,从对比图中可以得到的结论就是越复杂的场景越能体现出算法的高效性。
所以说,本实验的结论再次证明了越复杂的场景,使用该算法,越能提高场景的渲染程度和渲染的速度。
 
 
7 总结与展望
7.1  总结
   本文主要研究基于GPU的大规模复杂场景的优化算法。在研究前,本文分析了国内外的研究形式,点出了目前已经有哪些学者提出了对场景渲染有着突破性的算法和构想。本文所提出的算法结合了LOD算法和遮挡剔除算法的优点,在一定程度上加快对于大型复杂场景的渲染速率。在于硬件方面,该算法利用了CPU和GPU在空闲时刻的运算能力,使得整个计算机在使用该算法时并不需要一定的硬件配置需求。对于LOD算法所拥有的处理物体相对位置的优点,以及遮挡剔除算法中能够剔除遮挡物体以及视野外物体的特性,该算法都会包含。所有在算法执行效率,以及时间复杂度上具有相当的优势。
  第一章提出了研究的论题,并就国内外的研究现状做出了相应的分析。第二章主要会就大型复杂场景渲染所需要的相关技术进行介绍。第三章主要会就大型复杂场景的渲染管线进行介绍。第四章主要会就如何利用软件来实现对于层次化遮挡提出算法进行介绍。第五章主要会就在算法上实现可视化并行计算,利用LOD算法的特点来实现该算法。第六章主要会就本算法进行实验的结果进行分析,并且得出相应结论。本章主要对前面的内容做出了总结。
本文在讲解该算法的时候,便于理解,运用了几百个面片构成的大型森林场景作为例子来进行说明。利用该算法,不仅仅只是实现了对于大型森林场景的实时渲染,并且在算法效率上,只对比于LOD算法或者是遮挡剔除算法,在速度上都有了很大的提高。
 
7.2  展望
    在对于场景的真实感的设计方面,本文所提出的算法并没有利用光线的阴影来对物体进行处理,在之后的算法完善过程中,会考虑到对于物体阴影的处理,从而能够使得整个物体更加鲜活,使得整个场景看上去更有真实感。
   在对于大型复杂场景的渲染速率来说,本文在空间数据结构上只是采用了简单BVH,使得整个空间的层次感划分不太强烈,造成整个算法的时间复杂度较高,算法的执行效率较低,从而导致渲染的速度较慢。
     对于LOD算法的使用上,一般是通过与实例化技术共同作用来实现的。但是本算法,考虑到了渲染管线与实例化技术并不兼容的因素,并没有采用这个方法。在未来对算法进行优化时,会考虑到通过优化渲染管线来起到加快场景渲染速度的效果。
       本文在对算法的介绍上仅仅只局限在森林场景这个例子中,LOD算法的主要处理对象也是针对于树模型来说。在未来对算法进行优化时,会考虑到让理的对象更加普遍的。
 
  
致  谢
在这篇论文完成之时,我的学业生活也要告一段落,回想期间付出的汗水,特别是在工作的同时还要进行论文的撰写,每晚坚持撰写到深夜。这是对我自身的考验,也是我感到最为丰富的一段记忆!
 在此,我想要感谢我的指导老师陈泽琳老师,开始,我对研究课题的把握不是很精准,正是陈老师耐心的指导,才让我很快的掌握了课题的研究方向。然后通过在项目开发中的探索,最终完成了这篇论文中所设计的系统。我之所以能顺利的完成课题的研究和论文的撰写是因为陈老师的热心关怀和耐心帮助。感谢他对我的悉心教导。感谢陈老师在我毕业论文选题、实验方案的确定、课题工作的开展以及论文的撰写等方面对我的帮助。在我研究生学习的生涯中,陈老师一直耐心的指导着我,教育着我。陈老师和蔼可亲,对待学生的诚挚与热情,对待学问的孜孜不倦与热情、以及对问题严谨的态度都让我如沐春风,收获颇多。这些也将成为我日后工作的财富。
  其次要感谢的就是跟我一起生活和学习,与我共同进步和克难奋进的同学们了,是你们在我以往的学习中跟论文的撰写过程中对我无私的帮助使得我顺利的完成。在与你们的相处中我学到了许多的书本上和社会上的知识。让我成为一个更加完美的人。 
  最后要感谢的就是我的家人们了,如果没有他们的支持和鼓励我也不可能坚持到现在,你们的对我的关心,是我遇到困难时,照亮前路的明灯。谢谢大家


收缩