大规模场景的消隐技术

大规模场景的消隐技术
2011年03月22日
　　学无止境，把这几年收藏的文章都晒出来，大家共享吧! 声明：早期转载的文章未标明转载敬请原谅，以后将陆续改过来，向原创者致敬！ C++ , Direct3D, OpenGL, GPU,OGRE,OSG,STL, Lua, Python, MFC, Win32 (有问题可留言，部分网页看不到图片可网页另存为到本地再打开即可看到) 痞子龙3D编程 QQ技术交流群:32103634
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　
　　浙江大学CAD&CG国家重点实验室 陆艳青、王章野、彭群生   杭州 310027 可见性判断，即从某个视点决定哪些面可见，是计算机图形学的一个基本问题，其重要性已广为人知。如今在基于网络的图形学，虚拟环境，阴影测试，全局光照，遮挡剔除，交互漫游中已成为关键问题。令场景S, 由一些模型单元构成（如三角形），S={P0.P1,…, Pn},视域锥定义了视点，视线方向，及广角, 消隐算法就是要找到可见面，剔除隐藏面，为了减少绘制的元素，定义可见集VS为至少在屏幕上贡献一个象素的元素集。然而对大规模场景，困难在于场景的复杂性，当场景个数为n=O(|S|),消隐算法的复杂度可能达到O(n2)。大规模场景使消隐成了至关重要的问题，通常可见的物体数要比总数少得多，例如，典型的城市场景，只能看到城市的一角，这类场景称为稠密遮挡场景，在任何一个视点均只能看到一小部分。其它如室内场景，墙壁遮挡了大部分场景，实际上从房屋的任何视点，仅能看到该屋内的场景及通过门廊的可见物。常用的一些方法有视域剔除，背面剔除，遮挡剔除（见fig1），用得最多的方法是遮挡剔除。可见性判断不是个简单问题，因为视点的小小变动有可能引起可见性的巨大变化，解决了一个视点或许对附近点帮助不大。因此，研究大规模场景的消隐已日益变得重要了。 可见性计算还可用到其它一些问题，例如：
　　---阴影计算：从光源处的不可见部分为阴影，所以遮挡剔除与阴影计算有许多相似之处。然而，阴影计算通常需要更精确的方法解决，保守可见性计算法则不能应用。 ---辐射度算法：在辐射度算法中，能量需要从一个面片传到场景中的每一个可见的面片，这需要在面片上应用区域可见性判断。 Fig 2 两物体间的遮挡关系   1．消隐算法的分类               在近几年出现的大规模场景消隐算法中，大致可分为以下几类
　　●    精确对近似。
　　●    保守对精确。
　　●    预处理对实时处理。
　　●    点对区域
　　●    图象空间对景物空间
　　●    软件对硬件
　　●    静态场景对动态场景
　　精确可见集:仅包括所有完全和部分可见多边形。
　　近似可见集：包括大部分可见多边形可能还包括一些隐藏面。
　　1.1 保守对近似:
　　很少算法试图寻找精确可见集，大部分算法是保守估计，即多估计可见集，少部分近似估计可见集，但其可见集不完全正确，例如PLP算法[4]。有些试图找保守的，但实际上丢失了小的可见面，如HOM[12]，基于OpenGL的遮挡剔除[13]。
　　1.2 预处理对实时:
　　大部分技术需要一定量的预处理，但这里所指的预处理是指把存储信息作为其一部分，几乎所有的区域消隐都属于预处理。有些算法需要一些预处理，但仍称为实时消隐，如，HOM[12],DDO[14],Hudson et al.[15],Coorg and Teller[17],花费一些时间选择一定数量的遮挡物，但只需存储很少的信息。
　　1.3 点对区域：
　　主要不同在于算法执行计算是依赖于精确位置还是在区域内使得其内部任何一点均可重用可见信息。显然，区域消隐在空间区域执行可见性计算，即在其内部时用相同的几何物体。
　　1.4 图象空间对物体空间：
　　几乎所有的算法采用了层次结构，分为图象空间和物体空间依赖于在何处执行可见性计算。例如HOM[12]和HZB[3]在图象空间执行遮挡判断。在HOM中，遮挡图在在二维图象投影面上执行而不在原三维表示中执行。其它利用图象空间的DDO[14]（也利用物体空间执行依赖视点产生遮挡物进行遮挡剔除），其它大部分算法在物体空间进行。
　　1.5 单独遮挡物对遮挡物融合：
　　给定三个元素，既不被遮挡，也不被遮挡，但被两者联合遮挡，一些算法能够执行遮挡融合，而另一些则只能利用单个元素。 2.景物空间的消隐
　　景物空间的消隐算法最早是Teller和Sequin[18]对室内场景的工作，处理的是二维情况，把场景组织成2D BSP树，然后在各个单元网格见判断是否有门廊，由此判断两者是否遮挡。
　　2.1Coorg 和 Teller[15，16]
　　Coorg 和 Teller提出了两种景物空间的消隐技术[15，16]，第二种更适合于场景中有大量的遮挡物，其算法在两个凸体之间判断可见性关系，（见图2），当观察者在两支撑平面之间左边的区域，被完全遮挡。Coorg 和 Teller方法基于视点变化时跟踪可见物及变化可见物之间的关系，它利用了时间的连贯性来检测可见物。
　　在[15]，基于物体轮廓边的关系及不同物体的支撑面和分离面，他们给出了两物体之间可见性判断的有效条件。并建立了一套算法跟踪这些关系的变化，物体建立层次结构（八叉树）。在绘制时，根据视点的连续变化重建可见信息。
　　作者在[16]给出了更有效的算法，仍基于两物体之间可见性关系，但抛弃了大量连续可见性判断，动态选择遮挡集用来决定场景中余下的那些部分不可见面。在这片论文中，作者提出了几种有效的建筑物遮挡来执行这个思想，包括用简单的表决定多个遮挡物能合在一块，一个快速的方法是决定支撑平面和分离平面。更重要的是他们提出了一个简单的测度，基于物体的近似夹角来判断动态遮挡物：
　　其中A是遮挡物面积，法向，视线方向，视点到物体中心的矢量。
　　2.2 Hudson等[17]
　　其算法类似[16]，也是动态选择遮挡物，以这些物体剔除余下的物体。不同在于所依赖的元素细节，作者给出了新的标准，取代用物体近似夹角，也利用深度复杂性及遮挡物的连贯性。他们首先对场景进行空间剖分，对每个网格，遮挡物的选择是在该网格内的任何视点均有效，以便存储为以后使用。实际的遮挡物也不同，对每个遮挡物，用视点与物体的轮廓线建立遮挡阴影锥，任何在阴影锥中的物体被遮挡，通过一些遮挡物，场景中大部分物体被剔除。
　　2.3 BSP树剔除[19]
　　该方法联合遮挡物的锥形域形成遮挡树，遮挡树的建立是从一个可见的叶结点开始，每个遮挡物不断插入，如果遮挡物与叶结点的阴影相交，则扩大阴影锥，如果结点完全位于阴影锥内，则寒冷该遮挡物。一旦层次遮挡树建立了，就可用来遮挡比较。场景结点自上向下遍历，如果结点完全可见或完全遮挡，则停止迭代，否则其子结点重复与遮挡树比较，这样做的好处是避免了与N个遮挡阴影锥比较，而只与树的深度数目比较。
　　这个方法把遮挡树用BSP树表示达到联合遮挡物的目的，虽然使遮挡剔除更有效，单仍需花时建立好的场景BSP表示和树的联合。
　　2.4 优先层投影算法(PLP)[4]
　　优先层投影算法(PLP)是对高度复杂场景的一种快速绘制算法。执行思想是从给定视点迅速估计可见多边形，每次增加一个元素。PLP不是保守算法，适合于对绘制时间要求严格而允许部分错误存在。PLP是一般视域锥剔除算法的改进，但是它需要计算每个网格的遮挡值，用来决定元素投影的顺序。
　　预处理：把空间景物有效的组织成凸单元网格，使每个网格中的面片个数大致相同（如八叉树），类似于体绘制中不透明度，在每个网格内定义遮挡度，遍历算法根据其遮挡度从小到大遍历。
　　绘制过程：绘制算法大致按从前往后的顺序遍历单元网格，种子网格从包含视点的单元网格开始，其算法如下： t(c) 绘制c中所有的面片，同时记录实际已经绘制的面片数，如果绘制数目已达到某个阀值
　　直接从视点估计场景中可见的面片数，适合于对绘制时间要求严格而允许部分错误存在，其主要特点是预处理简单快速，绘制效率高，不足是会在上产生空洞。
　　3.图像空间的遮挡剔除
　　在视域坐标中执行剔除，关键是在场景绘制的过程中屏幕得到填充，后面的物体通过这些已填充的图像快速剔除。
　　3.1 层次Z-Buffer(HZB)[3]
　　层次算法由等于1993年会议上提出的，该算法首次对传统的Z-Buffer进行了改造，Z-Buffer 用Z-金字塔取代,极大的提高了具复杂遮挡率场景的消隐过程。算法将场景中的景物组织八叉树结构，并利用景物的空间连贯性来考察每一八叉树结点的可见性。若八叉树结点对应的立方体的六个表面关于当前的缓冲器不可见，则立方体内上任何景物均不可见；否则，重复迭代其子结点。若为可见叶结点，则该结点内所有景物需逐一绘制。为提高结点立方体关于缓冲器的可见性判断效率，层次算法将屏幕象素的可见点按其深度值组织成四叉树结构，以便快速拒绝被遮挡结点。该结构类似于纹理映射中的表结构，是个分层结构，其中后一级的分辨率是上一级的四分之一，其中每一象素所存储的值为该象素所对应屏幕空间可见结点的最大值。这样，利用层次算法就可实现景物八叉树结点和当前屏幕象素可见点集的快速区域重叠测试和深度比较，从而快速地判定结点和面片的可见性。
　　初始缓冲器的好坏对画面绘制效率的影响，层次算法利用时间域上的可见连贯性来加速画面的可见性计算。算法首先对上一帧可见的八叉树结点所含景物面片无条件地绘制，构造初始的层次缓冲器。层次算法能高效的剔除不可见面，但现在硬件仍未支持，由于其构件层次缓冲器比较费时，不能做到实时绘制。
　　3.2层次遮挡图(HOM)[11,12]
　　这个方法类似于层次，它利用了当前的图形硬件，支持近似的遮挡剔除，提出了层次遮挡图，是指一帧二维图象，其中每个象素记录了屏幕空间的一方形区域的不透明度，则不透明度定义为其中不透明区域面积与整个方形区域面积比。
　　在预处理过程中得到潜在的遮挡集，在绘制每帧时执行两步：建立层次遮挡图和用遮挡图剔除场景几何。为建立，从遮挡物集中挑选一些遮挡物绘制到帧缓冲器，这个过程仅需值，无需纹理，光照及深度信息，景物绘制白色，背景为黑色，然后从帧缓冲器读出建立层次遮挡图。
　　判断一个物体是否遮挡，首先投影其包围盒到屏幕进行重叠测试，如果重叠部分不透明或超出了预先给定的阀值，则需进行深度测试决定其是否在遮挡物后面。否则不能剔除该物体。
　　这篇文章给出了一些物体深度测试的方法，最简单的方法是在所有遮挡物后面用一个平面取代,虽然是快速简单的,但该方法太保守,很多遮挡面不能被剔除,一个改进方法是在屏幕空间分成几个区域,用几个分离平面分别进行测试.
　　3.3直接离散遮挡物(DDO)[14]
　　直接离散遮挡物方法类似于HZB和HOM也用景物空间和图象的连贯性，在预处理过程中建立景物八叉树计算简单的依赖视点的多边形遮挡物代替复杂的几何物体单元体素的每个面认为是一个潜在遮挡物,这样,方形,轴对齐的面取代原有几何体用作依赖视点的遮挡物.
　　绘制算法自上而下,从近至远遍历八叉树,在遍历过程中发现有效遮挡物,投影到二维平面,建立四叉树每个八叉树首先与遮挡物的投影面进行比较如果结点不可见,则停止。否则重复迭代其子结点知道可见的叶结点,绘制其几何。
　　DDO方法预处理过程化时不多，DDO的内存要求只是每个结点记录是否为虚拟遮挡物的六个位平面,DDO方法很容易执行遮挡融合,无需特别的图形硬件。图是DDO方法的二维示例,网格是离散的八叉树结点,A,B为输入几何，视点的有效遮挡物用粗的实线表示。
　　3.4基于OpenGL的遮挡剔除[13]
　　Bartz等描述了图象空间的另一种剔除算法，场景用层次结构表示，类似于HZB和HOM遮挡测试在图象空间进行，与这些方法相比，遮挡物没有层次表示，而是对视域锥和遮挡剔除均用OpenGL调用硬件查询可见信息。
　　对视域锥剔除用选择模式，选择模式能检测屏幕某个区域决定一个物体是否已绘制到屏幕了。设置检测区域为整个屏幕区域，绘制物体的层次包围盒，能很快决定哪些物体与视域锥相交。绘制包围盒只是选择需绘制的物体，不对帧缓冲器作贡献。
　　遮挡测试是另一个单独的缓冲器，称为虚拟遮挡缓冲器，联合帧缓冲器检测对屏幕有贡献的物体，用模板缓冲器，
　　读取虚拟遮挡缓冲器，任何在屏幕上有覆盖区域的包围盒均认为是可见的，绘制其中的元素，读取虚拟遮挡缓冲器花时很大。
　　4 区域消隐
　　经典的消隐算法，是以单个视点进行遮挡测试，这些算法在交互漫游过程中只能单帧处理，一个更好的策略是从视区网格内找到潜在可见面(PVS)，使得在该视点网格内能重用这些可见面。
　　以前的剔除物体当且仅当它被一个凸的物体遮挡,一般当遮挡物比视点区域大得多时才比较有效,然而这种情况在实际中并不多见,例如图,每个遮挡物对于视点区域多很小她们联合起来形成的遮挡锥很大。近来，用联合遮挡物（遮挡物融合）的新技术得到了发展，遮挡物之间不一定相连，遮挡物也不一定是凸体。这些方法的效果比以前的有了较大的改善。
　　4.1 用遮挡融合保守体可见性判断[8]
　　这篇文章介绍了一种新的区域可见性计算的保守技术，这方法先对空间进行离散表示。用物体内部的不透明部分作为遮挡物，有利于遮挡物扩展到空间相邻的不透明区域。该方法有效的检测和表示被遮挡的空间区域，第一次利用了能与被遮挡的空白区域融合，结果显示这是有效的融合。 首先，物体边界在空间进行离散化，内部标为不透明。对每一个视区，算法遍历这些不透明体，把相邻的不透明体素组织成有效的遮挡物，然后从视区构建一伞状物，把空间分为可见和隐藏区，实现遮挡物的融合，一个优化的方法是不透明体素按从大到小或从前往后的顺序排列，被遮挡的不透明体素不在认为是遮挡物。为了得到场景中物体的可见性，建立查找表记录其占有的空间体素，如果所占体素都为隐藏体，则该物体也为隐藏体。由于视点区域和遮挡物都是轴对齐的，所以对三维伞状物可以转化为三个二维的伞状物进行处理，作者对2D和21/2D作了进一步的处理，对两个2D盒子的位置关系进行分析，列出一张关系表。 4.2 用扩展投影作保守可见性预处理[2]
　　这篇文章是基于点的图象空间的方法（如层次遮挡图和）扩展到区域的可见性，是的预计算，遮挡物和被遮挡物投影到同一平面，如果被遮挡物的投影面完全被覆盖并且位于其后面，则被遮挡物记为隐藏体。为了保证不丢失可见面，遮挡物的投影面保守估计，而被遮挡物的投影面需高估计，该投影成为扩展投影。扩展投影的象素表示称为扩展深度图，多个遮挡物的投影平面可以融合，对凸体的扩展投影可以计算视区八个顶点处的投影面的交，这个可用图形硬件有效的加速（模板缓冲器），非凸体遮挡物的扩展投影。投影平面可以重新投影到新的投影平面，以使前面累积的遮挡图扩充到新的遮挡物形成。
　　4.3 虚拟遮挡物[6]
　　论文引进了虚拟遮挡物的概念，给定一场景和视区，一个虚拟遮挡物是个依赖于视点的凸体，被认为是从视区的任何一点均被完全遮挡,作为给定视区的一个有效遮挡物。引入虚拟遮挡物是应用有效的区域对区域的消隐技术，计算视区内有效的潜在可见集。论文提出了一种景物空间合成单个遮挡物，在实时交互漫游时只需很少的虚拟物来计算潜在可见面。
　　在预处理阶段几个物体标为种子物体，对每个种子物体，联合附近的一些遮挡物构建一个虚拟遮挡物替代这些遮挡物,开始只有一个遮挡物然后逐步加入遮挡物,虚拟遮挡物放在最远的遮挡物后面,见图
　　迭代的每一步保存一个虚拟遮挡物，这些更大的遮挡物能更有效的遮挡，在实是绘制时视点区域的PVS只有在进入该区域时才计算，层次结点通过虚拟遮挡物进行判断。
　　4.4 遮挡融合[10]
　　论文提出了一种基于观察点的方法，从视区网格边界的一系列采样计算保守遮挡锥。
　　如果一个物体被遮挡，充分条件是它包含在所有网格内采样点的遮挡锥内。显然，用离散采样的方法不是充分条件，可能会在采样点之间的视点丢失一些可见面。
　　该论文采用的方法是对每一个遮挡物收缩，这样，一个收缩的遮挡物遮住，对应于原始遮挡物在范围内的视点在原视点范围内的视点也被遮挡，
　　利用这个思想，考虑多个遮挡物，如果物体被视区内每个采样点的收缩遮挡锥所遮挡，则它在整个视区内也是被遮挡的，遮挡融合就可执行。
　　4.5 PVS的存储
　　视点区域预计算潜在可见面需要解决空间存储问题。场景剖分成视点网格，对每个网格预处理PVS并保存。因为视点网格很多，所有可见集的总数比原始场景中的数目多得多。
　　5.总结
　　对于大规模场景要做到实时消影，没有一定的预处理是不行的，今年Siggraph和Eurograph上关于这方面的文章，大多是保守估计，预计算视点区域内的PVS,它们的共同点都是要预先计算选择遮挡物，所以遮挡物的选取对PVS的数目非常关键，如果一个视点区域内所选择的遮挡物投影在屏幕上还不到二分之一，则被这些遮挡物所遮挡的物体可能就非常的少了。
　　进一步研究，降低预处理，内存是关键，尤其对区域消隐。能够充分利用硬件特征，基于硬件的快速消隐算法。
　　参考文献： [1]    Daniel Cohen-Or, Yiorgos Chrysanthou, Claudio T.Silva, A Survey of Visibility for Walkthrough Applications. Daniel Cohen, Yiorgos Chrysanthou, Claudio T.Silva. Siggraph Course notes 04. [2] Fr?? edo Durand, George Drettakis, Jo¨ elle Thollot, and Claude Puech. Conservative visibility preprocessing using extended projections. SIGGRAPH 2000, 2000.  [3] Ned Greene and M. Kass. Hierarchical Z-buffer visibility.In Computer Graphics Proceedings, Annual Conference Series, 1993, pages 231 240, 1993. [4] J. T.Klosowski and C. T. Silva. The Prioritized-Layered Projection Algorithm for Visible Set Estimation. Submitted for publication, 2000. [5] J. T. Klosowski and C. T. Silva. Efficient Conservative Visibility Culling Using The Prioritized-Layered Projection Algorithm. submitted for publication, 2000. [6] Vladlen Koltun, Yiorgos Chrysanthou, and Daniel Cohen-Or. Virtual occluders: An efficient intermediate pvs representation. In submitted for publication, 2000. [7] Carlos Saona-Vazquez, Isabel Navazo, and Pere Brunet.The visibility octree: A data structure for 3d navigation.Computer & Graphics, 23(5):635 644, 1999. [8] Gernot Schaufler, Xavier Decoret, Julie Dorsey, and Francois Sillion. Conservative volumetric visibility with occluder fusion. In SIGGRAPH 2000, 2000.  [9] Peter Wonka and Dieter Schmalstieg. Occluder shadows for fast wakthroughs of urban environments. In Computer Graphics Forum, volume 18, pages C51 C60,1999. [10] Peter Wonka, Michael Wimmer, and Dieter Schmal-stieg. Visibility preprocessing with occluder fusion for urban walkthroughs. Technical Report TR-186-2-00-06,Institute of Computer Graphics, Vienna University of Technology, Karlsplatz 13/186, A-1040 Vienna, Austria,March 2000. [11] Hansong Zhang. Effective Occlusion Culling for the InteractiveDisplay of Arbitrary Models. Ph.D. thesis, Department of Computer Science, UNC-Chapel Hill, 1998. [12] Hansong Zhang, Dinesh Manocha, Thomas Hudson, and Kenneth E. Hoff III. Visibility culling using hierarchical occlusion maps. In SIGGRAPH '97, pages 77 88,August 1997. [13] Dirk Bartz, Michael Meissner, and Tobias Huettner.Opengl-assisted occlusion culling for large polygonal models. Computer & Graphics, 23(5):667 679, 1999. [14] F. Bernardini, J. T. Klosowski, and J. El-Sana. Di-rectional discretized occluders for accelerated occlusion culling. Computer Graphics Forum, 19(3), 2000.  [15] Satyan Coorg and Seth Teller. Real-time occlusion culling for models with large occluders. 1997 Sympo-sium on Interactive 3D Graphics, pages 83 90, April 1997. [16] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithmand Applications. Springer-Verlag, Berlin, 1997. [17] T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang. Accelerated occlusion culling using shadow frustra. In Proc. 13th Annu. ACM Sympos. Comput.Geom., pages 1 10, 1997. [18] Seth Teller and Carlo S?? equin. Constructing easily invertible b?? ezier surfaces that parameterize general quadrics.SMA '91: Proceedings of the First Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 303 316, June 1991 [19] J. Bittner, V. Havran, and P. Slavik. Hierarchical visibility culling with occlusion trees. In Proceedings of Computer Graphics International '98, pages 207 219, June 1998..