计算机图形学 课件 第7章 消隐处理

第7章消隐处理7.1概述7.2单个凸多面体的消隐算法7.3一般平面立体的消隐算法7.4深度存储算法7.5扫描线算法

7.1概述

用计算机绘制或显示三维物体的立体图时，描述物体的图形形式有两种：一种是用线条勾画的立体图，称为轮廓线图，如轴测图；另一种是用不同的灰度或色彩表现物体的各个表面的明暗度的图，称为真实感图(明暗图)。真实感图与实际拍摄的照片几乎没有区别。

轮廓线图或真实感图均是按投影原理绘制的。我们顺着投影方向看去，物体上有的线或面被前面部分遮挡看不见，我们把看不见的线称为隐藏线，看不见的面称为隐藏面。绘制轮廓线图时要消除隐藏线，绘制真实感图时要消除隐藏面，这就是消隐处理。不经过消隐处理的图有不确定性。例如，图7.1(a)为两长方体组成的物体，由于没有消除隐藏线，可以理解为图7.1(b)、(d)和图7.1(c)、(e)两个物体。因此，只有经过消隐处理的图形才有实际意义。

图7.1未消隐立体图的不确定性

1.消隐算法简介

目前消隐处理形成了多种算法，有如下三种分类方法：

(1)按照描述立体的图形形式分为消除隐藏线算法和消除隐藏面算法。前者适合于轮廓线图消隐，后者适合于真实感图消隐。

(2)按立体形状不同有凸多面体消隐算法、一般平面立体消隐算法、规则曲面消隐算法、自由曲面消隐算法等。浮动水平线算法是规则曲面消隐的典型算法。对于自由曲面消隐，可以将其离散为三角形、四边形平面片，然后按平面立体消隐算法处理。

(3)按照算法进行的空间又分为物空间消隐算法和像空间消隐算法。物空间消隐算法是指在物体所在的空间即世界坐标系中进行的算法，它着重分析物体之间的几何关系，确定线段和面的可见性，因此需要运用多种几何计算来实现。

像空间消隐算法是在物体成像的空间(即屏幕坐标系)中进行消隐计算的。它着眼于最终在视区中形成的图像，需要确定组成物体的各个面在图像范围内所对应的光栅像素点的可见性，算法精度与屏幕分辨率有关。计算时间与物体的复杂程度及像素点数量有关，这类算法适用于消除隐藏面。

2.消隐算法应考虑的问题

(1)排除与遮挡无关的要素。

(2)判别遮挡关系。

(3)合理组织物体的数据结构。

3.消隐算法与投影体系

消隐算法往往与投影体系有关，主要是投影面和观察方向，即投影方向的选取。如图7.2(a)、(b)所示，可将xOz坐标面作为投影面、y轴作为观察方向，此时物体的y坐标反映其深度信息，即反映物体表面距离观察者的远近。对图7.2(a)的投影体系来说，y坐标越大，物体表面距离观察者越远；而对图7.2(b)的投影体系来说，y坐标越小，物体表面距离观察者越远。如图7.2(c)所示，若将xOy坐标面作为投影面、z轴作为观察方向，此时物体的z坐标反映其深度信息，z坐标越大，物体表面距离观察者越远。使用消隐算法时，要注意算法所针对的投影体系。

图7.2用于消隐的投影体系

7.2单个凸多面体的消隐算法

1.凸多面体的表面外法线矢量与表面可见性物体经投影变换后，假设在xOz坐标面上输出投影图，此时的观察方向与y轴平行，如图7.3所示。

图7.3表面SAB的外法线矢量N

如图7.3所示，描述物体表面的顶点顺序符合外环规定，即正对表面看去，顶点逆时针排列。按照2.3节外法线矢量的定义，外法线矢量用表面中相邻两边矢量叉乘得到。例如，表面SAB的外法线矢量N为

其中，D、E、F分别是N在x、y、z轴上的分量，决定表面可见性的y分量(即E分量)为

E>0，外法线矢量N朝前倾，该表面可见(如面SAB、面SCA)，面上所有棱线可见；

E=0，外法线矢量N垂直于观察方向(如水平面、正垂面、侧平面的外法线矢量)，该表面与投影面垂直且其投影积聚为一条直线(如面ACB)；

E<0，外法线矢量N朝后倾，该表面不可见(如面SBC)。

2.凸多面体的消隐算法及数据结构

凸多面体消隐算法所用数据结构为单链三表结构。以图7.3中的三棱锥为例，其数据结构如图7.4所示。这里，增加一个消隐过程中使用的可见边表MT。

图7.4凸多面体消隐的数据结构

消隐算法的主要步骤如下：

(1)根据所绘投影图是正交投影图还是透视投影图，利用前述的正交投影变换或透视变换把处于原始位置的凸多面体的顶点表VT转化成新的顶点表PT。

(2)对每个表面执行下列操作：

①取出表面上第1、2、3个顶点，计算表面的E值；

②若E>0，则该面可见，把此面上的所有边记入可见边表MT，转(2)；若E≤0，直接转(2)。

(3)搜索MT表中的重复边，令重复边的特征值为-1。

(4)取MT表中的非重复边绘图。

7.3一般平面立体的消隐算法

1.“边面”比较算法步骤(1)计算立体各表面外法矢的E值，由E值将各表面分成潜在可见面和不可见面两种。E>0的面即朝前面称为潜在可见面，因它仍有可能被本立体的其他面或其他立体的面挡住，故称为潜在可见面；E≤0的面即朝后面及重影面称为不可见面。这一步目的是排除不可见面留下潜在可见面。

(2)在潜在可见面之间进行隐藏关系的判别与计算。我们把潜在可见面的棱边称为潜在可见棱边。

(3)求出不可见子段的并集，得到线段可见部分并输出。这种情况用于某线段与多个表面有隐藏关系，需要把该线段分别与各个表面进行比较，每次比较得到一种可见子段和不可见子段的分布情况，最后求所有不可见子线段的并集，其补集就是可见线段，然后输出。

由此可见，在整个消隐过程中，要进行大量的计算与判别。

2.算法中的主要几何计算及判别

1)棱边与面遮挡与否的检测

这种检测主要用来排除不可能有遮挡关系的对象，以减少计算工作量，加快处理速度。如图7.5所示，取一条潜在可见棱边P1P2(其坐标分别为x1、y1、z1，x2、y2、z2)与一个朝前面QRST的包围盒作比较，若满足下列条件之一，则棱边P1P2不被平面QRST遮挡：

(1)x1>xmax且x2

>xmax，即P1P2在该平面之左；

(2)x1<xmin且x2

<xmin，即P1P2在该平面之右；

(3)z1>zmax且z2>zmax，即P1P2在该平面之上；

(4)z1<zmin且z2<zmin，即P1P2在该平面之下；

(5)y1>ymax且y2>ymax，即P1P2在该平面之前。

这里，xmin、xmax、ymin、ymax、zmin、zmax分别是盒子的边界坐标。

图7.5棱边与平面的遮挡关系

2)两直线段投影的交点及深度的检测

该方法用于被测棱边被部分遮挡的检测计算。方法是检测被测棱边与朝前面的棱边投影相交时交点处的深度，即确定哪个点离观察者近。如图7.6所示，AB是被测棱边，CD为朝前面上一条棱边，两者在空间交叉，且在xOz投影面上的投影相交。首先求出投影的交点(即重影点)，然后按两直线上重影点处的y坐标(即深度)的大小来判别可见性。

图7.6两直线重影点的深度检测

若分母为零，则两投影线段平行或重合，无交点。若λ∈[0，1]，且μ∈[0，1]，则两投影线段的交点在两线段范围内，为有效交点，说明有重影点；否则两线段投影不相交，即无重影点。线段AB上的重影点P、线段CD上的重影点Q的y坐标由直线参数方程的y分量求得，即

若yQ>yP，被测棱边上P点为被遮点，令遮挡关系参数RMB=λ；若yQ<yP，被测棱边上P点为可见点，令遮挡关系系数RMB=-λ。

由于讨论对象为一般平面立体，因此它可能有凹多边形表面和有内孔的表面。图7.7是一被测棱边P1P2穿越有内孔的表面F的情况，被测棱边P1P2与表面F有四个重影点，其位置参数分别为

特殊地，棱边端点的位置参数λ为0或1。

图7.7棱边穿越表面的情况

3)直线段的投影包含在平面投影之内时的深度检测

用于被测棱边被完全遮挡，或被测棱边靠前完全未遮挡，或被测棱边穿越孔洞时的检测计算。此时，被测棱边与朝前面可能不相交(如完全在朝前面之后或之前)，也可能相交(如棱边穿越表面孔洞的情况)。

图7.8中P1P2为被测棱边，它与朝前面F的棱边投影没有有效交点，且与面F不相交。这时通过P1或P2作平行于y轴的直线l1或l2，如直线l1的方程为

图7.8无有效交点时的深度检测

4)点与平面图形投影包含性检测

设朝前面在xOz投影面上的投影为F′，被测棱边在该投影面的投影为P′1P′2，如图7.9所示。从P′1P′2各子段(图中7段)的中点沿z轴向下引直线，求出引线与F′面的边线的有效交点(即射线与线段相交)数，若交点数为奇数且子段两端的RMB均大于0，则该子段为不可见；若交点数为偶数(含0)或交点数为奇数但子段两端的RMB均小于0，则该子段为可见。

图7.9点与平面投影包含性检测

进行包含性检测时，要正确处理重交点，以免判断出错。所谓重交点，是指引线与平面图形的顶点相交，产生两个交点。处理重交点的方法是：平面图形各边线段的xmin、xmax与引线的xP坐标如果满足不等式

则引线与平面图形的顶点在相交时计为一个交点，否则不计为交点。图7.10表示采用这种重交点处理方法的几种情况。

图7.10重交点的判断处理

5)不可见子线段的求并集运算

如图7.11所示，假设一条被测棱边投影与第一个朝前面棱边投影的有效交点位置为λ11、λ12、λ13、λ14，其不可见子段经包含性检测后定为

λ11λ12及λ13λ14(图中画剖面线的两段)。该棱边投影与第二个、第三个朝前面棱边投影的有效交点位置及不可见子段也表示在图中。通过求棱边与这三个面的不可见子段的并集，得到λ2λ3及λ4λ5为不可见子段，其补集λ1λ2、λ3λ4、λ5λ6为可见子段。这样，一条被检测棱边经过前面四步的计算最终得到它的可见子段，将可见部分绘制出来。对所有朝前面的棱边均进行这样的处理，从而绘制出一般平面物体消隐后的立体图。

图7.11不可见子段求并集

7.4深度存储算法

假定屏幕视区是矩形区域，矩形区域的范围为xmin≤x≤xmax，ymin≤y≤ymax，(x，y)为视区内像素点的位置坐标，均为整数。建立深度数组depth(x，y)和颜色数组intensity(x，y)，颜色由光照计算得到。设要消隐的物体是由多个平面多边形围成的，y轴方向为观察方向亦即深度方向，如图7.2(a)所示。

参见图7.12，算法的主要步骤如下：

(1)对视区内所有像素点置初值，即初始化如下：

depth(x，y)=y′max(取足够大的一个值表示深度最大值，代表离观察者最远)

intensity(x，y)=背景值

(2)把组成物体的每一个多边形表面投影到屏幕上，即在图7.2(a)所示投影体系下经过投影变换和窗口到视区的变换，利用区域像素填充的方法找出相应的投影多边形区域内的所有像素(x，y)。

3)求出该多边形每个像素在该表面上对应点处的深度值y′及颜色值。方法是先利用视区到窗口的变换(即窗口到视区的逆变换)求出与像素对应的表面上点的正交投影坐标(亦即世界坐标)x′、z′，再用表面的平面方程求出深度值y′，即

这里要指出的是，对于正交投影，取原物体的表面求y′；对于透视投影，按4.8.2节取透视变换体的表面求y′。

(4)对该多边形的每个像素：若其y′<depth(x，y)，则说明该点离观察者又近了，有可能可见，应重新记录这个像素点的深度值及颜色值，即令

若其y′≥depth(x，y)，则说明此点又远离了观察者，肯定不可见，保持depth(x，y)和intensity(x，y)不变。

(5)所有的多边形表面都处理完后，颜色数组intensity(x，y)中存储了物体最靠近观察者的表面的颜色信息，即消隐后的结果，向帧缓冲存储器输出即可得到消隐后的立体图像。图7.12深度与颜色存储

7.5扫描线算法

扫描线算法以光栅扫描为前提条件，一行像素就是一条扫描线。理解扫描线算法的关键是要清楚屏幕、投影面、物体(对于透视投影则为透视变换体)三者的关系，扫描线在屏幕坐标系下，而投影面、物体在观察坐标系下，由屏幕到投影面要利用窗口到视区的逆变换。扫描线算法的投影体系如图7.2(b)所示。

扫描线算法的基本思想是：按扫描行的顺序处理一帧画面，在由过扫描线且平行于坐标平面所形成的扫描平面上解决消隐问题。当处理了全部的扫描线后，可见的图形元素用光照计算的颜色描绘出来，并消除不可见图形元素。典型的扫描线算法有扫描线间隔连贯性算法和扫描线z缓冲区算法，后者是前者算法和上节深度存储算法的结合。这里介绍扫描线间隔连贯性算法。该算法的主要步骤如下：

(1)求出扫描线与各投影多边形的交线。

屏幕上的每一个投影多边形均可以由一组扫描线段表示。如图7.13所示，扫描线m同时与三个多边形F1、F2和F3相交，其中多边形F1有两条扫描线段S11和S12，多边形F2有扫描线段S21，多边形F3有扫描线段S31。从图中看出，S21与S31有重叠部分。

图7.13扫描线与多边形相交

(2)确定采样间隔的可见性。连续可见的扫描线段间隔称为采样间隔。采样间隔的确定可采用以下准则：

①采样间隔上没有任何多边形时，采样间隔用背景色显示。

②采样间隔上只有一个多边形(如图7.13中的S11、S12)时，采样间隔用多边形在该