计算机图形学第八章.ppt

第八章第八章 消消 隐隐 技技 术术 本本 章章 重重 点点1.理解并掌握消隐的基本概念、消隐算法中 常用的处理技术及提高消隐算法效率的常 用方法。2.掌握基本的消隐算法。难点：难点：消隐算法的理解和掌握8.1 8.1 基本概念基本概念一.为什么要消隐为什么要消隐 因为计算机图形处理的过程中，不会自动消去隐藏部分，相反会将所有的线和面都显示出来。问题：对于线画图形会出现多义性。对于光栅扫描着色的面图形则会导致图形错误。要增强图形的真实感必须进行消隐处理。二二.消隐的分类消隐的分类 1.消除隐藏线 对于采用物体的棱线或轮廓线表示的线画图形，应消去物体本身看不见的棱线和轮廓线部分，以及因物体间的互相遮挡而被隐藏的棱线和轮廓线。2.消除隐藏面 对于采用光栅扫描着色方法（即采用物体表面不同的明暗度）绘制的图形，应消除物体上看不见的面以及因物体间的互相遮挡而被隐藏的面。与此相对应，消隐的算法也可分为两种：第一种方法第一种方法是以场景中的物体为处理单元，将一个物体与其余的 k1 个物体逐一比较，仅显示它可见的表面以达到消隐的目的。此类算法通常用于消除隐藏线消除隐藏线。假定场景中有 k 个物体，平均每个物体的表面由 h 个多边形构成，其计算复杂度为 O(kh)2)。算法描述如下：for(场景中的每一个物体)将该物体与场景中的其它物体进行比较，确定其表面的可 见部分；显示该物体表面的可见部分；第二种方法第二种方法是以窗口内的每个像素为处理单元，确定在每一个像素处，场景中的物体哪一个距离观察点最近（可见的），从而用它的颜色来显示该像素。此类算法通常用于消除隐藏面消除隐藏面。若显示区域中有 mn 个像素，则其计算复杂度为O(mnkh)。算法描述如下：for(窗口内的每一个像素)确定距观察点最近的物体，以该物体表面的颜色来显示像素；三.消隐算法中常用的处理技术 1.排序 确定物体间遮挡关系的要素：视点位置 视线方向 按观察方向上离视点（投影参考点）的远近（通常用 z 值来表示）排序。2.测试 用以判断点与面、线与面、面与面之间的关系。u(x)v(y)n(z)视点z 值包含测试：测试空间点的投影是否在某个空间多边形的投影内，若在，则可能存在遮挡关系；若不在，则不存在遮挡关系。测试方法：从空间点的投影开始向与 y 轴平行的方向作射线，计算该射线与空间多边形的投影的交点个数交点个数，若为奇数奇数，则点的投影在多边形的投影内；若为偶数偶数，则点的投影不在多边形的投影内。xy特殊情况左闭右开重叠测试：测试两个空间多边形的投影是否重叠，若重叠，则可能存在遮挡关系；若不重叠，则不存在遮挡关系。测试方法：用包围框方法来测试。四.提高消隐算法效率的常用方法 1.利用相关性（连贯性）物体的相关性物体的相关性：若物体 A 与物体 B 是完全相互分离的，消隐时只需比较 A、B 两物体之间的遮挡关系，而不需对其表面多边形逐一进行测试。面的相关性：面的相关性：一个面内的各种属性值（坐标值、灰度值等）一般都是缓慢变化的，可采用简单增量方式进行计算。区域相关性：区域相关性：一个区域是指屏幕上一组相邻的像素，它们通常属于同一个可见面。区域相关性表现在一条扫描线上时,即为扫描线上的每个区间内只有一个面可见。扫描线相关性：扫描线相关性：在相邻的两条扫描线上，可见面的分布情况相似。深度相关性：深度相关性：物体的同一表面上的相邻部分深度是相近的。2.包围盒技术 用于对物体间的某些关系进行比较和测试，从而可避免盲目的求交运算，减少计算量，提高效率。二维图形-包围框（重叠测试）；三维物体-包围盒、包围球。3.背面剔除 一个平面多面体的表面由若干个平面多边形构成，若一个多边形表面的外法线方向与投影方向（观察方向）的夹角为钝角，则该面为前向面；若其夹角为锐角，则为后向面或背面。4.活化表技术(active list)设置活化表，用于存放与当前的处理相关的信息，从而可最大限度地缩小处理范围，提高算法的效率。投影方向ABCD8.2 8.2 深度缓存算法深度缓存算法 (Z(ZBufferBuffer算法算法)1.ZBuffer 用于存放与屏幕上像素点对应的物体上点的深度值。xyz视线方向视点位置屏幕像素F BufferZBuffer投影面基本思路：对于显示屏上的每一个象素，记录下位于该象素内最靠近观察者的那个景物面的深度坐标，同时相应记录下用来显示该景物面的颜色（或灰度），那么所有记录下的这些象素所对应的颜色就可以形成最后要输出的图形。Z-Buffer中保存与屏幕上象素点对应的物体上点的深度值，F-Buffer中存放对应象素点的颜色（或灰度）。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.算法的进一步改进 采用分区处理方法。利用相关性。8.3 8.3 扫描线算法扫描线算法 1.基本思路 只需考虑与多边形投影相交的扫描线。对每条扫描线，只需处理与多边形投影中某二条边的交点 中间的部分（边对边对）。对各多边形逐个处理，方法同ZBuffer算法。xyo扫描线基本方法：对每一条扫描线来说，把相应的帧缓存单元置成背景色，在Z缓冲器中存放机器最大值。对每个多边形检查它在投影面上的投影是否和当前的扫描线相交，若不相交，则不考虑该多边形。若相交，则扫描线和多边形边界的交点一定是成对出现的。对每对交点中间的象素计算多边形所在平面对应点的深度（即Z值），并和Z缓冲器中相应单元存放的深度值比较，若前者小于后者，则Z缓冲器中相应单元的内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。对所有的多边形都作上述处理后，帧缓存中这一行的值便反应了消隐后的图形。对帧缓存每一行的单元都填上相应内容后也就得到了整个消隐后的图形。为提高算法的效率，需解决几个问题：如何建立扫描线与多边形投影之间的关系；如何建立扫描线与多边形边投影之间的关系；如何突出边对信息；如何方便地计算边对中各像素点处的相关坐标。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 就可方便地递推得到该边与下一条扫描线交点的 x 坐标。Xj=Xj+1=Xj=Xj X(p 0)F FkL扫描线xyoj+1jxj xj+1 计算多边形计算多边形 F Fk k 在点在点(i,j,Zi,j,Zi,ji,j)处的深度值处的深度值 Z Zi,ji,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,j 为：ai+bj+d a c c利用 Z Zx x 就可方便地递推得到该多边形在同一条扫描线上相邻后续各点的深度值。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利用 Z Zy y 就可递推得到下一条扫描线与边 L 交点处的深度值。Z j=Z j+1=+3.数据结构 桶桶 源于 Knuth 的 bucket sort。用于存放按照一定的规则（顺序）排列的若干组数据或处理对象。通常情况下，桶是采用向向量量形式和链链表表形式结合起来构造成的一种特定的数据结构。多边形 Y 桶 用于描述图形中的各多边形与扫描线之间的关系。桶的长度与屏幕上的扫描线数相同。根据多边形各顶点中最小的 y 坐标，将其放入相应的桶内。xy2681012345678910 Ymax=8Ymax=10 Ymax=1041 有效多边形表 APT（多边形活化表）前图中当 Y=4 时的有效多边形表 Ymax=10指向边Y桶的指针 Ymax=8指向边Y桶的指针 边 Y 桶 用于描述多边形的各条边与扫描线之间的关系。桶的长度与屏幕上的扫描线数相同。根据各边两端点中较小的 y 坐标，将其放入相应的桶内。YmaxX Xz12345678910 有效边表 AET（边活化表）记录多边形边界与当前扫描线相交的各个边对边对的信息。xl：左交点的x坐标值；xl：左交点所在边和相邻扫描线交点的x坐标之差；ylmax：左侧边两端点中较大的 y 值；xr，xr，yrmax：右交点对应的三个量；zl：左交点处多边形所在平面的深度值；zx：沿扫描线向右走过一个象素时，多边形所在平面深度的增 量；zy：沿 y 方向向上移过一根扫描线时，多边形所在平面深度 的增量；IP：边对所在多边形的编号。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;FB(i)=该边对所在多边形的颜色。*检查有效边表中的每一个边对：若 ylmax 或 yrmax 等于 j，则从有效边表中删去左侧边或右侧边，并与其余的边组成新的边对；*检查有效多边形表中的每一个多边形，若某个多边形顶点的最大 y 坐标已等于 j，则从有效多边形表中删去该多边形。计算下一条扫描线与各边对交点的相关信息：xl=xl xl；xr=xr xr；zl =zl+zx xl zy 重复执行算法中的第步，直至所有扫描线处理完毕。5.算法的进一步改进 采用包围盒技术，尽可能减少处理的扫描线数。避免重复处理。将一条扫描线按其与各多边形的交点划分成 几个区域，在每个区域中只须表示离视点最近的多边形。每 个区域只显示一个面，因此只要在区间任一点处找出在该处 Z值最大的一个面就是离视点最近的多边形，将之表现出来 即可。xyx1 x2 x3x4扫描线区间扫描线算法区间扫描线算法 本本 章章 小小 结结1。为了使表示三维形体的图形准确和真实，在三维图形的绘 制过程中必须进行消隐消隐处理。2。消隐是一个复杂的处理过程，需要很多相关的技术相关的技术来实现 如排序、包含测试、重叠测试等等。3。消隐在整个图形处理过程中占用了大量的机时，因此必须 提高消隐算法的效率效率。例如，充分利用相关性（连贯性）、采用包围盒或包围球技术、背面剔除、活化表技术等等。4。消隐的实现方法很多，其中深度缓存算法深度缓存算法(ZBuffer算法)是一种比较简单的经典算法，也是一些其它算法的基础。