第二章光栅图形学 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) 将二元组压入堆栈 While(栈不空) { = 栈顶； 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),则必须作进一步的检查。这种检查分 以下五项(如图 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)，则必须作进一步的检查。这种检查分 以下五项（如图 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
for(多面体上的每个多边形P) if(象素点(,j)在p的投影多边形之内) (计算R在(i,j处的深度值 depth; if( depth大于zb) I zb= depth index = k If(zb!= Minvalue)计算多边形Pa在交点(,j)处的光照颜色并显示 上面的算法要求点与多边形的包含性检测,实际上是判断一个给定的点是在一个多边形内、在多边 形外,还是在多边形边界上。可采用射线法或弧长法。 (1)射线法 由被测点P处向y=-m方向作射线,交点个数是奇数,则被测点在多边形内部,否则,在多边形外 部。若射线正好经过多边形的顶点,则采用“左开右闭”的原则来实现。即:当射线与某条边的顶点 相交时,若边在射线的左侧,交点有效,计数:若边在射线的右侧,交点无效,不计数。 (a)奇数交点(b)偶数交点 图2.7.12射线法交点计数 (a)射线与边重合(b)射线穿过交点相邻的边(c)射线在交点邻边的一侧 图2.7.13射线与顶点相交时的计数 实际上,我们只关心交点个数,没必要真正求出射线与边的交点。改进的射线与边判是否相交方法如 下:被检测的点P(x,y)向 方向作射线。对边PP按以下顺序检测。 若(yx1)且(x>x+),点在边的右侧,射线与边无交。 若(x<=x)且(x<=x1+),点在边的左侧,射线与边无交。 a(y(=yi) aNd(y (=i+1))AND
for(多面体上的每个多边形 Pk) { if(象素点(i,j)在 pk的投影多边形之内) { 计算 Pk在(i,j)处的深度值 depth; if(depth 大于 zb) { zb = depth; indexp = k; } } } If(zb != MinValue) 计算多边形 Pindexp在交点 (I,j) 处的光照颜色并显示 } } 上面的算法要求点与多边形的包含性检测，实际上是判断一个给定的点是在一个多边形内、在多边 形外，还是在多边形边界上。可采用射线法或弧长法。 （1）射线法 由被测点 P 处向 y = - 方向作射线，交点个数是奇数，则被测点在多边形内部，否则，在多边形外 部。若射线正好经过多边形的顶点，则采用“左开右闭”的原则来实现。即：当射线与某条边的顶点 相交时，若边在射线的左侧，交点有效，计数；若边在射线的右侧，交点无效，不计数。 (a)奇数交点 （b）偶数交点 图 2.7.12 射线法交点计数 （a）射线与边重合 （b）射线穿过交点相邻的边 （c）射线在交点邻边的一侧 图 2.7.13 射线与顶点相交时的计数 实际上，我们只关心交点个数，没必要真正求出射线与边的交点。改进的射线与边判是否相交方法如 下：被检测的点 P(x,y)向 y = - 方向作射线。对边 Pi Pi+1按以下顺序检测。 若(y xi ) 且(x > xi＋1 ), 点在边的右侧，射线与边无交。 若(x <= xi ) 且(x <= xi＋1 ), 点在边的左侧，射线与边无交。 若 ( (y <= yi ) AND (y <= yi＋1 ) ) AND
(((x10,则弧长代数和增加π,若f(0,则弧长代数和减少π 表2.7.1符号对变化与弧长变化的关系 (Sxi, Syi) (sxH+l, S, +1) 弧长变化 象限变化 ++ +) π/2 (++) ±丌 π/2
( ( (xi 0，则弧长代数和增加 ，若 f<0，则弧长代数和减少 表 2.7.1 符号对变化与弧长变化的关系 (sxi , syi) (sxi+! , syI+1) 弧长变化 象限变化 (+ +) (+ + ) 0 I → I (+ +) (- + ) /2 I → II (+ +) (- - ) I → III (+ +) (+ - ) - /2 I → IV (- +) (+ + ) - /2 II → I (- +) (- + ) 0 II → II (- +) (- - ) /2 II → III
±丌 l→Ⅳ ±丌 III-I n2 (-) IⅣ (+-) (++) h2 ⅣV→I ±丌 ⅣV→ll ⅣV→Ⅲ ⅣV→Ⅳ 计算多边形Rk在点(i,j)处的深度 ax+b+z+a=0设多边形Pk的平面方程为 若C≠0,则把(I,j)代入方程,就可得深度值 ai+bi+d depth- 若c=0,则说明多边形Ⅳ的法向与z轴垂直,Ⅳ在X0Y面上的投影为一条直线。在 Zbuffer消隐算法 中可以不考虑这种多边形。 273.3扫描线 Z-buffer算法 对Z- buffer算法,如利用相关性提高点与多边形的包含性测试和深度计算的速度,就得到扫描线 Z- buffer算法。 算法的主要思想 在处理当前扫描线时,开一个一维数组作为当前扫描线的Z- uffer e首先找出与当前扫描线相关的 多边形,以及每个多边形中相关的边对。对每一个边对之间的小区间上的各象素,计算深度,并与 Z- buffer中的值比较,找出各象素处可见平面,计算颜色,写帧缓存。对深度计算,采用増量算法。 2.数据结构 多边形Y表。实际上是一个指针数组。将所有多边形存在多边形Y表中,根据多边形顶点中最小的 y坐标,插入多边形Y表中的相应位置。多边形Y表中只保存多边形的序号和其顶点的最大y坐标。根 据序号可以从定义多边形的数据结构中取多边形信息:多边形所在面的方程f=ax+by+cz+d的系数 a,b,C,d、多边形的边、顶点的坐标、颜色等 5|∧ 4∧ 3 PⅠYmax囚 01234567 图2.7.16待消隐对象与多边形y表 活化多边形表AP:与当前扫描线相交的多边形存在APT中,APT是一个动态的链表
(- +) (+ - ) II→ IV (- -) (+ + ) III→ I (- -) (- + ) - /2 III→ II (- -) (- - ) 0 III→ III (- -) (+ - ) /2 III→ IV (+ -) (+ + ) /2 IV→ I (+ -) (- + ) IV→ II (+ -) (- - ) - /2 IV→ III (+ -) (+ - ) 0 IV→ IV 计算多边形 Pk 在点（i，j）处的深度 设多边形 Pk 的平面方程为： 若 C≠0，则把（I，j）代入方程，就可得深度值 若 c=0，则说明多边形 Pk 的法向与 z 轴垂直，Pk 在 XOY 面上的投影为一条直线。在 Zbuffer 消隐算法 中可以不考虑这种多边形。 2.7.3.3 扫描线 Z-buffer 算法 对 Z-buffer 算法，如利用相关性提高点与多边形的包含性测试和深度计算的速度，就得到扫描线 Z-buffer 算法。 1. 算法的主要思想 在处理当前扫描线时，开一个一维数组作为当前扫描线的 Z-buffer。首先找出与当前扫描线相关的 多边形，以及每个多边形中相关的边对。对每一个边对之间的小区间上的各象素，计算深度，并与 Z-buffer 中的值比较，找出各象素处可见平面，计算颜色，写帧缓存。对深度计算，采用增量算法。 2. 数据结构 多边形 Y 表。 实际上是一个指针数组。将所有多边形存在多边形 Y 表中，根据多边形顶点中最小的 y 坐标，插入多边形 Y 表中的相应位置。多边形 Y 表中只保存多边形的序号和其顶点的最大 y 坐标。根 据序号可以从定义多边形的数据结构中取多边形信息：多边形所在面的方程 f=ax+by+cz+d 的系数 a,b,c,d、多边形的边、顶点的坐标、颜色等。 图 2.7.16 待消隐对象与 多边形 y 表 活化多边形表 APT：与当前扫描线相交的多边形存在 APT 中，APT 是一个动态的链表
APP2Ymx2囚A→回YP2Y2 图2.7.17活化多边形表APT 边表ET:活化多边形表中的每一个多边形都有一个边表ET。多边形Pl的边表ET如下图所示。边表 中,存放了每条边端点中较大的y值,增量Δx,y值较小一端的x坐标和z坐标。 1[·[ max,4,x,zYma,xz人 图2.7.18边表ET 活化边对表AET。在一条扫描线上,同一多边形的相邻两条边构成一个边对。活化边表AET中存放 当前多边形中与当前扫描线相交的各边对的信息 AET→→ AET (y=2 1234567 图2.7.19边对与活化边对表AET AET的每个节点包括边对中如下信息 x1左侧边与扫描线交点的x坐标 Δx1左侧边在扫描线加1时的x坐标增量 y1m左侧边两端点中最大的y值 x右侧边与扫描线交点的x坐标 Δx右侧边在扫描线加1时的x坐标增量 ym右侧边两端点中最大的y值 Z1左侧边与扫描线交点处的多边形深度值 IP多边形序号 Δz。沿扫描线方向增加1个象素时,多边形所在平面的z坐标增量,为-a/ Δz扫描线加1时,多边形所在平面的z坐标增量,为-b/c 扫描线Z- buffer算法0 建多边形y表:对每一个多边形根据项点最小的y值,将多边形置入多边形y表 活化多边形表APT,活化边表AET初始化为空 For(每条扫描线i,i从小到大) 1.帧缓存CB置为背景色
图 2.7.17 活化多边形表 APT 边表 ET：活化多边形表中的每一个多边形都有一个边表 ET。多边形 P1 的边表 ET 如下图所示。边表 中，存放了每条边端点中较大的 y 值，增量 x，y 值较小一端的 x 坐标和 z 坐标。 图 2.7.18 边表 ET 活化边对表 AET。 在一条扫描线上，同一多边形的相邻两条边构成一个边对。活化边表 AET 中存放 当前多边形中与当前扫描线相交的各边对的信息。 图 2.7.19 边对与活化边对表 AET AET 的每个节点包括边对中如下信息: xl 左侧边与扫描线交点的 x 坐标 xl 左侧边在扫描线加 1 时的 x 坐标增量 ylmax 左侧边两端点中最大的 y 值 xr 右侧边与扫描线交点的 x 坐标 xr 右侧边在扫描线加 1 时的 x 坐标增量 yrmax 右侧边两端点中最大的 y 值 zl 左侧边与扫描线交点处的多边形深度值 IP 多边形序号 za 沿扫描线方向增加 1 个象素时，多边形所在平面的 z 坐标增量，为－a/c zb 扫描线加 1 时，多边形所在平面的 z 坐标增量，为－b/c 扫描线 Z-buffer 算法() { 建多边形 y 表；对每一个多边形根据顶点最小的 y 值，将多边形置入多边形 y 表。 活化多边形表 APT，活化边表 AET 初始化为空。 For(每条扫描线 i，i 从小到大) { 1. 帧缓存 CB 置为背景色
2.深度缓存ZB(一维数组)置为负无穷大 3.将对应扫描线i的多边形y表中的多边形加入到活化多边形表A中。 4.对新加入的多边形,生成其相应的边Y表 5.对A中每一个多边形,若其边Y表中对应扫描线Ⅰ增加了新的边,将新的边配对,加到活化边 对表AET中。 6.对AET中的每一对边: 6.1对x1〈x<x的每一个象素,按增量公式z=z+△z计算各点深度 depth e 6.2与B中的量比较, depth〉ZB(I),则令ZB(I)= depth,并计算颜色值,写帧缓存。 7.删除APT中,多边形顶点最大y坐标为I的多边形,并删除相应的边。 8.对AET中的每一个边对,作如下处理: 8.1删除y或ym已等于I的边。若一边对中只删除了其中一边,需对该多边形的边 重新配对。 8.2用增量公式计算新的x1、x和z1。用增量公式计算新的x=x+△x1、x=x1+△x2 和z1=z1+△x△Z。+△zb 734区间扫描线算法 与Z- buffer算法相比,扫描线Z- buffer算法做了两点改进。一、将整个绘图窗口内的消隐问题 分解到一条条扫描线上解决,使所需的Z缓冲器大大减少。二、计算深度值时,利用了面连贯性,只 用了一个加法。但它在每个象素处都计算深度值,进行深度比较。因此,被多个多边形覆盖的象素区 处还要进行多次计算,计算量仍然很大。区间扫描线算法克服了这一缺陷,使得在一条扫描线上每个 区间只计算一次深度值,并且不需要Z缓冲器。它是把当前扫描线与各多边形在投影平面的投影的交 点进行排序后,使扫描线分为若干子区间。因此,只要在区间任一点处找出在该处z值最大的一个面, 这个区间上的每一个象素就用这个面的颜色来显示 a/a2△a3|as/a587 图2.7.20扫描线与多边形的投影相交得到若干子区间 a1 a2 b a3 a4 a4 图2.7.21(a)两个平面在屏幕上的投影(b)无贯穿的情形(c)相互贯穿的情形 如何确定小区间的颜色可分为三种情况 7.小区间上没有任何多边形,如[a4a5,这时该小区间用背景色显示。 8.小区间上只有一个多边形,如ala2aa6这时可以对应多边形在该处的颜色显示 9.小区间上存在两个或两个以上的多边形如a6,a7,必须通过深度测试判断哪个多边形可见。若允许物体表面 相互贯穿时,还必须求出它们在扫描平面(ZX平面)的交点。用这些交点把该小区间分成更小的子区间(称 为间隔),在这些间隔上决定哪个多边形可见。如将[a2a3区间分成[a2bb,a3两个子区间。为了确定某间隔
2. 深度缓存 ZB (一维数组) 置为负无穷大。 3. 将对应扫描线 i 的多边形 y 表中的多边形加入到活化多边形表 APT 中。 4. 对新加入的多边形，生成其相应的边 Y 表。 5. 对 APT 中每一个多边形，若其边 Y 表中对应扫描线 I 增加了新的边，将新的边配对，加到活化边 对表 AET 中。 6. 对 AET 中的每一对边： 6.1 对 xl ZB(I), 则令 ZB(I) =depth，并计算颜色值， 写帧缓存。 7. 删除 APT 中，多边形顶点最大 y 坐标为 I 的多边形，并删除相应的边。 8. 对 AET 中的每一个边对，作如下处理： 8.1 删除 ylmax或 ylmax 已等于 I 的边。若一边对中只删除了其中一边，需对该多边形的边 重新配对。 8.2 用增量公式计算新的 xl 、xr 和 zl 。用增量公式计算新的 xl＝xl＋ xl、xr＝xr＋ xr 和 zl＝zl＋ xl za + zb } } 2.7.3.4 区间扫描线算法 与 Z－buffer 算法相比，扫描线 Z－buffer 算法做了两点改进。一、将整个绘图窗口内的消隐问题 分解到一条条扫描线上解决，使所需的 Z 缓冲器大大减少。二、计算深度值时，利用了面连贯性，只 用了一个加法。但它在每个象素处都计算深度值，进行深度比较。因此，被多个多边形覆盖的象素区 处还要进行多次计算，计算量仍然很大。区间扫描线算法克服了这一缺陷，使得在一条扫描线上每个 区间只计算一次深度值，并且不需要 Z 缓冲器。 它是把当前扫描线与各多边形在投影平面的投影的交 点进行排序后，使扫描线分为若干子区间。因此，只要在区间任一点处找出在该处 z 值最大的一个面， 这个区间上的每一个象素就用这个面的颜色来显示。 图 2.7.20 扫描线与多边形的投影相交得到若干子区间 图 2.7.21 (a)两个平面在屏幕上的投影 (b)无贯穿的情形 (c) 相互贯穿的情形 如何确定小区间的颜色可分为三种情况： 7. 小区间上没有任何多边形，如[a4,a5]，这时该小区间用背景色显示。 8. 小区间上只有一个多边形，如[a1,a2][a5,a6]这时可以对应多边形在该处的颜色显示。 9. 小区间上存在两个或两个以上的多边,形如[a6,a7]，必须通过深度测试判断哪个多边形可见。若允许物体表面 相互贯穿时，还必须求出它们在扫描平面（ZX 平面）的交点。用这些交点把该小区间分成更小的子区间（称 为间隔），在这些间隔上决定哪个多边形可见。如将[a2,a3]区间分成[a2,b][b,a3]两个子区间。为了确定某间隔