可见面的判定

1、XYZx1y1z1z2XpYp窗口坐标系屏幕坐标系模型坐标系世界坐标系视口窗口建建 模模显显 示示处处 理理几几 何何 变变 换换裁裁 剪剪确定可见面确定可见面光光 照照 明明投投 影影v 由于投影变换失去了深度信息，往往导致图形的二义性。由于投影变换失去了深度信息，往往导致图形的二义性。要消除二义性，就必须在绘制时消除被遮挡的不可见的线要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面或面，习惯上称作消除隐藏线和隐藏面（或可见线判定、（或可见线判定、可见面判定），可见面判定），或简称为或简称为消隐。消隐。经过消隐得到的投影图称经过消隐得到的投影图称为物体的真

2、实图形。为物体的真实图形。v按消隐对象分类按消隐对象分类 (a)线消隐线消隐 消隐对象是物体上的边，消除的是物体上不可见的边。消隐对象是物体上的边，消除的是物体上不可见的边。 (b)面消隐面消隐 消隐对象是物体上的面，消除的是物体上不可见的面。消隐对象是物体上的面，消除的是物体上不可见的面。1以构成图像的每一个以构成图像的每一个像素像素为处理单元，确定场景中为处理单元，确定场景中的所有在该像素上有投影的所有在该像素上有投影的表面，相对于观察点可的表面，相对于观察点可见的表面。适于面消隐。见的表面。适于面消隐。2以三维场景中的以三维场景中的物体对象物体对象为处理单元，在所有对象为处理单元，在所有

3、对象之间进行比较，除去完全之间进行比较，除去完全不可见的物体和物体上不不可见的物体和物体上不可见的部分可见的部分。 适于面消隐适于面消隐也适于线消隐。也适于线消隐。窗口像素视点图7.1 以像素为对象的消隐算法xz窗口平行投影y图7.2 以物体为对象的消隐算法前提：把物体看成是由一个或多个多边形（或更复杂的面片）组成前提：把物体看成是由一个或多个多边形（或更复杂的面片）组成！假定构成物体假定构成物体的面不能相互的面不能相互贯穿，也不能贯穿，也不能有循环遮挡的有循环遮挡的情况。情况。(a)(b) 贯穿和循环遮挡贯穿和循环遮挡如果构成物体的面不满足该假如果构成物体的面不满足该假定，可以把它们定，可以

4、把它们剖分剖分成互不贯成互不贯穿和不循环遮挡的情况。穿和不循环遮挡的情况。例如，用上图中的虚线便可把原来例如，用上图中的虚线便可把原来循环遮挡的三个平面，分割成不存循环遮挡的三个平面，分割成不存在循环遮挡的四个面。在循环遮挡的四个面。 提提 醒醒7.1.1347.1.27.1.3后向面消除后向面消除边界盒边界盒投影规范化投影规范化物体的边界盒是指能够包含该物体的一个简单的几何形状，物体的边界盒是指能够包含该物体的一个简单的几何形状，如矩形、圆、长方体等。如矩形、圆、长方体等。 边界盒边界盒 ：采用边界盒在消隐中的好处：采用边界盒在消隐中的好处：可避免不必要的裁剪运算，避免在物体或它们的投影之间

5、进可避免不必要的裁剪运算，避免在物体或它们的投影之间进行不必要的比较运算。行不必要的比较运算。 xyz图图7.4 两个物两个物体投影在体投影在xy平面，包围平面，包围投影的边界投影的边界盒为矩形盒为矩形注意选取适当的边界盒：注意选取适当的边界盒：不可太小，也不可太大。不可太小，也不可太大。一种简单的求边界盒的方法：一种简单的求边界盒的方法：计算多边形顶点坐标的最大值和计算多边形顶点坐标的最大值和最小值得到（即采用矩形边界盒）最小值得到（即采用矩形边界盒） A边界盒不相交边界盒不相交：在在Oxy平面投影的边界盒，两个边界盒不平面投影的边界盒，两个边界盒不 相交，所以两个多边形不相交。相交，所以两

6、个多边形不相交。 B 边界盒相交边界盒相交：相交的情况可分为相交的情况可分为两种两种，投影相交或投影，投影相交或投影 不相交。无论哪种情况都需要做进一步的不相交。无论哪种情况都需要做进一步的 处理，以判断两物体的投影是否相交。处理，以判断两物体的投影是否相交。 边界盒应用原则边界盒应用原则xyzA 不相交不相交(a)(a)边界盒和投影均重边界盒和投影均重叠叠(b)(b)边界盒重叠，投影不重叠边界盒重叠，投影不重叠 用边界盒技术判断两条直线是否相交。用边界盒技术判断两条直线是否相交。 ),(iiiyxQ举例：举例：xminxmaxymaxyminxyQ1Q6Q5Q2Q4Q3记点记点vi在在oxy

7、面上的投影为面上的投影为 。直线段直线段 的边界盒是包含该直线且的边界盒是包含该直线且边平行于坐标轴的最小矩形，这个矩边平行于坐标轴的最小矩形，这个矩形由下面四个参数确定形由下面四个参数确定 21QQ)max()max()min()min(21max21max21min21min,yyy,xxx,yyy,xxx，设两个边界盒的参数为设两个边界盒的参数为: :21,maxmaxminmin, i , y, x, yxiiii当它们满足当它们满足: : )(2max1minxx)(2max1minyy)(1max2minxx)(1max2minyy或或或或或或 表明两个边界盒不相交，则边界盒中的两

8、条直线段也不相交。表明两个边界盒不相交，则边界盒中的两条直线段也不相交。v 用球代替长方体作为边界盒可以简化判断直线同边界盒是用球代替长方体作为边界盒可以简化判断直线同边界盒是否相交的计算过程，否相交的计算过程，即若边界球的球心到直线的距离大于即若边界球的球心到直线的距离大于球的半径，那么直线与边界球不相交，球的半径，那么直线与边界球不相交，也就与球内的物体也就与球内的物体不相交。一个有效的确定边界球的方法是取球的不相交。一个有效的确定边界球的方法是取球的中心为：中心为：2minmaxxxxc2minmaxyyyc2minmaxzzzc222lllzyxRmaxmin2lxxxmaxmin2l

9、yyymaxmin2lzzz取半径为：取半径为：其中：其中：进一步简化判断进一步简化判断v 1、后向面后向面v 多面体表面多变形的法向可分为两种：一种是指向多面体多面体表面多变形的法向可分为两种：一种是指向多面体的外部的外部外法向，一种指向多面体的内部外法向，一种指向多面体的内部内法向。内法向。v 必然有一些多边形表面的必然有一些多边形表面的外法向指向与观察者相背离的方外法向指向与观察者相背离的方向向，这些多边形完全被多面体上其它，这些多边形完全被多面体上其它 多边形遮挡。这些多边形遮挡。这些被遮挡的多边形被遮挡的多边形 称为后向面。称为后向面。v 首先消除掉这些面，去除后向面的过首先消除掉这

10、些面，去除后向面的过 程称为程称为后向面消除。后向面消除。 思路：把显然不可见的面去掉，减少消隐过程中的思路：把显然不可见的面去掉，减少消隐过程中的直线求交数目直线求交数目IJFGH，FABG，HCDI，IDEJ 所在的面为前向面所在的面为前向面 JEAF，DEABC,HGBC所在的面为后向面所在的面为后向面如何判断：根据定义寻找外（或内）法向，则外法向背离观如何判断：根据定义寻找外（或内）法向，则外法向背离观 察者，或内法向指向观察者，则该面为后向面。察者，或内法向指向观察者，则该面为后向面。2、判断后向面的方法、判断后向面的方法1）首先对多边形的顶点进行排序：）首先对多边形的顶点进行排序：

11、设多边形设多边形F F的顶点为的顶点为 v1,v2,vL顶点顶点 的坐标为的坐标为 。次序要求如下排列：使观察者在多面体外沿。次序要求如下排列：使观察者在多面体外沿着着v1v2 vL走时，多边形的内部始终在它的右侧。走时，多边形的内部始终在它的右侧。iV),(iiizyx右设多边形设多边形F F的顶点为的顶点为 v1,v2,vL顶点顶点 的坐标为的坐标为 。次序如图。次序如图iV),(iiizyx2）判断后向面：判断后向面：如果如果v1,v2,vL构成凸的多边形，则向量构成凸的多边形，则向量 12 ,111Lkvvvvkka a是是F的的内法线方向，内法线方向，如果如果 a的的z分量分量0)(

12、za说明说明内法向量内法向量和和z轴正方向的夹角轴正方向的夹角大于大于9090度，度，F的的外法线方向外法线方向和和z z轴正方向的夹角小于轴正方向的夹角小于9090度，度，F为前向面。为前向面。否则，即否则，即a a的的z z分量大于分量大于0 0 即即 ，则，则F F的的内法向内法向和和z z轴正方向的夹角大于轴正方向的夹角大于9090度，度，外法线方向外法线方向和和z z轴正方向的夹角小于轴正方向的夹角小于9090度，度，F F为后向面。为后向面。2、判断后向面的方法、判断后向面的方法0)(zav1v2v3v4v5v6 ：可以看作是三角形：可以看作是三角形v1vk vk+1在平面在平面o

13、xy上投影的上投影的有向面积的二倍。有向面积的二倍。 )(21sin| |21*21npmqcitaACABACABSz)(a2、判断后向面的方法、判断后向面的方法顶点为顶点为A，B，C的三角形面积求解如下，设：的三角形面积求解如下，设：),(nmAB ),(qpAC 所以，三角形所以，三角形v1vk vk+1在平面在平面oxy上投影的上投影的有向面积为：有向面积为：1111111()()()()2kkkkxxyyxxyy恰好是恰好是是否可以这样说，求一个多边形的内法向的是否可以这样说，求一个多边形的内法向的z z分量等价于求其分量等价于求其任意一个三角形的有向面积？任意一个三角形的有向面积？

14、Zkkkkkkzzyyxxzzyyxxkji11111111z)(a a2、判断后向面的方法、判断后向面的方法111121() ()2LkkKzspv vv v 注意：如果多边形是凸的，则可只取一个三角形计算有向面积注意：如果多边形是凸的，则可只取一个三角形计算有向面积sp。如。如果多边形不是凸的，只取一个三角形计算有向面积果多边形不是凸的，只取一个三角形计算有向面积sp可能会出现错误，可能会出现错误，即即F所在的面为前向面也可能出现所在的面为前向面也可能出现sp0的情况的情况, ,因此，需按上式计算多因此，需按上式计算多边形边形F的有向面积。的有向面积。 v1v2v3v4v5v6v1v2v3

15、v4v5v6如果如果 ，则，则F所在的面为后向面。所在的面为后向面。如果如果 ，则，则F所在的面为前向面。所在的面为前向面。2、判断后向面的方法、判断后向面的方法3）可以通过计算可以通过计算多边形多边形在在Oxy平面上投影的平面上投影的有向面积有向面积判判断断F是否为后向面。是否为后向面。有向面积有向面积sp可如下计算：可如下计算：)()(21 )()(211111211111121yyxxyyxxvvvvspkkLKkkzkLKk0SP0SP 物体之间的遮挡关系与投影中心和投影方向有着密切的关系，对物体物体之间的遮挡关系与投影中心和投影方向有着密切的关系，对物体的可见性判定也和投影方式有密切

16、的关系。的可见性判定也和投影方式有密切的关系。注意：注意：垂直投影的优点：进行投影时可以忽略垂直投影的优点：进行投影时可以忽略z值，即实物的值，即实物的（x，y）即可直接做为投影后的二维平面上的坐标即可直接做为投影后的二维平面上的坐标（x，y）(x,y,z) (x,y)(x,y,z)(x,y) 所以，下面的工作就是将非垂直投影转换成垂直投影。这样可以降低所以，下面的工作就是将非垂直投影转换成垂直投影。这样可以降低算法的复杂性，提高运算速度。算法的复杂性，提高运算速度。 如何把透视投影变为垂直投影，如何把透视投影变为垂直投影，其本质是把棱台变成长方体。其本质是把棱台变成长方体。 AB) , (y

17、x),(AzAyAx投影平面投影平面由棱台到长方体的变换由棱台到长方体的变换(,)ccccxyzP把左边的棱台把左边的棱台A变换成右边长方体变换成右边长方体B。设。设 (xA,yA,zA )是棱台是棱台A中任意一点，中任意一点，它在投影平面的投影为它在投影平面的投影为 (x,y,0) ，事实上透视投影是把线段，事实上透视投影是把线段 (xA,yA,zA)和和(x,y,0)之间的点都变换成之间的点都变换成 (x,y,0)，如果能把，如果能把 (xA,yA,zA)和和(x,y,0)之间的之间的点指定一个相应的点指定一个相应的Z值，值，且该值不改变原线段上点之间的前后关系，且该值不改变原线段上点之间

18、的前后关系，就可就可把棱台把棱台A变为长方体变为长方体B，即将透视投影变换成了正投影。，即将透视投影变换成了正投影。求求A的坐标如何的坐标如何变换到变换到B的坐标，即（的坐标，即（xA,yA,zA）到（）到（xB,yB,zB）的变换）的变换), , (Bzyx),(BzByBx同一图形同一图形垂直投影不改变垂直投影不改变x，y值值投影面投影面) , (yx如果对如果对z的射影变换是线的射影变换是线性的，则不改变视见体性的，则不改变视见体内各表面的前后位置关内各表面的前后位置关系可以通过不改变视见系可以通过不改变视见体的前后平面体的前后平面 z=zf和和zzb，的前后位置关系实现，的前后位置关系

19、实现，把这两个条件代入左式，把这两个条件代入左式，得：得： ()()fcffbcbbzzzAzBzzzAzB, cfbfbAzzzBz z投影公式投影公式则只剩下则只剩下zB没有解，没有解，则按照类似于则按照类似于xB和和yB的形式来找的形式来找zB与与ZA的关系的关系()/()()/()BcAcccABcAcccAxxxxx zzzyyyyy zzz()/()AcAzAzBzza,ba,b是系数，是我们假定的，是系数，是我们假定的，则，如何求解？则，如何求解？v 判断哪个多边形是可见判断哪个多边形是可见 ： 可在两多边形共同覆盖的区域内取一点可在两多边形共同覆盖的区域内取一点（x, y），）

20、，如果投如果投影为影为垂直投影垂直投影, ,把（把（x, y）分别代入两个多边形表达式，得）分别代入两个多边形表达式，得到两个空间点到两个空间点P1(x,y,z1)和和P2(x,y,z2)，当，当z1z2时，时，P1遮挡遮挡P2，当，当z2z1时，时，P2遮挡遮挡P1； 但但如果不是垂直投影，则需根据视点或投影方向计算两个多如果不是垂直投影，则需根据视点或投影方向计算两个多边形在边形在oxy平面的投影为平面的投影为P1(x1,y1,z1) 和和P2(x2,y2,z2)总结：总结： 在非垂直投影下计算在非垂直投影下计算P1和和P2要比在垂直投影下计要比在垂直投影下计算花费的计算量大许多。算花费的

21、计算量大许多。 射影变换之后射影变换之后 7.2.17.2.2基于多边形的细分算法基于多边形的细分算法基于窗口的细分算法基于窗口的细分算法概述概述区域细分算法区域细分算法是一种是一种分而治之分而治之(Divide-Conquer)的算法，它把投影区域作为考察对象，如果很容的算法，它把投影区域作为考察对象，如果很容易确定投影区域内的多边形是否可见，便显示这易确定投影区域内的多边形是否可见，便显示这些多边形，否则将这些区域进一步细分，随着不些多边形，否则将这些区域进一步细分，随着不断细分，判断多边形的可见性将越来越简单。断细分，判断多边形的可见性将越来越简单。本节介绍基于窗口的细分算法和基于多边形

22、的细本节介绍基于窗口的细分算法和基于多边形的细分算法。分算法。基本思想基本思想子分的过程子分的过程 把物体投影到全屏幕窗口上，然后递归的将窗口把物体投影到全屏幕窗口上，然后递归的将窗口一分为一分为四，四，如果可以确定小窗口内的多边形是否可见，则显示如果可以确定小窗口内的多边形是否可见，则显示这些多边形，否则，将小窗口细分为更小的窗口，递归这些多边形，否则，将小窗口细分为更小的窗口，递归地执行上述过程。每一次把矩形的窗口等分成四个相等地执行上述过程。每一次把矩形的窗口等分成四个相等的小矩形。的小矩形。注意：分成的小矩形也称为窗口。注意：分成的小矩形也称为窗口。 具体分析关系判断具体分析关系判断

23、细分后都要对多边形和窗口就下面四种关系作判断：细分后都要对多边形和窗口就下面四种关系作判断：窗口和多边形分离窗口和多边形分离(图中情况图中情况1)1多边形和窗口相交多边形和窗口相交(图中情况图中情况2)2窗口包围了多边形窗口包围了多边形(图中情况图中情况3)3多边形包围了窗口多边形包围了窗口(图中情况图中情况4)41234 多边形和窗口的关系多边形和窗口的关系具体分析可见性判断具体分析可见性判断 对以下的三种情况，窗口中多边形的可见性容易判定，不需要再对对以下的三种情况，窗口中多边形的可见性容易判定，不需要再对窗口进行分割：窗口进行分割： 所有多边形均和窗口分离，则窗口内只需所有多边形均和窗口

24、分离，则窗口内只需显示背景色；显示背景色； 1只有一个多边形和窗口相交，或这个多边只有一个多边形和窗口相交，或这个多边形包含在窗口内。这时，先对窗口内每一形包含在窗口内。这时，先对窗口内每一像素填上背景颜色，再对窗口内多边形部像素填上背景颜色，再对窗口内多边形部分用扫描线算法填色。分用扫描线算法填色。 2一个多边形包围窗口，其他多边形和窗口一个多边形包围窗口，其他多边形和窗口分离，或有多个多边形和窗口的关系分别分离，或有多个多边形和窗口的关系分别是相交、内含或包围，但是有一个多边形是相交、内含或包围，但是有一个多边形包围窗口并且在其他多边形前面，则窗口包围窗口并且在其他多边形前面，则窗口用包围

25、多边形的颜色填充。用包围多边形的颜色填充。 3橙色橙色紫色紫色具体分析分割结束条件具体分析分割结束条件 对不满足上述三种情况的窗口，重复细分过程，并对细分后对不满足上述三种情况的窗口，重复细分过程，并对细分后的各子窗口重复做同样的处理。细分若干次后，窗口的面积的各子窗口重复做同样的处理。细分若干次后，窗口的面积就小于或等于一个像素的面积了，此时细分结束，该窗口对就小于或等于一个像素的面积了，此时细分结束，该窗口对应的像素的颜色可取成最靠近观察者的多边形的颜色。应的像素的颜色可取成最靠近观察者的多边形的颜色。 橙色橙色紫色紫色基本思想基本思想 用多边形的边界对区域作划分，其目的是尽量减少对区域用

26、多边形的边界对区域作划分，其目的是尽量减少对区域划分的次数划分的次数利用裁剪算法。利用裁剪算法。 该算法是对上节基于窗口细分算法的改进。由于算法在景该算法是对上节基于窗口细分算法的改进。由于算法在景物空间中以任意指定的精度进行运算，其输出结果仍为多物空间中以任意指定的精度进行运算，其输出结果仍为多边形，所以算法不仅可用来处理隐藏面消除，也可用来处边形，所以算法不仅可用来处理隐藏面消除，也可用来处理多面体隐藏线消除问题。理多面体隐藏线消除问题。 算法描述算法描述Step1：Step2：Step3：内部表：放入位于窗口内的部分内部表：放入位于窗口内的部分 外部表：放入位于窗口外的部分外部表：放入位

27、于窗口外的部分yx4321要消隐的多边形要消隐的多边形xyz43212i3i4i4oni为窗口内的多边形表；为窗口内的多边形表；no为窗口外的多边形表为窗口外的多边形表3o算法描述算法描述Step4：即取为窗口的那个多边形即取为窗口的那个多边形) ) yx4321要消隐的多边形要消隐的多边形xyz4321如何判断窗口是如何判断窗口是否遮挡其余的多否遮挡其余的多边形边形 求出裁减多边形也就是内部表中第一求出裁减多边形也就是内部表中第一个多边形，各顶点坐标的极小值个多边形，各顶点坐标的极小值Zmin； 求出内部多边形各顶点坐标求出内部多边形各顶点坐标z的极大值的极大值Zmaxi； 对那些满足对那些

28、满足ZminZmaxi的内部表中的的内部表中的多边形，便可认为它被裁减多边形所多边形，便可认为它被裁减多边形所遮挡；遮挡； 若某一内部多边形不满足上式，则要若某一内部多边形不满足上式，则要从该两多边形相交的区域上取一点，从该两多边形相交的区域上取一点，做和做和z轴平行的线，求出该线和两个多轴平行的线，求出该线和两个多边形所在平面的交点，根据交点的位边形所在平面的交点，根据交点的位置便可准确地确定哪一个多边形更靠置便可准确地确定哪一个多边形更靠近观察者。近观察者。如何判断窗口是如何判断窗口是否遮挡其余的多否遮挡其余的多边形边形EAzmaxzminBCDGHFxz算法描述算法描述Step5：如果内

29、部表中有某多边形如果内部表中有某多边形H比裁剪区域（多边形）更比裁剪区域（多边形）更靠近观察者，说明原来的预排序不对，此时要用多边形靠近观察者，说明原来的预排序不对，此时要用多边形H的原始多边形（即未被裁剪时的多边形）代替原来的裁剪的原始多边形（即未被裁剪时的多边形）代替原来的裁剪多边形重复上述工作。多边形重复上述工作。 yx4321要消隐的多边形要消隐的多边形xyz4321！如左图如果对顶点排序如左图如果对顶点排序的话，则的话，则1 1自然要排最自然要排最前面，首先会用前面，首先会用1 1做裁做裁剪多边形，但实际情况剪多边形，但实际情况是是2 2在在1 1的前面，所以应的前面，所以应该以该以

30、2 2做新的裁剪多边做新的裁剪多边形，重复上述工作形，重复上述工作算法描述算法描述Step6：内部表中多边形的按前后顺序排好序后，接下来是内部表中多边形的按前后顺序排好序后，接下来是对外部表对外部表中中的各多边形进行排序。对外部表中各多边形的排序和对内部表中各的各多边形进行排序。对外部表中各多边形的排序和对内部表中各多边形的处理方法相同，即把外部表中第一个多边形作为裁剪多边多边形的处理方法相同，即把外部表中第一个多边形作为裁剪多边形形(假定外部表中的多边形也是按原来的多边形次序排序假定外部表中的多边形也是按原来的多边形次序排序)，对外部，对外部表中的其它多边形作裁剪并确定遮挡关系，这一过程又形

31、成新的外表中的其它多边形作裁剪并确定遮挡关系，这一过程又形成新的外部表。裁剪过程要重复到外部表中不再有多边形为止。部表。裁剪过程要重复到外部表中不再有多边形为止。 yx4321要消隐的多边形要消隐的多边形xyz43214o 3o基本思想基本思想将能够包含整个场景的立方体，即八叉树的将能够包含整个场景的立方体，即八叉树的根结点根结点，按照，按照x，y，z三个方向中的剖面分割成八个子立方体，称为根结三个方向中的剖面分割成八个子立方体，称为根结点的点的八个子结点八个子结点。对每一个子立方体，如果它包含的表面。对每一个子立方体，如果它包含的表面片少于一个给定的值（例如片少于一个给定的值（例如3），则该

32、子立方体为八叉树），则该子立方体为八叉树的的终端结点终端结点，否则为非终端结点并将其进一步分割成八个，否则为非终端结点并将其进一步分割成八个子立方体；重复上述过程，直到每个小立方体所包含的表子立方体；重复上述过程，直到每个小立方体所包含的表面片少于一个给定的值，分割即告终止。面片少于一个给定的值，分割即告终止。 具体分析具体分析1）每一终端结点对应一个求交面片表，该表中包含的是与终端结点对）每一终端结点对应一个求交面片表，该表中包含的是与终端结点对应的立方体中所包含的景物表面片。应的立方体中所包含的景物表面片。2）八叉树由于其不相交立方体之间的规则结构，可以很方便的进行空）八叉树由于其不相交立

33、方体之间的规则结构，可以很方便的进行空间预排序，然后再根据列表优先级算法便可以很容易对平行投影给间预排序，然后再根据列表优先级算法便可以很容易对平行投影给出正确的显示顺序。出正确的显示顺序。122333314455556666777xyzv从后向前显示的八叉树排列从后向前显示的八叉树排列对从后向前排对从后向前排列算列算 法，先显示最法，先显示最远的八远的八 分体，然后分体，然后是与最是与最 远的八分远的八分 体体共享一共享一 个面的三个个面的三个相邻八相邻八 分体顺序任分体顺序任意），意）， 然后显示最然后显示最近八分近八分 体的三个相体的三个相邻八分邻八分 体（顺序任体（顺序任意），最后显意

34、），最后显示最近的八分示最近的八分体体 具体分析具体分析 对于过视点和像素的射线，根据空间网格之间的邻接关系，能很快对于过视点和像素的射线，根据空间网格之间的邻接关系，能很快地求得射线和景物的第一个交点，从而使计算量大大减少，见图地求得射线和景物的第一个交点，从而使计算量大大减少，见图7.15。具体地说，射线从起始点开始，跨越一个个它所经过的网格。具体地说，射线从起始点开始，跨越一个个它所经过的网格单元，直到遇到它与景物有交点的网格单元为止，此后射线无需再单元，直到遇到它与景物有交点的网格单元为止，此后射线无需再继续跟踪下去，从而避免了与后面景物表面的求交计算。继续跟踪下去，从而避免了与后面景

35、物表面的求交计算。对射线与对射线与景物有交点的第一个网格单元，如果射线与景物有多个交点，则需景物有交点的第一个网格单元，如果射线与景物有多个交点，则需选择离视点最近的交点。选择离视点最近的交点。 射线沿网格与表面片求交射线空间网格对屏幕上对屏幕上每一个像素点，每一个像素点，过像素中心做一条投影过像素中心做一条投影线，找到此投影线与所有多边形交点中线，找到此投影线与所有多边形交点中离观察者离观察者最近的点，最近的点，此点的属性（颜色或灰度）值即为这此点的属性（颜色或灰度）值即为这一屏幕像素点的属性值。一屏幕像素点的属性值。 基本思想：基本思想：Z缓冲器缓冲器v z缓冲器是一组缓冲器是一组存贮单元

36、存贮单元 其单元个数和屏幕上其单元个数和屏幕上像素像素的个数相同的个数相同 也和也和帧缓冲器帧缓冲器的单元个数相同，它们之间一一对应。的单元个数相同，它们之间一一对应。Z缓缓冲冲区区示示意意图图 具体实现具体实现需要两个缓冲器数组，需要两个缓冲器数组，z缓冲器数组缓冲器数组用于存储投影线与所有用于存储投影线与所有多边形交点的多边形交点的z值，值，帧缓冲器数组帧缓冲器数组用来存储像素的颜色值。用来存储像素的颜色值。分别设为分别设为Zdepth 与与Frame 对屏幕上每个点（对屏幕上每个点（x，y），令），令Zdepth xy为为z的极小的极小值，值，Frame xy为背景颜色。为背景颜色。 对

37、所有多边形做如下工作：对多边形上在像素中心有投对所有多边形做如下工作：对多边形上在像素中心有投影的每一点（影的每一点（x,y）计算其）计算其z值。若值。若zZdepth xy，则，则Zdepth xyz，并将此点属性值赋给，并将此点属性值赋给Framexy，否，否则说明此点离观察者较远，两个数组的值都不用改变。则说明此点离观察者较远，两个数组的值都不用改变。 12具体实现具体实现只有只有z坐标值坐标值大于大于z z缓冲器缓冲器时才改变时才改变帧缓帧缓冲器冲器的那一个单元的值，同时的那一个单元的值，同时z缓冲器中缓冲器中相应单元的值也要改成这点的相应单元的值也要改成这点的z坐标值。坐标值。如果这

38、点的如果这点的z坐标值小于坐标值小于z缓冲器缓冲器中相应单元的值，则说中相应单元的值，则说明对应象素已显示了物体上一个点的属性，该点比要考虑明对应象素已显示了物体上一个点的属性，该点比要考虑的点更接近观察者。这样，无论帧缓冲器或的点更接近观察者。这样，无论帧缓冲器或z z缓冲器相应缓冲器相应单元的值均不应改变。单元的值均不应改变。l 对显示物体的对显示物体的每一个面上每一个面上的的每一个点每一个点都做上述处理后，都做上述处理后，便可得到消除了隐藏面的图。便可得到消除了隐藏面的图。 Zdepth xyz1 Frame xygreenZdepth xyz2 Frame xyblue扫描线扫描线z缓

39、冲器算法缓冲器算法 将将z缓冲器的单元数置为和一条扫描线上的像素数目相同。缓冲器的单元数置为和一条扫描线上的像素数目相同。从最上面的一条扫描线开始工作，向下从最上面的一条扫描线开始工作，向下对每一条扫描线对每一条扫描线作作如下处理：如下处理： 把相应的帧缓冲器单元置成底色，把相应的帧缓冲器单元置成底色，z缓冲器中存放缓冲器中存放z的极小值。的极小值。 对每个多边形检查它在平面上的投影和当前的扫描线是否相对每个多边形检查它在平面上的投影和当前的扫描线是否相交。然后计算各重叠面片的深度值以确定离观察者最近的面交。然后计算各重叠面片的深度值以确定离观察者最近的面片。当某像素点所对应的可见面被确定后，

40、该点的颜色值置入片。当某像素点所对应的可见面被确定后，该点的颜色值置入帧缓冲器。帧缓冲器。 step1step2 扫描线算法也属于图像空间消隐算法。该算法可以看作是多边形区域填扫描线算法也属于图像空间消隐算法。该算法可以看作是多边形区域填充里介绍过的充里介绍过的边相关扫描线填充算法边相关扫描线填充算法的延伸。不同的是在的延伸。不同的是在消隐算法中处消隐算法中处理的是多个面片，理的是多个面片，而多边形填充中是对单个多边形面进行填充。而多边形填充中是对单个多边形面进行填充。 扫描线扫描线z缓冲器算法缓冲器算法 v 对每个多边形，检查它在对每个多边形，检查它在oxy平面上的平面上的投影和当前扫描线投

41、影和当前扫描线是否相交？是否相交？ 若不相交，则不考虑该多边形。若不相交，则不考虑该多边形。 如果相交，则扫描线和多边形边界的如果相交，则扫描线和多边形边界的交点是成对地交点是成对地出现出现v 对对每对交点中间的像素每对交点中间的像素计算多边形所在平面对应点的深度（计算多边形所在平面对应点的深度（即即z值值），并），并和和z缓冲器缓冲器中相应单元存放的深度值中相应单元存放的深度值进行比较进行比较。 若前者大于后者，则若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。替，帧缓冲器相应单元的内容也要换

42、成该平面的属性。v 对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形。后的图形。v 对帧缓冲器每一行的单元都填上相应内容后就得到了整个消隐后的图。对帧缓冲器每一行的单元都填上相应内容后就得到了整个消隐后的图。step2相交的判断相交的判断数据结构数据结构 与多边形扫描转换中扫描线算法数据结构和算法类似。与多边形扫描转换中扫描线算法数据结构和算法类似。 多边形多边形Y表表1/7107282 1 2 边边表（表（ET）step2 多边形所在平面方程多边形所在平面方程ax+by+cz+d=0系数系数a，b，c和和d，

43、 记录和该多边形在记录和该多边形在oxy平面上的投影相交的扫描线的条数平面上的投影相交的扫描线的条数y， 多边形的属性多边形的属性color和编号和编号IP。9-1=89-1=811-3=811-3=836 7 81110118713要消隐的物体要消隐的物体xyostep2实际上是一个实际上是一个指针数组指针数组 ，每个表的深度和显示屏幕每个表的深度和显示屏幕行数相同。行数相同。将所有多边形存在多边形将所有多边形存在多边形Y表中，根据表中，根据多边形顶点多边形顶点中中Y坐标最大值，坐标最大值，插入多边形插入多边形Y表中的相应位置，多表中的相应位置，多边形边形Y表中保存多边形的序号和其顶点的最大

44、表中保存多边形的序号和其顶点的最大y坐坐标。标。step2v 根据边两端点较大的根据边两端点较大的y坐标值决定放入边表的哪一行。坐标值决定放入边表的哪一行。边的上端点边的上端点x坐标的值坐标的值；该投影和相邻的两条扫描线交点的该投影和相邻的两条扫描线交点的x坐标的差坐标的差x；和该边在和该边在oxy平面上的投影相交的扫描线条数平面上的投影相交的扫描线条数y；该边所属多边形的编号该边所属多边形的编号IPIP。367811101198713图图7.16 7.16 要消隐的物体要消隐的物体xo1/7107282 12step2相交的判断相交的判断数据结构数据结构 活化多边形表活化多边形表1,; 3,

45、 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll活化边对表活化边对表step2v 记录在记录在oxy平面上的投影和当前考虑的扫描线相交的多边形，如：平面上的投影和当前考虑的扫描线相交的多边形，如：当扫描线对应当扫描线对应y=10或或11时，活化多边形表只有一个多边形。当时，活化多边形表只有一个多边形。当y=8时活化多边形表如图。表中的时活化多边形表如图。表中的y值值( (扫描线的条数）扫描线的条数）是已经过修改是已经过修改的。的。（由上到下扫描，故（由上到下扫描，故y=5 和和

46、y=7）367811101198713 图图 7.16 7.16 要消隐的物体要消隐的物体xo8-3=58-3=58-1=78-1=7step2v活化边对表中存放多边形边和扫描线相交的边对。活化边对表中存放多边形边和扫描线相交的边对。 例如图中例如图中y=6的扫描线上的活化边对表中有两个边对的扫描线上的活化边对表中有两个边对 一是和多边形一是和多边形在在oxy平面上的投影相交的两条边平面上的投影相交的两条边 另一是和多边形另一是和多边形投影相交的两条边。投影相交的两条边。367811101198713 图图7.16 7.16 要消隐的物体要消隐的物体xo1,; 3, 0, 7; 3, 1, 4

47、111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlllstep2xl左交点的左交点的x坐标值坐标值xl左交点所在边和两相邻扫描线交点的左交点所在边和两相邻扫描线交点的x坐标之差坐标之差yl以和左交点所在边相交的扫描线条数为初值，以以和左交点所在边相交的扫描线条数为初值，以后每处理一条扫描线减后每处理一条扫描线减1xr右交点的右交点的x坐标值坐标值xr右交点所在边和两相邻扫描线交点的右交点所在边和两相邻扫描线交点的x坐标之差坐标之差 以和右交点所在边相交的扫描线条数为以和右交点所在边相交的扫描线条数为初值，以后每

48、处理一条扫描线减初值，以后每处理一条扫描线减1yr1,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlllstep2zl左交点处多边形所在平面的深度值左交点处多边形所在平面的深度值zx沿扫描线向右走过一个象素时，多边形所在平面深度的增沿扫描线向右走过一个象素时，多边形所在平面深度的增量。对方程为量。对方程为ax+by+cz+d=0的平面来说的平面来说zx=a/c（c0）zy沿沿y y方向向下移过一根扫描线时，多边形所在平面深度的增量。方向向下移过一根扫描线时，多边形所在平面深度的增量。对方程为对方程为ax+by+cz+d=0的平面来说的平面来说zy=b/c（c0）

49、IP所在多边形的编号所在多边形的编号1,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll边对边对边对边对step2若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面方程为：面方程为： ax+by+cz+d=0则多边形面上的点（则多边形面上的点（x，y）所对应的深度值为：）所对应的深度值为：zl左交点处多边形所在平面的深度值左交点处多边形所在平面的深度值zx沿扫描线向右走过一个象素时，多边形所

50、在平面深度的增沿扫描线向右走过一个象素时，多边形所在平面深度的增量。对方程为量。对方程为ax+by+cz+d=0的平面来说的平面来说zx=a/c（c0）zy沿沿y y方向向下移过一根扫描线时，多边形所在平面深度的增量。方向向下移过一根扫描线时，多边形所在平面深度的增量。对方程为对方程为ax+by+cz+d=0的平面来说的平面来说zy=b/c（c0）step2zx沿扫描线向右走过一个像素时，多边形所在平面深度的增沿扫描线向右走过一个像素时，多边形所在平面深度的增量。对方程为量。对方程为ax+by+cz+d=0的平面来说的平面来说zx=a/c（c0）zy沿沿y y方向向下移过一根扫描线时，多边形所

51、在平面深度的增量。方向向下移过一根扫描线时，多边形所在平面深度的增量。对方程为对方程为ax+by+cz+d=0的平面来说的平面来说zy=b/c（c0）由于所有扫描线上相邻点间的水平间距为由于所有扫描线上相邻点间的水平间距为1个像素单位，扫描线行与行之间的个像素单位，扫描线行与行之间的垂直间距也为垂直间距也为1。因此可以利用这种连贯性来简化计算过程，如图所示。因此可以利用这种连贯性来简化计算过程，如图所示。step2若已计算出（若已计算出（x，y）点的深度值为）点的深度值为zi，沿，沿x方向相邻连贯点方向相邻连贯点（x+1，y）的深度值）的深度值zi+1可由下式计算：可由下式计算： 沿着沿着y方

52、向的计算应先计算出方向的计算应先计算出y坐标的范围，然后从上至下逐个处坐标的范围，然后从上至下逐个处理各个面片。由最上方的顶扫描线出发，沿多边形左边界递归计理各个面片。由最上方的顶扫描线出发，沿多边形左边界递归计算边界上各点的坐标：算边界上各点的坐标： 公式（公式（1 1）step2这里这里m为该边的斜率，沿该边的深度也可以递归计算出来，即：为该边的斜率，沿该边的深度也可以递归计算出来，即： 如果该边是一条垂直边界，则计算公式简化为：如果该边是一条垂直边界，则计算公式简化为： 公式（公式（2 2）对于每条扫描线，首先根据公式（对于每条扫描线，首先根据公式（2）计算出与其相交的多边）计算出与其相

53、交的多边形最左边的交点所对应的深度值，然后，该扫描线上所有的后形最左边的交点所对应的深度值，然后，该扫描线上所有的后续点由（续点由（1）式计算出来。）式计算出来。 v 对每一条扫描线，对每一条扫描线，检查对每个多边形检查对每个多边形的投影是否相交，如相交则交点成对的投影是否相交，如相交则交点成对出现，对出现，对每对交点中间的每个像素每对交点中间的每个像素计计算算多边形所在平面对应点的多边形所在平面对应点的深度深度（即（即z值），并值），并和和z缓冲器缓冲器中相应单元存放的中相应单元存放的深度值作比较深度值作比较，若前者大于后者，则，若前者大于后者，则z缓冲器的相应单元内容要被求得的平缓冲器的相

54、应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。容也要换成该平面的属性。 对所有的多边形都作上述处理后，帧缓冲器中这一行对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形，对帧缓冲器每一行的单的值便反应了消隐后的图形，对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图。元都填上相应内容后也就得到了整个消隐后的图。367811101198713xo多边形多边形y表表1/7107 28 2 1 2边表边表1) 建立多边形建立多边形y表和边表，初始化表和边表，初始化活化多边形和活化边对表为空活化多边形和活化

55、边对表为空2)2)以最上面的扫描线为当前扫描线。以最上面的扫描线为当前扫描线。3)3)对当前扫描线对当前扫描线y y，把帧缓冲器相应，把帧缓冲器相应行置成底色行置成底色z z缓冲器的各单元放缓冲器的各单元放z z的极小值。的极小值。算法步骤：算法步骤：多边形多边形Y Y表表 4)4) 检查检查多边形多边形y表，表，如果有新的多边形涉及当前扫描线，如果有新的多边形涉及当前扫描线，则把它放入则把它放入活化多边形表中。活化多边形表中。118 896 68 88 要消隐的物体要消隐的物体107 若有新的多边形加入活化多边形表，则要把该多边形在若有新的多边形加入活化多边形表，则要把该多边形在Oxy平面上

56、的投影和扫描线相交的平面上的投影和扫描线相交的边对加入活化边对表边对加入活化边对表。多边形Y表1/7107 28 2 1 2边表661,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll5）对边活化表中的对边活化表中的每个边对，每个边对，令令 ，对每一个满足，对每一个满足 的坐标为的坐标为 的像素从的像素从左到右左到右依次进行处依次进行处理，求深度值理，求深度值z并与并与z缓冲器的值比较。缓冲器的值比较。zx=zx+zx6）若所有扫描线都已经处理完，则算法结束，若所有扫描

57、线都已经处理完，则算法结束，否则选下一否则选下一条扫描线为当前扫描线，条扫描线为当前扫描线，转步骤转步骤3），直到所有的扫描），直到所有的扫描线都处理完。线都处理完。lxzz rlxxx),(yx从上到下，从左到右从上到下，从左到右每条扫描线处理完后，处理下一条扫描线之前，需要每条扫描线处理完后，处理下一条扫描线之前，需要进行以下处理：进行以下处理：v 1）修改边活化表，对每一边对要做如下计算）修改边活化表，对每一边对要做如下计算 1,1llrry yy y lyrylyryrxlxlz若若或或小于小于0，则相应的边要从该边对中去掉，并从，则相应的边要从该边对中去掉，并从都不小于都不小于0，则修改，则修改边表边表中找合适的边来代替。若这两条边同时结束于某一点，中找合适的边来代替。若这两条边同时结束于某一点，则去掉这一边对。若则去掉这一边对。若公式（公式（2）,rrrlllxxx xxx又由于又由于ylxllz xz z z修改后的表便是新扫描线的