图形学教案第七章消除隐藏线和隐藏面(精品).ppt

《图形学教案第七章消除隐藏线和隐藏面(精品).ppt》由会员分享，可在线阅读，更多相关《图形学教案第七章消除隐藏线和隐藏面(精品).ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 消除隐藏线和隐藏消除隐藏线和隐藏面的算法面的算法 消隐消隐 面消隐面消隐 线消隐线消隐三维形体表示为三维形体表示为多边形多边形表面形集合表面形集合投影约定为沿着投影约定为沿着z z轴正向的轴正向的正交正交投影投影消除隐藏面算法：消除隐藏面算法：图象空间算法图象空间算法 客体空间算法客体空间算法 图象空间算法对显示设备上每一个图象空间算法对显示设备上每一个可分辨可分辨象素象素进行判断，看组成物体进行判断，看组成物体的多个多边形表面中哪一个在该象的多个多边形表面中哪一个在该象素上可见，即要对每一象素检查所素上可见，即要对每一象素检查所有的表面。有的表面。客体空间算法把注意力集中在分析

2、客体空间算法把注意力集中在分析要显示要显示形体形体各部分之间的关系上，各部分之间的关系上，这种算法对每一个组成形体的表面，这种算法对每一个组成形体的表面，都要与其它各表面进行比较，以便都要与其它各表面进行比较，以便消去不可见的面或面的不可见部分。消去不可见的面或面的不可见部分。第一节第一节 线面比较法消除隐藏线线面比较法消除隐藏线 多面体的面可见性多面体的面可见性 凸多面体的可见面就是朝向观察位凸多面体的可见面就是朝向观察位置的面置的面 设观察方向由设观察方向由指向观察位置指向观察位置的一的一个方向向量个方向向量k k给出，所考查的面的外法给出，所考查的面的外法向量是向量是n n，则这两个向量

3、的夹角则这两个向量的夹角 满满足足0 0 /2/2时，所考查面是可见时，所考查面是可见的，否则就是不可见的的，否则就是不可见的 把把n n和和k k记作记作 则则分子分子 为为正正 ，则则 ,面为可见；若为面为可见；若为负负，则，则 ，面为，面为不可见；若为不可见；若为零零，则，则 ，此面退化为，此面退化为线。线。设空间有一个四面体，顶点设空间有一个四面体，顶点A A，B B，C C，D D的坐标依次是（的坐标依次是（0 0，0 0，0 0），），（2 2，0 0，1 1），（），（4 4，0 0，0 0）,(3,2,1),(3,2,1)从从z z轴正向无穷远处观察轴正向无穷远处观察,求各面的

4、可求各面的可见性见性 观察方向向量是观察方向向量是k=(0,0,1),k=(0,0,1),三角三角面面DABDAB的法向量是的法向量是:因此因此,，面，面DABDAB为可见面为可见面.类似类似计算可知，面计算可知，面DBCDBC是可见面是可见面,面面ADCADC是不可是不可见面见面,面面ACBACB退化为线。退化为线。利用外法线就可以判断凸多面体上利用外法线就可以判断凸多面体上各表面的可见性，由此就能解决对单个各表面的可见性，由此就能解决对单个凸多面体的隐藏线和隐藏面的消除问题。凸多面体的隐藏线和隐藏面的消除问题。消除消除隐藏线隐藏线的线面比较法的最先一的线面比较法的最先一步就是利用外法线判断

5、出所有可能的可步就是利用外法线判断出所有可能的可见面，可能可见面上的线段是可能可见见面，可能可见面上的线段是可能可见线。线。要依次用每一条可能可见线，与每要依次用每一条可能可见线，与每一个可能可见面比较一个可能可见面比较，从而确定出可见，从而确定出可见线、隐藏线及可见线上的隐藏部分。线、隐藏线及可见线上的隐藏部分。可能可见线和可能可见面可能可见线和可能可见面 空间任一线段，只有其投影与多边空间任一线段，只有其投影与多边形表面的形表面的投影范围发生交迭投影范围发生交迭时，才可能时，才可能与多边形表面有遮档关系与多边形表面有遮档关系 一个多边形表面的投影范围一个多边形表面的投影范围 范围检查也称为

6、范围检查也称为最大最小检验最大最小检验，即通过，即通过比较有关的最大或最小值来判定范围的比较有关的最大或最小值来判定范围的交迭情形。交迭情形。按按XvXv方向对投影范围的检查，可分别方向对投影范围的检查，可分别计算出投影线段和多边形表面计算出投影线段和多边形表面投影范围投影范围X X坐标的最大值和最小值，设分别是坐标的最大值和最小值，设分别是 于是若于是若 或者或者 ,线线段和多边形表面就必然没有遮挡关系。段和多边形表面就必然没有遮挡关系。显然按显然按x xv v方向或按方向或按y yv v方向都可以类似地方向都可以类似地做范围检查，这时可避免消除隐藏面时很做范围检查，这时可避免消除隐藏面时很

7、多不必要的深度比较。多不必要的深度比较。z zv v方向的范围检查是沿方向的范围检查是沿z zv v方向观方向观察时察时粗略的深度检验粗略的深度检验。在此范围检查中若线段投影的最在此范围检查中若线段投影的最大大z z坐标坐标 小于多边形表面投影范小于多边形表面投影范围最小的围最小的z z坐标坐标 ，则线段完全，则线段完全在表面前面，根本不发生遮挡现象，在表面前面，根本不发生遮挡现象，可以不必再往下做精确的深度检验。可以不必再往下做精确的深度检验。精确深度检验精确深度检验 l2 线段可能被线段可能被遮挡遮挡;线段不会被线段不会被遮挡遮挡;求交点求交点 直线直线L L1 1的参数方程可写成的参数方

8、程可写成X=xX=x1 1，Y=yY=y1 1，Z=zZ=z1 1+t+t，代入平面方程得：代入平面方程得：若若t0,t0,则则Z Z1 1 ，若，若t t0,0,则则Z Z1 1 。需要检查出某一段子线段是否可见。为此可需要检查出某一段子线段是否可见。为此可以取子线段上任意一点，若这点在多边形表面各以取子线段上任意一点，若这点在多边形表面各边线的投影所形成的封闭多边形内，这子线段就边线的投影所形成的封闭多边形内，这子线段就不可见，否则就可见。不可见，否则就可见。空空间间一一条条线线段段可可能能被被一一个个多多边边形形表表面面遮遮挡挡的的消除隐藏线的算法的步骤如下：消除隐藏线的算法的步骤如下：

9、x xv v方向和方向和y yv v方向的方向的范围检查范围检查；若不能判断，；若不能判断，则接着做则接着做z zv v方向的范围检查即方向的范围检查即粗略的深度比较粗略的深度比较；若还不能判断就再进行若还不能判断就再进行精确的深度比较精确的深度比较，比较，比较时应计算线段两端点在可能遮挡它的平面上的时应计算线段两端点在可能遮挡它的平面上的投影点，比较相应的坐标。这时可能出现线段投影点，比较相应的坐标。这时可能出现线段与平面相交需要用与平面相交需要用交点交点，这些交点把线段的投，这些交点把线段的投影分成两部分考虑的情况。判断得知线段确实影分成两部分考虑的情况。判断得知线段确实被平面遮挡了哪些部

10、分做精确计算，计算是求被平面遮挡了哪些部分做精确计算，计算是求出线段的投影与遮挡平面上多边形表面边框投出线段的投影与遮挡平面上多边形表面边框投影的所有交点，这些交点把线段的投影分成可影的所有交点，这些交点把线段的投影分成可见和不可见的一些子线段。对见和不可见的一些子线段。对子线段子线段的可见性，的可见性，先取上面一点做点的先取上面一点做点的包含性包含性检验来进行判断。检验来进行判断。第二节第二节 曲面隐藏线消除的浮动曲面隐藏线消除的浮动水平线算法水平线算法 建立建立M M个象素，则建立个象素，则建立M M个内个内存单元存单元y yu u(j)(j)称之为上浮水平线数称之为上浮水平线数组，在这些

11、单元中先放上初值，组，在这些单元中先放上初值，初值应取成小于初值应取成小于 。曲面方程曲面方程设设平平面面是是最最靠靠近近观观察察者者的，从平面上的，从平面上的曲线的曲线 水平方向每个象素的对应水平方向每个象素的对应x x坐坐标值，计算标值，计算 若若 ，则点，则点 是是可见点，并把可见点，并把 内容成内容成 。若若 ，则，则 为不可见，为不可见，就不要改变就不要改变 的内容了。的内容了。上图上图c c点附近的线虚部分应是可见点附近的线虚部分应是可见的，但按上述算法却成了不可见了。的，但按上述算法却成了不可见了。为了解决这个问题，可另建立为了解决这个问题，可另建立M M个单个单元元 ，可称之为

12、下浮水平线数组。，可称之为下浮水平线数组。初值取成初值取成 或比这更大或比这更大一点得数，每次求出一点得数，每次求出 IfthenIfthen 如果函数如果函数 是用离散点形式是用离散点形式 给出，则可如下处给出，则可如下处理。这时的理。这时的 单元个数不是由单元个数不是由显示器在显示器在x x方向的象素个数来定，而是根方向的象素个数来定，而是根据给定的离散点在据给定的离散点在x x方向的个数来定方向的个数来定。基本想法是用线性插值法所得直线基本想法是用线性插值法所得直线来代替两个点之间的曲线。若上述判断来代替两个点之间的曲线。若上述判断结果为结果为 均为不可见，均为不可见，则认为平面则认为平

13、面 上的从上的从 的的一段曲线为不可见。若两点均为可见，一段曲线为不可见。若两点均为可见，则用这两点的连线代替原来这两点之间则用这两点的连线代替原来这两点之间的曲线，并认为可见的，若这两点中有的曲线，并认为可见的，若这两点中有一点可见，如图的一点可见，如图的A A点，另一点则为不可点，另一点则为不可见，如图中的见，如图中的B B点，这时要求出点连线的点，这时要求出点连线的交点交点E E。AEAE部分为可见，部分为可见，EBEB为不可见。为不可见。ABCDE 一般用一般用 两族两族曲线来表示一曲面时常用斜投影。曲线来表示一曲面时常用斜投影。为了得到消隐后曲面表示，不为了得到消隐后曲面表示，不能对

14、两族曲线分别消隐在叠加在一能对两族曲线分别消隐在叠加在一起，正确的做法是对两族曲线一起起，正确的做法是对两族曲线一起做，即处理好平面一段曲线后，马做，即处理好平面一段曲线后，马上处理平面的一段曲线。上处理平面的一段曲线。X=XkZ=ZiB第三节第三节 深度排序算法深度排序算法 深度排序算法的主要步骤：深度排序算法的主要步骤：1.1.把把所所有有的的多多边边形形按按顶顶点点最最大大z z坐坐标标值值进行排序。进行排序。2.2.解解决决当当多多边边形形z z范范围围发发生生交交迭迭时时出出现现的不明确问题。的不明确问题。3.3.按最大按最大z z坐标值逐渐减小的次序，对坐标值逐渐减小的次序，对每个

15、多边形进行扫描转换。每个多边形进行扫描转换。算法的基本思想是按多边形离算法的基本思想是按多边形离开观察位置的开观察位置的距离距离进行排序，然后进行排序，然后按照按照距离减少距离减少的次序，把每个多边的次序，把每个多边形内部点应有的象素值送入帧缓存形内部点应有的象素值送入帧缓存存贮器中。存贮器中。算法考查多边形的深度次序是算法考查多边形的深度次序是在客体空间中进行，图形显示时覆在客体空间中进行，图形显示时覆盖步骤是在图象空间中实现，所以盖步骤是在图象空间中实现，所以可以说是一个可以说是一个客体空间和图象空间客体空间和图象空间的混合算法。的混合算法。不明确问题检验方法不明确问题检验方法 所有多边形

16、按顶点最大所有多边形按顶点最大z z坐标值坐标值排序后得到一个排序表，设排序后得到一个排序表，设P P是排在是排在表中最后的那个多边形。表中最后的那个多边形。设设Q Q是排在是排在P P前面并且前面并且z z坐标范围坐标范围与其发生交迭的一个多边形，对与其发生交迭的一个多边形，对Q Q与与P P的次序关系进行检查。的次序关系进行检查。检查可以按下面列出的五个步检查可以按下面列出的五个步骤进行，每个步骤判断一种情况。骤进行，每个步骤判断一种情况。1 1多多边边形形的的x x坐坐标标范范围围不不相相交交迭迭，所所以以多边形不相交迭。多边形不相交迭。2 2多多边边形形的的y y坐坐标标范范围围不不相

17、相交交迭迭，所所以以多边形不相交迭。多边形不相交迭。3.P3.P整个在整个在Q Q远离观察点的一侧。远离观察点的一侧。4.Q4.Q整个在整个在P P的靠近观察点的一侧。的靠近观察点的一侧。5.5.多多边边形形在在z=0z=0平平面面上上的的投投影影本本身身不不相相交迭。交迭。如果所有这五步检查都为假，就假如果所有这五步检查都为假，就假定定P P是遮挡了是遮挡了Q Q，交换交换P P和和Q Q在排序表中的在排序表中的位置。位置。如果仍做交换，算法会永远循环下如果仍做交换，算法会永远循环下去而没有结果。去而没有结果。为了避免循环，可以做一个限制。为了避免循环，可以做一个限制。当做过首次五步检查后，

18、发生某个多边当做过首次五步检查后，发生某个多边形被移到排序表的末尾时，就立即加上形被移到排序表的末尾时，就立即加上一个标记，以后就不能再做移动。出现一个标记，以后就不能再做移动。出现再次应该移动时，用一个多边形再次应该移动时，用一个多边形所在的平面，把另一个多边形剪裁分所在的平面，把另一个多边形剪裁分为两个。为两个。PQ/第四节第四节 画家算法画家算法 画家算法又称深度优先级表画家算法又称深度优先级表法，它是深度排序算法的一种具法，它是深度排序算法的一种具体实现。体实现。先画远景，再画中景，最后先画远景，再画中景，最后画近景。画近景。810011011110100001001100161234

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

20、屏幕）坐标。面记录由四个域组成，每个域存放对应的顶点号。排序数组的每个元素有两存放对应的顶点号。排序数组的每个元素有两个域，其中一个域存放面与视点的距离，另一个域，其中一个域存放面与视点的距离，另一个域存放该面的面号。个域存放该面的面号。ReadkeyboardReadkeyboard：打打开开物物体体的的边边界界表表示示数数据据文文件件，从从键键盘盘读读进进旋旋转转角角和和透透视视角角，物物体体表表面面的颜色参数（色彩和饱和度），光源方向。的颜色参数（色彩和饱和度），光源方向。Vertices：读读进进顶顶点点的的空空间间坐坐标标，计计算算物物体体的的包包围围球球半半径径，把把物物体体缩缩小

21、小到到单单位位球球中中去去，计算物体各顶点在屏幕上的投影坐标。计算物体各顶点在屏幕上的投影坐标。开始开始Patches：读读进进面面定定义义数数据据，求求出出各各面面与与视视点点的的距距离离，把把面面号号与与距距离离放放进进排排序序数数组组。然然后后以以面面与与视视点点的的距距离离为为参参照照值值，对对数数组组进进行行排排序。序。Gmode：使使终终端端进进入入图图形形状状态，设备参数初始化态，设备参数初始化Setpen：建立查色表建立查色表Painting：从从排排好好序序的的数数组组中中依依次次取取出出一一面面号号，计计算算对对应应面面的的法法向向量量，再再计计算算该该面面的的光光强，然后

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

23、，值。对每一个多边形，不不必必进行深度排序算法要求的进行深度排序算法要求的初始排序初始排序，立，立即就可以逐个进行扫描转换。即就可以逐个进行扫描转换。扫扫描描转转换换时时，对对每每个个多多边边形形内内部部的的任任意意点点（x,yx,y）,实施如下步骤：实施如下步骤：1 1 计计算算在在点点（x x，y y）处处多多边边形形的的深深度度值值z z（x x，y y）。）。2 2如如果果计计算算所所得得的的z z（x x，y y）值值，小小于于在在z z 缓缓冲冲存存储储器器中中点点 x x y y 处处记记录录的的深深度度值值，那那么么就做：就做：（1 1）把把值值z z x x y y 送送入入

24、z z 缓缓冲冲存存储储器的点处。器的点处。（2 2）把多边形在深度）把多边形在深度z(xz(x y y 处应有的象处应有的象素值，送入更新缓冲存储器的点素值，送入更新缓冲存储器的点 x x y y 处。处。算法中深度计算，可通过多边形的算法中深度计算，可通过多边形的顶点坐标求出所在平面的方程，然后再顶点坐标求出所在平面的方程，然后再使用平面方程，对每个点使用平面方程，对每个点 x x y y，解出相解出相应的应的z z。对面方程对面方程 ，解出解出 是：是：设在点（设在点（x,yx,y）处的深度值是处的深度值是z z1 1:则在点（则在点（x+x,yx+x,y）处的深度值就是处的深度值就是z

25、 z 缓冲算法的工作流程：缓冲算法的工作流程：帧缓冲区置成背景色；帧缓冲区置成背景色；z z 缓冲区置成最小缓冲区置成最小z z值；值；for(for(各个多边形各个多边形)扫描转换该多边形；扫描转换该多边形；for(for(计算多边形所覆盖的每个象素（计算多边形所覆盖的每个象素（x,yx,y）)计算多边形在该象素的深度值计算多边形在该象素的深度值Z(x,y)Z(x,y)；if(Z(x,y)if(Z(x,y)大于大于Z Z缓冲区中的缓冲区中的(x,y)(x,y)处的值处的值)把把Z(x,y)Z(x,y)存入存入Z Z缓冲区中的缓冲区中的(x,y)(x,y)处；处；把把多多边边形形在在(x,y)

26、(x,y)处处的的亮亮度度值值存存入入帧帧缓缓存存区的区的(x,y)(x,y)处；处；第六节第六节 扫描线算法扫描线算法 扫扫描描线线算算法法是是图图象象空空间间算算法法，它它建建立立图图象象是是通通过过每每次次处处理理一一条条扫扫描描线线来来完完成成的的。这这个个算算法法是是第第二二章章讨讨论论的的多多边边形形填填充充的的扫扫描描线线算算法法的的推推广广。在在多多边边形形填填充充的的扫扫描描线线算算法法中中，只只是是对对一一个个多多边边形形做做扫扫描描转转换换，而而这这里里是是同同时时对对多多个个多多边边形形做做扫扫描描转换。转换。要要建建立立一一个个边边表表ETET。ETET中中各各登登记

27、记项项按按边边的的较较小小的的y y坐坐标标递递增增排排列列；每每一一登登记记项项下下的的“吊吊桶桶”，按按所所记记x x坐坐标标递递增增排列。排列。“吊桶吊桶”中各项的内容依次是：中各项的内容依次是：1 1与与较较小小的的y y坐坐标标对对应应的的端端点点的的x x坐坐标标xminxmin。2 2 边的另一端点的较大的边的另一端点的较大的y y坐标坐标ymaxymax。3 3x x的的增增量量xx，它它实实际际上上是是边边的的斜斜率率的的倒倒数数，是是从从一一条条扫扫描描线线走走到到下下一一条条扫描线时，按扫描线时，按x x方向递增的步长。方向递增的步长。4.4.边所属多边形的标记。边所属多

28、边形的标记。设有两个空间的三角形设有两个空间的三角形ABCABC、DEF,DEF,各各顶点的坐标依次是（顶点的坐标依次是（1 1，1 1，1010），（），（2 2，5 5，1010），（），（5 5，3 3，1010），（），（3 3，4 4，5 5），（），（4 4，6 6，5 5），（），（6 6，2 2，5 5）。）。ABCDEF两个多边形两个多边形在在z zv v=0=0平面平面上的投影上的投影 两个多边形建立的两个多边形建立的“吊桶吊桶”已排序的边表已排序的边表 图图7.21 需要建立一个多边形表PT(polygon Table)，其中要包含下列信息：1每个多边形所在平面方程的系数

29、。在需 要 比 较 深 度 时，要 通 过 对 所 在（x,y），根据平面方程解出深度z。2每个多边形的亮度或颜色值。实际做扫描转换时应用。3.一个“进入退出”标志，初值为“假”。在扫描转换处理时，用以标记扫描线对该多边形是“进入”，还是“退出”。通通过过以以上上的的讨讨论论，可可以以写写出出整整个个扫扫描描线算法实施的步骤。线算法实施的步骤。首首先先正正确确形形成成边边表表ETET和和多多边边形形表表PTPT之之后后，实实施施步步骤骤就就与与第第二二章章叙叙述述的的多多边边形形填填充充的的扫扫描描线线算算法法的的实实施施步步骤骤基基本本相相同同，只只是是需需要要把把那那里里的的步步骤骤:在在

30、扫扫描描线线y y上上，按按照照AETAET表表提提供供的的x x坐坐标标对对，用用colorcolor实实施施填填充充修改加细如下：修改加细如下：1 1 将将实实施施扫扫描描转转换换时时遍遍查查AETAET表表中中各各“吊吊桶桶”的的指指针针i i初初始始置置为为1 1，扫扫描描线线正正在在多多少少个个多多边边形形内内的的累累计计数数值值s s初初始始置置为为零零，将将活活动动多多边边形形表表，即即扫扫描描线线正正在在通通过过的的多多边边形形按按深深度度递递增增次次序序排排列列而而形形成成的的表表，记记为为p p，初始置为空。初始置为空。2 2 设设第第i i个个“吊吊桶桶”记记录录的的相相

31、应应多多边边形形是是A A。若若A A的的“进进入入/退退出出”标标记记FAFA为为“假假”，则则改改FAFA为为“真真”，将将A A加加到到表表P P的的前前面面，s s增增加加1 1。否否则则，FAFA即即为为“真真”，则则改改FAFA为为“假假”，将，将P P中的中的A A去掉，去掉，s s减少减少1 1。3 3 若若s=0s=0，则到则到5 5。（这时扫描线不在。（这时扫描线不在任何多边形内，正通过背景，不必做扫任何多边形内，正通过背景，不必做扫描转换。描转换。）若）若s=1s=1，则到则到4 4（这时扫描线（这时扫描线只在一个多边形内，不必做深度比较，只在一个多边形内，不必做深度比较

32、，去做扫描转换。）若前面两个判断都为去做扫描转换。）若前面两个判断都为“假假”，扫描线至少在两个多边形内，扫描线至少在两个多边形内，应做深度比较。对表应做深度比较。对表P P前面两个多边形前面两个多边形做深度比较，比较后放回应保证做深度比较，比较后放回应保证P P表中表中的多边形按深度递增的次序。的多边形按深度递增的次序。4 4 对第对第i i个和第个和第i+1i+1个个“吊桶吊桶”存有的存有的x x坐标指示的扫描线上的一段，按照坐标指示的扫描线上的一段，按照P P表表最前面多边形指示的亮度或颜色，实施最前面多边形指示的亮度或颜色，实施扫描转换。扫描转换。5 i5 i增加增加1 1，若，若i

33、i所指已无所指已无“吊桶吊桶”，步骤，步骤结束，去下一步骤（结束，去下一步骤（删除删除y=ymaxy=ymax的边的边）。）。否则，回到步骤否则，回到步骤2 2。在扫描线。在扫描线y=4y=4，实施实施前面步骤的各步骤，情形如表前面步骤的各步骤，情形如表7.17.1所示。所示。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发发生生深深度度比比较较，比比较较结结果果DEF

34、DEF更更靠近观察者，它仍在靠近观察者，它仍在P P表前面，表前面，3 3到到3 3 填填DEFDEF的亮度或颜色值的亮度或颜色值 3 31 1(DEF(DEF)falsfalse e3 3 到到5 5填填DEFDEF的亮度或颜色值的亮度或颜色值 4 40 0()falsfalse e 如果按照步骤如果按照步骤3 3的条件决定是否做深度的条件决定是否做深度比较，会有许多深度比较是不必要的。例比较，会有许多深度比较是不必要的。例如，假定有一个大的多边形如，假定有一个大的多边形GHIJGHIJ在两个三在两个三角形角形ABCABC和和DEFDEF的后面。在扫描线的后面。在扫描线y=y=离开离开边边C

35、BCB时，按步骤时，按步骤3 3的条件判断，扫描线还同的条件判断，扫描线还同时在时在DEFDEF和和GHIJGHIJ中，应该做深度比较，但是中，应该做深度比较，但是在大多数可以假定在大多数可以假定没有多边形穿透另一个没有多边形穿透另一个多边形的情况下多边形的情况下，DEFDEF和和GHIJGHIJ的深度关系并的深度关系并没有变化，深度比较是不必要的。没有变化，深度比较是不必要的。如果扫如果扫描线从一个描线从一个被遮挡被遮挡的多边形中走出，深度的多边形中走出，深度比较将是比较将是不必要不必要的；的；扫描线从一个扫描线从一个遮挡遮挡了了其它多边形的多边形中走出，深度比较才其它多边形的多边形中走出，

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

37、图7.217.21中的扫描线中的扫描线r+1r+1到到r+2r+2就是这种就是这种情形，在两条扫描线上情形，在两条扫描线上AETAET表中的边及次序关表中的边及次序关系都是系都是ABAB，CBCB，DEDE，FEFE。但从但从r r到到r+1r+1，DEDE，CBCB的次序要变化为的次序要变化为CBCB，DEDE，次序关系就变化次序关系就变化了。利用深度的相关性可以对算法作出改进。了。利用深度的相关性可以对算法作出改进。上图所示是一个多边形穿透了另一个多边形。为使算上图所示是一个多边形穿透了另一个多边形。为使算法能处理这种情况，应该把其中的多边形法能处理这种情况，应该把其中的多边形KLMKLM

38、分成两个多分成两个多边形边形KLLMKLLM和和LMMLMM，加进了一条没有的边加进了一条没有的边MLML。或者修改算法，使能够在逐条扫描线的处理进行中，发现或者修改算法，使能够在逐条扫描线的处理进行中，发现扫描线上的穿透点。扫描线上的穿透点。关于背景的处理，最简单的办法是把关于背景的处理，最简单的办法是把更新缓冲存储器整个初始化为某个合适的更新缓冲存储器整个初始化为某个合适的值，于是算法就只需处理扫描线在多边形值，于是算法就只需处理扫描线在多边形内的情形。另一个办法是，定义一个大的内的情形。另一个办法是，定义一个大的矩形，让他包含了客体中所有的多边形，矩形，让他包含了客体中所有的多边形，位于

39、比其它多边形都更远离观察者的平行位于比其它多边形都更远离观察者的平行于投影平面的一个平面上，并具有某个合于投影平面的一个平面上，并具有某个合适的亮度或颜色值。再一个办法就是修改适的亮度或颜色值。再一个办法就是修改算法。使得每当扫描线不在任何多边形内算法。使得每当扫描线不在任何多边形内时，就往帧缓冲存储器中送入背景的象素时，就往帧缓冲存储器中送入背景的象素值。值。第七节第七节 区域分割算法区域分割算法 区域分割算法区域分割算法将投影平面分割成区域将投影平面分割成区域，考察区域内的图象。如果容易决定在这个考察区域内的图象。如果容易决定在这个区域内某些多边形是可见的，那么就可以区域内某些多边形是可见

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

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

42、的被包含的 分离的分离的 若若区区域域与与多多边边形形为为下下面面的的四四种种情情况况，不必再做进一步的分割，可直接绘制。不必再做进一步的分割，可直接绘制。1 1所所有有的的多多边边形形与与区区域域分分离离，所所以以在在区区域内只需显示背景值。域内只需显示背景值。2.2.只有一个相交的多边形，或者只有一只有一个相交的多边形，或者只有一个被包含的多边形。这时可以对区域首先个被包含的多边形。这时可以对区域首先填充背景值，然后对多边形进行扫描转换。填充背景值，然后对多边形进行扫描转换。在某些显示设备上，将整个帧缓冲存储器在某些显示设备上，将整个帧缓冲存储器都初始化为背景值，可能更为方便。对于都初始化

43、为背景值，可能更为方便。对于相交的多边形，只是被包含的部分被扫描相交的多边形，只是被包含的部分被扫描转换。转换。3.3.只只有有一一个个包包围围的的多多边边形形，无无其其它它的的多多边边形形。整个区域填充该多边形的象素值。整个区域填充该多边形的象素值。4.4.有多于一个的包围的、相交的或被包围的有多于一个的包围的、相交的或被包围的多边形，且至少有一个包围的多边形。检查是多边形，且至少有一个包围的多边形。检查是否能有一个包围的多边形，它位于所有其它多否能有一个包围的多边形，它位于所有其它多边形的前面。如果有，就可以让整个区域都填边形的前面。如果有，就可以让整个区域都填充为这个多边形的象素值。具体

44、的检查方法是，充为这个多边形的象素值。具体的检查方法是，对所有的多边形，对所有的多边形，计算其所在平面在区域的四计算其所在平面在区域的四个角点的应有深度个角点的应有深度，即相应的，即相应的z z坐标，如果有坐标，如果有一个包围的多边形的响应四个一个包围的多边形的响应四个z z坐标，都小于坐标，都小于其它多边形的对应其它多边形的对应z z坐标，那么这个包围的多坐标，那么这个包围的多边形就位于所有其它多边形的前面。边形就位于所有其它多边形的前面。情形情形4 4的两种情形的两种情形 区区域域经经过过分分割割变变小小以以后后，只只需需要要考考虑虑包含的多边形和相交的多边形的变化包含的多边形和相交的多边

45、形的变化。因因为为分分离离的的或或包包围围的的多多边边形形，对对变变小小的的区区域域，仍仍然然保保持持是是分分离离的的或或包包围围的的。分分割割进进行行到到达达到到显显示示设设备备的的分分辨辨能能力力之之后后就就可可以以停停止止，即即最最小小的的区区域域可可以以是是显显示示表表面面上上的的一一个个象象素素单单位位。如如果果在在做做了了准准备备做做的的最最大大数数目目的的分分割割之之后后，仍仍然然不不能能做做出出应应该该如如何何填填充充的的决决定定，那那么么，就就计计算算所所有有有有关关多多边边形形在在这这个个不不可可再再分分区区域域对对应应的的点点的的范范围围的的中中心心处处的的z z坐坐标标

46、值值，取取z z坐坐标标最最小小的的多多边形象素值填充这个区域。边形象素值填充这个区域。WanockWanock首先提出的最初的区首先提出的最初的区域分割算法是每次把区域分成四个域分割算法是每次把区域分成四个正方形。下图所示是对一个投影是正方形。下图所示是对一个投影是一个三角形和一个长方体的场景，一个三角形和一个长方体的场景，做了做了5 5次区域分割的情形，其中区次区域分割的情形，其中区域内标出的数字，表示可以作出决域内标出的数字，表示可以作出决定的前面所说的四种情形中的哪一定的前面所说的四种情形中的哪一种。没有标出数字的区域是还不能种。没有标出数字的区域是还不能做出决定。做出决定。分割区域为

47、正方形分割区域为正方形 区域分割不一定总是等分，当区域内有多区域分割不一定总是等分，当区域内有多边形的顶点时，可以按照顶点位置来做分割，边形的顶点时，可以按照顶点位置来做分割，这样显然可以少做一些分割。这样显然可以少做一些分割。围绕多边形顶围绕多边形顶点分割（先是点分割（先是A A，后是后是B B）区域分割还可以按照客体中多边形投区域分割还可以按照客体中多边形投影的范围进行，这可以少做很多分割。影的范围进行，这可以少做很多分割。WeilerWeiler和和AthertonAtherton提出的算法，直接就提出的算法，直接就用多边形的投影做为分割的区域。选择用用多边形的投影做为分割的区域。选择用

48、做分割的区域时，可以按照多边形各顶点做分割的区域时，可以按照多边形各顶点坐标最小值的递增次序坐标最小值的递增次序 按照多边形投影选择区域做分割按照多边形投影选择区域做分割/第八节第八节 BSPBSP树算法树算法 BSPBSP（binary binary space-partitioningspace-partitioning）树树算算法法将将表表面面由由后后往往前前地地在在屏屏幕幕上上绘绘出出，该该算算法法特特别别适适用用于于场场景景中中物物体体位位置置固固定定不不变、仅视点移动的情况。变、仅视点移动的情况。利用利用BSPBSP树来判别表面的可见性，其树来判别表面的可见性，其主要操作是在每次主

49、要操作是在每次分割空间分割空间时，判别该表时，判别该表面相对于视点与分割平面的位置关系，即面相对于视点与分割平面的位置关系，即位于其内侧还是位于其内侧还是外侧。外侧。平面平面P P1 1将空间分割为两部分，一组物体位于将空间分割为两部分，一组物体位于P P1 1的后面（相对于视点），而另一组则在的后面（相对于视点），而另一组则在P P1 1之前，而之前，而B B和和D D在在P P1 1之后。平面之后。平面P P2 2对空间进行了二次分割，并对空间进行了二次分割，并生成如图（生成如图（b b）所示的二叉树表示。在这棵树上，所示的二叉树表示。在这棵树上，物体用叶节点表示，分割平面前方的物体组作为

50、左物体用叶节点表示，分割平面前方的物体组作为左分支，而后方的物体组为右分支。分支，而后方的物体组为右分支。对于由多边形面组成的物体，对于由多边形面组成的物体，可以可以选择与多边形面重合的分割平面选择与多边形面重合的分割平面，利用，利用平面方程来区分平面方程来区分“内内”、“外外”多边形多边形顶点。随着将每个多边形面作为分割平顶点。随着将每个多边形面作为分割平面，可生成一棵树，面，可生成一棵树，与分割平面相交的与分割平面相交的每个多边形将被分割为两部分每个多边形将被分割为两部分。一旦。一旦BSPBSP树创建完毕，即可选择树上的面并树创建完毕，即可选择树上的面并由后往前显示，即前面物体覆盖后面的由