常用的消隐算法及总结数学092邹继瑶 090064摘要：用计算机生成三维物体的真实图形是计算机图形学研究的重要内容。
真实图形在仿真模拟、几何造型、广告影视、指挥控制和科学计算的可视化等许多领域都有广泛应用。
经过消隐得到的投影图称为物体的真实图形。
较常用的消隐算法有画家算法、Z-Buffer算法及其它一些改进算法。
消隐算法从算法基本思想、算法描述和算法步骤等方面对画家算法、Z-Buffer算法和其它改进算法进行了分析,并得出了它们相关的特点。
关键词：计算机图形学消隐景物空间消隐图像空间消隐算法引言：近年来，产生真实的虚拟环境是计算机图形学孜孜以求的目标。
在虚拟对象或场景的创建中要用到许多综合处理过程，每一种都非常令人感兴趣也非常重要。
计算机辅助设计、科学可视化、模拟训练、医疗成像、娱乐、广告等等，所有的这些，都要依赖于当今最前沿的计算机图形技术。
伴随着计算机硬件、软件的飞速发展，计算机图形学技术也得到了质的飞跃。
特别是面向对象技术和多媒体技术取得的成功，使得图形学成为计算机软件业中一个重要的分支。
而程序设计方法、数据库系统和人工智能等新技术渗入到计算机图形学领域，又为计算机图形学提供了更加宽阔的发展空间和强劲动力。
计算机图形学是研究通过计算机将数据转换成图形，并在专用显示设备上显示的原理、方法和技术的学科。
主要介绍了计算机图形系统的基本知识，图形生成与显示的算法，图形的表示与图形的数据结构，图形的几何变换与投影变换，图形的裁剪技术，图形消隐处理，真实感图形的生成等内容。
面消隐作为图形学中一个分支是本文的一个重要的研究内容。
一．消隐的基本概念由于屏幕上的一些图元被另一些图元挡住所造成的。
例如，当需要描绘一个由多边形面组成的三维物体时，那么它的一部分必然要被挡住，要在屏幕上显示的必须是可见的东西。
打个比方，对于一个立方体，无论从哪个方向进行透视处理，最多只能看到其中的三个面。
这样，就要想出一种方法来决定哪些面是所能看到的。
如果使用从屏幕到世界的视处理方法，那么很自然的就能保证只有图元上正确的部分才显示在屏幕上。
在这种视处理中，可见性在屏幕的每一个像素上进行判断。
从人眼发出一条射线，穿过一个给定的像素，那么首先与这条射线相交的表面在这一个像素上就是可见的。
从这个表面反射的光线能够进入我们的眼睛。
用计算机生成三维物体的真实图形，是计算机图形学研究的重要内容。
真实图形在仿真模拟、几何造型、广告影视、指挥控制和科学计算的可视化。
等许多领域都有广泛应用。
在用显示设备描述物体的图形时，必须把三维信息经过某种投影变换，在二维的显示表面上绘制出来。
由于投影变换失去了深度信息，往往导致图形的二义性。
要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，或简称为消隐。
经过消隐得到的投影图称为物体的真实图形。
消隐算法是把线框图变成实体图必要的算法。
通过看相关的报道知道，地面勘测卫星，气象卫星等要不断的向地面的工作站发送图片资料来帮助技术人员进行研究。
而那个量是非常庞大的，因而接收到图像时往往是已经过压缩和消隐后得到的图片。
由于最普通的图元就是多边形，所以讨论的许多技术都是只针对多边形模型的。
由此将重点讨论用于多边形地形、体素模型的一些技术，为了能够更深入的了解消隐有关的基本知识，做了如下的一些介绍和研究。
二．常用的消隐算法消隐算法按其实现方式可分为图像空间消隐算法和景物空间消隐算法两大类。
图像空间（屏幕坐标系）消隐算法以屏幕像素为采样单位，确定投影于每一像素的可见景物表面区域，并将其颜色作为该像素的显示颜色。
景物空间消隐算法直接在景物空间（观察坐标系）中确定视点不可见的表面区域，并将它们表达成同原表面一致的数据结构。
图像空间消隐算法有深度缓存器算法、A缓存器算法、区间扫描线算法等；景物空间消隐算法则包含BSP算法、多边形区域排序算法等；介于二者之间的有深度排序算法、区域细分算法、光线投射算法等。
（1）深度缓存器算法深度缓存器算法最早由Catmull提出，是一种典型的，也是最简单的图像空间面消隐算法，但其所需的存储容量较大，不仅要有帧缓存器来存放每个像素的颜色值，还需要有深度缓存器来存放画面上每一像素对应的可见表面采样点的深度值。
由于通常选择z轴的负向为观察方向，因此算法沿着观察系统的z轴来计算各景物距离观察平面的深度，故该算法也称为Z-buffer算法。
Z-buffer算法的原理是：先将待处理的景物表面上的采样点变换到图像空间（屏幕坐标系），计算其深度值，并根据采样点在屏幕上的投影位置，将其深度值与已存贮在Z缓存器中相应像素处的原可见点的深度值进行比较。
如果新的采样点的深度（z值）大于原可见点的深度，表明新的采样点遮住了原可见点，则用该采样点处的颜色值更新帧缓存器中相应像素的颜色值，同时用其深度值更新Z缓存器中的深度值；否则，不做更改。
深度缓存器算法最大的优点是算法原理简单，不过算法的复杂度为O(N)，N为物体表面采样点的数目。
另一优点是便于硬件实现。
现在许多中高档的图形工作站上都配置有硬件实现的Z-buffer算法，以便于图形的快速生成和实时显示。
深度缓存器算法的缺点是占用太多的存储单元，假定屏幕分辨率为1024×768，则需要2×1024×768个存储单元，即使每一存储单元只占一个字节，也需要超过100万个字节。
不过，若采用扫描线Z-buffer算法时，可以每次只对一条扫描线进行处理，这样深度缓存器所需的存储量仅为1×屏幕水平显示分辨率×深度存储位数，当然需要增加边表和多边形表的存储量。
深度缓存器算法的其它缺点还有它在实现反走样、透明和半透明等效果方面的困难。
同时，在处理透明或半透明效果时，深度缓存器算法在每个像素点处只能找到一个可见面，即它无法处理多个多边形的累计颜色值。
（2）区间扫描线算法每一条扫描线被物体中多边形的边界在屏幕的投影分割成若干相互邻接的子区间，每一子区间上只有一个可见面，如图9-3。
因此，只要在每一个子区间内任一点处，在投影于该处的各多边形中找出在该处深度（z值）最大的多边形（最近的多边形），则这一多边形为该扫描线子区间内的唯一可见面，可按这一多边形的光照属性和几何位置计算确定子区间内各像素的显示颜色。
这就是所谓的区间扫描线算法。
区间扫描线算法也是一种图像空间消隐算法。
区间扫描线算法原理算法首先为各多边形建立一张边表和一张多边形表。
边表需包含的内容有：进行消隐的场景中所有线段的端点坐标、线段斜率的倒数、指向多边形表中对应多边形的指针。
多边形表需包含的内容有：各多边形的平面方程系数、各多边形的颜色值、指向边表的指针。
在消隐算法执行的过程中，从边表和多边形表中提取信息，构造一张有效边表。
有效边表中包含与当前扫描线相交的边，按x的升序进行排列。
排列后这些边将扫描线分成一个个的子区间[xi, xi+1]，如图9-2，可将扫描线上的子区间分为三种类型：图扫描线子区间（1）子区间为空，如图中的子区间1和5。
（2）子区间中只包含一个多边形，如图(a)中的2和4，图(b) 中的2和4，图(c) 中的4。
（3）子区间中包含多个多边形，如图(a)中的3，图(b) 中的3，图(c)中的2和3。
若这些多边形在子区间内不相互贯穿，如图(a)中的3，则仅需计算这些多边形在子区间任一端点处的深度，深度（z值）大的平面为可见面。
若两多边形交于子区间一端点但不贯穿，如图(b) 中的3，则只要计算它们在区间另一端点处的深度，深度大者为可见面。
为了使算法能处理互相贯穿的多边形，如图(c)，扫描线上的分割点不仅应包含各多边形的边与扫描线的交点，而且应包含这些贯穿边界与扫描线的交点，如图(c)中增加了一个分割点，从而形成了子区间2和3，否则算法不能处理多边形相互贯穿的情形。
当然还有另外一种难以处理的情形就是循环遮挡（实际上贯穿也可看作循环遮挡的一种），若存在这种情况，则需将多边形进行划分以消除循环遮挡。
在形成了子区间后，只要取其投影覆盖该子区间的各多边形，计算它们在区间端点处采样点的z值（深度），深度最大的平面为可见面。
于是，需要在有效边表的每个分割点对应的数据结点中增加一类信息：为每个多边形建立一个标志位，以表示扫描线上每一子区间所对应的覆盖多边形。
（3）深度排序算法排序算法（Depth-Sorting Method）是介于图像空间消隐算法和景物空间消隐算法之间的一种算法，它在景物空间中预先计算物体上各多边形可见性的优先级，然后再在图像空间中产生消隐图。
深度排序算法可分为两步进行：（1）将多边形按深度进行排序：距视点近的优先级高，距视点远的优先级低。
（2）由优先级低的多边形开始，逐个对多边形进行扫描转换。
其中步骤（1）是关键。
假定沿z轴的负向进行观察，因而z值大的距观察者近，多边形A上各点z坐标的最小值和最大值分别记作zmin(A)、zmax(A)。
将多边形按深度进行排序的算法步骤为：（1）对场景中的所有多边形按zmin(多边形)由小到大的顺序存入一个先进先出队列中，记为M，同时初始化一空的先进先出队列N（N中存放已确定优先级的多边形，优先级低的先进，扫描转换时也先处理）。
（2）若M中的多边形个数为1，则将M中的多边形直接加入到N中，算法结束；否则按先进先出的原则从M中取出第一个多边形A进行处理（A是M中zmin值最小的多边形），同时将A从M中删除。
（3）从当前M中任意选择一多边形B，对A与B进行判别。
①若对M中任意的B均有zmin(B)>zmax(A)，则说明A是M中所有多边形中深度最深的，它与其它多边形在深度方向上无任何重叠，不会遮挡别的多边形。
将A按先进先出原则加入N中，转（2）；否则继续。
②否则说明存在某一多边形B，A与B有深度重叠，则需要依次进行以下判别：a. 判别多边形A和B在xoy平面上投影的包围盒有无重叠，若无重叠，则A、B在队列中的顺序无关紧要，将A按先进先出原则加入N中，转（2）；否则继续。
b. 判别平面A是否完全位于B上A与B的重叠平面之后，若是，将A按先进先出原则加入N中，转（2）；否则继续。
c. 判别B上平面A与B的重叠平面是否完全位于A之前，若是，将A按先进先出原则加入N中，转（2）；否则继续。
d. 判别多边形A和B在xoy平面上的投影有无重叠，若无重叠，则A、B在队列中的顺序无关紧要，将A按先进先出原则加入N中，转（2）；否则在A与B投影的重叠区域中任取一点，分别计算出A、B在该点处的z值，若A的z值小，说明A距视点远，优先级低，将A按先进先出原则加入N中，转（2）；若A的z值大，则交换A和B的关系，即将B看作是当前处理对象，转（3）进行M中其它多边形的判别。
排序完成后得到队列N，由于N是按优先级由低到高顺序排列的多边形先进先出队列，因此只需从N中逐个取出多边形进行扫描转换即可。
