图形可见面算法分析

1、 图形可见面算法分析胡宁宁,周公博,贾晓娜中国矿业大学机电学院,江苏徐州(221008摘要:本文分析了近16种现有的典型可见面消隐算法的原理与特点,提出了一种算法分类的方法,比较了各类算法的执行性能及适用领域。关键词:消隐算法,图像空间,景物空间,算法分析1 引言可见面算法,在计算机图形学发展的初期被称为隐藏线、隐藏面算法。由于图形可能出现二义性,消除图形中的隐藏线、面或体,是必要的。消隐问题本身的复杂性导致许多不同的算法,其中相当多的部分是针对某些特定的应用问题而设计的。没有一种算法是十全十美的。实时模拟如飞行模拟等需要以视频速率(每秒30帧画面快速消隐;而计算机动画却采用高度真实感图形算法

2、,所生成的图像具有连续色调,能产生阴影、透明、表面纹理以及反射、折射等视觉效果。但这类算法比较慢,产生一幅图需用几分钟甚至几个小时。在算法设计上,需要在计算速度和图形细节之间进行权衡。没有一种算法可以两者兼得。随着计算机硬件速度的提高和快速算法的出现,画面中已能包含较多的图形细节,然而,无疑永远会有更多的图形细节需加以描绘。所有可见面算法都涉及到排序。一般来说,先取哪一个几何坐标进行排序对算法的效率并不重要。排序的核心是分辨体、线、面、点与观察点间几何距离的远近。按距离排序基于一个前提,即一个物体离观察点越远,它越有可能被遮挡。在确定各景物在距离和深度上的顺序后,还需对它们作横向和纵向排序,以

3、便确定一个物体实际上是否为那些距离观察点较近的物体所遮挡。可见面算法的效率很大程度上取决于排序的效率。通常利用连贯性来提高排序过程的效率。可见面算法可以依据算法实现时所在的坐标系或空间进行分类,分为景物空间、图像空间及优先级排序算法。2 典型用于景物空间的算法景物空间算法在景物被定义时所处的坐标系中实现,这种算法精度较高,通常只受限于所采用的显示设备的分辨率,生成的图形可以放大很多倍而仍然令人满意,景物空间算法特别适用于精密的工程应用领域。从理论上分析,在景物空间算法中,场景中的每一个景物都需与场景中的其他景物一一比较,其计算量将随场景中的景物数以平方律(2n增长。对象空间消隐算法以场景中的物

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

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

6、行运算,其输出结果仍为多边形。故便于用做可见线、可见面算法。可见面算法可分为四步:按深度进行预排序;用距视点最近的多边形对所有多边形进行裁剪和区域分类;删去位于离视点最近的多边形之后的其他多边形;必要时递归地进行分割。最后用深度排序消除所有不确定性。2.3 景物空间扫描线算法1和许多经典的在图像空间实现的扫描线算法不同,Sechrest 和Greenberg 针对非相交多边形提出了一种在景物空间实现的类似于扫描线算法的方法。由于在多边形场景中可见性的改变仅出现在边的交叉处或顶点处,该算法引入了Appel 算法1中可见性量化的思想,将场景沿垂直方向划分成一系列的水平带、在每一水平带中扫描线的可见

7、性不变。初始时,仅在每个物体最小y 值顶点处分割场景。算法采用了一种很精巧的数据结构,按y 进行排序并建立活化边表。在处理活化边表的过程中,初始的场景分割被不断细化,其分割位置逐渐包括所有顶点和边的交叉处。算法最后输出具有景物空间精度的可见边段,并辅以足够的信息来重建可见多边形。算法使用背面剔除法来消除自隐藏面。3 典型用于图像空间的算法图像空间算法在景物显示时所在的屏幕坐标系中实现,一旦达到屏幕的分辨率,计算就不再进行下去。通常一幅画面取10241280×个整数点,这当然还十分粗糙,图像空间算法生成的画面在放大后往往不能令人满意,例如线段端点之间可能不再衔接等。从理论上说,在图像空

8、间算法中,场景中的每一个景物必须与屏幕坐标系中的每一个像素进行比较,其计算量为nN 其中n 为场景中的景物数(体、面或边,而N 为屏幕的像素个数。一般说来,由于N n <(N 通常为6100.23.1×,景物空间算法较图像空间算法计算量小。因此,从理论上分析,大多数算法应在景物空间中实现。然而实际情况并非如此,由于在光栅扫描过程中易于利用画面的连贯性,图像空间算法实现效率往往更高。图象空间的消隐算法以窗口内的每个像素为处理单元, 算法可描述为:for (窗口内的每一个像素确定距视点最近的物体, 以该物体表面的颜色来显示像素;2 3.1 浮动水平线算法浮动水平线算法1常用于形如(

9、0,=z y x F 的曲面中,由于曲面方程的特定表现形式,算法通常在图像空间中实现。其基本思想是:采用一系列与坐标平面平行的平面(x 、y 或z 为定值去切割曲面,把三维问题转化成二维问题。如图1所示,当z 取一系列常数值时,可定义一簇平行平面。函数(0=z ,y ,x F 表示的曲面与每一平行平面的交线为一条曲线,即(z ,x f y =或(z ,y g x =其中z 为常数。一般地,浮动水平线算法的基本前提是假设曲面在每个剖面上的交线,特别是轮廓线,必须仅为x (或y 的函数。 图1 坐标常数值剖面3.2 Z 缓冲器算法Z 缓冲器算法1即深度缓存算法,该算法需要两个缓冲器:帧缓冲器用以存

10、储图像空间中每个像素的属性(光亮度;Z 缓冲器用来存储图像空间中每一可见像素相应的深度或z 坐标,它是一个独立的深度缓冲器。其基本原理是:计算准备写入帧缓冲器像素的深度即z 值,并与已存储在Z 缓冲器中该像素的原深度比较。如果新像素位于帧缓冲器上原像素的前面,则将新像素写入帧缓冲器,同时Z 缓冲器用新的z 值更新。否则,不写入也不更新。本算法的实质是对一给定的y x ,查找最大的(y x z ,值。Z 缓冲器算法简单稳定,利于硬件实现。但是,它需要一个额外的Z 缓冲器,在每个多边形占据的每个像素处都要计算深度值,计算量大,而且在处理斜直线的阶梯效应、透明与半透明效果等问题时存在较大的困难。3.

11、3 曲面分割算法曲面分割算法1是针对双三次曲面片的,递归地分割曲面,但其基本原理适用于任何曲面。算法的效率取决于曲面分割的效率。该算法可简述为:递归地将曲面分割为子曲面片直到每一子曲面片在图像空间的投影至多覆盖一个像素中心为止;决定子曲面片在像素中心处的深度;使用Z 缓冲器算法,确定该曲面片是否可见;如果该曲面片可见,则计算在此像素区域上曲面的属性并显示该像素。 3.4 A 缓冲器算法A 缓冲器算法1是Z 缓冲器算法思想的延伸,A 表示反走样、区域平均和累计缓冲器。Z 缓冲器算法的一个缺点是只能处理非透明的物体表面,而无法处理透明面片所存在的在各像素点处对多张面片进行光强度累计的问题。A 缓冲

12、器算法对深度缓冲器作了扩充,使其各单元均对应一张面片列表,这样,可考虑各像素点处多张面片对其属性值的影响,还可对物体的边界进行反走样处理。A 缓冲器可类似于深度缓冲器进行有效的组织,即沿每条扫描线判别以找出各像素点所覆盖面片。曲面片可分割为多边形网络,并用像素边界对它们进行裁剪。采用透明因子和面片覆盖度,可将所有覆盖面片对该像素点的影响取平均以计算该点的属性值。3.5 几种基于扫描线技术的算法此类算法按扫描线顺序依次处理场景,算法在图像空间中实现。它将三维的可见线、可见面问题简化为二维的问题。由视点(位于z 轴正向无穷远处和扫描线所确定的平面称为扫描平面,如图1(a所示。扫描平面与三维场景的交

13、线定义一个扫描线窗口,可见面问题就在此扫描线窗口中解决。图1(b给出了扫描平面与场景中多边形的交线。从该图可知可见面问题可简化为在扫描线的每个点上判定哪一条线段可见的问题。 图2 扫描平面扫描线Z 缓冲器算法1,作为Z 缓冲器算法的特例,是一种最简单的扫描线消隐算法。该算法中显示窗口的高为一条扫描线的高度,宽即其水平显示宽度。其帧缓冲器和Z 缓冲器所需的存储量仅为深度水平显示分辨率××1。Z 缓冲器的深度位数决定于z 的取值范围。该算法是将它记录的整屏深度数据改为只记录当前扫描线所在行的各点深度数据,在计算出一条扫描线上的所有多边形的各点深度并填充其象素值之后,才刷新行深度

14、缓存数组,以便计算下一行扫描线上对应的所有图形。这样循环处理之后,即一次性的逐行显示出整个画面上的图形。克服了深度缓存算法占用存储单元太大的不足,减少了占用的存储空间。扫描线深度缓存算法的一个主要优点是缩小了z 向深度缓存数组,便于用软件实现该算法。 区间扫描线算法1,又称间隔扫描线算法,是将一个平面分成了3种类型的间隔区间:区间为空,区间中仅含有一条线段和区间中含有多条线段。当扫描区间时,只需在此区间中显示画面的背景色;当扫描区间中仅含有一条线段时,只要显示这条线段相应多边形的颜色即可;区间中只包含一个区段,扫描区间时,按该段所在多边形的属性显示;区间中包含多个区段,则在扫描时计算该区间中各

15、区段的深度,具有最大z 值的区段为该区间中的可见段,按此区段所在的多边形属性显示。扫描线Z 缓冲器算法需要计算多边形中每个象素的深度,而区间扫描线算法可以减少计算深度的次数,并使它能适应透明或半透明有界表面的输出。区间扫描线算法的一个优点在于利用平面之间边线的相关性,分割各原有界平面,避免了深度优先级算法中多边形之间相交、交叉重叠分割处理复杂这一难题。曲面扫描线算法1是在曲面分割算法的基础上,引入扫描线技术,改进而成的,与曲面分割算法不同的是,该算法按照扫描线的次序输出结果。此算法直接从曲面的定义出发,按扫描线顺序显示双参数多项式曲面。算法过程为:通过视点和扫描线所确定的扫描平面与场景相交,由

16、此即发现在处理多边形表面和参数曲面之间的差别。对于多边形表面,所有交线均为直线段,这些直线段易于由其端点表示。对于参数曲面,扫描平面与参数曲面的交线由下式给出(t tan cons ysan w ,u y =其中w ,u 为曲面的参数,所得交线称为层面线或等高线。交线不一定是单值的。其次在同一层面上可能有多条交线。最后,求出扫描线对应的曲线后,尚需确定沿扫描线相应曲线上每点的位置即,(w ,u x x =,并计算出在此位置上曲面的深度(w ,u z z =以确定它是否可见。3.6 光线跟踪算法光线跟踪算法1,又称光线投射算法4,是将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交。如果有交点, 用深度值最大的交点(最近的所属的多边形的颜色显示相应的像素;如果没有交点, 说明没有多边形的投影覆盖此像素, 用背景色显示即可。其工作过程是:假定场景中的景物均已变换到图像空间。暂不考虑透视变换,并设视点或观察者位于