计算机图形学第八章.ppt

第八章 消 隐 技 术 本 章 重 点 1. 理解并掌握消隐的基本概念、消隐算法中 常用的处理技术及提高消隐算法效率的常 用方法。 2. 掌握基本的消隐算法。 难点：消隐算法的理解和掌握 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 轴平行的方向作射线，计算 该射线与空间多边形的投影的交点个数，若为奇数，则点的投 影在多边形的投影内；若为偶数，则点的投影不在多边形的投 影内。 x y 特殊情况 左闭右开 重叠测试： 测试两个空间多边形的投影是否重叠，若重叠，则可能存 在遮挡关系；若不重叠，则不存在遮挡关系。 测试方法：用包围框方法来测试。 四.提高消隐算法效率的常用方法 1. 利用相关性（连贯性） 物体的相关性：若物体 A 与物体 B 是完全相互分离的，消 隐时只需比较 A 、 B 两物体之间的遮挡关系，而不需对其表面 多边形逐一进行测试。 面的相关性：一个面内的各种属性值（坐标值、灰度值等） 一般都是缓慢变化的，可采用简单增量方式进行计算。 区域相关性：一个区域是指屏幕上一组相邻的像素，它们 通常属于同一个可见面。区域相关性表现在一条扫描线上时,即 为扫描线上的每个区间内只有一个面可见。 扫描线相关性：在相邻的两条扫描线上，可见面的分布情 况相似。 深度相关性：物体的同一表面上的相邻部分深度是相近的 。 2. 包围盒技术 用于对物体间的某些关系进行比较和测试，从而可避免盲 目的求交运算，减少计算量，提高效率。 二维图形 - 包围框（重叠测试）； 三维物体 - 包围盒、包围球。 3. 背面剔除 一个平面多面体的表面由若干个 平面多边形构成，若一个多边形表面 的外法线方向与投影方向（观察方向） 的夹角为钝角，则该面为前向面；若 其夹角为锐角，则为后向面或背面。 4. 活化表技术 ( active list ) 设置活化表，用于存放与当前的处理相关的信息，从而可 最大限度地缩小处理范围，提高算法的效率。 投影方向 AB C D 8.2 深度缓存算法 ( ZBuffer算法) 1. ZBuffer 用于存放与屏幕上像素点对应的物体上点的深度值。 x y z 视线方向 视点位置 屏幕像素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 扫描线算法 1. 基本思路 只需考虑与多边形投影相交的扫描线。 对每条扫描线，只需处理与多边形投影中某二条边的交点 中间的部分（边对）。 对各多边形逐个处理，方法同ZBuffer算法。 x y o 扫描线 基本方法：对每一条扫描线来说，把相应的帧缓存单元 置成背景色，在Z缓冲器中存放机器最大值。对每个多边 形检查它在投影面上的投影是否和当前的扫描线相交， 若不相交，则不考虑该多边形。若相交，则扫描线和多 边形边界的交点一定是成对出现的。对每对交点中间的 象素计算多边形所在平面对应点的深度（即Z值），并和 Z缓冲器中相应单元存放的深度值比较，若前者小于后者 ，则Z缓冲器中相应单元的内容要被求得的平面深度代替 ，帧缓冲器相应单元的内容也要换成该平面的属性。对 所有的多边形都作上述处理后，帧缓存中这一行的值便 反应了消隐后的图形。对帧缓存每一行的单元都填上相 应内容后也就得到了整个消隐后的图形。 为提高算法的效率，需解决几个问题： 如何建立扫描线与多边形投影之间的关系； 如何建立扫描线与多边形边投影之间的关系； 如何突出边对信息； 如何方便地计算边对中各像素点处的相关坐标。 x y 扫描线 j j+1 2. 相关性的应用 计算多边形边的投影与扫描线交点的 x 坐标 设多边形 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) Fk L 扫描线 x y o j+1 j xj 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, j 为： ai + bj + d a c c 利用 Zx 就可方便地递推得到 该多边形在同一条扫描线上相邻 后续各点的深度值。 Zi, j = (c 0) Zi+1, j = = Zi, j Zx x y o z Fk i i+1 j Zi, j Zi+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 坐标，将其放入相应的桶内。 x y 2 6 8 10 1 2 3 4 5 6 7 8 9 10 Ymax= 8 Ymax=10 Ymax=10 4 1 有效多边形表 APT（多边形活化表） 前图中当 Y=4 时的有效多边形表 Y max=10 指向边Y 桶的指针 Y max= 8 指向边Y 桶的指针 边 Y 桶 用于描述多边形的各 条边与扫描线之间的关 系。 桶的长度与屏幕上的 扫描线数相同。 根据各边两端点中较 小的 y 坐标，将其放入 相应的桶内。 Y maxX Xz 1 2 3 4 5 6 7 8 9 10 有效边表 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值最大的一个面