8-消隐技术n.ppt

第八章第八章 消消 隐隐 技技 术术8.1 基本概念基本概念一.为什么要消隐为什么要消隐 因为计算机图形处理的过程中，不会自动消去隐藏部分，相反会将所有的线和面都显示出来。问题：对于线画图形会出现多义性。对于光栅扫描着色的面图形则会导致图形错误。要增强图形的真实感必须进行消隐处理。多义性多义性二二.消隐算法的分类消隐算法的分类通常按照消隐对象的不同，有两类消隐问题：线消隐（Hidden-line removal）：用于线框图，消隐对象是物体上的边，消除的是物体上被遮挡的边。面消隐（Hidden-surface removal）：用于填色图，消隐对象是物体上的面，消除的是物体上被遮挡的面。按照消隐的工作空间进行分类，可以将消隐算法分为三大类对象空间（Object Space）消隐算法 （如：光线投射、Roberts算法）图像空间（Image Space）消隐算法 (如：扫描线、Zbuffer、Warnock算法)对象空间和图像空间的混合消隐算法 (如：画家算法)1.消除隐藏线 对于采用物体的棱线或轮廓线表示的线框图形，应消去物体本身看不见的棱线和轮廓线部分，以及因物体间的互相遮挡而被隐藏的棱线和轮廓线。2.消除隐藏面 对于采用光栅扫描着色方法（即采用物体表面不同的明暗度）绘制的图形，应消除物体上看不见的面以及因物体间的互相遮挡而被隐藏的面。对象空间（对象空间（Object Space）消隐算法消隐算法 是以场景中的物体为处理单元，将一个物体与其余的 k1 个物体逐一比较，仅显示它可见的表面以达到消隐的目的。此类算法通常用于消除隐藏线消除隐藏线。假定场景中有 k 个物体，平均每个物体的表面由 h 个多边形构成，其计算复杂度为 O(kh)2)。算法描述如下：for(场景中的每一个物体)将该物体与场景中的其它物体进行比较，确定其表面的可 见部分；显示该物体表面的可见部分；图像空间（图像空间（Image Space）消隐算法：消隐算法：是以窗口内的每个像素为处理单元，确定在每一个像素处，场景中的物体哪一个距离观察点最近（可见的），从而用它的颜色来显示该像素。此类算法通常用于消除消除隐藏面隐藏面。若显示区域中有 mn 个像素，则其计算复杂度为O(mnkh)。算法描述如下：for(窗口内的每一个像素)确定距观察点最近的物体，以该物体表面的颜色来显示像素；三.消隐算法中常用的处理技术 1.排序 确定物体间遮挡关系的要素：视点位置 视线方向 按观察方向上离视点（投影参考点）的远近（通常用 z 值来表示）排序。2.测试 用以判断点与面、线与面、面与面之间的关系。u(x)v(y)n(z)视点z 值包含测试：测试空间点的投影是否在某个空间多边形的投影内，若在，则可能存在遮挡关系；若不在，则不存在遮挡关系。测试方法：从空间点的投影开始向与 y 轴平行的方向作射线，计算该射线与空间多边形的投影的交点个数交点个数，若为奇数奇数，则点的投影在多边形的投影内；若为偶数偶数，则点的投影不在多边形的投影内。xy特殊情况左闭右开P414夹角之和检验法夹角之和检验法重叠测试：测试两个空间多边形的投影是否重叠，若重叠，则可能存在遮挡关系；若不重叠，则不存在遮挡关系。测试方法：包围盒法包围盒法 四.提高消隐算法效率的常用方法 1.利用相关性（连贯性）物体的相关性物体的相关性：若物体 A 与物体 B 是完全相互分离的，消隐时只需比较 A、B 两物体之间的遮挡关系，而不需对其表面多边形逐一进行测试。面的相关性：面的相关性：一个面内的各种属性值（坐标值、灰度值等）一般都是缓慢变化的，可采用简单增量方式进行计算。区域相关性：区域相关性：一个区域是指屏幕上一组相邻的像素，它们通常属于同一个可见面。区域相关性表现在一条扫描线上时,即为扫描线上的每个区间内只有一个面可见。扫描线相关性：扫描线相关性：在相邻的两条扫描线上，可见面的分布情况相似。深度相关性：深度相关性：物体的同一表面上的相邻部分深度是相近的。2.包围盒技术 用于对物体间的某些关系进行比较和测试，从而可避免盲目的求交运算，减少计算量，提高效率。二维图形-包围框（重叠测试）；三维物体-包围盒、包围球。3.背面剔除 一个平面多面体的表面由若干个平面多边形构成，若一个多边形表面的外法线方向与投影方向（观察方向）的夹角为钝角，则该面为前向面；若其夹角为锐角，则为后向面或背面。4.活化表技术(active list)设置活化表，用于存放与当前的处理相关的信息，从而可最大限度地缩小处理范围，提高算法的效率。投影方向ABCD画家算法的基本思想，先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序。离视点远的在表头，离视点近的在表尾，构造深度优先表。然后，从表头至表尾逐个取出多边形，投影到屏幕上，显示多边形所包含的实心区域。由于后显示的图形取代先显示的画面，而后显示的图形所代表的面离视点更近，所以，由远及近地绘制各面，就相当于消除隐藏面。这与油画家作画的过程类似，先画远景，再画中景，最后画近景，因此将这种算法称为画家算法。五五.画家算法画家算法画家算法画家算法画家算法的优点是简单、易于实现，并且可以作为实现更为复杂算法的基础。它的缺点是只能处理互不相交的面，而且深度优先级表中的顺序可能出错，如两个面相交或三个面相互重叠的情况，用任何方法都不能排出正确的顺序。这时，只能把有关的面进行分割后再排序。增加了算法的复杂度，因此，该算法使用具有一定的局限性。画家算法画家算法为了避免画家算法复杂的运算，人们提出了Z缓冲区算法。Z缓冲区算法又称为深度缓存算法，是一种简单的面消隐算法。它不仅需要一个帧缓冲区(FB)来存放每个像素的亮度值，而且还需要有一个Z缓冲区(ZB)来存放每个像素的深度值，即Z坐标。这正是Z缓冲区算法名称的来历。六六.深度缓存算法深度缓存算法(Zbuffer算法算法)深度缓存算法深度缓存算法(Zbuffer算法算法)1.ZBuffer 用于存放与屏幕上像素点对应的物体上点的深度值。xyz视线方向视点位置屏幕像素F BufferZBuffer投影面2.算法 初始化：ZB(i,j)=机器最大值；FB(i,j)=背景色。for(j=1;j=n;j+)/*共有 n 根扫描线*/for(i=1;i=m;i+)/*每根扫描线上有 m 个像素点*/for(k=1;k=p;k+)/*共有 p 个多边形*/判断像素点(i,j)是否在多边形Fk在投影面上的投影内;若(i,j)在多边形Fk的投影内，计算多边形Fk上对应于 像素点(i,j)处的深度值 Zi,j;if (Zi,j ZB(i,j)ZB(i,j)=Zi,j ;FB(i,j)=多边形Fk的颜色 else 不作处理 3.算法实现中的关键问题 判断点(i,j)是否在多边形Fk在投影面上的投影内 解决办法：采用包含测试。计算多边形Fk在点(i,j)处的深度值 Zi,j 若多边形Fk的平面方程为：ax+by+cz+d=0 若 c 0，则 ai+bj+d c 若 c=0，则多边形Fk的法线方向与 Z 轴垂直，Fk在投影面上的投影为一条直线，可不予考虑。Zi,j=4.算法的特点 简单 不需要将所有的多边形按离视点的远近排序，其算法的复 杂度只与多边形的个数成正比。需要有一个较大容量的 ZBuffer。5.算法的改进 采用包围框技术，提高算法的效率。采用硬件 ZBuffer 来实现。6.算法的进一步改进 采用分区处理方法。利用相关性。七七.扫描线算法扫描线算法 1.基本思路 只需考虑与多边形投影相交的扫描线。对每条扫描线，只需处理与多边形投影中某二条边的交点 中间的部分（边对边对）。对各多边形逐个处理，方法同ZBuffer算法。xyo扫描线 为提高算法的效率，需解决几个问题：如何建立扫描线与多边形投影之间的关系；如何建立扫描线与多边形边投影之间的关系；如何突出边对信息；如何方便地计算边对中各像素点处的相关坐标。xy扫描线jj+12.相关性的应用 计算多边形边的投影与扫描线交点的计算多边形边的投影与扫描线交点的 x x 坐标坐标 设多边形 F Fk 的投影上的边 L 的方程为：px+qy+r=0则扫描线 y=j 与其交点的 X 坐标为：qj+r p 而扫描线 y=j+1 与其交点的 X 坐标为：q(j+1)+r qj+r q q p p p p 利用X 就可方便地递推得到该边与下一条扫描线交点的 x 坐标。Xj=Xj+1=Xj=Xj X(p 0)F FkL扫描线xyoj+1jxj xj+1 计算多边形计算多边形 Fk 在点在点(i,j,Zi,j)处的深度值处的深度值 Zi,j 设多边形 Fk 的方程为：ax+by+cz+d=0 则多边形 Fk 上的点(i,j,Zi,j)处的深度值 Zi,j 为：ai+bj+d c 而点(i+1,j,Zi+1,j)处的深度值 Zi+1,j为：ai+bj+d a c c利用 Zx 就可方便地递推得到该多边形在同一条扫描线上相邻后续各点的深度值。Zi,j=(c 0)Zi+1,j=Zi,j Zx xyozFki i+1jZi,jZi+1,j 计算多边形边界上（对应于边的投影与扫描线交点处）的计算多边形边界上（对应于边的投影与扫描线交点处）的深深 度值度值 设 L 为多边形 Fk的一条边，与扫描线 j 的交点为 Xj，则多边形 Fk 在交点(Xj,j)处的深度为：axj+bj+d c 当扫描线向上移动一条，即 y=j+1 时，边 L 与扫描线的交点为(Xj+1,j+1),多边形 Fk 在此点处的深度为：axj+1+b(j+1)+d axj+bj+d a q b c c c p c =Z j+Zx X zy利用 Zy 就可递推得到下一条扫描线与边 L 交点处的深度值。Z j=Z j+1=+3.数据结构 桶桶 源于 Knuth 的 bucket sort。用于存放按照一定的规则（顺序）排列的若干组数据或处理对象。通常情况下，桶是采用向向量量形式和链链表表形式结合起来构造成的一种特定的数据结构。多边形 Y 桶 用于描述图形中的各多边形与扫描线之间的关系。桶的长度与屏幕上的扫描线数相同。根据多边形各顶点中最小的 y 坐标，将其放入相应的桶内。xy2681012345678910 Ymax=8Ymax=10 Ymax=104链表中存储每个多边形的序号及其多边形顶点的最大y坐标xy268104 有效多边形表 APT（多边形活化表）用于描述扫描线和多边形之间的关系；前图中当 Y=4 时的有效多边形表 Ymax=10指向边Y桶的指针 Ymax=8指向边Y桶的指针 边 Y 桶 用于描述多边形的各条边与扫描线之间的关系。桶的长度与屏幕上的扫描线数相同。根据各边两端点中较小的 y 坐标，将其放入相应的桶内。边Y桶中，存放了每条边端点中较大的Ymax值，增量x，y值较小一端的x 坐标和z坐标 Ymaxx xz12345678910 xy268104 有效边表 AET（边活化表）4.算法基本思路：对每条扫描线进行处理；逐个处理各多边形投影与扫描线相交的部分（边对）；各边对的处理方法与 Z-Buffer 相同，但充分利用了相关性。初始化：*对于每个多边形，根据其各顶点中最小的 y 坐 标，将其放入相应的多边形 Y 桶内；*对于多边形中的各条边，根据其端点中较小的 y 坐标，将其放入相应的边 Y 桶内；*有效多边形表 APT和有效边表 AET置为空。对于每条扫描线 j(j=1n),做以下工作：*对应的帧缓存FB置成背景色；*对应的 Z 缓存ZB置成机器最大值；*检查多边形Y 桶内对应于扫描线 j处是否有新的多边形，若有，则将其加入有效多边形表 APT；同时将边 Y 桶内对应的新边加入有效边表 AET。*对于有效边表中的每一个边对，做以下工作：置zij初值为 zl+zx ;从边对的左交点开始，对于满足 xl i xr的每一个象素(i,j)，做以下工作：zij=zijzx;若 zijZB(i),则 ZB(i)=zij;CB(i)=该边对所在多边形的颜色。*检查有效边表中的每一个边对：若 ylmax 或 yrmax 等于 j，则从有效边表中删去左侧边或右侧边，并与其余的边组成新的边对；*检查有效多边形表中的每一个多边形，若某个多边形顶点的最大 y 坐标已等于 j，则从有效多边形表中删去该多边形。计算下一条扫描线与各边对交点的相关信息：xl=xl xl；xr=xr xr；zl =zl+zx xl zy 重复执行算法中的第步，直至所有扫描线处理完毕。5.算法的进一步改进 采用包围盒技术，尽可能减少处理的扫描线数。避免重复处理。将一条扫描线按其与各多边形的交点划分成几个区域，在每个区域中只须表示离视点最近的多边形。xyx1 x2 x3x4扫描线区间扫描线算法区间扫描线算法