论文 关键词：可见性裁减 扩展投影 层次遮挡图 层次深度图
论文摘要：可见性裁减是 计算 机图形学的基本问题，也是虚拟现实引擎中的一个关键技术。在解决可见性裁减问题时，将 durand提出的扩展投影作为保守可见性预处理的算法与greene等人提出的层次遮挡图和层次深度图的算法相结合，根据层次遮挡图来判断被遮挡物是否可见，并对算法中视点单元的大小和遮挡板的数量对裁减结果的影响作了分析。
0 引 言
可见性裁减就是找到从视点处可以看到的并需要进一步处理的所有物体。1974年 ，sutherland等人 在一份研究报告中已经对已有的隐藏面消除 hsr(hidden surface remova1)算法进行了分类，在当时已经基本解决了隐藏面的消除问题。
但随着三维场景的规模和复杂度的不断增加，这些方法已经不能满足如今大规模场景中隐藏面的消除。大规模场景的绘制时，在性能上至少有三个目标：每秒有更多的帧、更高的分辨率、更多的场景物体。为加速绘制场景，首先是使用裁减(cul1ing)技术 。
可见性裁减大致分为三种：背面裁减、视截体裁减和遮挡裁减。视截体和背面裁减是最常用的，而且几乎是必不可少的两种裁减。遮挡裁减比较复杂，对于简单的场景可能并不需要进行遮挡裁减，但是对于大规模密集的场景来说遮挡裁减是必不可少的 。www.133229.Com本文中的方法主要是针对遮挡裁减。 一种改进可见性裁减的方法。
1．1 场景组织
在进行裁减之前，首先要对场景进行组织。场景的组织是个预处理过程。这里采用二叉包围盒树来组织场景，利用两步来递归建立二叉树：(1)建立一组对象的紧密包围盒；(2)把这组对象细分为两组，然后对两组建立紧密包围盒。这个递归过程将场景图元细化成最小的组。场景对象的包围盒采用方向包围盒(obb)，在对象进行遮挡测试时，投影就会更接近对象本身的大小。图 1为实验场景的包围盒。
1．2 可见性裁减算法
1．2．1 视截体裁减
在进行裁减时，首先进行视截体的裁减。判断场景中的对象是否在视截体中，也就是判断包围盒是否在视截体中。包围盒与一个平面的位置关系可以有三种：在平面正面，在平面反面，与平面相交，如图2所示。
如果包围盒在视截体平面的反面则包围盒是不可见的，将不会被渲染；如图包围盒在所有平面的正面，则包围盒是可见的。要判断包围盒是否在平面的正面最直接的方法就是判断包围盒上的每个顶点是否都在平面的正面，同样计算量也是相当巨大的，在这里采用包围盒的中心点与平面的距离来判断包围盒的位置。
1．2．2 遮挡 裁减
(1)选择遮挡板
经过视截体裁减，在剩余的对象中选择一组对象作为遮挡板。选择遮挡板是至关重要的，应该选择那些形状比较大的，距离视点单元较近的对象作为遮挡板，才可能生成较好的遮挡效果，我们根据公式(1)来选择遮挡板 。
(2)遮挡板和被遮挡物的扩展投影
所谓扩展投影就是将基于点的投影扩展到基于空间区域的投影。算法中的遮挡板和被遮挡物的扩展投影是根据 durand等人提出的扩展投影作保守可见性预处理算法 中的定义：遮挡板的扩展投影被定义为视点单元上每个顶点处产生投影的交集；而被遮挡物的扩展投影被定义为视点单元上每个顶点处产生投影的并集。通过扩展投影可以在视点单元内部任一点处观察，被遮挡物的扩展投影都能完全在遮挡板的扩展投影中。
(3)层次遮挡图和层次深度图
计算完遮挡板的扩展投影，将其渲染到帧缓冲区中，生成遮挡图。如图3所示，遮挡图只需要占用信息，不需要纹理和光照信息。因此我们将遮挡板渲染成纯白色，背景为黑色。而遮挡图的层次可以通过对前一层的像素累加平均的方法来获得 。
通过深度估计缓冲器来生成遮挡板的深度图，它的每个像素记录着对应区域中遮挡板的最大值。如图4所示，每一层中的像素对应着上一层中2×2像素块中的最大值。
(4)重叠测试和深度测试
在重叠测试中，采用一种快速的测试方法，取层次遮挡图中与被遮挡物投影大小接近的矩形，检测矩形所覆盖的遮挡图上的像素是否完全不透明，如图5所示。
图5中矩形 a所占的区域是完全不透明的，那么矩形 a通过了重叠测试。而左图中矩形 b所占的区域是半透明的，将其与下层的遮挡图进行比较，得到右图，可知矩形 b所对应的遮挡图上的像素是完全透明的，则 b是可见的。
当潜在被遮挡物通过了重叠测试，那么接下来进行深度测试。在深度测试中采用与重叠测试类似的方法。将被遮挡物的深度值与最高层上的深度值进行比较，如果被遮挡物的深度值大，则其通过了深度测试，否则将其与下一层深度图进行比较。完成了重叠测试和深度测试 ，就可以根据潜在被遮挡物的可见性，对场景的保守可见集进行更新。
2 算法实现与分析
为了测试这个可见性裁减算法，在 opengl中导人一个3ds格式的城市模 型，如图 6所示，模型中共有 2848个顶点，3892个面。
在进行算法实现中发现，影响裁减算法的因素很多，我们主要对视点单元大小和遮挡板的数量进行分析。
2．1 视点单元大小对裁减结果的影响
我们分别对视点单元大小为 500、300、100、50、1进行测试得到如表 1所示的结果。根据表 1和图7可以看出，视点单元越小 ，就会裁减越多的面，因为随着视点单元的缩小，扩展投影就越接近透视投影。而视点单元越小，划分视点单元和计算遮挡裁减的工作量也越大。
2．2 遮挡板数量对裁减结果的影响
根据视点单元大小和遮挡板数量对裁减结果的影响，将以上两个因素分别取不同的值，观察对裁减结果的影响，如表3所示。
2.3 其他因素的影响
在算法中，还有其他因素会影响到裁减结果以及运行时间。例如，包围盒类型的选择，采用沿坐标轴方向的包围盒(aabb)或方向包围盒 obb；包围盒树的叶子的大小以及遮挡图和深度图的大小同样会影响裁减结果。但在试验中，我们将上面的因素作统一的规定，例如场景划分采用 obb包围盒，包围盒叶子 的大小设为 1o，遮挡图或深度图的分辨率设为256×256。
3 结 论
在可见性裁减算法中，采用层次遮挡图与层次深度图进行重叠测试和深度测试时，可以加快测试速度，减少运行时间。通过对影响算法的两个主要因素：视点单元大小和遮挡板数量进行分析，得出视点单元越小，视点单元上的顶点就越集中，遮挡板的扩展投影范围就越大，越接近单个视点的透视投影，这样遮挡效果就越好，但是视点单元越小，预处理所需的时间越多，这样不利于场景的实时性。
随着遮挡板数量的增加，裁减比例开始急速下降，然后趋于稳定，但是运行时间也会随着遮挡板数量的增加而成倍增加。
参考 文献
[1]sutherland i e，sproull r f，schumaeher r a．a characterization of ten hidden-surface algorithms[j]．computing surveys，1974，6(1)：1 —55．
[2]张毅彬．虚拟现实引擎中的入口生成与路径规划[d]．杭州：浙江大学。2002．
[3]王章野，陆艳青，彭群生．大规模场景的消隐技术[j]． 计算 机工程与应用 ，2001，9：8—12．
[4]satyan coorg，seth teller．real—time occlusion culling for models with large occluders[j]．in michael cohen and david zehzer，editors，1997 sympostum on interactive 3d graphics，page 83-90． acm siggraph ，april 1997．
[5]fr6do durand，george drettakis，jo／~lle thollot，and claude puech． conservative visibility preprocessing using extended．projeetions[c]． in kurt akeley，editor，siggraph 2000，computer graphics proceed· ings，annual conference series，acm press／acm siggraph／addison w esley longman，2000：239—248．
[6]zhang hansong，dinesh manocha，thomas hudson，et a1．visibilityculling using hierarchical occlusionmaps[c]．inturnerwhitted，editor，siggraph 97 conference proceedings，annual conference sedes．acm siggraph．addisoh wesley，august 1997：77—88．
