图形消隐技术

2.4.1 图形消隐的基本概念

当选择不同的视点看物体时，由于物体表面之间的遮挡关系，所以不能看到物体上所有的线和面。三维立体的所有部分在计算机输出时均被投影到投影平面上并显示出来，若不对其进行处理会影响到图形的立体感。而且这种图形表示的形体往往也是不确定的，即具有二义性或多义性。如图2-16a所示，无法从该线图来判断它是图2-16b还是图2-16c。

图2-16　图形表达的二义性

如果多个物体在一起，则问题更为复杂。如图2-17a所示，无法确定图中两个长方体的前后遮掩关系，很难判定是图2-17b还是图2-17c。

图2-17　两个长方体的相互遮掩关系

以上两个例子表明，要使显示的图形具有真实的立体感，避免因二义性而造成的错觉，需要在显示图形时消除因物体自身遮挡或物体间相互遮挡而无法看见的棱线。如果物体的表面信息要显示出来，如明暗效应、色彩等，则还需要在显示时消除被其他物体所遮挡的面。

当沿着投影线观察一个三维立体时，由于物体自身某些表面或其他物体的遮挡，造成某些线或面被遮挡，这些被遮挡的线称为隐藏线，被遮挡的面被称为隐藏面。将这些隐藏线或隐藏面消除的过程就称为消隐。在消隐过程中，首先要决定显示对象的哪些部分是可见的，哪些部分是为自身或其他物体所遮挡而不可见的，即找出消隐线和消隐面，然后再消除这些不可见部分，只显示可见的线和面，所显示的图形没有多义性。查找、确定并消除隐藏线和面的技术就称为消隐技术。

2.4.2 消隐算法中的基本测试方法

消除隐藏线、隐藏面的算法是将一个或多个三维物体模型转换成二维可见图形，并在屏幕上显示。对不同的显示对象和显示要求会有不同的消隐算法与之相适应。各种消隐算法的策略方法各有特点，但都是以一些基本的测试方法为基础的。一种算法中往往会包含一种甚至多种基本测试方法。下面介绍消隐算法中常用的几种基本测试方法。

1）重叠测试

重叠测试是检查两个多边形是否重叠，若不重叠则说明两个多边形互不遮挡。这种测试也称为最大最小测试或边界盒测试，它提供了一种判断多边形是否重叠的快速方法。其基本原理：找到每个多边形的极值（最大和最小的x、y值），然后用一个矩形去外接每个多边形（图2-18）。接着检查在x和y方向上任意两个矩形是否相交，若不相交，则相应的多边形不重叠（图2-19a）。设两个多边形为A和B，其顶点坐标满足下面四个不等式之一，则两个四边形不可能重叠。

而如果上述四个不等式均不满足，则这两个多边形有可能重叠。图2-19b所示的两个多边形，尽管它们的外接矩形相互重叠，但它们自身并没有重叠。此时将一个多边形的每一条边与另一个多边形的每条边比较（图2-19d），来测试它们是否相交，从而判别两个多边形是否重叠。若两个多边形确有重叠关系（图2-19c），则通过两线段求交的算法来计算其交点。

图2-18　多边形的外接矩形

图2-19　重叠测试

2）包含性测试

对于不满足重叠测试的两个多边形，除了因多边形边框相交而产生相互遮蔽外，还可能因为一个多边形包容在另一个多边形内部而产生相互遮蔽。检验一个多边形是否包含在另一个多边形内部，需要逐个检验多边形顶点是否包含在另一个多边形内部。包含性测试就是在检查一个给顶点是否位于给定的多边形或多面体内。

对于凸多边形，计算某点的包含性时只需将该点的x和y坐标带入多边形每一条边的直线方程，按计算结果判断：若该点在每条边的同一侧，则可判断该点是被凸多边形包围的。

对于非凸多边形，可以用两种方法来检验点与多边形的包含性关系，即射线交点数算法和夹角求和算法。

（1）射线交点数算法。检验时从待测试的点引出一条射线，该射线与多边形棱边相交。如果交点数是奇数，则该点在多边形内（如图2-20a中的P1点）；如果交点个数为偶数，则该点在多边形外（如图2-20a中的P2点）。如果多边形的一条边位于射线上或射线过多边形的顶点，则需要进行特殊处理，以保证结论的一致性。若引出的射线恰好通过多边形的一条边（P 3点的情况），则记为相交两次（图2-20b）；若两条边在射线的两侧（P4点的情况），则记为相交一次；若两条边在射线的同侧（P 5点的情况），则记为相交两次或零次。因而，可以判断P 3、P 4在多边形内，而P 5在多边形外。当遇到这些特殊情况时，也可改变射线的方向，按上述方法重新判断。

图2-20　射线交点数算法

图2-21　夹角求和算法

（2）夹角求和算法。夹角求和算法如图2-21所示。首先将多边形定义为有向边，逆时针为正，顺时针为负。然后由被测试点P1或P2与多边形每条边的两端点构成三角形，求被测试点与多边形各个边对应的中心角θ，如果构成的三角形的边相对于被测点为逆时针方向，则θ为正值；若构成的三角形的边相对于被测点为顺时针方向，则θ为负值。然后根据被测点与每条边构成的三角形中心角的总和∑θ来判别测试点是否为多边形所包含。当∑θ＝±2π时，则被测试点在多边形的内部；当∑θ＝0时，则被测试点在多边形的外部。

3）深度测试

深度测试是用来测定一个物体遮挡另外物体的基本方法。深度测试方法常用的是优先级测试法。

如图2-22a所示，设投影面为xOy平面，P12是空间矩形F 1和三角形F 2的正投影的重影点。将P 12的x、y坐标代入平面F 1和F 2的方程中，分别求出z1和z2。若z1＞z2，P 1为可见点，矩形F 1比三角形F 2的优先级高；若z1＜z2，P 2为可见点，三角形F 2比矩形F 1的优先级高。

深度测试方法有时会出现异常情况。如图2-22b所示，当两个多边形循环遮挡时，仅从一点的比较不能判断两个面在整体上哪个更靠近观察者，需要将其中一个多边形分成两个多边形（如图2-22b中的虚线），再使用上述方法分别判别。

4）可见性测试

可见性测试主要用来判别物体自身各部分中哪些地方是没有被其自身的其他部分遮挡，即可见的；哪些部分是被其自身的其他部分遮挡，即不可见的。

如图2-23所示，无论物体的外表面是平面还是曲面，只要知道它的几何表述，便可求出其外法矢N。对于凸多面体，物体表面外法矢指向观察者方向的面是可见的，否则是不可见的。定义由观察点C至物体方向的视线矢量为S，则可以通过计算物体表面某点的外法矢N和视线矢量S的点积来判别该点是否可见：

图2-22　深度测试

图2-23　可见性测试

N·S＝｜N｜·｜S｜cosθ

外法矢N指向物体的外部。θ为N和S的夹角，当N指向视点方向时其积为正，即为可见面。若物体是含有凹性表面的物体，则在满足法线检验的可见面之间还可能发生相互遮蔽，还需做进一步的消隐检验和判别。但是，进一步的消隐检验和判别只需对上述可见面进行。

2.4.3 常用的消隐算法

经过上述测试方法，可以判别两个物体或物体自身各部分之间是否存在重叠或遮挡关系。如果不存在重叠或遮挡关系，则无须进行消隐处理，否则需要进行消隐处理，即在图形的显示过程中，判别哪个物体被遮挡而不显示，哪个物体不被遮挡而显示出来。

消隐算法可分为两大类：物空间算法和像空间算法。物空间算法是利用物体间的几何关系来判断物体的隐藏与可见部分。这种算法利用计算机硬件的浮点精度来完成几何计算，因而计算精度高，不受显示器分辨率的影响。但对于复杂图形的消隐，运算量大，运算效率低。像空间算法在显示图形的屏幕坐标系中实现，针对形体的图形，确定光栅显示器哪些像素可见。该算法是以显示器分辨率相适应的精度来进行的，尽管算法不够精确，但对于复杂图形的消隐，运算效率极高。通常，大多数隐藏面消除算法用像空间算法，而大多数隐藏线消除算法用物空间算法。下面介绍几种常用的消隐算法。

1）区域子分割算法

区域子分割算法是一种循环细分算法，其基本思想是：把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单，可以显示为止。首先，该算法把初始窗口作为屏幕坐标系的矩形，将场景中的多边形投影到窗口内。若窗口内没有物体，则按背景色显示；若窗口内含有两个以上的面，则把窗口等分成四个子窗口。对每一个小窗口再做上述同样的处理，这样反复地进行下去。如果到某个时刻，窗口仅有像素那么大，而窗口内仍有两个以上的面，这时不必再分割，只取窗口每最近的可见面的颜色或所有可见面的平均颜色作为该像素的值，如图2-24所示。

这个算法是通过将图像递归地细分为子图像来解决隐藏面问题。整个屏幕称为窗口，细分是一个递归的四等分过程，每一次将矩形的窗口等分为四个相等的小矩形，其中每个小矩形也称为窗口。每一次细分都要判断显示的多边形和窗口的关系，这种关系有以下几种类型。

图2-24　区域子分割过程

①多边形环绕窗口：如图2-25a所示，多边形完全环绕着窗口。

②多边形与窗口相交：如图2-25b所示，多边形部分落在窗口内。

③窗口环绕多边形：如图2-25c所示，多边形完全落在窗口内。

④多边形窗口分离：如图2-25d所示，多边形与窗口在任何方向上均无重叠。

图2-25　多边形与窗口之间的关系

当窗口与每一个多边形的关系确定以后，在以下情况下，窗口足够简单，可以直接显示。

①所有多边形都与窗口分离，这时只需将窗口内所有的像素填上背景色。

②只有一个多边形和窗口相交，或这个多边形包含在窗口内，这时先对窗口内每一像素填上背景色，再对窗口内的多边形部分用扫描算法填充。

③存在一个或多个多边形，但其中离观察者最近的多边形包围了窗口，此时将整个窗口填上该多边形的颜色。

2）z向缓冲区算法

z向缓冲区算法也称为z向深度缓冲区算法或深度缓冲区算法，它是所有图像空间消隐算法中原理最简单的一种。这种算法中需要两个缓冲区，一个用来存储每一像素点亮度或色彩的帧缓冲区，还有一个用来存储每一像素点所显示对象深度的缓冲区，称为z向缓冲区或深度缓冲区。在z向缓冲区可以对每一个像素点的z值排序，并用最小的z值初始化z缓冲区；而在帧缓冲区中，用背景像素值进行初始化。帧缓冲区和z缓冲区用像素坐标（x，y）来进行索引。

z向缓冲区算法过程如下：对场景中每个多边形，找到多边形投影到屏幕上时位于多边形内或边界上所有像素的坐标（x，y）。对每个像素，在其坐标（x，y）处计算多边形的深度z，并与z缓冲区相应单元的现行值比较，如果z大于z缓冲区的现行值，则该多边形比其他早已存于像素中的多边形更靠近观察者。在这种情况下，用z值更新z缓冲区的对应单元，同时将（x，y）处多边形的明暗值写入帧缓冲区对应的该屏幕像素的单元中。当所有的多边形被处理完后，帧缓冲区中保留的是已消隐的最终结果。

3）扫描线算法

扫描线算法是图形消隐中经常使用的方法，它的特点是在图像空间中按扫描线从上到下的顺序来处理所显示的对象，通过每一行扫描线与各物体在屏幕上投影之间的关系来确定该行的有关显示信息。最常用的扫描线算法是z向缓冲器扫描线算法，如图2-26所示。

z向缓冲器扫描线算法是z向缓冲区算法的一个特例。z向缓冲器扫描线算法工作于高度只有一条扫描线的显示窗口中，故只有一行的深度缓冲区，而其宽度就是水平显示宽度，其深度缓冲区和帧缓冲区所需的存储量仅为1×水平显示分辨率×深度位数，而深度缓冲区的深度位数取决于z的取值范围。

对于每一条扫描线，帧缓冲区取背景属性作为初始值，深度缓冲区的初始值置为足够小的z值。然后求出这条扫描线与画面中每一个多边形的二维投影之间的交点，这些交点是成对出现的，而且是多边形某两条边与扫描平面交点的投影。在逐个考察扫描线上一对交点之间的像素时，将每一像素处的深度与深度缓冲区中该位置上的原存储值进行比较。若当前像素深度大于原有值，则多边形在此位置的显示属性写入帧缓冲区，同时更新深度缓冲区的原存储深度值。这样逐步处理完所有多边形，帧存储器中的内容即为画面在此扫描线位置上的消隐结果。

图2-26　z向缓冲器扫描线算法

思考与练习

1.简述在几何造型系统中，坐标系的种类及其关系。

2.简述二维图形变换的基本原理和种类。

3.简述三维几何变换的作用及其与二维几何变换的差异。

4.将顶点分别为（0，0）、（0，1）、（1，1）、（1，0）的单位正方形变换成顶点分别为（a，b）、（c，b＋h）、（c，d＋h）、（a，d）的平行四边形（其中，c＞a，d＞b）。试推导其变换矩阵。

5.投影中心为点（0，0，1），求△ABC的透视投影，已知A（2，0，－1）、B（0，0，－1）、C（0，2，－1）。

6.用点P 0（0，1）、P 1（1，1）、P 2（1，0）作为特征多边形顶点，构造一条Bezier曲线，写出它的方程并作图。

7.为什么要进行图形裁剪和消隐？

8.常用的消隐算法有哪些，并简述其原理。