《计算机图形学基础及应用教程 教学课件 ppt 作者 张怡芳 李继芳 第8章消隐》由会员分享，可在线阅读，更多相关《计算机图形学基础及应用教程 教学课件 ppt 作者 张怡芳 李继芳 第8章消隐（38页珍藏版）》请在金锄头文库上搜索。
1、计算机图形学基础,第8章 消隐,线消隐与面消隐 面消隐的几种常用算法 深度缓存(Z-buffer)算法 区间扫描线算法 深度排序算法（画家算法） 区域细分算法（Warnock算法）,本章主要内容,真实感图形绘制流程,一.什么是消隐 因为计算机图形处理的过程中，不会自动消去隐藏部分，相反会将所有的线和面都显示出来。所以： 如果想有真实感地显示三维物体，必须在视点确定之后，将对象表面上不可见的点、线、面消去。执行这种功能的算法，称为消隐算法。 例如：,一.为什么要消隐 问题： 对于线画图形会出现多义性，要增强图形的真实感必须进行消隐处理。 对于光栅扫描着色的面图形则会导致图形错误。,基本概念 二.
2、消隐涉及的算法： 排序 连贯性 是指所考察的物体或画面的性质在局部区域内保持不变的一种倾向。 例如： 棱边的连贯性是指：棱边的可见性在它与其他棱边相交时才发生变换； 面的连贯性是指：如果面的一部分是可见的，则一般情况下整个面都是可见的。 一般：选择z轴的负向为观察方向.,消隐算法分类,根据实现时所在的坐标系或空间： 1、图像空间算法（image space） ，在屏幕坐标系中实现，（一旦达到屏幕分辨率，就不再计算下去） 在投影屏幕上，以屏幕像素为采样单位，确定投影于每一像素的可见景物表面区域 将其颜色作为该像素的显示光亮度 侧重于向屏幕投影后形成的图像，实际中更常用。 计算量 = 屏幕像素点N
3、 * 物体个数n,2、物体空间算法 （也称景物空间、对象空间（object space）算法）： 把n个对象中的每一个与其它（n-1）个对象比较，消去不可见的对象: 直接在视点坐标系中确定视点不可见的表面区域 将它们表达成同原表面一致的数据结构 侧重于景中各物体之间的几何关系 计算量=n(n-1),背面剔除算法,背面剔除算法,8.1.1 消隐的分类 线消隐 (Hidden-line)景物空间消隐 对象：线框模型 面消隐 (Hidden-surface)图像空间消隐 对象：填色图,线框模型,填色图,8.1 消隐基础,线消隐(景物空间消隐算法） 是以场景中的物体为处理单元，将一个物体与其余的 k1
4、 个物体逐一比较，仅显示它可见的表面以达到消隐的目的。 此类算法通常用于消除隐藏线。 假定场景中有 k 个物体，平均每个物体的表面由 h 个多边形构成，其计算复杂度为 O(kh)2)。,算法描述如下： for (场景中的每一个物体) 将该物体与场景中的其它物体进行比较，确定其表面的可见部分； 显示该物体表面的可见部分； （示例如右图）,线消隐示例,面消隐是以窗口内的每个像素为处理单元， 确定在每一个像素处，场景中的物体哪一个距离观察点最近（可见的)， 从而用它的颜色来显示该像素。此类算法通常用于消除隐藏面。 若显示区域中有 mn 个像素，则其计算复杂度为O(mnkh)。,算法描述如下： for
5、 (窗口内的每一个像素) 确定距观察点最近的物体，以该物体表面的颜色来显示像素； ,面削隐示例,8.1.2 提高消隐算法效率,利用连贯性 将透视投影转换成平行投影 包围盒技术：界定物体边界的矩形,提高消隐算法效率的常见方法1,利用连贯性 相邻物体的属性之间具有一定的连贯性；即从一个物体到相邻的物体，属性值通常是平缓过渡的，如颜色值、空间位置等； 具体包括： 物体连贯性 面的连贯性 区域连贯性 扫描线的连贯性 深度连贯性,连贯性,物体连贯性 若物体A与物体B是完全分离的，消隐时只需要比较两物体之间的遮挡关系即可，不需要对它们的表面多边形逐一进行测试； 面的连贯性 一张面内的各种属性值一般是缓慢变
6、化的，可采用增量的形式对其进行计算； 区域连贯性 一个区域一般指屏幕上一组相邻的象素，他们通常为同一个可见面所占据，可见性相同； 扫描线的连贯性 在相邻两条扫描线上，可见面的分布情况相似； 深度连贯性 同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同，这样只需取其上一点计算出深度值，比较该深度值便能得出结果；,提高消隐算法效率的常见方法2,将透视投影转换成平行投影 消隐必须在投影之前完成，因为消隐需要物体三维信息，投影后只有二维信息； 物体之间的遮挡关系与投影中心的选取有关； 在平行投影时，其遮挡关系可通过深度值来确定；,8.2.1 深度缓存(Z-buffer)算法
7、由来： 帧缓冲器 保存各像素颜色值(CB) z缓冲器 -保存各像素处物体深度值(ZB) z缓冲器中的单元与帧缓冲器中的单元一一对应 思路： 将z缓冲器中各单元的初始值置为-1(规范视见体的最小n值）。当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值（保存在该像素所对应的Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改变。,8.2 面消隐,x,y,z,视线方向,视点位置,屏幕像素,F Buffer,ZBuffer,投影面,深度缓存算法 (
8、 ZBuffer算法) ZBuffer - 用于存放与屏幕上像素点对应的物体上点的深度值。,Z-buffer算法的步骤如下： 初始化ZB和CB，使得ZB(i, j)=Zmax，CB(i, j)=背景色。其中，i=1, 2, , m，j=1, 2, , n。 对多边形，计算它在点(i, j)处的深度值zi, j。 若zijZB(i, j)，则ZB(i, j)=zij，CB(i, j)=多边形的颜色。 对每个多边形重复、两步。最后，在CB中存放的就是消隐后的图形。,这个算法的关键在第步，要尽快判断出哪些点落在一个多边形内 ，并尽快求出一个点的深度值 。（下页） 优点： 算法简单，易于硬件实现。 缺
9、点： (1)：ZB和CB两个缓存数组占用的存储单元太多 ，需要有一个较大容量的 ZBuffer 。 (2)：在每个多边形占据的每个像素处都要计算深度值，计算量大； (3)：在实现反走样、透明和半透明等效果方面困难（可以用A-缓存器算法解决）。,Z-Buffer算法实现中的关键问题 判断点( i, j )是否在多边形Fk在投影面上的投影内 解决办法：采用包含测试。 计算多边形Fk在点( i, j )处的深度值 Zi, j 若多边形Fk的平面方程为： ax + by + cz + d = 0 若 c 0，则 axi + byi + d c 若 c = 0，则多边形Fk的法线方向与 Z 轴垂直， F
10、k在投影 面上的投影为一条直线，可不予考虑。,Zi, j = ,8.2.2 区间扫描线算法 在多边形填充算法中，活性边表的使用取得了节省运行空间的效果。用同样的思想改造Z-buffer算法：将整个绘图区域分割成若干个小区域，然后一个区域一个区域地显示，这样Z缓冲器的单元数只要等于一个区域内像素的个数就可以了。如果将小区域取成屏幕上的扫描线，就得到扫描线Z缓冲器算法。,for ( 各条扫描线) 将帧缓冲器I(x)置为背景色； 将Z缓冲器的Z(x)置为最大值； for (每个多边形） 求出多边形在投影平面上的投影与当前扫描线的相交区间 for （该区间内的每个像素） if ( 多边形在此处的Z值小
11、于Z(x) ） 置帧缓冲器I(x)值为当前多边形颜色； 置Z缓冲器Z(x)值为多边形在此处的Z值; ,扫描线算法描述,8.2.3 深度排序算法（画家算法） 由来：画家的作画顺序暗示出所画物体之间的相互遮挡关系 算法基本思路： 1）先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中； （线性表构造： 距观察点远的称优先级低，放在表头；距观察点 近的称优先级高，放在表尾。该表称为深度优先级表） 2）然后按照从表头到表尾的顺序逐个绘制物体。,画家算法,关键：如何对场景中的物体按深度（远近）排序，建立深度优先级表？ 一种针对多边形的排序算法如下： 假定在规范化投影坐标系uvn中,投影方向
12、是n轴的负向，因而n坐标大距观察者近。记nmin(P) nmax(P)分别为多边形P的各个顶点n坐标的最小值和最大值，算法步骤如下：,画家算法步骤,Step 1: 将场景中所有多边形存入一个线性表（链表或数组），记为L; Step 2: 如果L中仅有一个多边形，算法结束；否则根据每个多边形的nmin对它们预排序。不妨假定多边形P落在表首，即nmin(P)为最小。再记Q为L P(表中其余多边形）中任意一个； Step 3: 判别P, Q之间的关系，有如下二种：,step 3.1: 对有的Q，有nmax(P) nmin (Q),需进一步判别： step 3.2.1 若P,Q投影P,Q的包围盒不相交
13、，则P,Q在表中的次序不重要，令L = L P, 返回step 2;否则进行下一步。 step 3.2.2 若P的所有顶点位于Q所在平面的不可见的一侧，则P,Q关系正确，令L = L P, 返回step 2;否则进行下一步。 step 3.2.3 若Q 的所有顶点位于P所在平面的可见的一侧，则P,Q关系正确，令L = L P, 返回step 2;否则进行下一步。 step 3.2.4 对P,Q投影P,Q求交，若P,Q不相交，则P,Q在表中的次序不重要，令L = L P, 返回step 2;否则在它们所相交的区域中任取一点，计算P,Q在该点的深度值，如果P的深度小，则P,Q关系正确，令L = L
14、 P, 返回step 2;否则交换P,Q,返回step 3.,画家算法步骤,画家算法,在多边形面片数量很大时（而且没有循环遮挡或贯穿的情况下），画家消隐算法最快。 本算法不能处理的情况： 多边形循环遮挡 多边形相互穿透 解决办法：分割成两个,8.2.4 区域细分算法（Warnock算法）,利用图形的区域连贯性，在连续的区域上确定可见面及其颜色、亮度。 基本思想：把物体投影到全屏幕窗口上，递归地分割窗口，直到窗口内目标足够简单，可以直接显示为止。 具体步骤： 1) 观察整个窗口区域，判别窗口是否足够简单，可考虑以下两个观察点： 窗口内无任何可见物体。 窗口已被一个可见面片完全充。 2)将非单纯的
15、窗口四等分为四个子窗口，对每个子窗口再进一步判别是否是单纯的，直到窗口单纯或窗口边长已缩至一个象素点为止。 即使屏幕分辨率为10241024，视图被细分10次后，也能使每个子窗口覆盖一个像素。,基本思想： 在图象空间中，将待显示的所有多边形按深度值从小到大排序，用前面可见多边形去切割后面的多边形，最终使得每个多边形要么是完全可见，要么是完全不可见。用区域排序算法消隐，需要用到一个多边形裁剪算法。,8.2.5 其它算法 区域排序算法（1）,当对两个形体相应表面的多边形进行裁剪时，我们称用来裁剪的多边形为裁剪多边形，另一个多边形为被裁剪多边形。算法要求多边形的边都是有向的，不妨设多边形的外环总是顺时针方向的，并且沿着边的走向，左侧始终是多边形的外部，右侧是多边形的内部。若两多边形相交，新的多边形可以用“遇到交点后向右拐”的规则来生成。于是被裁剪多边形被分为两个乃至多个多边形；我们把其中落在裁剪多边形外的多边形叫作外部多边形；把落在裁剪多边形之内的多边形叫作内部多边形。,区域排序算法（2）,算法的步骤： 进行初步深度排序，如可按各多边形z向坐标最小值(或最大值、平均值)排序。 选择当前深度最小(离视点最近)的多边形为裁剪多边形。 用裁剪多边形对那些深度值更大的多边形进行裁剪。 比较裁剪多边形与各个内部多边形的深度，检查裁剪多边形是否是离视点最近的多边形。如果裁
