图形可见面算法分析

《图形可见面算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn图形可见面算法分析胡宁宁，周公博，贾晓娜中国矿业大学机电学院，江苏徐州(221008)E-mail：zhougongbo1985@163.com摘要：本文分析了近16种现有的典型可见面消隐算法的原理与特点，提出了一种算法分类的方法，比较了各类算法的执行性能及适用领域。关键词：消隐算法，图像空间，景物空间，算法分析1引言可见面算法，在计算机图形学发展的初期被称为隐藏线、隐藏面算法。由于图形可能出现二义性，消除图形中的隐藏线、面或体，是必要的。消隐问题本身的复杂性导致许

2、多不同的算法，其中相当多的部分是针对某些特定的应用问题而设计的。没有一种算法是十全十美的。实时模拟如飞行模拟等需要以视频速率（每秒30帧画面）快速消隐；而计算机动画却采用高度真实感图形算法，所生成的图像具有连续色调，能产生阴影、透明、表面纹理以及反射、折射等视觉效果。但这类算法比较慢，产生一幅图需用几分钟甚至几个小时。在算法设计上，需要在计算速度和图形细节之间进行权衡。没有一种算法可以两者兼得。随着计算机硬件速度的提高和快速算法的出现，画面中已能包含较多的图形细节，然而，无疑永远会有更多的图形细节需加以描绘。所

3、有可见面算法都涉及到排序。一般来说，先取哪一个几何坐标进行排序对算法的效率并不重要。排序的核心是分辨体、线、面、点与观察点间几何距离的远近。按距离排序基于一个前提，即一个物体离观察点越远，它越有可能被遮挡。在确定各景物在距离和深度上的顺序后，还需对它们作横向和纵向排序，以便确定一个物体实际上是否为那些距离观察点较近的物体所遮挡。可见面算法的效率很大程度上取决于排序的效率。通常利用连贯性来提高排序过程的效率。可见面算法可以依据算法实现时所在的坐标系或空间进行分类，分为景物空间、图像空间及优先级排序算法。2典型用于

4、景物空间的算法景物空间算法在景物被定义时所处的坐标系中实现，这种算法精度较高，通常只受限于所采用的显示设备的分辨率，生成的图形可以放大很多倍而仍然令人满意，景物空间算法特别适用于精密的工程应用领域。从理论上分析，在景物空间算法中，场景中的每一个景物都2需与场景中的其他景物一一比较，其计算量将随场景中的景物数以平方律(n)增长。对象空间消隐算法以场景中的物体为处理单元,算法可描述为:for(场景中的每一个物体)[2]{将其与场景中的其它物体比较,确定其表面的可见部分；显示该物体表面的可见部分}；2.1Robert

5、s算法[1]Roberts算法是第一个知名的可见面算法，它在景物空间中实现，数学处理严谨。该算法要求画面中所有物体都是凸的，凹体则需预先分解为凸体的组合，算法首先消除被物体自身遮挡的边和面。然后，每一物体上剩下的边再与其他物体一一比较，以确定这些边上哪些-1-http://www.paper.edu.cn部分被遮挡。显然，Roberts算法的计算量随着场景中物体数量的平方递增。另外，光栅扫描显示应用日益广泛，而光栅显示算法一般都在图像空间中实现，这使得Roberts算法大为逊色。但Roberts算法数学处理简单

6、、精确、适用性强，且可以用它说明一些重要的概念。若采用Z向优先级预排序以及简单的最大最小包围盒等方法，可使该算法的计算量几乎与景物个数呈线性增长。算法分为三部分：第一部分对每一物体进行分析，消去自隐藏面。第二部分对余下的边与所有其他的物体一一比较以确定被其他物体所遮挡的部分。第三部分确定贯穿物体之间的相贯线。假定物体为多面体，表面由棱边围成。而棱边由顶点决定，所有的顶点、棱边和表面都附属于一定的物体。2.2Weiler-Atherton算法[1]Weiler-Atherton算法基于Weiler-Atherto

7、n多边形裁剪算法。算法在景物空间中以任意给定精度进行运算，其输出结果仍为多边形。故便于用做可见线、可见面算法。可见面算法可分为四步：按深度进行预排序；用距视点最近的多边形对所有多边形进行裁剪和区域分类；删去位于离视点最近的多边形之后的其他多边形；必要时递归地进行分割。最后用深度排序消除所有不确定性。2.3景物空间扫描线算法[1]和许多经典的在图像空间实现的扫描线算法不同，Sechrest和Greenberg针对非相交多边形提出了一种在景物空间实现的类似于扫描线算法的方法。由于在多边形场景中可见性的改[1]变仅出

8、现在边的交叉处或顶点处，该算法引入了Appel算法中可见性量化的思想，将场景沿垂直方向划分成一系列的水平带、在每一水平带中扫描线的可见性不变。初始时，仅在每个物体最小y值顶点处分割场景。算法采用了一种很精巧的数据结构，按y进行排序并建立活化边表。在处理活化边表的过程中，初始的场景分割被不断细化，其分割位置逐渐包括所有顶点和边的交叉处。算法最后输出具有景物空间精度的可见边段，并辅以足够的