常用的消隐算法及总结

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