第七章消除隐藏线和隐藏面PPT讲稿.ppt

《第七章消除隐藏线和隐藏面PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第七章消除隐藏线和隐藏面PPT讲稿.ppt（90页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第七章 消除隐藏线和隐藏面第1页，共90页，编辑于2022年，星期一图象空间算法对显示设备上每一个可分图象空间算法对显示设备上每一个可分辨辨象素象素进行判断，看组成物体的多个多进行判断，看组成物体的多个多边形表面中哪一个在该象素上可见，即边形表面中哪一个在该象素上可见，即要对每一象素检查所有的表面。要对每一象素检查所有的表面。客体空间算法把注意力集中在分析要客体空间算法把注意力集中在分析要显示显示形体形体各部分之间的关系上，这种各部分之间的关系上，这种算法对每一个组成形体的表面，都要算法对每一个组成形体的表面，都要与其它各表面进行比较，以便消去不与其它各表面进行比较，以便消去不可见的面或面的不

2、可见部分。可见的面或面的不可见部分。第2页，共90页，编辑于2022年，星期一第一节第一节 线面比较法消除隐藏线线面比较法消除隐藏线 多面体的面可见性多面体的面可见性 凸多面体的可见面就是朝向观察位置凸多面体的可见面就是朝向观察位置的面的面 设观察方向由设观察方向由指向观察位置指向观察位置的一个方的一个方向向量向向量k k给出，所考查的面的外法向量是给出，所考查的面的外法向量是n n，则这两个向量的夹角，则这两个向量的夹角 满足满足0 /2时，所考查面是可见的，否则就是不可见时，所考查面是可见的，否则就是不可见的的 第3页，共90页，编辑于2022年，星期一把把n和和k记作记作则则分子分子 为

3、为正正 ，则，则 ,面面为可见；若为为可见；若为负负，则，则 ，面为不可见；，面为不可见；若为若为零零，则，则 ，此面退化为线。，此面退化为线。第4页，共90页，编辑于2022年，星期一第5页，共90页，编辑于2022年，星期一 设空间有一个四面体，顶点设空间有一个四面体，顶点A，B，C，D的坐标依次是的坐标依次是（0,0,0）,（2,0,1）,（4,0,0）,(3,2,1),沿沿z轴正向观察轴正向观察,求各面的可见性求各面的可见性观察方向向量是观察方向向量是k=(0,0,1),三角面三角面DAB的法向量是的法向量是:第6页，共90页，编辑于2022年，星期一 因此因此,面面DAB为可见面为可

4、见面.类类似计算可知，面似计算可知，面DBC是可见面是可见面,面面ADC是不是不可见面可见面,面面ACB退化为线。退化为线。第7页，共90页，编辑于2022年，星期一 利用外法线就可以判断凸多面体上各利用外法线就可以判断凸多面体上各表面的可见性，由此就能解决对单个凸多面表面的可见性，由此就能解决对单个凸多面体的隐藏线和隐藏面的消除问题。体的隐藏线和隐藏面的消除问题。消除消除隐藏线隐藏线的线面比较法的最先一步就的线面比较法的最先一步就是利用外法线判断出所有可能的可见面，可是利用外法线判断出所有可能的可见面，可能可见面上的线段是可能可见线。能可见面上的线段是可能可见线。要依次用要依次用每一条可能可

5、见线，与每一个可能可见面每一条可能可见线，与每一个可能可见面比较比较，从而确定出可见线、隐藏线及可见，从而确定出可见线、隐藏线及可见线上的隐藏部分。线上的隐藏部分。第8页，共90页，编辑于2022年，星期一可能可见线和可能可见面可能可见线和可能可见面 空间任一线段，只有其投影与多边形空间任一线段，只有其投影与多边形表面的表面的投影范围发生交迭投影范围发生交迭时，才可能与多时，才可能与多边形表面有遮档关系边形表面有遮档关系 一个多边形表面的投影范围一个多边形表面的投影范围 第9页，共90页，编辑于2022年，星期一范围检查也称为范围检查也称为最大最小检验最大最小检验，即通过比较，即通过比较有关的

6、最大或最小值来判定范围的交迭情形。有关的最大或最小值来判定范围的交迭情形。第10页，共90页，编辑于2022年，星期一 按按Xv方向对投影范围的检查，可分别方向对投影范围的检查，可分别计算出投影线段和多边形表面计算出投影线段和多边形表面投影范围投影范围X坐标的最大值和最小值，设分别是坐标的最大值和最小值，设分别是 于是若于是若 或者或者 ,线段线段和多边形表面就必然没有遮挡关系。和多边形表面就必然没有遮挡关系。显然按显然按xv方向或按方向或按yv方向都可以类似地做方向都可以类似地做范围检查，这时可避免消除隐藏面时很多不必范围检查，这时可避免消除隐藏面时很多不必要的深度比较。要的深度比较。第11

7、页，共90页，编辑于2022年，星期一第12页，共90页，编辑于2022年，星期一 zv方向的范围检查是沿方向的范围检查是沿zv方向观察方向观察时时粗略的深度检验粗略的深度检验。在此范围检查中若线段投影的最大在此范围检查中若线段投影的最大z坐标坐标 小于多边形表面投影范围最小小于多边形表面投影范围最小的的z z坐标坐标 ，则线段完全在表面前面，则线段完全在表面前面，根本不发生遮挡现象，可以不必再往下根本不发生遮挡现象，可以不必再往下做精确的深度检验。做精确的深度检验。第13页，共90页，编辑于2022年，星期一精确深度检验精确深度检验 l2 线段不会被线段不会被遮挡遮挡;线段有可能线段有可能被

8、遮挡被遮挡;第14页，共90页，编辑于2022年，星期一 求交点求交点 直线直线L1的参数方程可写成的参数方程可写成X=x1，Y=y1，Z=z1+t，代入平面方程得：，代入平面方程得：第15页，共90页，编辑于2022年，星期一若若t0,则则Z1，若，若t0Z1。需要检查出某一段子线段是否可见。为此可以取子需要检查出某一段子线段是否可见。为此可以取子线段上任意一点，若这点在多边形表面各边线的投影所线段上任意一点，若这点在多边形表面各边线的投影所形成的封闭多边形内，这子线段就不可见，否则就可见。形成的封闭多边形内，这子线段就不可见，否则就可见。第16页，共90页，编辑于2022年，星期一 空空间

9、间一一条条线线段段可可能能被被一一个个多多边边形形表表面面遮遮挡挡的消除隐藏线的算法的步骤如下：的消除隐藏线的算法的步骤如下：做做xv方向和方向和yv方向的方向的范围检查范围检查；若不能判定，；若不能判定，则接着做则接着做zv方向的范围检查即方向的范围检查即粗略的深度比较粗略的深度比较；若还不能判定就再进行若还不能判定就再进行精确的深度比较精确的深度比较，比较，比较时应计算线段两端点在可能遮挡它的平面上的时应计算线段两端点在可能遮挡它的平面上的投影点，比较相应的坐标。这时可能出现线段投影点，比较相应的坐标。这时可能出现线段与平面相交需要用与平面相交需要用交点交点，这些交点把线段的投，这些交点把

10、线段的投影分成两部分考虑的情况。判定得知线段确实影分成两部分考虑的情况。判定得知线段确实被平面遮挡了哪些部分做精确计算，计算是求被平面遮挡了哪些部分做精确计算，计算是求出线段的投影与遮挡平面上多边形表面边框投出线段的投影与遮挡平面上多边形表面边框投影的所有交点，这些交点把线段的投影分成可影的所有交点，这些交点把线段的投影分成可见和不可见的一些子线段。对见和不可见的一些子线段。对子线段子线段的可见性，的可见性，先取上面一点做点的先取上面一点做点的包含性包含性检验来进行判断。检验来进行判断。第17页，共90页，编辑于2022年，星期一线面消隐算法（）线面消隐算法（）坐标变换；坐标变换；for(对每

11、一个面对每一个面FACEi的每一条边的每一条边EDGEj)将二元组将二元组压入堆栈；压入堆栈；while(栈不空栈不空)=栈顶；栈顶；for(i!=i0的每个面的每个面FACEi）if(EDGEj被被FACEi全部遮挡全部遮挡)将将EDGEj清空；清空；break;if(EDGEj被被FACEi部分遮挡部分遮挡)从从EDGEj中将被遮挡的部分裁掉；中将被遮挡的部分裁掉；if(EDGEj被分成若干段被分成若干段)将其中的一段作为当前段；将其中的一段作为当前段；将其他段及相应的将其他段及相应的i压入堆栈；压入堆栈；if(EDGEj段不为空段不为空)显示显示EDGEj；第18页，共90页，编辑于20

12、22年，星期一第二节第二节 曲面隐藏线消除的浮动曲面隐藏线消除的浮动水平线算法水平线算法 若存在若存在M M个象素，则建立个象素，则建立M M个内存个内存单元单元 ，称之为上浮水平线数组，称之为上浮水平线数组，在这些单元中先放上初值，初值应取在这些单元中先放上初值，初值应取成小于成小于 。曲面方程曲面方程第19页，共90页，编辑于2022年，星期一第20页，共90页，编辑于2022年，星期一设设平平面面是是最最靠靠近近观观察察者者的的，从平面上从平面上的曲线的曲线第21页，共90页，编辑于2022年，星期一 水平方向每个象素的对应水平方向每个象素的对应x x坐坐标值，计算标值，计算 若若 ，则

13、点，则点 是是可见点，并把可见点，并把 内容变成内容变成 。若若 ，则，则 为不可见，为不可见，则不改变则不改变 的内容。的内容。第22页，共90页，编辑于2022年，星期一 上图上图c c点附近的虚线部分应是可见的，点附近的虚线部分应是可见的，但按上述算法却成了不可见了。为了解但按上述算法却成了不可见了。为了解决这个问题，可另建立决这个问题，可另建立M M个单元个单元 ，可称之为下浮水平线数组。，可称之为下浮水平线数组。第23页，共90页，编辑于2022年，星期一 初值取成初值取成 或比这更大或比这更大一点得数，每次求出一点得数，每次求出 第24页，共90页，编辑于2022年，星期一Ifth

14、enIfthen 如果函数如果函数 是用是用离散点形式离散点形式 给出给出，则可如下处理。，则可如下处理。这时的这时的 单元个数不是由显示器单元个数不是由显示器在在x x方向的象素个数来定，而是根据给定的方向的象素个数来定，而是根据给定的离散点在离散点在x x方向的个数来定方向的个数来定。第25页，共90页，编辑于2022年，星期一基本想法是用线性插值法所得直线来代基本想法是用线性插值法所得直线来代替两个点之间的曲线。若上述判断结果为替两个点之间的曲线。若上述判断结果为 均为不可见，则认为平面均为不可见，则认为平面 上的从上的从 的一段曲线为不可见。若两点均为可见，的一段曲线为不可见。若两点均

15、为可见，则用这两点的连线代替原来这两点之间的则用这两点的连线代替原来这两点之间的曲线，并认为可见的，若这两点中有一点曲线，并认为可见的，若这两点中有一点可见，如图的可见，如图的A A点，另一点则为不可见，如点，另一点则为不可见，如图中的图中的B B点，这时要求出点连线的交点点，这时要求出点连线的交点E E。AEAE部分为可见，部分为可见，EBEB为不可见。为不可见。第26页，共90页，编辑于2022年，星期一ABCDEZi+1Zi第27页，共90页，编辑于2022年，星期一 一般用一般用 两族曲线两族曲线来表示一曲面时常用斜投影。来表示一曲面时常用斜投影。为了得到消隐后曲面表示，不能对为了得到

16、消隐后曲面表示，不能对两族曲线分别消隐在叠加在一起，正确两族曲线分别消隐在叠加在一起，正确的做法是对两族曲线一起做，即处理好的做法是对两族曲线一起做，即处理好平面平面 一段曲线后，马上一段曲线后，马上处理平面处理平面 的一段曲线。的一段曲线。对这两族曲线用公共的对这两族曲线用公共的第28页，共90页，编辑于2022年，星期一X=XkZ=ZiB第29页，共90页，编辑于2022年，星期一第三节第三节 深度排序算法深度排序算法 深度排序算法的主要步骤：深度排序算法的主要步骤：1.把所有的多边形按顶点最大把所有的多边形按顶点最大z坐标值进坐标值进行排序。行排序。2.解决当多边形解决当多边形z范围发生

17、交迭时出现不范围发生交迭时出现不明确问题。明确问题。3.按最大按最大z坐标值逐渐坐标值逐渐减小减小的次序，对每的次序，对每个多边形进行扫描转换。个多边形进行扫描转换。第30页，共90页，编辑于2022年，星期一 算法的基本思想是按多边形离开算法的基本思想是按多边形离开观察位置的观察位置的距离距离进行排序，然后按照进行排序，然后按照距离减少距离减少的次序，把每个多边形内部的次序，把每个多边形内部点应有的象素值送入帧缓存存贮器中。点应有的象素值送入帧缓存存贮器中。算法考查多边形的深度次序是在算法考查多边形的深度次序是在客体空间中进行，图形显示时覆盖步客体空间中进行，图形显示时覆盖步骤是在图象空间中

18、实现，所以可以说骤是在图象空间中实现，所以可以说是一个是一个客体空间和图象空间客体空间和图象空间的混合算的混合算法。法。第31页，共90页，编辑于2022年，星期一第32页，共90页，编辑于2022年，星期一不明确问题检验方法不明确问题检验方法 所有多边形按顶点最大所有多边形按顶点最大z坐标值排坐标值排序后得到一个排序表，设序后得到一个排序表，设P是排在表中是排在表中最后的那个多边形。最后的那个多边形。设设Q是排在是排在P前面并且前面并且z坐标范围与坐标范围与其发生交迭的一个多边形，对其发生交迭的一个多边形，对Q与与P的的次序关系进行检查。次序关系进行检查。第33页，共90页，编辑于2022年

19、，星期一 检查可以按下面列出的五个步骤检查可以按下面列出的五个步骤进行，每个步骤判断一种情况。进行，每个步骤判断一种情况。1 1多边形的多边形的x坐标范围不相交迭，所以多坐标范围不相交迭，所以多边形不相交迭。边形不相交迭。2多边形的多边形的y坐标范围不相交迭，所以多坐标范围不相交迭，所以多边形不相交迭。边形不相交迭。3.P整个在整个在Q远离远离观察点的一侧。观察点的一侧。4.Q整个在整个在P的的靠近靠近观察点的一侧。观察点的一侧。5.多边形在多边形在z=0平面上的投影本身不相交平面上的投影本身不相交迭。迭。第34页，共90页，编辑于2022年，星期一第35页，共90页，编辑于2022年，星期一

20、 如果所有这五步检查都为假，就假定如果所有这五步检查都为假，就假定P是遮挡了是遮挡了Q，交换，交换P和和Q在排序表中的位在排序表中的位置。置。如果仍做交换，算法会永远循环下去而如果仍做交换，算法会永远循环下去而没有结果。没有结果。为了为了避免循环避免循环，可以做一个限制。当，可以做一个限制。当做过首次五步检查后，发生某个多边形被做过首次五步检查后，发生某个多边形被移到排序表的末尾时，就立即加上一个标移到排序表的末尾时，就立即加上一个标记，以后就不能再做移动。出现再次应该记，以后就不能再做移动。出现再次应该移动时，用一个多边形移动时，用一个多边形第36页，共90页，编辑于2022年，星期一所在的

21、平面，把另一个多边形剪裁分为所在的平面，把另一个多边形剪裁分为两个。两个。PQ第37页，共90页，编辑于2022年，星期一第四节第四节 画家算法画家算法 画家算法又称深度优先级表法，画家算法又称深度优先级表法，它是深度排序算法的一种具体实现。它是深度排序算法的一种具体实现。先画远景，再画中景，最后画先画远景，再画中景，最后画近景。近景。第38页，共90页，编辑于2022年，星期一81001101111010000100110016123426736587514843785621第39页，共90页，编辑于2022年，星期一 边界表示边界表示 三元组表示物体顶点的坐标。三元组表示物体顶点的坐标。四

22、元组表示物体的某个面由哪些顶点构成，每四元组表示物体的某个面由哪些顶点构成，每个面顶点个数都是个面顶点个数都是4 4个。个。程序中所使用的数据结构包括点记录程序中所使用的数据结构包括点记录（vertexvertex）、面记录（）、面记录（patchpatch）和排序数组。点记）和排序数组。点记录由五个域构成。其中，三个域用于存储点的空录由五个域构成。其中，三个域用于存储点的空间坐标，另外两个域用于存储点的投影（屏幕）间坐标，另外两个域用于存储点的投影（屏幕）坐标。面记录由四个域组成，每个域存放对应的坐标。面记录由四个域组成，每个域存放对应的顶点号。排序数组的每个元素有两个域，其中一顶点号。排序

23、数组的每个元素有两个域，其中一个域存放面与视点的距离，另一个域存放该面的个域存放面与视点的距离，另一个域存放该面的面号。面号。第40页，共90页，编辑于2022年，星期一ReadkeyboardReadkeyboard：打打开开物物体体的的边边界界表表示示数数据据文文件件，从从键键盘盘读读进进旋旋转转角角和和透透视视角角，物物体体表表面面的颜色参数（色彩和饱和度），光源方向。的颜色参数（色彩和饱和度），光源方向。Vertices：读读进进顶顶点点的的空空间间坐坐标标，计计算算物物体体的的包包围围球球半半径径，把把物物体体缩缩小小到到单单位位球球中中去去，计计算算物体各顶点在屏幕上的投影坐标。物

24、体各顶点在屏幕上的投影坐标。开始开始第41页，共90页，编辑于2022年，星期一Patches：读读进进面面定定义义数数据据，求求出出各各面面与与视视点点的的距距离离，把把面面号号与与距距离离放放进进排排序序数数组组。然然后后以以面面与与视视点点的的距距离离为为参参照照值值，对对数数组组进进行行排排序。序。Gmode：使使终终端端进进入入图图形形状状态，设备参数初始化态，设备参数初始化Setpen：建立查色表建立查色表第42页，共90页，编辑于2022年，星期一Painting：从从排排好好序序的的数数组组中中依依次次取取出出一一面面号号，计计算算对对应应面面的的法法向向量量，再再计计算算该该

25、面面的的光光强强，然后显示该面。然后显示该面。Amode：终端返回文字状态。终端返回文字状态。结束结束第43页，共90页，编辑于2022年，星期一第五节第五节 z z 缓冲算法缓冲算法 z 缓冲算法缓冲算法(深度深度缓冲算法缓冲算法)是一种最简单是一种最简单的图象空间算法。对每一个点，这个算法不仅的图象空间算法。对每一个点，这个算法不仅需要有一个需要有一个更新缓冲器更新缓冲器存储各点的象素值，而存储各点的象素值，而且还需要有一个且还需要有一个z 缓冲存储器缓冲存储器存储相应的存储相应的z值。更新缓冲存储器初始化为背景值，值。更新缓冲存储器初始化为背景值，z缓冲缓冲存储器初始化为可以表示的最大存

26、储器初始化为可以表示的最大z值。对每一值。对每一个多边形，个多边形，不必不必进行深度排序算法要求的进行深度排序算法要求的初初始排序始排序，立即就可以逐个进行扫描转换。，立即就可以逐个进行扫描转换。第44页，共90页，编辑于2022年，星期一 扫扫描描转转换换时时,对对每每个个多多边边形形内内部部的的任任意意点点(x,y),实施如下步骤：实施如下步骤：1计算在点计算在点(x,y)处多边形的深度值处多边形的深度值Z(x,y)。2如果计算所得的如果计算所得的Z(x,y)值，小于在值，小于在z 缓缓冲存储器中点冲存储器中点 x y 处记录的深度值，处记录的深度值，那么就做：那么就做：（1）把值）把值Z

27、(x,y)送入送入z 缓冲存储器的点缓冲存储器的点 x,y 处。处。（2）把多边形在深度）把多边形在深度Z(x,y)处应有的象素处应有的象素值，送入更新缓冲存储器的点值，送入更新缓冲存储器的点 x,y 处。处。第45页，共90页，编辑于2022年，星期一 算法中深度计算，可通过多边形的顶点算法中深度计算，可通过多边形的顶点坐标求出所在平面的方程，然后再使用平面坐标求出所在平面的方程，然后再使用平面方程，对每个点方程，对每个点 x y，解出相应的，解出相应的z。对面方程对面方程 解出解出 是：是：第46页，共90页，编辑于2022年，星期一则在点（则在点（x+x,y）处的深度值就是）处的深度值就

28、是设在点（设在点（x,y）处的深度值是）处的深度值是z1:第47页，共90页，编辑于2022年，星期一z 缓冲算法的工作流程：缓冲算法的工作流程：更新缓冲区置成背景色；更新缓冲区置成背景色；z 缓冲区置成最大缓冲区置成最大z值；值；for(各个多边形各个多边形)扫描转换该多边形；扫描转换该多边形；for(计算多边形所覆盖的每个象素（计算多边形所覆盖的每个象素（x,y）)计算多边形在该象素的深度值计算多边形在该象素的深度值Z(x,y)；if(Z(x,y)小于小于Z缓冲区中的缓冲区中的(x,y)处的值处的值)把把Z(x,y)存入存入Z缓冲区中的缓冲区中的(x,y)处；处；把多边形在把多边形在(x,

29、y)处的亮度值存入更新缓处的亮度值存入更新缓存区的存区的(x,y)处；处；第48页，共90页，编辑于2022年，星期一第六节第六节 扫描线算法扫描线算法 扫扫描描线线算算法法是是图图象象空空间间算算法法，它它建建立立图图象象是是通通过过每每次次处处理理一一条条扫扫描描线线来来完完成成的的。这这个个算算法法是是第第二二章章讨讨论论的的多多边边形形填填充充的的扫扫描描线线算算法法的的推推广广。在在多多边边形形填填充充的的扫扫描描线线算算法法中中，只只是是对对一一个个多多边边形形做做扫扫描描转转换换，而而这这里里是是同同时时对对多个多边形多个多边形做扫描转换。做扫描转换。第49页，共90页，编辑于2

30、022年，星期一 要要建建立立一一个个边边表表ET。ET中中各各登登记记项项按按边边的的较较小小的的y坐坐标标递递增增排排列列；每每一一登登记记项项下下的的“吊吊桶桶”，按按所所记记x坐坐标标递递增增排排列列。“吊吊桶桶”中中各项的内容依次是：各项的内容依次是：1与较小的与较小的y坐标对应的端点的坐标对应的端点的x坐标坐标xmin。2边的另一端点的较大的边的另一端点的较大的y坐标坐标ymax。3x的增量的增量x，它实际上是边的斜率的，它实际上是边的斜率的倒数，是从一条扫描线走到下一条扫倒数，是从一条扫描线走到下一条扫描线时，按描线时，按x方向递增的步长。方向递增的步长。4.边所属多边形的标记。

31、边所属多边形的标记。第50页，共90页，编辑于2022年，星期一 设有两个空间的三角形设有两个空间的三角形ABC、DEF,各各顶点的坐标依次是顶点的坐标依次是（1,1,10）,（2,5,10）,（5,3,10）,（3,4,5）,（4,6,5）,（6,2,5）.ABCDEF两个多边形两个多边形在在zv=0平面上平面上的投影的投影 第51页，共90页，编辑于2022年，星期一两个多边形建立的两个多边形建立的“吊桶吊桶”已排序的边表已排序的边表 2第52页，共90页，编辑于2022年，星期一图图7.21第53页，共90页，编辑于2022年，星期一 还还需需要要一一个个多多边边形形表表PT(polyg

32、onTable)，其其中中要包含下列信息：要包含下列信息：1每每个个多多边边形形所所在在平平面面方方程程的的系系数数。在在需需要要比比较较深深度度时时，要要通通过过对对所所在在（x,y），根根据据平平面面方方程程解解出出深度深度z。2每每个个多多边边形形的的亮亮度度或或颜颜色色值值。实实际际做做扫扫描描转转换换时应用。时应用。3一一个个“进进入入退退出出”标标志志，初初值值为为“假假”。在在扫扫描描转转换换处处理理时时，用用以以标标记记扫扫描描线线对对该该多多边边形形是是“进入进入”，还是，还是“退出退出”。象在多边形填充的扫描线算法中一样，操象在多边形填充的扫描线算法中一样，操作通过一个活跃

33、边表作通过一个活跃边表AET进行。进行。第54页，共90页，编辑于2022年，星期一 通通过过以以上上的的讨讨论论，可可以以写写出出整整个个扫扫描描线算法实施的步骤。线算法实施的步骤。首首先先正正确确形形成成边边表表ET和和多多边边形形表表PT之之后后，实实施施步步骤骤就就与与第第二二章章叙叙述述的的多多边边形形填填充充的的扫扫描描线线算算法法的的实实施施步步骤骤基基本本相相同同，只只是是需需要要把把那那里里的的步步骤骤:在在扫扫描描线线y上上，按按照照AET表表提提供供的的x坐标对，用坐标对，用color实施填充修改加细如下：实施填充修改加细如下：第55页，共90页，编辑于2022年，星期一

34、1 1 将将实实施施扫扫描描转转换换时时遍遍查查AET表表中中各各“吊吊桶桶”的的指指针针i初初始始置置为为1，扫扫描描线线正正在在多多少少个个多多边边形形内内的的累累计计数数值值s初初始始置置为为零零，将将活活跃跃多多边边形形表表，即即扫扫描描线线正正在在通通过过的的多多边边形形按按深深度度递递增增次次序序排排列列而而形形成成的的表表，记记为为p，初初始始置为空置为空。2设设第第i个个“吊吊桶桶”记记录录的的相相应应多多边边形形是是A。若若A的的“进进入入/退退出出”标标记记FA为为“假假”，则则改改FA为为“真真”，将将A加加到到表表P的的前前面面，s增增加加1。否否则则，FA即即为为“真

35、真”，则则改改FA为为“假假”，将将P中的中的A去去掉，掉，s减少减少1。第56页，共90页，编辑于2022年，星期一 3 3 若若s=0，则到，则到5。（这时扫描线不在任。（这时扫描线不在任何多边形内，正通过背景，不必做扫描转何多边形内，正通过背景，不必做扫描转换。）若换。）若s=1，则到，则到4（这时扫描线只在一（这时扫描线只在一个多边形内，不必做深度比较，去做扫描个多边形内，不必做深度比较，去做扫描转换。）若前面两个判断都为转换。）若前面两个判断都为“假假”，扫，扫描线至少在两个多边形内，应做深度比较。描线至少在两个多边形内，应做深度比较。对表对表P前面两个多边形做深度比较，比较后前面两

36、个多边形做深度比较，比较后放回应保证放回应保证P表中的多边形按深度递增的次表中的多边形按深度递增的次序。序。4对第对第i个和第个和第i+1个个“吊桶吊桶”存有的存有的x坐标指坐标指示的扫描线上的一段，按照示的扫描线上的一段，按照P表最前面多边表最前面多边形指示的亮度或颜色，实施扫描转换。形指示的亮度或颜色，实施扫描转换。第57页，共90页，编辑于2022年，星期一5 5 i增加增加1，若，若i所指已无所指已无“吊桶吊桶”，步骤结束，步骤结束，去下一步骤（去下一步骤（删除删除y=ymax的边的边）。否则，）。否则，回到步骤回到步骤2。在扫描线。在扫描线y=4，实施前面步骤的，实施前面步骤的各步骤

37、，情形如表各步骤，情形如表7.1所示。所示。第58页，共90页，编辑于2022年，星期一 i is s P PPTPT表表 FABC FABC FDEFFDEF 说明说明 1 11 1(ABC)(ABC)truetrue1 1 到到3 3填填ABCABC的亮度或颜色值的亮度或颜色值 2 22 2(DEF,(DEF,ABC)ABC)truetrue在在步步骤骤3 3发发生生深深度度比比较较，比比较较结结果果DEFDEF更更靠近观察者，它仍在靠近观察者，它仍在P P表前面，表前面，3 3到到3 3 填填DEFDEF的亮度或颜色值的亮度或颜色值 3 31 1(DEF)(DEF)falsefalse3

38、 3 到到5 5填填DEFDEF的亮度或颜色值的亮度或颜色值 4 40 0()()falsefalse第59页，共90页，编辑于2022年，星期一第60页，共90页，编辑于2022年，星期一 如果按照步骤如果按照步骤3的条件决定是否做深度比较，的条件决定是否做深度比较，会有许多深度比较是不必要的。例如，假定有会有许多深度比较是不必要的。例如，假定有一个大的多边形一个大的多边形GHIJ在两个三角形在两个三角形ABC和和DEF的后面。在扫描线的后面。在扫描线y=离开边离开边CB时，按步时，按步骤骤3的条件判断，扫描线还同时在的条件判断，扫描线还同时在DEF和和GHIJ中，应该做深度比较，但是在大多

39、数可以假定中，应该做深度比较，但是在大多数可以假定没有多边形穿透另一个多边形的情况下没有多边形穿透另一个多边形的情况下，DEF和和GHIJ的深度关系并没有变化，深度比较是的深度关系并没有变化，深度比较是不必要的。不必要的。如果扫描线从一个如果扫描线从一个被遮挡被遮挡的多边形的多边形中走出，深度比较将是中走出，深度比较将是不必要不必要的；的；扫描线从一扫描线从一个个遮挡遮挡了其它多边形的多边形中走出，深度比了其它多边形的多边形中走出，深度比较才可能较才可能必要必要。第61页，共90页，编辑于2022年，星期一三个多边形三个多边形第62页，共90页，编辑于2022年，星期一 事实上前面给出的算法基

40、本步骤没有很好地利用事实上前面给出的算法基本步骤没有很好地利用深度的相关性。深度的相关性。深度相关性是指多个多边形之间的深深度相关性是指多个多边形之间的深度关系，常常对于一组相邻的扫描线来说是不变化的。度关系，常常对于一组相邻的扫描线来说是不变化的。如果在某条扫描线上，在如果在某条扫描线上，在AET表中保存的边及次序表中保存的边及次序关系，与在前面一条扫描线上时完全相同，那么深关系，与在前面一条扫描线上时完全相同，那么深度关系就不会变化，深度比较也就并不必要了。例度关系就不会变化，深度比较也就并不必要了。例如，图如，图7.21中的扫描线中的扫描线r+1到到r+2就是这种情形，在就是这种情形，在

41、两条扫描线上两条扫描线上AET表中的边及次序关系都是表中的边及次序关系都是AB，CB，DE，FE。但从。但从r到到r+1，DE，CB的次序要变的次序要变化为化为CB，DE，次序关系就变化了。利用深度的相，次序关系就变化了。利用深度的相关性可以对算法作出改进。关性可以对算法作出改进。第63页，共90页，编辑于2022年，星期一 上图所示是一个多边形穿透了另一个多边形。为使算法能处上图所示是一个多边形穿透了另一个多边形。为使算法能处理这种情况，应该把其中的多边形理这种情况，应该把其中的多边形KLM分成两个多边形分成两个多边形KLLM和和LMM，加进了一条没有的边，加进了一条没有的边ML。或者修改算

42、法，。或者修改算法，使能够在逐条扫描线的处理进行中，发现扫描线上的穿透点。使能够在逐条扫描线的处理进行中，发现扫描线上的穿透点。第64页，共90页，编辑于2022年，星期一 关于关于背景背景的处理，最简单的办法是把更的处理，最简单的办法是把更新缓冲存储器整个初始化为某个合适的值，新缓冲存储器整个初始化为某个合适的值，于是算法就只需处理扫描线在多边形内的于是算法就只需处理扫描线在多边形内的情形。另一个办法是，定义一个大的矩形，情形。另一个办法是，定义一个大的矩形，让他包含了客体中所有的多边形，位于比让他包含了客体中所有的多边形，位于比其它多边形都更远离观察者的平行于投影其它多边形都更远离观察者的

43、平行于投影平面的一个平面上，并具有某个合适的亮平面的一个平面上，并具有某个合适的亮度或颜色值。再一个办法就是修改算法。度或颜色值。再一个办法就是修改算法。使得每当扫描线不在任何多边形内时，就使得每当扫描线不在任何多边形内时，就往帧缓冲存储器中送入背景的象素值。往帧缓冲存储器中送入背景的象素值。第65页，共90页，编辑于2022年，星期一第七节第七节 区域分割算法区域分割算法 区域分割算法区域分割算法将投影平面分割成区域将投影平面分割成区域，考，考察区域内的图象。如果容易决定在这个区域察区域内的图象。如果容易决定在这个区域内某些多边形是可见的，那么就可以显示那内某些多边形是可见的，那么就可以显示

44、那些可见的多边形，完成对这一区域的显示任些可见的多边形，完成对这一区域的显示任务。否则，就将区域再分割成小的区域，对务。否则，就将区域再分割成小的区域，对小的区域递归地进行判断。由于区域逐渐变小的区域递归地进行判断。由于区域逐渐变小，在每个区域内的多边形逐渐变少，最终小，在每个区域内的多边形逐渐变少，最终总可以判定哪些多边形是可见的。这个算法总可以判定哪些多边形是可见的。这个算法利用的利用的区域的相关性区域的相关性，这种相关性，这种相关性是指位于适是指位于适当大小的区域内的所有象素，表示的其实是当大小的区域内的所有象素，表示的其实是同一个表面。同一个表面。第66页，共90页，编辑于2022年，

45、星期一 在在递递归归分分割割的的每每一一步步，要要显显示示客客体体中中每每个个多多边边形形的的投投影影多多边边形形与与所所考考察察区区域域之之间间的的关关系系，必然是下列四种之一：必然是下列四种之一：1.1.包围的多边形，即多边形包含了所考察包围的多边形，即多边形包含了所考察 的区域的全部。的区域的全部。2.2.相交的多边形，即多边形与所考察的区相交的多边形，即多边形与所考察的区 域相交。域相交。3.3.被包含的多边形被包含的多边形,即多边形全部在所即多边形全部在所 考察的区域之内。考察的区域之内。4.4.分离的多边形，即多边形与所考察的分离的多边形，即多边形与所考察的 区域完全分离。区域完全

46、分离。第67页，共90页，编辑于2022年，星期一 包围的包围的 相交的相交的 被包含的被包含的 分离的分离的第68页，共90页，编辑于2022年，星期一 若若区区域域与与多多边边形形为为下下面面的的四四种种情情况况，不不必必再做进一步的分割，可直接绘制。再做进一步的分割，可直接绘制。1 1所所有有的的多多边边形形与与区区域域分分离离，在在区区域域内内只只需显示背景值。需显示背景值。2.2.只有只有一个相交一个相交的多边形，或者只有的多边形，或者只有一个一个被包含被包含的多边形。这时可以对区域首先填充的多边形。这时可以对区域首先填充背景值，然后对多边形进行扫描转换。在某背景值，然后对多边形进行

47、扫描转换。在某些显示设备上，将整个帧缓冲存储器都初始些显示设备上，将整个帧缓冲存储器都初始化为背景值，可能更为方便。对于相交的多化为背景值，可能更为方便。对于相交的多边形，只是被包含的部分被扫描转换。边形，只是被包含的部分被扫描转换。第69页，共90页，编辑于2022年，星期一 3.3.只只有有一一个个包包围围的的多多边边形形，无无其其它它的的多多边边形。整个区域填充该多边形的象素值。形。整个区域填充该多边形的象素值。4.4.有多于一个的包围的、相交的或被包有多于一个的包围的、相交的或被包含的多边形，且至少有一个包围的多边形。含的多边形，且至少有一个包围的多边形。检查是否能有一个包围的多边形，

48、它位于所检查是否能有一个包围的多边形，它位于所有其它多边形的前面。如果有，就可以让整有其它多边形的前面。如果有，就可以让整个区域都填充为这个多边形的象素值。具体个区域都填充为这个多边形的象素值。具体的检查方法是，对所有的多边形，的检查方法是，对所有的多边形，计算其所计算其所在平面在区域的四个角点的应有深度在平面在区域的四个角点的应有深度，即相，即相应的应的z z坐标，如果有一个包围的多边形的相坐标，如果有一个包围的多边形的相应四个应四个z坐标，都小于其它多边形的对应坐标，都小于其它多边形的对应z z坐标，那么这个包围的多边形就位于所有坐标，那么这个包围的多边形就位于所有其它多边形的前面。其它多

49、边形的前面。第70页，共90页，编辑于2022年，星期一情形情形4 4的两种情形的两种情形第71页，共90页，编辑于2022年，星期一 区区域域经经过过分分割割变变小小以以后后，只只需需要要考考虑虑包包含含的多边形和相交的多边形的变化的多边形和相交的多边形的变化。因因为为分分离离的的或或包包围围的的多多边边形形，对对变变小小的的区区域域，仍仍然然保保持持是是分分离离的的或或包包围围的的。分分割割进进行行到到达达到到显显示示设设备备的的分分辨辨能能力力之之后后就就可可以以停停止止，即即最最小小的的区区域域可可以以是是显显示示表表面面上上的的一一个个象象素素单单位位。如如果果在在做做了了准准备备做

50、做的的最最大大数数目目的的分分割割之之后后，仍仍然然不不能能做做出出应应该该如如何何填填充充的的决决定定，那那么么，就就计计算算所所有有有有关关多多边边形形在在这这个个不不可可再再分分区区域域对对应应的的点点的的范范围围的的中中心心处处的的z坐坐标标值值，取取z z坐坐标标最最小小的的多多边边形形象象素素值值填填充充这这个个区区域。域。第72页，共90页，编辑于2022年，星期一 Warnock首先提出的最初的区域首先提出的最初的区域分割算法是每次把区域分成四个正方分割算法是每次把区域分成四个正方形。下图所示是对一个投影是一个三形。下图所示是对一个投影是一个三角形和一个长方体的场景，做了角形和