《隐藏面和隐藏线的消除.ppt》由会员分享，可在线阅读，更多相关《隐藏面和隐藏线的消除.ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第8章隐藏面和隐藏线的消除隐藏面和隐藏线的消除 n隐隐藏藏面面和和隐隐藏藏线线的的消消除除是是计计算算机机图图形形学学中中的的一一个基本问题。个基本问题。n由由于于存存在在不不透透光光的的物物体体，因因此此阻阻挡挡了了来来自自某某些些物物体体部部分分的的光光线线到到达达观观察察者者，这这些些物物体体部部分分成成为隐藏部分，隐藏部分是不可见的。为隐藏部分，隐藏部分是不可见的。n为为了了使使计计算算机机生生成成的的图图能能真真实实地地反反映映这这一一情情况况，必须把隐藏的部分从图中消除。必须把隐藏的部分从图中消除。n如如果果不不把把隐隐藏藏的的线线或或面面消消除除，还还可可能能发发生生对对图图的错
2、误理解。的错误理解。图图8.1 8.1 两种理解两种理解基于图像空间的方法基于图像空间的方法以构成图像的每一个像素为处理单元，对场景中的所有表以构成图像的每一个像素为处理单元，对场景中的所有表面，确定相对于观察点是可见的表面，用该表面的颜色填面，确定相对于观察点是可见的表面，用该表面的颜色填充该像素。充该像素。该算法多用于面消隐。该算法多用于面消隐。算法的简单描述如下：算法的简单描述如下：对于图像中的每一个像素：对于图像中的每一个像素：在和投影点到像素连线相交的表面中，找到离观在和投影点到像素连线相交的表面中，找到离观察点最近的表面；察点最近的表面；用该表面上交点处的颜色填充该像素用该表面上交
3、点处的颜色填充该像素隐藏面和隐藏线的消除有两种基本的算法隐藏面和隐藏线的消除有两种基本的算法基于物体空间的方法基于物体空间的方法是以三维场景中的物体对象为处理单元，在所有对象之间进是以三维场景中的物体对象为处理单元，在所有对象之间进 行比较，除去完全不可见的物体和物体上不可见的部分。行比较，除去完全不可见的物体和物体上不可见的部分。该算法多用于线消隐，也用于面消隐。该算法多用于线消隐，也用于面消隐。算法的简单描述如下：算法的简单描述如下：对于三维场景中的每一个物体：对于三维场景中的每一个物体：判定场景中的所有可见表面；判定场景中的所有可见表面；用可见表面的颜色填充相应的像素以构成图形；用可见表
4、面的颜色填充相应的像素以构成图形；隐藏面和隐藏线的消除有两种基本的算法隐藏面和隐藏线的消除有两种基本的算法假定假定1 1：n隐藏线和隐藏面消除所讨论的对象是一个三维图形，消隐后要在隐藏线和隐藏面消除所讨论的对象是一个三维图形，消隐后要在二维空间中表示出来，因此消隐后显示的图形将和三维空间至二二维空间中表示出来，因此消隐后显示的图形将和三维空间至二维空间的投影方式有关。维空间的投影方式有关。n下面讨论消隐算法时，都假定投影平面就是下面讨论消隐算法时，都假定投影平面就是oxy平面，投影方向平面，投影方向为负为负z轴方向的垂直投影。轴方向的垂直投影。n如果不是这种情况，可对消隐的对象先作变换，变成这
5、种情况，如果不是这种情况，可对消隐的对象先作变换，变成这种情况，然后再作消隐计算。然后再作消隐计算。n在投影平面就是在投影平面就是oxyoxy平面以及投影是透视时，可用变换平面以及投影是透视时，可用变换（4.144.14）（4.164.16）式。）式。n投影是平行投影，但投影方向不是负投影是平行投影，但投影方向不是负z z轴方向，则可用变换轴方向，则可用变换（4.214.21）（4.234.23）式。）式。n如果投影平面不是如果投影平面不是oxyoxy平面，平行投影时则先要用变换平面，平行投影时则先要用变换（4.364.36）式，透视时先要用变换（）式，透视时先要用变换（4.334.33）式，
6、式（）式，式（4.334.33）中的）中的常数常数A A和和B B应满足式（应满足式（4.174.17）假定2：n本章说明的各种消隐方法都假定构成对象的不同面不能相互贯穿，见图8.1，n也不能有循环遮挡的情况，如果有这种情况，可把它们剖分成互不贯串和不循环遮挡的情况。n例如用图8.2（b）中的虚线便可把原来循环遮挡的三个平面，分割成不互相循环遮挡的四个面。图8.2 贯穿和循环遮挡8.1 8.1 多面体的隐藏线消除多面体的隐藏线消除 n设有多个互不相交的多面体，对它们的设有多个互不相交的多面体，对它们的消隐问题，和他们的显示方式有关。消隐问题，和他们的显示方式有关。n讨论隐藏线消除问题，总假定它
7、们是用讨论隐藏线消除问题，总假定它们是用线框方式来表示的。在这种方式下多面线框方式来表示的。在这种方式下多面体用棱来表示。体用棱来表示。n这时隐藏线便是某些不可见的棱或棱的这时隐藏线便是某些不可见的棱或棱的一部分。一部分。n如果能把各棱上可见和不可见部分的分如果能把各棱上可见和不可见部分的分界点找到，消隐问题也就迎刃而解了界点找到，消隐问题也就迎刃而解了。n这些分界点都是多面体的各棱在这些分界点都是多面体的各棱在oxy平平面上投影间的交点，见图面上投影间的交点，见图8.3。n这样，问题就转化成了在这样，问题就转化成了在oxy平面上求平面上求很多直线的交点的计算很多直线的交点的计算。图图8.38
8、.38.1 8.1 多面体的隐藏线消除多面体的隐藏线消除在在oxyoxy平面上求很多直线的交点的计算。平面上求很多直线的交点的计算。n如果消隐对象有如果消隐对象有N条棱，用两两求交的条棱，用两两求交的方法求所有交点的工作量为方法求所有交点的工作量为O（N2）。）。当当N很大时，这个工作量是可观的。要很大时，这个工作量是可观的。要提高算法的效率，就要设法减少求交的提高算法的效率，就要设法减少求交的工作量。工作量。n实际上交点个数远小于实际上交点个数远小于O（N2），例如），例如图图8.3的多面体有的多面体有15条边，如果不计棱条边，如果不计棱端点处的交点，棱在端点处的交点，棱在oxy平面上的投影
9、平面上的投影相互间只有相互间只有5个交点。这说明有很多棱个交点。这说明有很多棱在在oxy平面上的投影相互间并不相交。平面上的投影相互间并不相交。n问题在于如何能预先知道它们是不相交问题在于如何能预先知道它们是不相交的，从而把它们排挤在求交计算之外。的，从而把它们排挤在求交计算之外。8.1 8.1 多面体的隐藏线消除多面体的隐藏线消除减少求交计算的若干方法：减少求交计算的若干方法：n把后向面全部去掉把后向面全部去掉 n用边界盒排除不相交的线段求交。用边界盒排除不相交的线段求交。n在后向面被删除后，如果两个相邻的多在后向面被删除后，如果两个相邻的多边形的公共边都在两个多边形的凸包上，边形的公共边都
10、在两个多边形的凸包上，则这两个多边形不会发生一个遮挡另一则这两个多边形不会发生一个遮挡另一个的现象。因而在考虑一个多边形的边个的现象。因而在考虑一个多边形的边的显示时，可以不考虑另一个多边形对的显示时，可以不考虑另一个多边形对它的影响。它的影响。8.1 8.1 多面体的隐藏线消除多面体的隐藏线消除n去掉后向面去掉后向面n把内法线方向背向视点的面称为前向面，把内法线方向背向视点的面称为前向面，n如图如图8.38.3中的中的IJFGHIJFGH，FABGFABG，HCDIHCDI和和IDEJIDEJ所在所在的面均为前向面。的面均为前向面。n其余的面称为后向面，其余的面称为后向面，n例如图例如图8.
11、38.3中中JEAFJEAF和和DEABCDEABC所在的面均为后向所在的面均为后向面，面，n后向面总是看不见的，不会仅由于后向后向面总是看不见的，不会仅由于后向面的遮挡，而使别的棱成为不可见，面的遮挡，而使别的棱成为不可见，n因此可把后向面全部去掉，这不影响消因此可把后向面全部去掉，这不影响消隐结果。隐结果。8.1 8.1 多面体的隐藏线消除多面体的隐藏线消除n设多边形设多边形F的顶点为的顶点为v1,v2,vL，顶点，顶点vi的坐标为（的坐标为（xi yi zi）。）。n顶顶 点点 的的 次次 序序 要要 求求 这这 样样 排排 列列，使使 观观 察察 者者 在在 多多 面面 体体 外外 沿
12、沿 着着v1v2v3vL走时，多边形的内部始终在它的右侧。走时，多边形的内部始终在它的右侧。n为为了了确确定定多多边边形形的的内内法法线线方方向向，可可以以计计算算多多边边形形在在oxy平平面面上上投投影影的的有向面积。有向面积有向面积。有向面积sp可如下计算可如下计算n n如果如果sp0，则，则F所在的面为后向面。所在的面为后向面。n如果如果sp0，则，则F所在的面为前向面。所在的面为前向面。8.1 多面体的隐藏线消除n用边界盒排除不相交的线段求交 8.1 多面体的隐藏线消除n在后向面被删除后，如果两个相邻的多边形的公共边都在两个多边形的凸包上，则这两个多边形不会发生一个遮挡另一个的现象。n
13、这时，在考虑一个多边形的边的显示时，可以不考虑另一个多边形对它的影响。8.1 多面体的隐藏线消除隐藏线消除实际计算过程：n要对体一个一个来考虑，如考虑体A的显示时，n先确定可能遮挡A的那些体（包括体A本身），n对体A的每个多边形G，要找出可能遮挡它的所有多边形-这些多边形要从可能遮挡A的所有体的表面多边形中去找。n然后对多边形G的每一条边L找出可能遮挡它的所有多边形-这些多边形要从可能遮挡多边形G的所有多边形中去找。（以上各步均采用边界盒方法）n找到所有可能遮挡边L的多边形后，便可求L和这些多边形的交点，n并决定L的可见部分。L8.1 多面体的隐藏线消除 设边设边L的二端点顶点是的二端点顶点是
14、vi和和vj，对边，对边vivj（即（即L）和每一个可能遮挡它的多边）和每一个可能遮挡它的多边形，都要作下列计算和判断，以确定其隐藏关系。形，都要作下列计算和判断，以确定其隐藏关系。n如果如果vi和和vj都在多边形所在平面靠近观察者的一侧都在多边形所在平面靠近观察者的一侧n则这个多边形不能遮挡直线段vivj，这时没有必要再考虑vivj和这个多边形的关系。n如果如果vi和和vj不都在多边形所在平面靠近观察者的一侧，且不都在多边形所在平面靠近观察者的一侧，且vivj和多边形在和多边形在oxy平面的投影之间有交点，平面的投影之间有交点，n那么把vivj和多边形的边界投影到oxy平面上，求出它们的投影
15、之间的交点。n对每一个交点还要判断它在vivj上的对应点是在多边形前面还是后面，n只有在多边形后面，交点才要保留。n如图8.6中边v1v2和多边形ABCD在oxy平面上的投影虽然有交点Q，但它在v1v2上的对应点v却在多边形的前方，这种交点可不考虑。n如果如果vivj和多边形在和多边形在oxy平面的投影之间没有交点平面的投影之间没有交点，n那么，这时要判断vi或vj在oxy平面上的投影是否在 多边形投影的内部，n如果在内部，则vivj就会整个被这个多边形所遮挡住了。图8.6现在来说明确定现在来说明确定L L的可见部分的具体计算过程的可见部分的具体计算过程 ：（1）确定确定L L顶点处的与遮挡多
16、边形的前后位置关系顶点处的与遮挡多边形的前后位置关系n设多边形的顶点为 ，其坐标为（,），i=1,2,L。任取三个不在一直线上的顶点，设为 ,，则这多边形所在的平面方程为 n或 8.1 多面体的隐藏线消除设点vj的坐标为（xj,yj,zj），若z（xj,yj）zj 则vj在多边形所在平面的前面，否则认为vj在多边形所在平面的后面。其中8.1 多面体的隐藏线消除（2 2）确定）确定L L与遮挡多边形的交点同遮挡多边形的前后位置关系：与遮挡多边形的交点同遮挡多边形的前后位置关系：n为了判断边vivj和多边形在oxy平面的投影之间是否有交点，可首先计算求边vivj和多边形的边界在oxy平面上投影的交
17、点，我们可以把vivj的投影线段用参数方程表示:n多边形上任一边的投影用用参数方程表示:n求交点时解方程 n可得 其中 （8.9）n只有当0l1和0t 1时线段和线段vivj在oxy平面上的投影才有交点n为了判断vIvj上对应交点的点是在多边形所在平面的前面还是后面，则要去比较 和 ，若前者大于后者，则vivj上交点的对应点在多边形所在平面的前面，否则在后面。8.1 多面体的隐藏线消除（3 3）确定交点和多边形的关系）确定交点和多边形的关系是内点还是出点是内点还是出点 ：n由式（8.9）可知 ,其中（）z是指向量在z轴上的投影。n当 0时，QiQj由多边形内离开多边形到多边形外（该交点称为出点
18、）。n这个信息也要和交点的信息一起保存起来。8.1 多面体的隐藏线消除（4）确定确定Q Qi i起点和多边形的关系起点和多边形的关系 判断Qi点在多边形内或外，可以从Qi点出发沿x轴的正向作一射线，见图8.8。若该射线和多边形边界的交点个数是奇数，则Qi在多边形内，否则就在多边形外。但正确地找到交点的个数并不容易。如图8.8中点Q6处，由于舍入误差，计算时可能认为Q5 Q6，Q6 Q7和QiF均有交点，也可能算出一个交点或没有求出交点，不同的交点数可得到完全不同的结果。-需要特殊处理 图8.88.1 多面体的隐藏线消除（5 5）确定）确定L L的可见部分的可见部分n这里引入不可见阶ivord的
19、概念n它是一个数字，是某个确定的点的属性，n代表了边上从该点到下一个交点的部分被几个多边形遮挡。n这里要分两步来做：nStep1.确定边QiQj顶点处的不可见阶 nStep2.确定边QiQj与遮挡多边形交点处的不可见阶。8.1 多面体的隐藏线消除（5 5）确定）确定L L的可见部分的可见部分-Step1.-Step1.确定边确定边Q Qi iQ Qj j顶点处的不可见阶顶点处的不可见阶 n首先将Qi处的ivord设置为0，n对每一个和QiQj有交点的多边形，从与该多边形相交的交点中找出距离Qi最近的交点（交点参数最小），如图8.9中所示QiQj和多边形H1的交点B，n若这个交点为QiQj的出点
20、，则在ivord上加1，交点为进点，则ivord不变。n事实上Qi处的ivord反映了有几个多边形遮挡由Qi到QiQj与所有多边形的所有交点中距离Qi最近的交点形成的线段，n若Qi处不可见阶为0，则QiQj从l=0至l=l1段为可见，否则为不可见。图8.98.1 多面体的隐藏线消除（5 5）确确定定L L的的可可见见部部分分-Step2.-Step2.确确定定边边Q Qi iQ Qj j与与遮遮挡挡多多边边形形交交点点处处的的不不可可见见阶。阶。n假设直线QiQj和所有的多边形共有n个的交点，将直线与所有多边形的交点按着交点参数的大小排序，形成统一的交点序列 n下面我们计算 的不可见阶ivor
21、d,注意这里L0不可见阶就 是Qi的不可见阶。n首先将Li的不可见阶ivord设置Li-1的不可见阶n如果Li处的交点为进点，说明该交点所在的多边形不遮挡由参数Li-1 和Li所决定的直线段，而遮挡由参数Li 和Li+1所决定的直线段。因此Li的不可见阶加1n如果Li处的交点为出点，说明该交点所在的多边形遮挡由参数Li-1 和Li所决定的直线段，而不遮挡由参数参数Li 和Li+1所决定的直线段。因此Li的不可见阶减1n若Li处不可见阶为0，则由参数Li 和Li+1所决定的直线段是可见的，否则为不可见。8.3 区域子分算法 讨论一个面或面的一部分可见与否。n为了减少计算量，可先去掉所有的后向面。
22、n区域子分算法（warnock）是一种所谓分而治之的算法。整个屏幕称为窗口，分而治之算法是一个递推的四等分过程，每一次把矩形的窗口等分成四个相等的小矩形，分成的矩形也称为窗口。n每一次子分，均要把要显示的多边形和窗口的关系作一判断。8.3 区域子分算法这种关系可有以下四种，即n多边形包围了窗口n多边形和窗口相交n窗口包围了多边形n窗口和多边形分离8.3 区域子分算法在在窗窗口口和和每每个个多多边边形形的的关关系系确确定定之之后后，有有些些窗窗口口内内的的图图形便可显示了。它们属于下列三种情况之一。形便可显示了。它们属于下列三种情况之一。n所所有有多多边边形形都都和和窗窗口口分分离离，这时只要把
23、窗口内所有的象素填上背景颜色。n只只有有一一个个多多边边形形和和窗窗口口相相交交，或或这这个个多多边边形形包包含含在在窗窗口口内内。这时先对窗口内每一象素填上背景颜色，再对窗口内多边形部分用扫描线算法填色n只只有有一一个个多多边边形形和和窗窗口口相相交交，这这个个多多边边形形把把窗窗口口整整个个包包围围在在内内，或或虽虽有有几几个个多多边边形形和和窗窗口口相相交交，但但离离观观察察者者最最近近的的一一个个多多边边形形包包围围了了整整个个窗窗口口，这时把整个窗口填上离观察者最近的那个多边形的颜色。对上述三种情况的窗口来说，图已可画出，因而不必再分细了。8.3 区域子分算法n对上述三种情况不成立的
24、窗口再一分为四，见图8.18。分得的窗口重复上述的处理。对不能处理的窗口再一分为四。n窗口的边长越分越短，分了若干次后，窗口的边长就和一个象素的宽度一样了，n这时这个窗口对应的象素的颜色可取成最靠近观察者的多边形的颜色，n或和这个窗口相交的多边形颜色的平均值。图8.188.3 区域子分算法 Divide-Conqer算法的思想虽然简单，具体实现时的细节要处理好，才能提高效率。下面介绍一些有效的处理方法。n对所有的多边形按其顶点的z坐标最大值（即最靠近观察者的一个顶点的z坐标值）来排序。n对一个具体窗口来说，随着窗口不断地被细分，这个多边形序列的元素将越来越少。n窗口变小了，用边界盒的办法就可能
25、判定一些多边形和这个窗口是无交的，这些多边形也不会和这个窗口的子窗口相交，因此对这个窗口来说这些多边形可从多边形序列中排除。n此外窗口变小了，就可能被一个多边形包含在内，这样在这个窗口内，比这个多边形远离观察者的多边形都会被这个多边形所遮挡，对这个窗口的子窗口来说这些多边形也被遮挡了，因此对这个窗口来说，这些被遮挡的多边形可从序列中去掉。8.3 区域子分算法 n对于不能用边界盒办法判断和窗口不相交的多边形，则要经过计算去确定它们之间的关系。n这时可以采用与第四章中多边形裁剪算法类似的方法去确定多边形的窗口的边界是否有交点。n有交点时，说明多边形和窗口有交。n无交点时还要去确定它们是分离还是有包
26、含关系。8.3 区域子分算法n在找到了一个多边形包围所考虑的窗口后，就要把它和多边形序列中其它多边形离观察者的远近进行比较，把被它遮挡的多边形从序列中去掉。n为此可把窗口四个顶点坐标的x,y值代入那个包围窗口的多边形所在的平面方程，以求出对应四个顶点处该平面的z坐标值。以zmin记这四个z坐标值的最小值，n对序列中第i个多边形，把它各顶点z坐标值的最大值记为zmaxi,若满足zminzmaxi,则序列中第i个多边形便被遮挡了，n如图8.19所示，多边形AB包含了窗口，多边形CD便可用此法证实是被遮挡的。n但多边形EF则不能用此方法证实被多边形AB所遮挡。遇见这种情况可在窗口内多边形EF上任找一
27、点G（xG,yG，zG），把xG，yG代入多边形AB所在的平面方程，求出H点处的坐标z值zH，若zH zG，则AB在窗口内遮挡了多边形EF。Divide-Conqer算法的具体实现：图8.198.3 区域子分算法n区域子分法提出来后，有不少文章提出了一些改进。参考文章88中提出的方法是用多边形的边界来对窗口作划分，n这样做的目的是尽量减少对窗口划分的次数。用多边形的边界来对窗口作划分的方法8.3 区域子分算法用多边形的边界来对窗口作划分的方法-算法思想：n先用某种方法对各多边形在深度方向作初步的排序，n例如可按多边形顶点z坐标值的最大值zmaxi来排序，zmaxi大的排在前面。n现把多边形序列
28、中的第一个多边形（裁剪多边形）取为窗口。多边形序列中的其它的多边形都要被这窗口裁剪。n裁剪的结果要建立两个多边形序列表，n一个是窗口内的多边形表，n一个是窗口外的多边形表。n每一个被裁剪的多边形裁剪后n位于窗口内的部分放入内部表中n位于窗口外的部分放在外部表中。n图8.21（a）和图8.21（b）分别为图8.20中多边形的内部表和外部表，图8.20中多边形1作为窗口。图8.20图8.21(a)(b)8.3 区域子分算法n下面要来确定裁剪多边形（即取为窗口的那个多边形）下面要来确定裁剪多边形（即取为窗口的那个多边形）是否比内部表中的多边形更靠近观察者是否比内部表中的多边形更靠近观察者n求出裁剪多
29、边形各顶点坐标z的极小值zminc,n求出内部多边形各顶点坐标z的极大值zmaxin对那些满足 zminc zmaxi的内部表中的多边形，便可确认它被裁剪多边形所遮挡n若某一内部多边形不满足上式，n则要从该多边形上取一点，作一和z轴平行的线，n求出该线和两个多边形所在平面的交点，n根据交点的位置便可准确地确定哪一个多边形更靠近观察者。用多边形的边界来对窗口作划分的方法-算法思想：8.3 区域子分算法n如果发现内部表中某多边形如果发现内部表中某多边形H比裁剪多边形更靠近观察者，比裁剪多边形更靠近观察者，n这时则只好把多边形H的原始多边形（即未被裁剪时的多边形）代替原来的裁剪多边形重复上述工作。n
30、若裁剪多边形确实比内部表中的多边形都靠近观察者，则若裁剪多边形确实比内部表中的多边形都靠近观察者，则裁剪多边形便是完全可见的，可把它全部显示出来。裁剪多边形便是完全可见的，可把它全部显示出来。用多边形的边界来对窗口作划分的方法-算法思想：8.3 区域子分算法n下面则要去处理外部表中的各多边型下面则要去处理外部表中的各多边型n把外部表中第一个多边形作为窗口（假定外部表中多边形也是按原来的多边形次序排序）n对外部表中的其它多边形作裁剪并确定遮挡关系n在这过程中又形成新的外部表。每一个新的外部表中多边形的个数均比原来的外部表中多边形的个数少。n这一过程要重复到外部表中不再有多边形为止用多边形的边界来
31、对窗口作划分的方法-算法思想：8.4 Z缓冲器算法 nz缓冲器算法是最简单的消除隐藏面算法之一nz缓冲器是一组存贮单元n其单元个数和屏幕上象素的个数相同n也和帧缓冲器的单元个数相同，它们之间一一对应。8.4 Z缓冲器算法z缓冲器的设置nz缓冲器中每个单元的位数取决于图形在z方向的变化范围，一般取20bits就可以了。nz缓冲器中每单元的值是对应象素点所反应的物体上点的z坐标值。nz缓冲器中每个单元的初值取成z的极小值，帧缓冲器每个单元的初值可放对应颜色的值 8.4 Z缓冲器算法n图形消隐和生成的过程就是给帧缓冲器和图形消隐和生成的过程就是给帧缓冲器和z缓冲器中相应单元填值的过程缓冲器中相应单元
32、填值的过程n在把显示物体的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相在把显示物体的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的应单元前，要把这点的z坐标值和坐标值和z缓冲器中相应单元内的值作比较。缓冲器中相应单元内的值作比较。n只有前者大于后者时才改变帧缓冲器的那一个单元的值，同时只有前者大于后者时才改变帧缓冲器的那一个单元的值，同时z缓冲器缓冲器中相应单元的值也要改成这点的中相应单元的值也要改成这点的z坐标值。坐标值。n如果这点的如果这点的z坐标值小于坐标值小于z缓冲器中相应单元的值，则说明对应象素已缓冲器中相应单元的值，则说明对应象素已显示了物体上一个点的
33、属性，该点比要考虑的点更接近观察者。这样，显示了物体上一个点的属性，该点比要考虑的点更接近观察者。这样，无论帧缓冲器或无论帧缓冲器或z缓冲器相应单元的值均不应改变。缓冲器相应单元的值均不应改变。n对显示物体的每一个面上的每一个点都做上述处理后，便可得到消除了隐对显示物体的每一个面上的每一个点都做上述处理后，便可得到消除了隐藏面的图。藏面的图。8.4 Z缓冲器算法n算法的优点n简单、可靠n不需要对显示物体的面预先进行排序n算法的缺点n要很大的z缓冲器n工作量较大：显示物体的表面和象素对应的每一个点处都要计算它的z值 n为了克服第一个缺点，n可把整个平面分成若干区域，一区一区来显示，这样z缓冲器的
34、单元数只要等于屏幕上一个区域的象素个数。n如果把这个区域取成屏幕上一行，就得到了扫描线z缓冲器算法。8.4扫描线Z缓冲器算法 扫描线z缓冲器-算法 思想nz缓冲器的单元数可以取成和一行上的象素数目相同。n从最上面的一条扫描线开始工作，向下对每一条扫描线作处理。n对每一条扫描线来说，把相应的帧缓冲器单元置成底色，在z缓冲器中存放z的极小值。8.4扫描线Z缓冲器算法扫描线z缓冲器-算法 思想n对每个多边形检查它在对每个多边形检查它在oxy平面上的投影和当前的扫描是否相交，平面上的投影和当前的扫描是否相交，n若不相交，则不考虑该多边形。n如果相交，则扫描线和多边形边界的交点一事实上是成对地出现n对每
35、对交点中间的象素计算多边形所在平面对应点的深度（即对每对交点中间的象素计算多边形所在平面对应点的深度（即z值），并值），并和和z缓冲器中相应单元存放的深度值作比较。缓冲器中相应单元存放的深度值作比较。n若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。n对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形。的图形。n对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图。8.4扫描线Z缓
36、冲器算法n上述算法要花费很多时间去计算n在处理每一条扫描线时，要检查各多边形是否和该线相交n还要计算多边形所在平面上很多点的z值n为了使这些工作能高效率地进行，可采取类似多边形扫描转换的扫描线算法处理。8.4扫描线Z缓冲器算法数据结构n一个多边形Y筒n一个边Y筒n一个多边形活化表n一个边活化表xl=4,!xl=1,!yl=3,xr=7,!xr=0,!yr=3,zl1,zx1,zy1,IP1xl=5,!xl=5/6,!yl=5,xr=9/8,!xr=3/8,!yr=5,zl2,zx2,zy2,IP28.4扫描线Z缓冲器算法n建立一个多边形Y筒-图8.23是图8.22的多边形Y筒n每个筒的深度和显
37、示屏幕行数相同。n根据多边形顶点Y坐标最大值来决定放入多边形Y筒的相应行数。n多边形Y筒要记录多边形所在平面方程ax+by+cz+d=0系数a，b，c和d，n还要记录和该多边形在oxy平面上的投影相交的扫描线的条数y，n以及多边形的属性colour和编号IP。图8.22图8.238.4扫描线Z缓冲器算法n建立一个边Y筒-图8.24是图8.22的边Y筒n每个筒的深度和显示屏幕行数相同。n根据边两端点较大的Y坐标值为决定放入边Y筒的相应行数。n边Y筒中记录的每一条边要保存下列信息：n和该边在oxy平面上的投影相交的扫描线条数y，n该投影和相邻的两条扫描线交点的x坐标的差x，(由上到下扫描)n该边所
38、属多边形的编号IPn及边的上端点x坐标的值x。图8.24图8.228.4扫描线Z缓冲器算法n建立一个多边形活化表n记录在oxy平面上的投影和当前考虑的扫描线相交的多边形，n以图8.22为例，当扫描线对应y=10或11时，多边形活化表只有一个多边形。n当y=8时多边形活化表如图8.25。表中的y值是已经过修改的。（由上到下扫描，故！y=5,和!y=7）图8.22图8.258.4扫描线Z缓冲器算法n建立一个边活化表n边活化表中存放多边形边界和扫描线相交的边对。n例如图8.22中y=6的扫描线上的边活化表中应有两个对边，n一是和多边形在oxy平面上的投影相交的两条边n另一是和多边形投影相交的两条边。
39、xl=4,!xl=1,!yl=3,xr=7,!xr=0,!yr=3,zl1,zx1,zy1,IP1xl=5,!xl=5/6,!yl=5,xr=9/8,!xr=3/8,!yr=5,zl2,zx2,zy2,IP2图8.228.4扫描线Z缓冲器算法n边活化表中每一边对要保存下列信息xl左交点的x坐标值xl左交点所在边和两相邻扫描线交点的x坐标之差yl以和左交点所在边相交的扫描线条数为初值，以后每处理一条扫描线减1xr右交点的x坐标值xr右交点所在边和两相邻扫描线交点的x坐标之差yr以和右交点所在边相交的扫描线条数为初值，以后每处理一条扫描线减1zl左交点处多边形所在平面的深度值zx沿扫描线向右走过一
40、个象素时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说zx=a/c（c0）zy沿y方向向下移过一根扫描线时，多边形所在平面深度的增量。对方程为ax+by+cz+d=0的平面来说zy=b/c（c0）IP所在多边形的编号xl=4,!xl=1,!yl=3,xr=7,!xr=0,!yr=3,zl1,zx1,zy1,IP1xl=5,!xl=5/6,!yl=5,xr=9/8,!xr=3/8,!yr=5,zl2,zx2,zy2,IP28.4扫描线Z缓冲器算法n一开始处理最上面的一条扫描线一开始处理最上面的一条扫描线n在处理前边和多边形的活化表均是空的。在处理前边和多边形的活化表均是空
41、的。n已建立图已建立图8.23和图和图8.24的两个的两个Y筒后筒后n在处理每条扫描线时要做下列工作在处理每条扫描线时要做下列工作 （1 1）把帧缓冲器相应行置成底色。）把帧缓冲器相应行置成底色。（2 2）z z缓冲器的各单元放缓冲器的各单元放z z的极小值。的极小值。（3 3）检检查查多多边边形形的的Y Y筒筒，如如果果有有新新的的多多边边形形涉涉及及该该扫扫描描线线，则则把把它它放入多边形活化表中。放入多边形活化表中。（4 4）如如果果有有新新的的多多边边形形加加入入多多边边形形活活化化表表，则则要要把把该该多多边边形形在在oxyoxy平面上的投影和扫描线相交的边对加入边活化表中。平面上的
42、投影和扫描线相交的边对加入边活化表中。（5 5）如如果果有有些些边边在在这这条条扫扫描描线线处处结结束束了了，而而其其所所在在的的多多边边形形仍仍在在多多边边形形活活化化表表内内，则则可可从从边边的的Y Y筒筒中中找找到到该该多多边边形形在在oxyoxy平平面面上上的的投投影影和和扫扫描描线线相相交交的的新新的的边边或或边边对对，修修改改或或加加到到边边的的活活化化表表中中去去。（边边对对在边活化表中的次序是不重要的）在边活化表中的次序是不重要的）。算法步骤：-扫描8.4扫描线Z缓冲器算法n下面从形成的活化边表中取出一个边对，令zx=zl，对每一个满足xlxxr的坐标为（x，y）的象素（y是当
43、前考虑的扫描线高度）从左到右依次作下列处理。先计算n这就是对应象素处多边形所在平面的深度。n如果此值比z缓冲器相应单元中存放的值大，则要用它代替z缓冲器相应单元中原来的值，并把帧缓存中相应单元改成这个多边形的属性。n这项工作要对活化表中的每个边对都做到，这项工作完成后，帧缓冲器相应行便存放了消隐后的结果。算法步骤：-消隐8.4扫描线Z缓冲器算法n修改后的表便是下一条扫描线的边活化表。n对每一边对可先计算 n若yl 或yr小于0，相应的边就要从一个边对中去掉，从边活化表中找合适的边来代替。也有可能这两条边同时结束于某一点，这说明这一边对可取消了。n边和下一条扫描线交点的x值可由下式求得n多边形所
44、在平面对应下一条扫描线在x=xl处的深度 算法步骤：-下面来说明对边活化表修改的方法8.4扫描线Z缓冲器算法n对多边形活化表中每一个多边形的y要做如下修改 n当y0时，该多边形则要从多边形活化表中删除。n做完这些工作后便可开始下一条扫描线的消隐工作。n当把每一条扫描线的消隐工作都完成后，整个消隐工作也就完成了。算法步骤：-下面来说明对多边形活化表修改的方法8.5区间（跨距）扫描线算法 n上节讲的扫扫描描线线z缓缓冲冲器器算算法法将消隐问题分散到每一条扫描线上去解决，n这样，问题变得较简单了。n但在每个象素处计算多边形z值的工作量仍是很大的。n实际上每条扫描线被各多边形边界在oxy平面上的投影分
45、割成为数不多的区间，每一个区间上只显示一个面，n因此，只要在区间上任一点处，找出在该处z值最大的一个面，这个区间上的每个象素就用这个面的颜色来显示。这种做法就是所谓跨距扫描线算法。8.5区间（跨距）扫描线算法n设多边形的边界在oxy平面上的投影和扫描线交点的横坐标为xi，这些交点把扫描线分成一个小区间xi,i+1，每个小区间称为一个跨距。n在每个区间上最靠近观察者的那个面就是这个区间上的可见面。n为了在区间上找到离观察者最近的面，n只要去求出各多边形（限于那些在oxy平面上的投影和所考虑的扫描线相交的多边形）所在平面在区间左端点的z值，找出z值最大的一个面。n如果两个面恰好在左端点相交时，可计
46、算这两个面在右端点的z值并做比较。8.7 优先级表算法 优先级表算法n按多边形离观察者的远近来建立一张表n距观察者远的优先级低，近的优先级高。n如果这张表能正确地建立好，那么只要从优先级低的多边形开始，依次把多边形的颜色填入帧缓冲存储器中以形成该多边形的图形n直到优先级最高的多边形的图形送入帧缓冲器后，整幅图就显示好了。n这种算法也称为油画家算法n因为油画家绘画时常先画底色，然后再一层层往上画。8.7 优先级表算法上述算法的困难在于怎样对多边形做一个正确的排序。上述算法的困难在于怎样对多边形做一个正确的排序。下面给出了一个动态的方法下面给出了一个动态的方法n先根据每个多边形顶点先根据每个多边形
47、顶点z z坐标的极小值坐标的极小值z zminmin的大小把多的大小把多边形做一个初步的排序。边形做一个初步的排序。n设设z zminmin 最小的多边形是最小的多边形是P P，它暂时成为优先级最低的一，它暂时成为优先级最低的一个多边形，把多边形序列中其他多边形记为个多边形，把多边形序列中其他多边形记为Q Qn现在先来确定现在先来确定P P和其他多边形和其他多边形Q Q的关系的关系n如果如果P P的顶点的顶点z z的坐标的极大值的坐标的极大值P zP zmaxmax 比某一多边形比某一多边形Q Q的顶点坐标的极小值的顶点坐标的极小值Q zQ zminmin 还要小，即还要小，即P zP zma
48、x max Q Q zQ zminmin，则必须做进一，则必须做进一步的检查，才能确定步的检查，才能确定P P和和Q Q的确切关系。的确切关系。8.7 优先级表算法 这种检查分以下五项。nP和Q在oxy平面上投影的边界盒在x方向上不相交(见图（a）)nP和Q在oxy平面上投影的边界盒在y方向上不相交(见图（b）)nP的各顶点均在Q的远离视点的一侧(见图（c）)nQ的各顶点均在P的靠近视点的一侧(见图（d）)nP和Q在oxy平面上的投影不相交(见图（e）)上述五项只要有一项成立，P就不遮挡Q。由于从第一项至第五项每项检查所需的工作量是递增，因此检查时要按第一至第五项次序进行。xyPQPxzxzQ
49、PPxyQxyPQQxyxyQ Q（a）（b）（c）（d）（e）8.7 优先级表算法n如果上述五项检查均不成立，则不能确定P不遮挡Q，n这时要在多边形序列中把P和Q交换一下次序，n并对交换后的序列中优先级最低的多边形P检查，看P是否遮挡别的多边形。8.7 优先级表算法n在图8.32，不可能找到一个多边形不遮挡另一个多边形。n在图8.33虽然P并不遮挡Q，得它也不能使上述五项检查成立。图8.32图8.338.7 优先级表算法n对这两种情况，如果不采取任何措施，而只在多边形序列中交换P和Q的位置，这时新的P和Q仍不能满足上述五项检查，n因而这样做下去只会使多边形不断进行交换。n为了避免这种现象产生
50、，在优先级最低的多边形和其他多边形交换时，n要对原来的优先级最低的多边形做一标志，当有标志的多边形再换成优先级最低的多边形时，则说明出现了图 中的现象，n这时可把P沿Q平面一分为二，见图8.33。把多边形序列中原多边形P从序列中删掉，而把P分成的两个多边形加入多边形表中。n采用这种方法后，但可得到一个正确排序的多边形的序列。8.7 优先级表算法n这种方法对有的多边形互相贯串时也可适用。n优先级表算法可以较好地解决透明或半透明物体的存在，n也可采用反走样算法改善多边形边界的显示效果。n这个算法可推广到解决三维立体的消隐问题。8.7 优先级表算法n优先级表算法对解决动态显示有很大的好处，例如飞机驾