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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 消除隐藏线和隐藏面的算法,消隐 面消隐,线消隐,三维形体表示为,多边形,表面形集合,投影约定为沿着,z,轴正向的,正交,投影,消除隐藏面算法：,图象空间算法,客体空间算法,图象空间算法对显示设备上每一个可分辨,象素,进行判断，看组成物体的多个多边形表面中哪一个在该象素上可见，即要对每一象素检查所有的表面。,客体空间算法把注意力集中在分析要显示,形体,各部分之间的关系上，这种算法对每一个组成形体的表面，都要与其它各表面进行比较，以便消去不可见的面或面的不可见部分。,第一节 线面比较法消除隐藏线,多面体的面可见性,凸多面体的可见面就是朝向观察位置的面,设观察方向由,指向观察位置,的一个方向向量,k,给出，所考查的面的外法向量是,n,，,则这两个向量的夹角,满足,0,/2,时，所考查面是可见的，否则就是不可见的,把,n,和,k,记作 则,分子,为,正,，,则,面为可见；若为,负,，则 ，面为不可见；若为,零,，则 ，此面退化为线。,设空间有一个四面体，顶点,A,，,B,，,C,，,D,的坐标依次是（,0,，,0,，,0,），（,2,，,0,，,1,），（,4,，,0,，,0,）,(3,2,1),从,z,轴正向无穷远处观察,求各面的可见性,观察方向向量是,k=(0,0,1),三角面,DAB,的法向量是,:,因此,，面,DAB,为可见面,.,类似计算可知，面,DBC,是可见面,面,ADC,是不可见面,面,ACB,退化为线。,利用外法线就可以判断凸多面体上各表面的可见性，由此就能解决对单个凸多面体的隐藏线和隐藏面的消除问题。,消除,隐藏线,的线面比较法的最先一步就是利用外法线判断出所有可能的可见面，可能可见面上的线段是可能可见线。,要依次用每一条可能可见线，与每一个可能可见面比较,，从而确定出可见线、隐藏线及可见线上的隐藏部分。,可能可见线和可能可见面,空间任一线段，只有其投影与多边形表面的,投影范围发生交迭,时，才可能与多边形表面有遮档关系,一个多边形表面的投影范围,范围检查也称为,最大最小检验,，即通过比较有关的最大或最小值来判定范围的交迭情形。,按,Xv,方向对投影范围的检查，可分别计算出投影线段和多边形表面,投影范围,X,坐标的最大值和最小值，设分别是,于是若 或者 ,线段和多边形表面就必然没有遮挡关系。,显然按,x,v,方向或按,y,v,方向都可以类似地做范围检查，这时可避免消除隐藏面时很多不必要的深度比较。,z,v,方向的范围检查是沿,z,v,方向观察时,粗略的深度检验,。,在此范围检查中若线段投影的最大,z,坐标 小于多边形表面投影范围最小的,z,坐标 ，则线段完全在表面前面，根本不发生遮挡现象，可以不必再往下做精确的深度检验。,精确深度检验,l,2,线段可能被遮挡,;,线段不会被遮挡,;,求交点,直线,L,1,的参数方程可写成,X=x,1,，,Y=y,1,，,Z=z,1,+t,，,代入平面方程得：,若t0,则Z,1,，若t0,则Z,1,。,需要检查出某一段子线段是否可见。为此可以取子线段上任意一点，若这点在多边形表面各边线的投影所形成的封闭多边形内，这子线段就不可见，否则就可见。,空间一条线段可能被一个多边形表面遮挡的消除隐藏线的算法的步骤如下：,x,v,方向和,y,v,方向的,范围检查,；若不能判断，则接着做,z,v,方向的范围检查即,粗略的深度比较,；若还不能判断就再进行,精确的深度比较,，比较时应计算线段两端点在可能遮挡它的平面上的投影点，比较相应的坐标。这时可能出现线段与平面相交需要用,交点,，这些交点把线段的投影分成两部分考虑的情况。判断得知线段确实被平面遮挡了哪些部分做精确计算，计算是求出线段的投影与遮挡平面上多边形表面边框投影的所有交点，这些交点把线段的投影分成可见和不可见的一些子线段。对,子线段,的可见性，先取上面一点做点的,包含性,检验来进行判断。,第二节 曲面隐藏线消除的浮动水平线算法,建立,M,个象素，则建立,M,个内存单元,y,u,(j),称之为上浮水平线数组，在这些单元中先放上初值，初值应取成小于 。,曲面方程,设,平面 是最靠近观察者的，从平面上 的曲线,水平方向每个象素的对应,x,坐标值，计算,若 ，则点 是可见点，并把 内容成 。若 ，则 为不可见，就不要改变 的内容了。,上图,c,点附近的线虚部分应是可见的，但按上述算法却成了不可见了。为了解决这个问题，可另建立,M,个单元 ，可称之为下浮水平线数组。,初值取成 或比这更大一点得数，每次求出,If then,If then,如果函数 是用离散点形式,给出，则可如下处理。这时的 单元个数不是由显示器在,x,方向的象素个数来定，而是根据给定的离散点在,x,方向的个数来定,。,基本想法是用线性插值法所得直线来代替两个点之间的曲线。若上述判断结果为 均为不可见，则认为平面 上的从 的一段曲线为不可见。若两点均为可见，则用这两点的连线代替原来这两点之间的曲线，并认为可见的，若这两点中有一点可见，如图的,A,点，另一点则为不可见，如图中的,B,点，这时要求出点连线的交点,E,。,AE,部分为可见，,EB,为不可见。,A,B,C,D,E,一般用 两族曲线来表示一曲面时常用斜投影。,为了得到消隐后曲面表示，不能对两族曲线分别消隐在叠加在一起，正确的做法是对两族曲线一起做，即处理好平面一段曲线后，马上处理平面的一段曲线。,X=Xk,Z=Zi,B,第三节 深度排序算法,深度排序算法的主要步骤：,1.,把所有的多边形按顶点最大,z,坐标值进行排序。,2.,解决当多边形,z,范围发生交迭时出现的不明确问题。,3.,按最大,z,坐标值逐渐减小的次序，对每个多边形进行扫描转换。,算法的基本思想是按多边形离开观察位置的,距离,进行排序，然后按照,距离减少,的次序，把每个多边形内部点应有的象素值送入帧缓存存贮器中。,算法考查多边形的深度次序是在客体空间中进行，图形显示时覆盖步骤是在图象空间中实现，所以可以说是一个,客体空间和图象空间,的混合算法。,不明确问题检验方法,所有多边形按顶点最大,z,坐标值排序后得到一个排序表，设,P,是排在表中最后的那个多边形。,设,Q,是排在,P,前面并且,z,坐标范围与其发生交迭的一个多边形，对,Q,与,P,的次序关系进行检查。,检查可以按下面列出的五个步骤进行，每个步骤判断一种情况。,1,多边形的,x,坐标范围不相交迭，所以多边形不相交迭。,2,多边形的,y,坐标范围不相交迭，所以多边形不相交迭。,3.P,整个在,Q,远离观察点的一侧。,4.Q,整个在,P,的靠近观察点的一侧。,5.,多边形在,z=0,平面上的投影本身不相交迭。,如果所有这五步检查都为假，就假定,P,是遮挡了,Q,，,交换,P,和,Q,在排序表中的位置。,如果仍做交换，算法会永远循环下去而没有结果。,为了避免循环，可以做一个限制。当做过首次五步检查后，发生某个多边形被移到排序表的末尾时，就立即加上一个标记，以后就不能再做移动。出现再次应该移动时，用一个多边形,所在的平面，把另一个多边形剪裁分为两个。,P,Q,/,第四节 画家算法,画家算法又称深度优先级表法，它是深度排序算法的一种具体实现。,先画远景，再画中景，最后画近景。,8,1 0 0,1 1 0,1 1 1,1 0 1,0 0 0,0 1 0,0 1 1,0 0 1,6,1 2 3 4,2 6 7 3,6 5 8 7,5 1 4 8,4 3 7 8,5 6 2 1,边界表示,三元组表示物体顶点的坐标。,四元组表示物体的某个面由哪些顶点构成，每个面顶点个数都是,4,个。,程序中所使用的数据结构包括点记录（,vertex,）、,面记录（,patch,）,和排序数组。点记录由五个域构成。其中，三个域用于存储点的空间坐标，另外两个域用于存储点的投影（屏幕）坐标。面记录由四个域组成，每个域存放对应的顶点号。排序数组的每个元素有两个域，其中一个域存放面与视点的距离，另一个域存放该面的面号。,Readkeyboard,：,打开物体的边界表示数据文件，从键盘读进旋转角和透视角，物体表面的颜色参数（色彩和饱和度），光源方向。,Vertices,：,读进顶点的空间坐标，计算物体的包围球半径，把物体缩小到单位球中去，计算物体各顶点在屏幕上的投影坐标。,开始,Patches,：,读进面定义数据，求出各面与视点的距离，把面号与距离放进排序数组。然后以面与视点的距离为参照值，对数组进行排序。,Gmode,：,使终端进入图形状态，设备参数初始化,Setpen,：,建立查色表,Painting,：,从排好序的数组中依次取出一面号，计算对应面的法向量，再计算该面的光强，然后显示该面。,Amode,：,终端返回文字状态。,结束,第五节,z,缓冲算法,z,缓冲算法,(,深度缓冲算法,),是一种最简单的图象空间算法。对每一个点，这个算法不仅需要有一个,更新缓冲器,存储各点的象素值，而且还需要有一个,z,缓冲存储器,存储相应的,z,值。帧缓冲存储器初始化为背景值，,z,缓冲存储器初始化为可以表示的最大,z,值。对每一个多边形，,不必,进行深度排序算法要求的,初始排序,，立即就可以逐个进行扫描转换。,扫描转换时，对每个多边形内部的,任意点,（,x,y,）,实施如下步骤：,1,计算在点（,x,，,y,）,处多边形的深度值,z,（,x,，,y,）。,2,如果计算所得的,z,（,x,，,y,）,值，小于在,z,缓冲存储器中点,x,y,处记录的深度值，那么就做：,（,1,）把值,z,x,y,送入,z,缓冲存储器的点处。,（,2,）把多边形在深度,z(x,y,处应有的象素值，送入更新缓冲存储器的点,x,y,处。,算法中深度计算，可通过多边形的顶点坐标求出所在平面的方程，然后再使用平面方程，对每个点,x,y,，,解出相应的,z,。,对面方程 ，,解出 是：,设在点（,x,y,）,处的深度值是,z,1,:,则在点（,x+x,y,）,处的深度值就是,z,缓冲算法的工作流程：,帧缓冲区置成背景色；,z,缓冲区置成最小,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),处；,第六节 扫描线算法,扫描线算法是图象空间算法，它建立图象是通过每次处理,一条扫描线,来完成的。这个算法是第二章讨论的多边形填充的扫描线算法的推广。在多边形填充的扫描线算法中，只是对一个多边形做扫描转换，而这里是同时对,多个多边形,做扫描转换。,要建立一个边表,ET,。,ET,中各登记项按边的较小的,y,坐标递增排列；每一登记项下的“吊桶”，按所记,x,坐标递增排列。“吊桶”中各项的内容依次是：,1,与较小的,y,坐标对应的端点的,x,坐标,xmin,。,2,边的另一端点的较大的,y,坐标,ymax,。,3,x,的增量,x,，,它实际上是边的斜率的倒数，是从一条扫描线走到下一条扫描线时，按,x,方向递增的步长。,4.,边所属多边形的标记。,设有两个空间的三角形,ABC,、,DEF,各顶点的坐标依次是（,1,，,1,，,10,），（,2,，,5,，,10,），（,5,，,3,，,10,），（,3,，,4,，,5,），（,4,，,6,，,5,），（,6,，,2,，,5,）。,A,B,C,D,E,F,两个多边形在,z,v,=0,平面上的投影,两个多边形建立的“吊桶”已排序的边表,图,7.21,需要建立一个多边形表,PT(polygon Table),，,其中要包含下列信息：,1,每个多边形所在平面方程的系数。在需要比较深度时，要通过对所在（,x,y,），,根据平面方程解出深度,z,。,2,每个多边形的亮度或颜色值。实际做扫描转换时应用。,3.,一个“进入,退出”标志，初值为“假”。在扫描转换处理时，用以标记扫描线对该多边形是“进入”，还是“退出”。,通过以上的讨论，可以写出整个扫描线算法实施的步骤。,首先正确形成边表,ET,和多边形表,PT,之后，实施步骤就与第二章叙述的多边形填充的扫描线算法的实施步骤基本相同，只是需要把那里的步骤,:,在扫描线,y,上，按照,AET,表提供的,x,坐标对，用,color,实施填充修改加细如下：,1,将实施扫描转换时遍查,AET,表中各“吊桶”的指针,i,初始置为,1,，扫描线正在多少个多边形内的累计数值,s,初始置为零，将活动多边形表，即扫描线正在通过的多边形按深度递增次序排列而形成的表，记为,p,，,初始置为空。,2,设第,i,个“吊桶”记录的相应多边形是,A,。若,A,的“进入,/,退出”标记,FA,为“假”，则改,FA,为“真”，将,A,加到,表,P,的前面，,s,增加,1,。否则，,FA,即为“真”，则改,FA,为“假”，将,P,中的,A,去掉，,s,减少,1,。,3,若,s=0,，,则到,5,。（这时扫描线不在任何多边形内，正通过背景，不必做扫描转换。,）若,s=1,，,则到,4,（这时扫描线只在一个多边形内，不必做深度比较，去做扫描转换。）若前面两个判断都为“假”，扫描线至少在两个多边形内，应做深度比较。对表,P,前面两个多边形做深度比较，比较后放回应保证,P,表中的多边形按深度递增的次序。,4,对第,i,个和第,i+1,个“吊桶”存有的,x,坐标指示的扫描线上的一段，按照,P,表最前面多边形指示的亮度或颜色，实施扫描转换。,5 i,增加,1,，若,i,所指已无“吊桶”，步骤结束，去下一步骤（,删除,y=ymax,的边,）。否则，回到步骤,2,。在扫描线,y=4,，,实施前面步骤的各步骤，情形如表,7.1,所示。,i,s,P,PT,表,FABC FDEF,说明,1,1,(ABC),true,1,到,3,填,ABC,的亮度或颜色值,2,2,(DEF,ABC),true,在步骤,3,发生深度比较，比较结果,DEF,更靠近观察者，它仍在,P,表前面，,3,到,3,填,DEF,的亮度或颜色值,3,1,(DEF),false,3,到,5,填,DEF,的亮度或颜色值,4,0,(),false,如果按照步骤,3,的条件决定是否做深度比较，会有许多深度比较是不必要的。例如，假定有一个大的多边形,GHIJ,在两个三角形,ABC,和,DEF,的后面。在扫描线,y=,离开,边,CB,时，按步骤,3,的条件判断，扫描线还同时在,DEF,和,GHIJ,中，应该做深度比较，但是在大多数可以假定,没有多边形穿透另一个多边形的情况下,，,DEF,和,GHIJ,的深度关系并没有变化，深度比较是不必要的。,如果扫描线从一个,被遮挡,的多边形中走出，深度比较将是,不必要,的；,扫描线从一个,遮挡,了其它多边形的多边形中走出，深度比较才可能,必要,。,三个多边形,事实上前面给出的算法基本步骤没有很好地利用深度的相关性。深度相关性是指多个多边形之间的深度关系，常常对于一组相邻的扫描线来说是不变化的。如果在某条扫描线上，在,AET,表中保存的边及次序关系，与在前面一条扫描线上时完全相同，那么深度关系就不会变化，深度比较也就并不必要了。例如，图,7.21,中的扫描线,r+1,到,r+2,就是这种情形，在两条扫描线上,AET,表中的边及次序关系都是,AB,，,CB,，,DE,，,FE,。,但从,r,到,r+1,，,DE,，,CB,的次序要变化为,CB,，,DE,，,次序关系就变化了。利用深度的相关性可以对算法作出改进。,上图所示是一个多边形穿透了另一个多边形。为使算法能处理这种情况，应该把其中的多边形,KLM,分成两个多边形,KLLM,和,LMM,，,加进了一条没有的边,ML,。,或者修改算法，使能够在逐条扫描线的处理进行中，发现扫描线上的穿透点。,关于背景的处理，最简单的办法是把更新缓冲存储器整个初始化为某个合适的值，于是算法就只需处理扫描线在多边形内的情形。另一个办法是，定义一个大的矩形，让他包含了客体中所有的多边形，位于比其它多边形都更远离观察者的平行于投影平面的一个平面上，并具有某个合适的亮度或颜色值。再一个办法就是修改算法。使得每当扫描线不在任何多边形内时，就往帧缓冲存储器中送入背景的象素值。,第七节 区域分割算法,区域分割算法,将投影平面分割成区域,，考察区域内的图象。如果容易决定在这个区域内某些多边形是可见的，那么就可以显示那些可见的多边形，完成对这一区域的显示任务。否则，就将区域再分割成小的区域，对小的区域递归地进行判断。由于区域逐渐变小，在每个区域内的多边形逐渐变小，最终总可以判定哪些多边形是可见的。这个算法利用的区域的相关性，这种相关性是指位于适当大小的区域内的所有象素，表示的其实是同一个表面。,在递归分割的每一步，要显示客体中每个多边形的投影多边形与所考察区域之间的关系，必然是下列四种之一：,1.,包围的多边形，即多边形全部包含了所考察的区域。,2.,相交的多边形，即多边形所考察的区域相交。,3.,被包含的多边形,即多边形全部在所考察的区域之内。,4.,分离的多边形，即多边形与所考察的区域完全分离。,包围的 相交的 被包含的 分离的,若区域与多边形为下面的四种情况，不必再做进一步的分割，可直接绘制。,1,所有的多边形与区域分离，所以在区域内只需显示背景值。,2.,只有一个相交的多边形，或者只有一个被包含的多边形。这时可以对区域首先填充背景值，然后对多边形进行扫描转换。在某些显示设备上，将整个帧缓冲存储器都初始化为背景值，可能更为方便。对于相交的多边形，只是被包含的部分被扫描转换。,3.,只有一个包围的多边形，无其它的多边形。整个区域填充该多边形的象素值。,4.,有多于一个的包围的、相交的或被包围的多边形，且至少有一个包围的多边形。检查是否能有一个包围的多边形，它位于所有其它多边形的前面。如果有，就可以让整个区域都填充为这个多边形的象素值。具体的检查方法是，对所有的多边形，,计算其所在平面在区域的四个角点的应有深度,，即相应的,z,坐标，如果有一个包围的多边形的响应四个,z,坐标，都小于其它多边形的对应,z,坐标，那么这个包围的多边形就位于所有其它多边形的前面。,情形,4,的两种情形,区域经过分割变小以后，只需要考虑包含的多边形和相交的多边形的变化,。,因为分离的或包围的多边形，对变小的区域，仍然保持是分离的或包围的。分割进行到达到显示设备的分辨能力之后就可以停止，即最小的区域可以是显示表面上的一个象素单位。如果在做了准备做的最大数目的分割之后，仍然不能做出应该如何填充的决定，那么，就计算所有有关多边形在这个不可再分区域对应的点的范围的中心处的,z,坐标值，取,z,坐标最小的多边形象素值填充这个区域。,Wanock,首先提出的最初的区域分割算法是每次把区域分成四个正方形。下图所示是对一个投影是一个三角形和一个长方体的场景，做了,5,次区域分割的情形，其中区域内标出的数字，表示可以作出决定的前面所说的四种情形中的哪一种。没有标出数字的区域是还不能做出决定。,分割区域为正方形,区域分割不一定总是等分，当区域内有多边形的顶点时，可以按照顶点位置来做分割，这样显然可以少做一些分割。,围绕多边形顶点分割（先是,A,，,后是,B,）,区域分割还可以按照客体中多边形投影的范围进行，这可以少做很多分割。,Weiler,和,Atherton,提出的算法，直接就用多边形的投影做为分割的区域。选择用做分割的区域时，可以按照多边形各顶点坐标最小值的递增次序,按照多边形投影选择区域做分割,/,第八节,BSP,树算法,BSP,（,binary space-partitioning,）,树算法将表面由后往前地在屏幕上绘出，该算法特别适用于场景中物体位置固定不变、仅视点移动的情况。,利用,BSP,树来判别表面的可见性，其主要操作是在每次,分割空间,时，判别该表面相对于视点与分割平面的位置关系，即位于其内侧还是,外侧。,平面,P,1,将空间分割为两部分，一组物体位于,P,1,的后面（相对于视点），而另一组则在,P,1,之前，而,B,和,D,在,P,1,之后。平面,P,2,对空间进行了二次分割，并生成如图（,b,）,所示的二叉树表示。在这棵树上，物体用叶节点表示，分割平面前方的物体组作为左分支，而后方的物体组为右分支。,对于由多边形面组成的物体，,可以选择与多边形面重合的分割平面,，利用平面方程来区分“内”、“外”多边形顶点。随着将每个多边形面作为分割平面，可生成一棵树，,与分割平面相交的每个多边形将被分割为两部分,。一旦,BSP,树创建完毕，即可选择树上的面并由后往前显示，即前面物体覆盖后面的物体。目前已有许多系统借助硬件来完成,BSP,树创建和处理的快速实现。,/,第九节,八叉树算法,当按照八叉树表示来描述观察体时，通常按由前往后的顺序将八叉树节点映射到观察表面，从而消除隐藏面。,空间区域的前部（相对于视点）为体元,0,、,1,、,2,、,3,。体元的前表面均可见，这些体元尾部的表面和后部体元（,4,、,5,、,6,、,7,）的表面都可能被前部的表面所遮挡。,编号的八分区域 观察方向,1,0,2,3,4,5,7,对于当前视线，体元,0,、,1,、,2,、,3,中的物体总是遮挡后面体元中的物体,观察面,S,的边界投影将区域,A,细分为,A,1,和,A,2,显示八叉树的算法：首先递归地,由前往后,遍历八叉树节点，将八叉树映射为可见区域的,四叉树,；然后将可见面的四叉树表示置入帧缓冲器中。下图描述一个空间区域内的八叉树元和相应观察平面上对应的四叉体元。八叉树元,0,和,4,直接影响四叉体元,0,，四叉体元,1,的颜色值从八叉体元,1,和,5,获得。另外两个四叉体元的值可以分别从与之对应的一对八叉体元中得到。,空间上的八叉体元,观察平面的四叉体元,3,2,1,0,3,2,1,5,4,7,6,一般情况下，确定四叉体元的正确颜色值必须同时考虑前面和后面的八叉体元。若前面体元统一用某种颜色填充，则无须处理后面的体元。对于多色区域，将递归调用该过程，并将不同色彩的八叉体元的子节点和一个新创建的四叉树节点作为新参数进行传递。若前面体元为空，则处理尾部体元。否则，需要两次递归调用，一次处理尾部体元，一次则处理前面体元。,/,第十节 光线投射算法,考查由视点出发穿过观察平面上一像素而射入场景的一条射线，则可以确定出场景中与该射线相交的物体。在计算出光线与物体表面的交点之后，,离像素最近的交点所在的表面即为可见面,。这种可见性判别模式应用了光线投射算法。,光线投射（,ray casting,）,建立于几何光学的基础之上，它沿光线的路径追踪可见面，是一种有效的可见性判别手段。由于场景中有无限多条光线，而我们仅对,穿过像素的光线,感兴趣，因此可考虑从像素出发，逆向跟踪射入场景的光线路径。光线投射算法对于包含曲面，特别是球面的场景有很高的效率。,像素,一条由象素点射入场景的视线,光线投射算法可以看做是深度缓冲器算法的一种变形。在深度缓冲器算法，每次处理,一个表面,并对表面上的,每个投影点,计算深度值。计算出来的值与以前保存的深度进行比较，从而确定每个像素所对应的可见表面。在光线投射算法中，每次处理,一个像素,，并沿光线的投射路径计算出该像素所对应的,所有表面,的深度值。,光线跟踪技术通过追踪多条光线在场景中的路径，以得到多个物体表面所产生的反射和折射效果。而在光线投射中，跟踪的光线仅从每个像素到最近的物体为止。,