第7章 消除隐藏线和隐藏面.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 隐藏面的消除,这一章我们将介绍消除隐藏面的方法,。,7.1,概述,第一章我们曾将输出的图形分为线条图和具有明暗效果的真实感图形（面图），在绘制或显示三维图形时，无论采用那种图形表示三维形体，都要消除不可见的线或面，即消除隐藏线或隐藏面（简称消隐），它是计算机图形学的重要内容，其算法有很多种，本章只介绍隐藏面的消除。,7.1,概述,当我们观察空间任何一个不透明的物体时，只能看到该物体上朝向我们的那部分表面，其余的表面由于被物体所遮挡我们看不到。如果把可见不可见的线都用一种线型表示出来，不仅表示不清，很混乱，而且还会产生“二义性”。如图,7.1,所示的物体,(,组合体,),在消除隐藏线之前，显然可以有四种不同的理解。其中,(a),是未消隐的原图，（,b,）、（,c,）、（,d,）和（,e,）表示四种可能的物体。,7.1,概述,未经消隐的图形,可能的四种形体,隐藏线和隐藏面,不可见的线和面分别称为,隐藏线,和,隐藏面,。,隐藏线和面不仅仅有形体自身的，而且还有形体之间互相遮挡的。消除它们即称为消除隐藏线和消除隐藏面。,形体之间互相遮挡的隐藏线,当我们显示线条图或用笔式绘图仪或其它线画设备绘制线条图形时，要解决的主要是消除,隐藏线,的问题。而当用光栅扫描显示器显示物体的明暗图形时，就必须要解决消除,隐藏面,的问题。,鉴于消隐问题的重要性和复杂性，自,60,年代以来，人们就消隐问题进行了大量的、深入的研究，提出了许多种算法。,60,年代初期，由于当时的显示器只能显示线条图，所以研究出了消除隐藏线算法，其中最著名的是罗伯茨（,L.G.Roberts,）算法（,1963,年）。从,60,年代以来，能产生具有真实感明暗图形的光栅扫描显示器逐渐成为显示器市场的主流，于是人们又研究出了多种隐藏面消除算法。并且随着计算机硬件技术的飞速发展，有些隐藏面消除算法已经固化，从而极大的提高了处理速度。然而，在多种消隐算法中，没有一种是完美的，它仍吸引人们去不断研究和探索。,真实感图形（物体的相互遮挡）,消隐与消隐对象有关，也与观察者的位置有关,从另一个角度观察,1.,物体空间的消隐算法,一般是指规范化投影空间或观察空间。在规范化投影空间，物体的平行投影和透视投影的消隐算法得到了统一,(,视点都在轴正向无穷远处），但在透视变换后，物体形状产生了变形。在物体空间进行消隐需将画面中的,k,个对象都与画面中的其余,k-,1,个对象一一比较，精确的求出它们之间的遮挡关系。因此，这类算法的计算量正比于,k,2,。,2.,图象空间的消隐算法,图象空间算法在物体显示时所在的屏幕坐标系中实现。画面中的每个对象必须与屏幕坐标系中的每个象素点进行比较，以决定哪个对象在该点的象素是可见的。若屏幕上有,mn,个象素点，则这类算法的计算量为,mnk,。,一般来说，当,k,mn,时，物体空间算法的计算量比图象空间小，从理论上来说，大多数算法应在物体空间实现。然而，由于光栅扫描过程中易于利用画面的连贯性，故图象空间算法的效率往往更高，而且也相对简单。但物体空间算法比图象空间算法精确。,7.2,消隐算法常用的几种几何计算方法,消隐的对象是三维物体。在第六章,6.3,我们曾介绍过表示三维物体的三种模型，其中常用的是表面模型。为简单，往往用平面多边形表示物体的表面，物体的曲面部分可以用平面多边形逼近的方法近似表示。多边形又可用它的边（直线段）表示，每条边又可以用其两个端点来定义。因此，消隐过程中所涉及到的几何元素一般都是点、直线段和平面多边形，消隐算法需要对它们之间进行大量的计算和比较。,7.2.1,平面多边形的外法矢量,为了判别物体上各表面是朝前面还是朝后面，需求出各表面,(,平面多边形,),指向体外的法矢量。设物体在右手坐标系中，多边形顶点按逆时针排列。当多边形为凸多边形时，则其法矢可取成多边形相邻两边矢量的叉积。,P,1,P,2,P,3,如图,7.4,中的法矢。这种算法虽然简单，但当多边形为凹多边形时，则可能出现错误，即所求的多边形法矢量指向体内。这时可采用如下的计算方法。,设,n,=,A,B,C,，而,式中若,i,n,，则,j,=,i,+1,；否则,i,=,n,，,j,=1,。,以上算法适合任何平面多边形。,非平面但接近平面的多边形的最佳逼近平面的法矢量也可用此算法求出。为避免在程序中出现两种计算平面外矢量的方法，建议凸多边形也采用该算法计算外法矢量。多边形所在平面的方程可写成,其中 ，,为平面上任意一点。,7.2.2,深度检验,深度检验是比较位于同一条投射线的若干个点的深度坐标（一般为,z,坐标），以确定哪个点是可见的，将可见点表示出来。消隐时必须进行深度检验。一般将需要比较的各点的,z,坐标按递增或递减排序，也可从中选出最大或最小的,z,坐标。至于选最大或最小与所选的坐标系有关。,z,y,x,s,深度检验,A,B,7.2.3,排序,上面已经提到，不仅需要对深度坐标排序，而且需要对,x,坐标排序，以将其两两配对。,7.2.4,求交点、交线,求直线与平面、曲面的交点，平面与平面、曲面的交线，是消隐中经常需要的计算。例如：光线追踪算法，,80%,的计算是求交。求直线与平面的交点和两平面的交线是容易的。求直线与平面的交点一般将直线方程表示成参数形式,平面方程,将直线方程代入平面方程，即可容易地求出交点的参数。求直线与二次曲面的交点时，可采用以下方法。二次曲面方程,的交点也可此方法，但代入后所得的方程为,但如果大于二次的曲面求交点稍难一些。求直线与参数曲面的交点就比较难了，而平面与参数曲面求交线则更难。故经常用平面逼近参数曲面，以简化求交等计算。,7.2.5,背面剔除,在消隐过程中，用背面剔除的方法可以将自身的大约,50%,的不可见面剔除掉，从而大幅度地减少计算量。对于凸多面体，可直接用其消除隐藏面。,平面,上任一点的法矢量,n,与该点的视线矢量的数量积为,当,cos,0,时，即,0/2,时，平面朝前，为可见，应画出。,当,cos,0,时，即,/2,时，平面朝后，为不可见，不画出或用虚线表示。,y,x,z,n,当视线方向为,z,轴时，上述计算可简化。,如设,则,7.3,深度（,z,）,缓冲器算法,深度缓冲器算法是一种最简单的消除隐藏面的算法，,在图象空间实现,。其基本思想是将投影平面每个象素所对应的所有面片,(,平面或曲面,),的对应点的深度进行比较，然后取最近点的属性值,(,该面片上与该象素对应点的属性值,),作为该象素的属性值。,深度缓冲器算法的基本思想,算法通常沿着观察坐标系系统的轴（通常是,z,轴）来计算各物体表面的,z,坐标。它对场景中的各个物体表面单独的进行处理，且在各面片上逐点进行。物体的描述转化为投影坐标之后，多边形面上的每个点（,x,y,z,）均对应于观察平面上的正投影点（,x,y,）。因而，对于观察平面上的每个象素点（,x,y,），其深度比较可通过它们,z,值的比较来实现,。,深度缓冲器算法原理,观察者,对于右手坐标系系统，,z,值最大的点应是可见的；左手坐标系统，,z,值最小的点应是可见的。下面以左手系为例。深度缓冲器算法有两个缓冲器：,深度缓冲器和帧缓冲器,。对应两个数组：深度数组,depth,（,x,y,）和属性数组,intensity,（,x,y,）。前者存放着图象空间每个可见象素的,z,坐标，后者用来存储图象空间每个象素的属性（光强或颜色）值。初始时，深度缓冲器所有单元均置为最大值，帧缓冲器各单元均置为背景色。,然后逐个处理多边形表中的各面片，每次扫描一行。计算该行各象素点（,x,y,）所对应的深度值，并将其与深度缓冲器中该象素单元所存储的深度值,depth,（,x,y,）进行比较，若,z,depth(,x,y,),depth(x,y,)=z,而且将该象素的属性值,I(x,y,),写入帧缓冲器，即,则,intensity,（,x,y,）,=,I(x,y,),否则不变。,也可用背面剔除进行预处理,(,见讲义,169 7.3),，以提高效率。,沿扫描线计算深度值,下面介绍深度值的计算。若已知多边形的方程，则可用增量法计算扫描线每一个象素的深度。设平面方程为,ax,+,by,+,cz,+,d,=0,则,z=,-(,ax,+,by,+,d,)/,c,c,0,即,在同一扫描线上,y,=,常数，因此沿扫描线上象素,x,i,+1=,x,i,+,x,处的深度为,(7.14),对于某一个面片，,a/c,是常数，故沿扫描线的后续点的深度值，可由上式仅执行一次加法计算即可求出。,对于每条扫描线，首先计算出与其相交的多边形最左边的交点所对应的深度值，然后，该线上所有后续点由式（,7.14,）计算。,计算每个面片左边界的深度值,如图所示，由最上方顶点出发，沿多边形的左边递推地计算各点的,z,坐标,其中,m,为该边斜率。将上式代入平面方程，沿该边还可递推的计算出深度值,（,7-16,）,（,7-15,）,所有多边形处理完毕，则把帧缓冲器,intensity,（,x,y,）向显示缓冲器输出，即得消隐后的图形（图象）。,若该边为垂直边，则斜率为无穷大，则上式变为,要注意的是：上述的平面是经过透视变换或轴测投影变换的平面。由此可看出保留,z,坐标的用途。,由此可以看出，深度缓冲器算法比较简单。它的主要缺点是，深度数组和属性数组需要占很大的内存，虽然属性数组可以由显示缓冲器代替，但仅深度数组占用的内存也相当大了。例如，对于一个,800600,分辨率则需要,480000,个单元的缓冲器，如每个单元需要,4,个字节，则需要,1.92,兆字节。一个减少存储需求的方案是，每次只对场景的一部分进行处理，这样只需要一个较小的深度数组（缓冲器）。在处理完一部分之后，该数组再用于下一步部分的处理。,深度缓冲器算法原理,7.3,扫描线深度缓冲器算法,上节提到为减少内存需求，可将场景划小。最自然的划法是由一条条扫描线分划成的区域进行消隐处理。该算法每次处理的区域为：高为一条扫描线的高度，宽即其水平显示宽度。,扫描线深度缓冲器算法,是深度缓冲器算法的特例，算法原理简单，对于每一条扫描线，帧缓冲器取背景属性作为初始值，深度缓冲器的初始值为最小值。然后求出这条扫描线与画面中每一个多边形的二维投影之间的交点。这些交点是成对出现的。,在逐个考察扫描线上一对交点之间的象素时，每一象素处的深度与深度缓冲器在该位置上原存储的深度值进行比较，若象素深度值小于深度缓冲器中的原有值，则该象素可见，多边形在此位置上的属性写入帧缓冲器的对应象素中，同时更新深度缓冲器上的储存值。见式,(7.10),和,(7.11),。当画面中所有的多边形都处理完毕时，该扫描线帧缓冲器中的内容即为画面在此扫描线的消隐结果。当所有的扫描线都处理完毕后，即得整个画面的消隐图形。,在具体处理时，若每条扫描线对所有的多边形都检查是否与该扫描线相交，则效率很低。为此，采用第三章,3.4,介绍的活化边表的一种变化形式，即采用,y,桶、活化多边形表,和,活化边表,，以提高算法的效率。从这个意义上说，扫描线深度缓冲器算法是多边形扫描线算法的推广。活化多边形表和活化边表都是链表，具体操作见第六章,6.6,。,扫描线深度缓冲器算法的步骤,1.,数据准备,（,1,）求出与每个多边形相交的最高扫描线，然后将多边形置入对应,y,桶中。,（,2,）将至少下述数据存入链表（活化多边形表和活化边表）。,活化多边形表：,a,b,c,d,多边形所在平面的系数,；,y,穿过该多边形的扫描线条数；,Next,指向下一多边形的指针。,活化边表含有每一多边形边对的下列信息：,x,l,多边形边对左边同当前扫描线的交点；,x,l,一条扫描线到下一条扫描线之间的增量；,y,l,穿过左边的扫描线条数；,x,r,多边形边对右边同当前扫描线的交点；,x,r,一条扫描线到下一条扫描线之间的增量；,y,r,穿过右边的扫描线条数；,z,l,当前扫描线与左边交点的深度。,多边形边对可以按任意顺序存放在活化边表中，在一边对上的交点按左右序排序。同一多边形可能有多个边对。,2.,隐藏面的消除,对每一条扫描线按以下步骤进行处理,（,2,）深度缓冲器按,z,max,初始化。,（,3,）检查,y,桶中是否有新交上的多边形，如有则将新的多边形置入活化多边形表。,（,4,）检查活化多边形表中是否有新交上的多边形，将新的多边形边配对置入活化边表。,（,1,）帧缓冲器按背景色初始化。,（,5,）从活化边表中提取多边形边对进行处理,并利用式（,7.14,）递推地求出当前扫描线上各象素的深度值,取出边对的上面顶点的,z,坐标与原深度缓冲器中的深度值进行比较；若前者大于后者，即,则,z,depth(,x,y,),（,7.11,）,depth(,x,y,)=,z,（,7.12,）,（,7.14,）,将计算的,z,值继续按式（,7.12,）和式（,7.13,）进行处理；,也可以只按式,(7.12),处理，同时将该象素写入显示缓冲器，,即按该象素的光强或颜色画出该象素，这时不必建立帧缓冲器。,（,5,）从活化边表中提取多边形边对进行处理,在每个多边形边对中，,y,l,和,y,r,各减去,1,，若,y,l,0,或,y,r,0,，则从活化边表删除该边；由式（,7.15,）求出下一条相邻扫描线与左边的交点和由式（,7.16,）求出该交点的深度值。,（,6,）更新活化边表,（,7.15,）,（,7.16,）,（,7,）检查并更新活化多边形表：若其中的某一多边形,y,0,，则从表中删除该多边形。,（,8,）返回到,直至所有扫描线处理完毕。,必要时可预先进行背面剔除，以减少需要处理的多边形数。从以上的步骤可以看出，采用桶、活化边表和活化多边形表之后，避免了大量无谓的检查，并利用了扫描线的空间连贯性和线段的连续性等特性，从而极大地提高了扫描线深度缓冲器算法的效率（实践证明：提高效率十几倍到几十倍），但算法也相应复杂多了，而且这些表也占用了许多内存。,上述两种算法处理的对象都是多边形，如果处理的对象是曲面，事先可用多个多边形去逼近，然后用上述算法去进行消隐处理。,7.4,区间扫描线算法,在扫描线,z,缓冲器算法中需计算扫描线上每个像素处多边形的深度，若采用区间的概念可以减少深度计算的次数。,下图,a,显示了两个多边形与一个扫描平面的交线，扫描线被各边交叉点（重影点）分割形成一个个区间。这样可见面问题可转化为确定每一个区间中可见的区段，共有三种类型的区间，见下图,a,。,扫描线的子区间,区间为空，按背景光强或颜色显示，,1,。,区间只包含一个区段，按该段所在的多边形显示，如区间,2,和,4,。,区间包含多个区段，计算该区间中各区段的深度，具有最大（或最小）,z,值的区段为该区间中的可见段。,若不出现互相贯穿的多边形，则仅需计算区间中各段在任意端点的深度。若两区段交于区间的一端点但不贯穿，那么只需计算区间中点的深度。如图,b,的区间,3,，显然在其左端点计算各区段深度无法得到正确答案，这时，若取区间中点计算其深度，即可得到正确结果。,为了使得算法能处理包含互相贯穿的多边形的情况，扫描线上的分割点不仅包含它与多边形各边的交叉点而且应包含各区段的交点。这时仍可采用计算区间中点处的深度。,区间扫描线算法原理,扫描线,z,缓冲器算法的基本结构也适用于区间扫描线算法，只需作少许修改。,7.5,深度排序算法（画家算法）,算法原理,：若场景中任何多边形在深度上均不贯穿或循环遮挡，则各多边形的优先级顺序可完全确定。,深度排序算法,：,1.,将多边形按深度进行排序：距视点近的优先级高，距视点远的优先级低。,2.,由优先级低的多边形开始逐个对多边形进行扫描转换。,其中的,关键是将多边形按深度进行排序,。,处理简单的画面元素如多边形时，该方法常被称为油画家算法。这是由于算法过程与画家创作一幅油画过程类似。画家先画背景，然后画中间景物，最后才画近景。画家采用相反的优先级顺序构造画面，从而解决可见性问题。,深度优先级算法从深度优先级排序开始，按照画面中的各元素离视点的距离确定一个深度优先级表。若该表是完全正确的，则画面中任两个元素在深度上均不重叠。算法执行时，先从离视点最远的画面元素开始，一次将每个像素写入帧缓冲器。表中离视点较近的元素覆盖帧缓冲器中原有内容，于是，隐藏面的问题迎刃而解。,画家算法原理,当多边形相互交叉覆盖时，画家算法出现困难，如图中的情况，均无法直接建立确定的深度优先表，解决的办法是沿多边形所在平面之间的交线循环地分割这些多边形，直至最终可建立确定的优先级表。,交叉覆盖多边形,凸多边形 凹多边形,一个典型的优先级算法步骤,1.,将所有景物按某种度量作优先级排序；,2.,识别和解决所有可能出现的二义性问题，获得一个确定的优先级顺序；,3.,从后至前，依次对优先级表中的物体作扫描转换。,7.6,可见面光线追踪,算法,前面讨论的隐藏面算法都利用了画面上景物的某些连贯性来高效地确定景物的可见部分。而光线追踪法则是一种带有强制性的方法。该方法基于下述思想：观察者能够看见景物是由于光源发出的光照在物体的结果，其中的一部分到达人的眼睛引起视觉。到达观察者眼中的光可由物体表面反射而来，也可通过表面折射或透射而来。,若从光源出发跟踪光线，则只有少量的光能到达观察者的眼睛，因此这样处理效率很低。,Appel,首先提出按相反途径跟踪光线，即按从观察者到景物的方向。,一个最简单的光线跟踪过程：光线从观察者出发，通过光栅中像素的中心进入场景。然后沿光线路线进行跟踪，以确定它与场景中的哪一物体相交。每一条光线均需与场景中的每一个物体进行比较。如果相交，则需求出光线与物体的所有可能的交点。,s,光线追踪算法,一条光线可能与场景中多个物体相交而形成多个交点，将这些交点按深度排序，具有最大,z,值的交点对应的面为在此像素的可见面，该像素处的显示值由物体的属性决定。,上述简单算法可用为代码描述如下,for,光栅显示器上的每条扫描线,for,扫描线上的每个像素,确定视点与该像素形成的光线,for,场景中的每个物体,如果光线与物体有交点，计算交点 并存储在交点表中,next,if,交点表非空,then,找到最近的交点,将该交点所在物体的属性赋给像素,else,将像素设置为背景值,end if,next pixel,next,scanline,光线追踪最重要的部分是,求交。画面包含的所有景物都需有相应的求交程序。,光线追踪算法中,75%,95%,的计算量用于求交，所以求交效率的高低直接影响到整个算法的效率。,计算空间一直线（光线）与给定物体的交点通常是很费时的，为了减少不必要的求交计算，可先检查光线与给定物体的最大最小长方体或圆球（包围盒）是否相交，如果不交，就不需要计算该包围盒内物体的交点。,作业,-,思考题,深度缓冲器算法和扫描线深度缓冲器算法是如何实现消隐的？清楚这两种算法的消隐思路。,