第二章光栅图形学 27消隐 用计算机生成三维物体的真实图形,是计算机图形学研究的重要内容。真实图形在仿真模拟、几何造型、广告影 视、指挥控制和科学计算的可视化等许多领域都有广泛应用。在用显示设备描述物体的图形时,必须把三维信息经 过某种投影变换,在二维的显示表面上绘制出来。由于投影变换失去了深度信息,往往导致图形的二义性(如图1 所示)。要消除二义性,就必须在绘制时消除被遮挡的不可见的线或面,习惯上称作消除隐藏线和隐藏面,或简称 为消隐。经过消隐得到的投影图称为物体的真实图形 图2.7.1长方体线框投影图的二义性 图2.7.2线框图图2.7.3消隐图 图2.7.4真实感图形 271消隐的分类 消隐的对象是三维物体。三维体的表示主要有边界表示和CSG表示等。最简单的表示方式是用表面上的平面多边 形表示。如物体的表面是曲面,则将曲面用多个平面多边形近似。消隐结果与观察物体有关,也与视点有关。 1.按消隐对象分类 (a)线消隐 消隐对象是物体上的边,消除的是物体上不可见的边。 (b)面消隐 消隐对象是物体上的面,消除的是物体上不可见的面 2. Southerland根据消隐空间的不同,将消隐算法分为三类 (a)物体空间的消隐算法(光线投射、 Roberts 将场景中每一个面与其他每个面比较,求出所有点、边、面遮挡关系。 (b)图像空间的消隐算法(亿-bufr、扫描线、 warnock) 对屏幕上每个象素进行判断,决定哪个多边形在该象素可见 (c)物体空间和图像空间的消隐算法(画家算法) 在物体空间中预先计算面的可见性优先级,再在图像空间中生成消隐图。 27.2消除隐藏线 1.对造型的要求 在线框显示模型中,用边界线表示有界平面,用边界线及若干参数曲线表示参数曲面,所以待显示的所有实 体均为线。但线不可能对线有遮挡关系,只有面或体才有可能对线形成遮挡。故消隐算法要求造型系统中有
第二章 光栅图形学 2.7 消隐 用计算机生成三维物体的真实图形，是计算机图形学研究的重要内容。真实图形在仿真模拟、几何造型、广告影 视、指挥控制和科学计算的可视化等许多领域都有广泛应用。在用显示设备描述物体的图形时，必须把三维信息经 过某种投影变换，在二维的显示表面上绘制出来。由于投影变换失去了深度信息，往往导致图形的二义性（如图 1 所示）。要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，或简称 为消隐。经过消隐得到的投影图称为物体的真实图形。 图 2.7.1 长方体线框投影图的二义性 图 2.7.2 线框图 图 2.7.3 消隐图 图 2.7.4 真实感图形 2.7.1 消隐的分类 消隐的对象是三维物体。三维体的表示主要有边界表示和 CSG 表示等。最简单的表示方式是用表面上的平面多边 形表示。如物体的表面是曲面，则将曲面用多个平面多边形近似。 消隐结果与观察物体有关，也与视点有关。 1. 按消隐对象分类 (a)线消隐 消隐对象是物体上的边，消除的是物体上不可见的边。 (b)面消隐 消隐对象是物体上的面，消除的是物体上不可见的面。 2. Southerland 根据消隐空间的不同，将消隐算法分为三类： (a)物体空间的消隐算法 （光线投射、Roberts） 将场景中每一个面与其他每个面比较，求出所有点、边、面遮挡关系。 (b)图像空间的消隐算法 (Z－buffer、扫描线、warnock) 对屏幕上每个象素进行判断，决定哪个多边形在该象素可见。 (c)物体空间和图像空间的消隐算法 (画家算法) 在物体空间中预先计算面的可见性优先级，再在图像空间中生成消隐图。 2.7.2 消除隐藏线 1. 对造型的要求 在线框显示模型中，用边界线表示有界平面，用边界线及若干参数曲线表示参数曲面，所以待显示的所有实 体均为线。但线不可能对线有遮挡关系，只有面或体才有可能对线形成遮挡。故消隐算法要求造型系统中有
面的信息,最好有体的信息。正则形体的消隐可利用其面的法向量,这样比一般情况快的多。 2.坐标变换 为运算方便,一般通过平移、旋转、透视等各种坐标变换,将视点变换到Z轴的正无穷大处,视线方向变为Z 轴的负方向。变换后,坐标Z值反映了相应点到视点的距离,可以作为判断遮挡的依据。另外,对视锥以外 的物体应先行虑掉,以减少不必要的运算。 3.最基本的运算 线消隐中,最基本的运算为:判断面对线的遮挡关系。体也要分解为面,再判断面与线的遮挡关系。在遮挡 判断中,要反复地进行线线、线面之间的求交运算。 图2.7.5遮挡关系 平面对直线段的遮挡判断算法 (1)若线段的两端点及视点在给定平面的同侧,线段不被给定平面遮挡,转7 (2)若线段的投影与平面投影的包围盒无交,线段不被给定平面遮挡,转7 (3)求直线与相应无穷平面的交。若无交点,转4。否则,交点在线段内部或外部。若交点在线段内部,交点将线 分成两段,与视点同侧的一段不被遮挡,另一段在视点异侧,转4再判:若交点在线段外部,转4。 (4)求所剩线段的投影与平面边界投影的所有交点,并根据交点在原直线参数方程中的参数值求出Z值(即深度)。 无交点,转5 (5)以上所求得的各交点将线段的投影分成若干段,求出第一段中点。 (6)若第一段中点在平面的投影内,则相应的段被遮挡,否则不被遮挡:其他段的遮挡关系可依次交替取值进行判 (7)结束。 图2.7.6视点与线段同侧 图2.7.7包围盒不交 图2.7.8分段交替取值 1.线消隐算法 基本数据结构 面表(存放参与消隐的面)+线表(存放待显示的线) 算法
面的信息，最好有体的信息。正则形体的消隐可利用其面的法向量，这样比一般情况快的多。 2. 坐标变换 为运算方便，一般通过平移、旋转、透视等各种坐标变换，将视点变换到 Z 轴的正无穷大处，视线方向变为 Z 轴的负方向。变换后，坐标 Z 值反映了相应点到视点的距离，可以作为判断遮挡的依据。另外，对视锥以外 的物体应先行虑掉，以减少不必要的运算。 3. 最基本的运算 线消隐中，最基本的运算为：判断面对线的遮挡关系。体也要分解为面，再判断面与线的遮挡关系。在遮挡 判断中，要反复地进行线线、线面之间的求交运算。 图 2.7.5 遮挡关系 平面对直线段的遮挡判断算法 (1)若线段的两端点及视点在给定平面的同侧，线段不被给定平面遮挡，转 7 (2)若线段的投影与平面投影的包围盒无交，线段不被给定平面遮挡，转 7 (3)求直线与相应无穷平面的交。若无交点，转 4。否则，交点在线段内部或外部。若交点在线段内部，交点将线 段分成两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转 4 再判；若交点在线段外部，转 4。 (4)求所剩线段的投影与平面边界投影的所有交点，并根据交点在原直线参数方程中的参数值求出 Z 值(即深度)。 若无交点，转 5。 (5)以上所求得的各交点将线段的投影分成若干段，求出第一段中点。 (6)若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判 断。 (7)结束。 图 2.7.6 视点与线段同侧 图 2.7.7 包围盒不交 图 2.7.8 分段交替取值 1. 线消隐算法 • 基本数据结构 面表(存放参与消隐的面) ＋ 线表(存放待显示的线) • 算法
HiddenLineRemove O 坐标变换 for(对每个面F for(F的每一条边E)将二元组<E,少压入堆栈 While(栈不空) <E,j=栈顶 for(j!=j的每一个面F) f(E被F全部遮挡) 将E清空; break;} if(E被F1部分遮挡) 从E中将被遮挡的部分裁掉 if(E1被分成若干段) 取其中的一段作为当前段 将其它段及相应的j压栈 if(E1段不为空) 显示E 如果消隐对象有N条棱,当N很大时,用两两求交的方法这个工作量是很大的0(N2)。为了提高算 法的效率,需要设法减少求交的工作量。设Ⅴ为由视点出发的观察向量,N为某多边形面的法向量。若 VN0,称该多边形为后向面。若VN0,称该多边形为前向面。如下图中的JEAF、HCBG和 DEABC所 在的面均为后向面。后向面总是看不见的,不会仅由于后向面的遮挡,而使别的棱成为不可见的。因 此可以把这些后向面全部去掉,这并不影响消隐结果。 D 图2.7.9(a)前向面(b)后向面(c)多面体的隐藏线消除 2.7.3消除隐藏面 在使用光栅图形显示器绘制物体的真实图形时,必须解决消除隐藏面的问题。这方面已有许多实用
HiddenLineRemove() { 坐标变换； for(对每个面 Fj) for(Fj的每一条边 Ei) 将二元组< Ei ,j>压入堆栈 While(栈不空) { < Ei ,j0> = 栈顶； for(j!= j0的每一个面 Fj) { if( Ei 被 Fj 全部遮挡) { 将 Ei 清空； break; } if( Ei 被 Fj 部分遮挡) { 从 Ei 中将被遮挡的部分裁掉； if(Ei 被分成若干段) { 取其中的一段作为当前段； 将其它段及相应的 j 压栈 } } } if(Ei 段不为空) 显示 Ei ; } } 如果消隐对象有 N 条棱，当 N 很大时，用两两求交的方法这个工作量是很大的 O（N 2）。为了提高算 法的效率，需要设法减少求交的工作量。设 V 为由视点出发的观察向量，N 为某多边形面的法向量。若 V·N>0，称该多边形为后向面。若 V·N<0，称该多边形为前向面。如下图中的 JEAF、HCBG 和 DEABC 所 在的面均为后向面。后向面总是看不见的，不会仅由于后向面的遮挡，而使别的棱成为不可见的。因 此可以把这些后向面全部去掉，这并不影响消隐结果。 图 2.7.9 (a)前向面 (b)后向面 (c)多面体的隐藏线消除 2.7.3 消除隐藏面 在使用光栅图形显示器绘制物体的真实图形时，必须解决消除隐藏面的问题。这方面已有许多实用
算法,下面介绍几种常用算法 27.31画家算法 画家算法的原理是:先把屏幕置成背景色,再把物体的各个面按其离视点的远近进行排序,离视点 远者在表头,离视点近者在表尾,排序结果存在一张深度优先级表中。然后按照从表头到表尾的顺序 逐个绘制各个面。由于后显示的图形取代先显示的画面,而后显示的图形所代表的面离视点更近,所 以由远及近的绘制各面,就相当于消除隐藏面。这与油画作家作画的过程类似,先画远景,再画中景 最后画近景。由于这个原因,该算法习惯上称为画家算法或列表优先算法 下面给出了一种建立深度优先级表方法。先可根据每个多边形顶点z坐标的极小值Zmin的大小把多 边形作一初步的排序。设Zmin最小的多边形为P,它暂时成为优先级最低的一个多边形。把多边形序 列中其它多边形记为Q。现在先来确定P和其它多边形Q的关系。Zmin(P)<Zmin(Q)若Zmax(P)<Zmin(Q), 则P肯定不能遮挡Q。如果对某一多边形Q有Zmax(P)>Zmin(Q),则必须作进一步的检查。这种检查分 以下五项(如图 abcde所示): b.P和Q在oxy平面上投影的包围盒在x方向上不相交 c.P和Q在oxy平面上投影的包围盒在y方向上不相交 dP和Q在oxy平面上的投影不相交 e.P的各项点均在Q的远离视点的一侧 f.Q的各顶点均在P的靠近视点的一侧 y 图2.7.10P不遮挡Q的各种情况(ab,c,d,e)及互相遮挡f 上面的五项只要有一项成立,P就不遮挡Q。如果所有测试失败,就必须对两个多边形在XY平面上 的投影作求交运算。计算时不必具体求出重叠部分,在交点处进行深度比较,只要能判断出前后顺序 即可。若遇到多边形相交或循环重叠的情况(如图f),还必须在相交处分割多边形,然后进行判断。 画家算法原理简单。其关键是如何对场景中的物体按深度排序。它的缺点是只能处理互不相交的面, 而且深度优先级表中面的顺序可能出错。在两个面相交,三个以上的面重叠的情形,用任何排序方法 都不能排出正确的序。这时只能把有关的面进行分割后再排序 2.73.22缓冲区( Z-Buffer)算法 画家算法中,深度排序计算量大,而且排序后,还需再检查相邻的面,以确保在深度优先级表中前 者在前,后者在后。若遇到多边形相交,或多边形循环重叠的情形,还必须分割多边形。为了避免这 些复杂的运算,人们发明了Z缓冲区(Z- Buffer算法。在这个算法里,不仅需要有帧缓存来存放每个 象素的颜色值,还需要一个深度缓存来存放每个象素的深度值
算法，下面介绍几种常用算法。 2.7.3.1 画家算法 画家算法的原理是：先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序，离视点 远者在表头，离视点近者在表尾，排序结果存在一张深度优先级表中。然后按照从表头到表尾的顺序 逐个绘制各个面。由于后显示的图形取代先显示的画面，而后显示的图形所代表的面离视点更近，所 以由远及近的绘制各面，就相当于消除隐藏面。这与油画作家作画的过程类似，先画远景，再画中景， 最后画近景。由于这个原因，该算法习惯上称为画家算法或列表优先算法。 下面给出了一种建立深度优先级表方法。先可根据每个多边形顶点 z 坐标的极小值 Zmin 的大小把多 边形作一初步的排序。设 Zmin 最小的多边形为 P，它暂时成为优先级最低的一个多边形。把多边形序 列中其它多边形记为 Q。现在先来确定 P 和其它多边形 Q 的关系。Zmin(P)<Zmin(Q)若 Zmax(P)<Zmin(Q)， 则 P 肯定不能遮挡 Q。如果对某一多边形 Q 有 Zmax(P)>Zmin(Q)，则必须作进一步的检查。这种检查分 以下五项（如图 abcde 所示）： b. P 和 Q 在 oxy 平面上投影的包围盒在 x 方向上不相交 c. P 和 Q 在 oxy 平面上投影的包围盒在 y 方向上不相交 d. P 和 Q 在 oxy 平面上的投影不相交 e. P 的各顶点均在 Q 的远离视点的一侧 f. Q 的各顶点均在 P 的靠近视点的一侧 图 2.7.10 P 不遮挡 Q 的各种情况(ab,c,d,e) 及互相遮挡 f 上面的五项只要有一项成立，P 就不遮挡 Q。如果所有测试失败，就必须对两个多边形在 XY 平面上 的投影作求交运算。计算时不必具体求出重叠部分，在交点处进行深度比较，只要能判断出前后顺序 即可。若遇到多边形相交或循环重叠的情况（如图 f），还必须在相交处分割多边形，然后进行判断。 画家算法原理简单。其关键是如何对场景中的物体按深度排序。它的缺点是只能处理互不相交的面， 而且深度优先级表中面的顺序可能出错。在两个面相交，三个以上的面重叠的情形，用任何排序方法 都不能排出正确的序。这时只能把有关的面进行分割后再排序。 2.7.3.2 Z 缓冲区(Z-Buffer)算法 画家算法中，深度排序计算量大，而且排序后，还需再检查相邻的面，以确保在深度优先级表中前 者在前，后者在后。若遇到多边形相交，或多边形循环重叠的情形，还必须分割多边形。为了避免这 些复杂的运算，人们发明了 Z 缓冲区(Z-Buffer)算法。在这个算法里，不仅需要有帧缓存来存放每个 象素的颜色值，还需要一个深度缓存来存放每个象素的深度值
屏幕 帧缓冲器 Z缓冲器 ◆◆◆◆◆ ◆◆◆◆◆◆ ◆◆◆◆◆◆◆ 每个单元存放对应 每个单元存放对应 象素的颜色值 象素的深度值 图2.7.11Z缓冲区示意图 Z缓冲器中每个单元的值是对应象素点所反映对象的z坐标值。Z缓冲器中每个单元的初值取成z 的极小值,帧缓冲器每个单元的初值可放对应背景颜色的值。图形消隐的过程就是给帧缓冲器和Z缓 冲器中相应单元填值的过程。在把显示对象的每个面上每一点的属性(颜色或灰度)值填入帧缓冲器 相应单元前,要把这点的z坐标值和z缓冲器中相应单元的值进行比较。只有前者大于后者时才改变 帧缓冲器的那一单元的值,同时z缓冲器中相应单元的值也要改成这点的z坐标值。如果这点的z坐 标值小于z缓冲器中的值,则说明对应象素已经显示了对象上一个点的属性,该点要比考虑的点更接 近观察点。对显示对象的每个面上的每个点都做了上述处理后,便可得到消除了隐藏面的图。 Z- Buffer算法() 帧缓存全置为背景色 深度缓存全置为最小Z值 for(每一个多边形) 扫描转换该多边形 for(该多边形所覆盖的每个象素(x,y)) 计算该多边形在该象素的深度值Z(x,y); if(Z(x,y)大于Z缓存在(x,y)的值) (把Z(x,y)存入Z缓存中(x,y)处 把多边形在(x,y)处的颜色值存入帧缓存的(x,y)处 Z- Buffer算法在象素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。这种取代方法 实现起来远比总体排序灵活简单,有利于硬件实现。然而Z- -Buffer算法存在缺点:占用空间大,没有 利用图形的相关性与连续性。Z- -Buffer算法以算法简单著称,但也以占空间大而闻名。一般认为, Z- Buffer算法需要开一个与图象大小相等的缓存数组ZB,实际上,可以改进算法,只用一个深度缓存 变量zb 多面体消隐的改进深度缓存算法 z-BufferO 帧缓存全置为背景色 //扫描整个屏幕 for(屏幕上的每个象素(i,j)) 深度缓存变量zb置最小值 Minvalue
图 2.7.11 Z 缓冲区示意图 Z 缓冲器中每个单元的值是对应象素点所反映对象的 z 坐标值。Z 缓冲器中每个单元的初值取成 z 的极小值，帧缓冲器每个单元的初值可放对应背景颜色的值。图形消隐的过程就是给帧缓冲器和 Z 缓 冲器中相应单元填值的过程。在把显示对象的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器 相应单元前，要把这点的 z 坐标值和 z 缓冲器中相应单元的值进行比较。只有前者大于后者时才改变 帧缓冲器的那一单元的值，同时 z 缓冲器中相应单元的值也要改成这点的 z 坐标值。如果这点的 z 坐 标值小于 z 缓冲器中的值，则说明对应象素已经显示了对象上一个点的属性，该点要比考虑的点更接 近观察点。对显示对象的每个面上的每个点都做了上述处理后，便可得到消除了隐藏面的图。 Z-Buffer 算法（） { 帧缓存全置为背景色 深度缓存全置为最小 Z 值 for(每一个多边形) { 扫描转换该多边形 for(该多边形所覆盖的每个象素(x,y) ) { 计算该多边形在该象素的深度值 Z(x,y); if(Z(x,y)大于 Z 缓存在(x,y)的值) { 把 Z(x,y)存入 Z 缓存中(x,y)处 把多边形在(x,y)处的颜色值存入帧缓存的(x,y)处 } } } } Z-Buffer 算法在象素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。这种取代方法 实现起来远比总体排序灵活简单，有利于硬件实现。然而 Z-Buffer 算法存在缺点：占用空间大，没有 利用图形的相关性与连续性。 Z-Buffer 算法以算法简单著称，但也以占空间大而闻名。一般认为， Z-Buffer 算法需要开一个与图象大小相等的缓存数组 ZB，实际上，可以改进算法，只用一个深度缓存 变量 zb。 多面体消隐的改进深度缓存算法 z-Buffer() { 帧缓存全置为背景色 //扫描整个屏幕 for(屏幕上的每个象素(i,j)) { 深度缓存变量 zb 置最小值 MinValue