第七章消除隐藏线和面

1、计算机图形学计算机图形学第六章第六章 消除隐藏线和隐藏面消除隐藏线和隐藏面n信电学院信电学院 王利娟王利娟本章内容n6.1 消除隐藏线消除隐藏线n6.2 消除隐藏面消除隐藏面问题的提出问题的提出 给出一个三维形体，要画出确定的给出一个三维形体，要画出确定的立体感强的投影视图，必须决定形体上立体感强的投影视图，必须决定形体上哪些哪些线线或哪些或哪些面面是是不可见不可见的，不可见的的，不可见的部分不显示，这就是部分不显示，这就是消除隐藏线与隐藏消除隐藏线与隐藏面面的问题。的问题。 ? 哪些部分是不可见的，与观察位置有关。哪些部分是不可见的，与观察位置有关。对某个确定的视点，需要确定遮挡关系。对某个

2、确定的视点，需要确定遮挡关系。面消隐面消隐：当采用面模型显示物体时，：当采用面模型显示物体时，确定可见确定可见面，消除场景中物体的不可见面，即消除隐藏面，消除场景中物体的不可见面，即消除隐藏面。面。 线消隐线消隐：当：当显示采用线框模型表示的物体时，显示采用线框模型表示的物体时，要消除不可见的线，即隐藏线的消除。要消除不可见的线，即隐藏线的消除。 确定可见性的基本思想非常简单，但用确定可见性的基本思想非常简单，但用计算机程序实现时，一般要涉及到相当复杂计算机程序实现时，一般要涉及到相当复杂的计算。针对不同的需要，提出了各种不同的计算。针对不同的需要，提出了各种不同的算法。的算法。 假设：三维形

3、体表示为假设：三维形体表示为多边形多边形表面形成的集表面形成的集合，投影约定为沿着合，投影约定为沿着z轴正向的轴正向的正交正交投影投影消除隐藏面算法：消除隐藏面算法： 图象空间算法（图象空间算法（Image Space Methods） 客体空间算法客体空间算法 （Object Space Methods） n图象空间算法图象空间算法对显示设备上每一个可分辨对显示设备上每一个可分辨象象素素进行判断，看组成物体的多个多边形表面进行判断，看组成物体的多个多边形表面中哪一个在该象素上可见，即要对每一象素中哪一个在该象素上可见，即要对每一象素检查所有的表面。检查所有的表面。n客体空间算法客体空间算法把

4、注意力集中在分析要显示把注意力集中在分析要显示形形体体各部分之间的关系上，这种算法对每一个各部分之间的关系上，这种算法对每一个组成形体的表面，都要与其它各表面进行比组成形体的表面，都要与其它各表面进行比较，以便消去不可见的面或面的不可见部分。较，以便消去不可见的面或面的不可见部分。每步比较都可能涉及较多的计算。每步比较都可能涉及较多的计算。6.1.1 6.1.1 凸平面体的消隐处理凸平面体的消隐处理n对于一个凸多面体对于一个凸多面体，若某个面可见。则该面上，若某个面可见。则该面上所有线均可见，若某个面不可见所有线均可见，若某个面不可见,则该面轮廓线以则该面轮廓线以外的线都不可见。于是判断出可见

5、面，只显示可外的线都不可见。于是判断出可见面，只显示可见面及与之有关的线段，就画出了消隐后的图形。见面及与之有关的线段，就画出了消隐后的图形。n利用利用表面外法线方向表面外法线方向可测试物体表面的可见性。可测试物体表面的可见性。6.1 6.1 消除隐藏线消除隐藏线（1 1）原理）原理从视点处看向形体，形体表面上的点与视点形成视线从视点处看向形体，形体表面上的点与视点形成视线向量向量 ，如果视线向量与表面外法矢，如果视线向量与表面外法矢量夹角量夹角900，表面可见，表面可见；cos 0，表面不可见，表面不可见分母分母|N|S|恒为正，所以恒为正，所以，只需判断，只需判断NS的符号的符号zzyyx

6、xSNSNSNSN表面不可见表面不可见表面可见表面可见00yNSN（3 3）实例）实例n设空间有一个四面体，顶点设空间有一个四面体，顶点A A、B B、C C、D D的坐标依次的坐标依次是（是（0,0,00,0,0）、（）、（2,0,12,0,1）、（）、（4,0,04,0,0）、）、(3,2,1)(3,2,1)从从z z轴正向无穷远处观察，求各面的可见性。观察方向向轴正向无穷远处观察，求各面的可见性。观察方向向量是量是S=(0,0,1)S=(0,0,1)。 因此，因此， ，面，面DABDAB为可见面。类似计算可知，面为可见面。类似计算可知，面DBCDBC是可见面，面是可见面，面ADCADC是

7、不可见面，面是不可见面，面ACBACB退化为线。退化为线。 2,1,42,1,42,0,12,0,11 12,2,3,3,ABABDADAn n三角面三角面DABDAB的法向量是的法向量是: :04SN凹多面体的朝前面并不都是完全可见的，存在着相互凹多面体的朝前面并不都是完全可见的，存在着相互遮挡问题。遮挡问题。n线面比较法：线面比较法：( (观察位置位于观察位置位于Z Z轴负方向无穷远处轴负方向无穷远处）p用外法线法用外法线法判断出所有可能可见面判断出所有可能可见面（朝前面）（朝前面）p依次提取当前可能可见面的每一条边框线段，依次提取当前可能可见面的每一条边框线段，检查其是否被其他的可能可见

8、面挡住了或部分挡检查其是否被其他的可能可见面挡住了或部分挡住了住了p绘制可见线段及绘制可见线段及可能可见线段可能可见线段的最终可见子段，的最终可见子段，输出图形。输出图形。6.1.2 6.1.2 凹多面体的消隐处理凹多面体的消隐处理（1 1）范围检查）范围检查n求出线段的投影：求出线段的投影：xmin1,xmax1,ymin1,ymax1xmin1,xmax1,ymin1,ymax1n求出多边形表面的投影范围：（求出多边形表面的投影范围：（zvzv平面上包含多边形投影的平面上包含多边形投影的最小矩形最小矩形）：）：xmin2,xmax2,ymin2,ymax2xmin2,xmax2,ymin2

9、,ymax2n比较投影范围：比较投影范围：p在在xvxv方向方向: :若若xmax1=xmin2xmax1=xmin2或或xmax2=xmin1,xmax2=xmin1,则无遮挡关则无遮挡关系系p在在yvyv方向方向: :若若ymax1=ymin2ymax1=ymin2或或ymax2=ymin1,ymax2zz1 1，远离视点，远离视点（4 4）进一步检查）进一步检查n对平面遮挡了线段的那些部分做精确计算对平面遮挡了线段的那些部分做精确计算p求线段投影与多边形边框投影的交点求线段投影与多边形边框投影的交点p设交点已经求出，设其对应的参数设交点已经求出，设其对应的参数 ，按从小到大依次，按从小到

10、大依次排序后是排序后是11，22。，则这些交点将投影线段分成的。，则这些交点将投影线段分成的各子线段的可见性应是可见、不可见交替出现。各子线段的可见性应是可见、不可见交替出现。p判断子线段的可见性判断子线段的可见性u需要检查出某一段子线段是否可见。为此可以取子线需要检查出某一段子线段是否可见。为此可以取子线段上任意一点，若这点在多边形表面各边线的投影所段上任意一点，若这点在多边形表面各边线的投影所形成的封闭多边形内，这子线段就不可见，否则就可形成的封闭多边形内，这子线段就不可见，否则就可见。见。 6.1.3 6.1.3 曲面体的消隐处理曲面体的消隐处理（1 1）离散法）离散法n把曲面离散成许多

11、小平面片，用平面逼近曲面把曲面离散成许多小平面片，用平面逼近曲面n当当曲面表示为一组网格多边形曲面表示为一组网格多边形时，曲面消隐处理的时，曲面消隐处理的主要工作是主要工作是确定各网格的多边形的可见性确定各网格的多边形的可见性，因此，可，因此，可以采用平面立体的消隐算法对曲面进行消隐处理。以采用平面立体的消隐算法对曲面进行消隐处理。n如：利用网格多边形的外法线方向可判断二次曲面如：利用网格多边形的外法线方向可判断二次曲面如球面、柱面等曲面网格多边形的可见性。如球面、柱面等曲面网格多边形的可见性。球面的参数方程为：球面的参数方程为：20 ,0cossinsincossinRzRyRxXZYOzy

12、xP,n 球面可由球面可由参数曲线簇和参数曲线簇和参数曲线簇所构成的网参数曲线簇所构成的网格来表示。格来表示。12120P1P3P2P 对对N进行单位化处理，有进行单位化处理，有n=nx, ny, nz=n/|N|， 设视线方向平行于设视线方向平行于Y轴，轴，S=0,1,0， 当当nS=ny0时，网格四边形可见，画出；时，网格四边形可见，画出； 当当ny0时，网格四边形不可见，不画。时，网格四边形不可见，不画。 12120P1P3P2P设相邻曲线的参数分别为设相邻曲线的参数分别为1、2和和1、2，则网格四边形，则网格四边形P0P1P2P3点的坐标分别为：点的坐标分别为：213222121110

13、,PPPP、可求出其外法矢量可求出其外法矢量N：3120PPPPN6.2 6.2 消除隐藏面消除隐藏面 用不同的颜色或灰度来表示立体的各表面，使用不同的颜色或灰度来表示立体的各表面，使得图形色彩丰富和逼真，因此，在绘图时要消除得图形色彩丰富和逼真，因此，在绘图时要消除隐藏面隐藏面6.2.1 6.2.1 画家算法画家算法先将各个面按离视点的距离远近排序先将各个面按离视点的距离远近排序. .在显示时在显示时, ,先先显示离视点远的面显示离视点远的面, ,再显示离视点近的面再显示离视点近的面.(.(类似画类似画油画的顺序油画的顺序, ,先画远景先画远景, ,再画近景再画近景) )过程例图：过程例图：

14、画家算法的实现过程：把景物中各个画家算法的实现过程：把景物中各个面按其离视点的距离进行排序建成面按其离视点的距离进行排序建成深深度优先级表度优先级表。然后由远至近取出表中。然后由远至近取出表中的多边形投影到屏幕上，近的后投的的多边形投影到屏幕上，近的后投的覆盖了远的先投的，结果相当于消除覆盖了远的先投的，结果相当于消除了隐藏面。了隐藏面。画家算法画家算法n 深度优先表建立的算法的主要步骤：深度优先表建立的算法的主要步骤：p把所有的多边形按顶点最大把所有的多边形按顶点最大z z坐标值进行排序。坐标值进行排序。（客体空间客体空间）p解决当多边形解决当多边形z z范围发生交迭时出现的不明确问范围发生

15、交迭时出现的不明确问题题p按最大按最大z z坐标值逐渐减小的次序，对每个多边形坐标值逐渐减小的次序，对每个多边形进行扫描转换。（进行扫描转换。（图像空间图像空间）n不明确问题检验方法不明确问题检验方法p所有多边形按顶点最大所有多边形按顶点最大z z坐标值排序后得到一坐标值排序后得到一个排序表，设个排序表，设P P是排在表中最后的那个多边形是排在表中最后的那个多边形p设设Q Q是排在是排在P P前面并且前面并且z z坐标范围与其发生交迭坐标范围与其发生交迭的一个多边形，对的一个多边形，对Q Q与与P P的次序关系的次序关系QPQP进行检查。进行检查。u多边形的多边形的x x坐标范围不相交迭，所以

16、多边坐标范围不相交迭，所以多边形不相交迭。形不相交迭。QPQPu多边形的多边形的y y坐标范围不相交迭，所以多边坐标范围不相交迭，所以多边形不相交迭。形不相交迭。QPQPuP P整个在整个在Q Q远离观察点的一侧。远离观察点的一侧。QPQPuQ Q整个在整个在P P的靠近观察点的一侧。的靠近观察点的一侧。QPQPu多边形在多边形在z=0z=0平面上的投影本身不相交迭。平面上的投影本身不相交迭。QPQP深度检测深度检测包围盒检测包围盒检测平面多边形平面多边形位置检测位置检测p以上五步中任何一步成立，都可以说明当前排序正确以上五步中任何一步成立，都可以说明当前排序正确p如果如果五步检查都为假五步检

17、查都为假，就假定，就假定P P是遮挡了是遮挡了Q Q，交换，交换P P和和Q Q在排序表中的位置。（在排序表中的位置。（QPQPPQPQ) )p如果如果Q Q的位置需的位置需再次交换再次交换，说明存在交叉覆盖情况，算，说明存在交叉覆盖情况，算法会陷入无限循环。法会陷入无限循环。p为了避免循环，可以做一个限制。当做过首次五步检为了避免循环，可以做一个限制。当做过首次五步检查后，发生某个多边形被移到排序表的末尾时，就立即查后，发生某个多边形被移到排序表的末尾时，就立即加上一个标记，以后就不能再做移动。出现再次应该移加上一个标记，以后就不能再做移动。出现再次应该移动时，用一个多边形所在的平面，把另一

18、个多边形动时，用一个多边形所在的平面，把另一个多边形裁剪裁剪分为两个，从表中删去原多边形，将这裁剪出的两个多分为两个，从表中删去原多边形，将这裁剪出的两个多边形排序插入表内，对新表重复上述检测。边形排序插入表内，对新表重复上述检测。6.2.2 6.2.2 深度缓冲器算法（深度缓冲器算法（Z Z缓冲区算法）缓冲区算法）nz z 缓冲算法缓冲算法:(:(深度缓冲算法深度缓冲算法) )是一种最简单的是一种最简单的图像空图像空间算法间算法。p帧缓冲存储器帧缓冲存储器: :存储各点的像素值，存储各点的像素值，初始化为背初始化为背景值：景值：colorcolorpz z 缓冲存储器缓冲存储器: :存储相应

19、的存储相应的z z值。初始化最大值。初始化最大z z值。值。depthdepthn对每一个多边形，对每一个多边形，不必不必进行深度排序算法要求的进行深度排序算法要求的初初始排序始排序，立即就可以逐个进行扫描转换。，立即就可以逐个进行扫描转换。 （1 1）相关概念）相关概念n初始化：初始化：depthij=maxz;colorij=bkcolordepthij=maxz;colorij=bkcolorn对于景物中的每个多边形平面，计算出该多边形平对于景物中的每个多边形平面，计算出该多边形平面的投影所包含的全部像素的位置，对每一像素进行面的投影所包含的全部像素的位置，对每一像素进行如下工作：如下工

20、作：p计算该多边形在点计算该多边形在点(i,j)(i,j)处多边形的深度值处多边形的深度值Z(i,j)Z(i,j)p比较比较Z(i,j)Z(i,j)和和Z Z缓冲区中缓冲区中(i,j)(i,j)处处的值，如果的值，如果Z(i,j)depthijZ(i,j)depthij，把把Z(x,y)Z(x,y)存入存入Z Z缓冲区中的缓冲区中的(x,y)(x,y)处；处；把多边形在把多边形在(x,y)(x,y)处的亮度值存入帧缓存区的处的亮度值存入帧缓存区的(x,y)(x,y)处；处；（2 2）算法步骤）算法步骤n算法中深度计算算法中深度计算p通过多边形的顶点坐标求出所在平面的方程，然通过多边形的顶点坐标求出所在平面的方程，然后再使用平面方程，对每个点后再使用平面方程，对每个点 x x y y 解出相应的解出相应的z z。 对应平面方