几种面消隐算法的研究与比较.doc

引言
消隐(HiddenSurfaceRemoval)是在一定观察方向下消除不可见的线和面。有时也称为可见性测试。虽然各种消隐算法在可见性测试和不可见面消除方法上区别不大．但这些消隐方法有时还可以一起被统称为不可见面的消除．简称消隐。在三维造型技术、真实感图形的显示、虑拟场景的显示、以及在地形．地图的绘制中．消隐都起到至关重要的作用。所以研究和实现消隐算法，并根据场景的复杂度和各个不同应用领域的场景来提高消隐算法的速度是很有必要的，它对整个三维图形显示．真实感图形的显示以及各种地形地貌图形的显示是很有意义的。

1面消隐算法的分类
就目前研究出的面消隐算法，按照它们对消隐算法加速的方法不同可分为两类：
一类是致力于消隐方法的研究：
(1)现有的消隐算法研究。现有的常用的几种面消隐算法主要有：Z-buffer算法、扫描线算法、画家算法、BSP树算法等，其主要区别在于它们消隐空间不同、可见面测试方法和不可见消除方法不同，故它们所适用的范围也不同。本文将在第三部分从每种算法本身的特点、消隐空间、排序效率和对场景的限制上对这几种消隐算法来分析和比较。 (2)由于消隐算法不同，它们适用的场景类型和复杂度也不同，所以有一些专门用于针对地形、地图的绘制、凸多边体消隐、复杂形体消隐、对某一种形体表示的场景的消隐、对曲面消隐等的算法研究。 (3)研究新的消隐方法或用不同方法对已有算法改进来提高消隐速度．如树结构的消隐算法、改进的扫描线算法、BSP树法在辐射度显示中的应用、BSP树法加入到层次遮挡图(HOM)算法、BSP树法结合Imagecache(Sprite)算法等．可以在不同程度的提高图形绘制效率。对于BSP树加入到其它算法中可提高其它算法效率，本文也将在第三部分进行比较。
另一类是致力于减少视域中的待处理的景物面片数,来达到加速消隐过程的目的。硬件Z-buffer算法是目前最为常用的实时图形绘制算法，尽管其线性复杂度为O(N)(N为面片数)，但该算法由于不考虑景物的空间连贯性，需逐一绘制景物面片而不管它是否隐藏。因而，对高度复杂的场景，硬件Z-buffer算法仍难以达到实时。解决这一个问题的关键是减少复杂场景中需实时绘制的景物面片数N。
而减少视域中的待处理面片数目前有两种途径： (1)基于空间连贯性的快速消隐算法。这种算法并不简化场景几何，而是充分利用景物空间、图象空间和时间域上的可见性和不可见性连贯性来剔除被遮挡的景物面片。层次遮挡图算法和层次Z—buffer算法是这类算法的典型代表。这两个算法均将景物空间组织成层次结构，并把面片的可见性计算分解为深度排序和在屏幕卜的重叠测试两个过程。算法引入深度z锥来实现快速的保守排序，而图象锥则用来加速面片的重叠测试，这两个层次结构的引入使得快速剔除不可见面成为可能．从而极大地降低了后续硬件Z-buffer算法的绘制复杂度。更进一步，时问域上可见性连贯性的使用保证了Z锥和图象锥具有一个极好的初始条件，为快速绘制提供了重要保障。由于着眼于开发不可见景物的空间连贯性，这类算法对高遮挡率的场景非常有效．但对遮挡复杂性不高的复杂场景却毫无优势，仍无法达到实时。 (2)基于层次细节的图形绘制技术。这种算法根据视觉特性．对离视点较远的景物进行几何简化，从而达到降低场景复杂性的目的．或利用其它几何方法对整个场景面片进行简化，来减少场景面片数。这种方法大大的减少了场景的复杂度．提高了绘制场景的速度，但对高度复杂的场景．经过几何简化后的场景可能仍无法实时绘制．直到九十年代中期发展起来的纹理简化技术较好地解决了这类问题。其典型代表是Shade的图象缓存(ImageCache)技术，该算法结合几何简化和基于图象的绘制技术的优点。算法首先将场景组织成一棵BSP树。漫游时，算法自动地决定BSP树中各个结点中的景物是否满足纹理简化的误差要求，若满足．则取图象缓存中对应图象作为纹理．将其映射到一空间四边形表面：来取代结点中的几何来绘制域面：否则，直接采用几何来绘制。显然，这种动态图象简化技术大大减低了场景的复杂性．从而提高了图形的绘制效率。但由于该算法采用从后向前的绘制方式，不能利用前述的空问不可见性连贯性来加速消隐过程。为此，郑文庭，鲍虎军等结合了层次遮挡图和图象缓存算法．提出了基于时空连贯性和几何简化技术的复杂场景快速消隐绘制算法口，可以适合对各种复杂场景的实时绘制．提高了图形绘制效率，加速了消隐过程。
2研究消隐算法的方法
2.1从消隐空间来分析
对消隐算法消隐空间的分析是对消隐算法的效率的分析的一个重要方面。因为这样可以对消隐算法进行归类，并为提高消隐算法的效率打好基础。根据消隐所在的空间分为消隐算法可以分为三大类：
物体空间法(光线投射Roberts)：物体空问是用户来定义三维形体的三维空间．即所说的世界坐标系空间。