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