计算机图形学-消隐.ppt

1、1,消隐,2,消隐,1 概述 2 线消隐 3 提高消隐算法的效率 4 面消隐,3,1 概述,什么叫做“消隐”？为什么要进行“消隐”？ 将三维场景绘制在计算机二维显示屏上必须经过投影变换，投影变换将三维信息变换到二维平面上，这个过程中深度信息被丢失，生成的图形往往具有二义性。 要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，简称为“消隐”。 经过消隐得到的投影图称为物体的“真实”图形。 通过消隐，也可降低光照、纹理等算法的计算量。,4,1 概述,消隐的对象是三维物体。 三维物体的表示主要有B-Rep和CSG表示。 在进行绘制时，消隐的对象是多边形网格模型。

2、消隐结果与被观察物体有关，也与视点、视方向有关。,5,1 概述,消隐算法的实现空间： 消隐算法可以在对象空间或图像空间中实现。对象空间算法是在定义对象的坐标系中实现的，而图像空间算法是在对象显示的屏幕坐标系中实现的。,6,1 概述,消隐算法的实现空间： 对象空间算法以尽可能高的精度完成几何计算，所以可以把图像放大许多倍而不致损害其准确性； 图像空间算法只能以与显示屏的分辨率相适应的精度来完成计算，所以其图像的放大效果较差。 另外，这两类算法的性能特性也是不同的。对象空间算法所需的计算时间随场量中物体的个数而增加；而图像空间的计算时间则随图像中可见部分的复杂程度而增加。,7,1 概述,消隐的分类

3、 1. 按消隐对象分类： 线消隐 (Hidden-line)： 对象：隐藏线，主要应用于早期的线框模型； 面消隐 (Hidden-surface)： 对象：隐藏面，应用于面模型、实体模型，用于真实感绘制；,8,1 概述,2. 按消隐算法的实现空间分类： 对象空间的消隐算法 以场景中的物体为处理单元；求出所有点、边、面遮挡关系（求出物体表面的可见部分）。 Roberts算法，光线投射算法 图像空间的消隐算法 以视区内的每个像素为处理单元；对视区内每个象素进行判断，决定哪个多边形在该象素可见。 Z-buffer、扫描线、Warnock 对象空间和图像空间结合的消隐算法 在对象空间中预先计算面的可见

4、性优先级，再在图像空间中生成消隐图。 画家算法,9,1 概述,消隐算法的选择： 不同的应用场合有不同的算法要求，有些算法要求速度快，有些要求图形的真实度高。例如： 快速消隐算法可用于实时模拟如飞行模拟等； 具有高度真实感图形的消隐算法可用于计算机动画等领域，所生成的图形一般具有连续色调，并能产生阴影、透明、表面纹理及反射、折射等视觉效果。不过这类算法比较慢。产生一幅图可能需要几分钟甚至几小时。 所以，在进行消隐算法的设计时，应在计算速度和图形细节之间进行权衡，任何一种算法都不能兼顾两者。,10,消隐,1 概述 2 线消隐 3 提高消隐算法的效率 4 面消隐,11,2 线消隐,隐藏线的产生是因为

5、在给定的观察方向下，某些棱(或棱的一部分)被表面多边形遮挡，因此多面体隐藏线消除可以归结为一个根本问题： 在给定的观察方向下，给定一条空间线段和一个多边形，判断线段是否被多边形遮挡。如果遮挡，求出遮挡部分。 对造型的要求： 要求造型系统中有面的信息，最好有体的信息； 如果存在多个实体，它们互不相交； 求交的线段和面(多边形)在空间不相交； 多边形网格模型可以满足要求。,12,2 线消隐,多面体隐藏线消除的步骤如下： (1)将线段p1p2和多边形投影到投影平面上得到线段p1p2和多边形； (2)计算线段p1p2和多边形各条边的交点； (3)交点将p1p2分成若干个子线段，特别地当交点不存在时，子

6、线段只有一个，即p1p2自身。现在每个子线段上的所有点具有相同的隐藏性； (4)分别判断各个子线段的隐藏性：,13,2 线消隐,(4)分别判断各个子线段的隐藏性： 取子线段的中点，判断该点是否在多边形内： a.如不在多边形内，子线段与多边形 是分离的，不存在隐藏关系，子线段是可见的； b.如在多边形内，从子线段中点向视点引射线，如果射线与多边形 相交，求交点深度值，判断该子线段是否被多边形遮挡，否则该子线段可见。,14,2 线消隐,线段和一个多边形进行隐藏性判断时，涉及到的运算包括： 投影变换 平面上线段和多边形的求交 判断点是否在多边形内 空间中射线和平面求交。 如果将多面体的每条棱与每个多

7、边形都按上面的方法消除隐藏线，那么计算量将非常大。 如何提高算法效率？ 减少计算的对象。,K,15,消隐,1 概述 2 线消隐 3 提高消隐算法的效率 4 面消隐,16,3 提高消隐算法的效率,1. 消除自隐线、面 2. 深度测试 3. 包围盒技术 4. 利用连贯性 5. 空间分割技术 6. 物体分层表示,17,1. 消除自隐线、面,对于多面体的任一个面，可以根据其外法向n和视矢量E的夹角来进行可见性检测。 法向n：规定每个多边形的法向都是指向物体外部的。 前向面： (-90,90)时，表示该表面可见，称为前向面。 后向面： 90, -90时，表示该表面不可见，称为后向面 。,剔除依据：后向面

8、总是被前向面所遮挡，从而不可见。不会由于后向面的遮挡，而使别的棱成为不可见的。因此计算时，可以把这些后向面全部去掉，这并不影响消隐结果。,18,1. 消除自隐线、面,图中的JFAE、HCBG和DEABC所在的面均为后向面。其它为前向面。,19,2. 深度测试,在观察坐标系下判断线段与多边形的前后关系。快速排除不需求交的情况。 如：多边形完全在线段之后(线段的两端点均比多边形靠近视点)，则线段完全可见，无需就线段和多边形的遮挡关系进行进一步判断。,20,3. 包围盒技术,一个形体的包围盒指的是包围它的简单形体。 一个好的包围盒要具有两个条件： 包围和充分紧密包围着形体； 对其的测试比较简单。 应

9、用：避免盲目求交。,21,3. 包围盒技术,包围盒不相交，线段和多边形也不相交，线段完全可见，无需就线段和多边形的遮挡关系进行进一步判断。可推广到面与面的遮挡快速判断。 例如：两个空间多边形A、B在投影平面上的投影分别为A，B ，因为A 、B的矩形包围盒不相交，则A、B不相交，无须进行遮挡测试。右图：包围盒相交，投影也相交；包围盒相交，投影不相交。,22,4. 利用连贯性,事物的属性之间有一定的连贯性，其属性值通常是平缓过渡的，如颜色值、空间位置关系等。 物体连贯性 面的连贯性 区域连贯性 扫描线的连贯性 深度连贯性,23,4. 利用连贯性,物体连贯性： 如果物体A与物体B是完全相互分离的，则

10、在消隐时，只需比较A、B两物体之间的遮挡关系就可以了，无须对它们的表面多边形逐一进行测试。例如，若A距视点较B远，则在测试B上的表面的可见性时，无须考虑A的表面。 面的连贯性： 一张面内的各种属性值一般都是缓慢变化的，可采用增量形式对其进行计算。,24,4. 利用连贯性,区域连贯性： 区域指屏幕上一组相邻的像素，它们通常为同一个可见面所占据，可见性相似。 区域连贯性表现在扫描线上的每个区间内通常只有一个面可见。 扫描线的连贯性： 相邻两条扫描线上，可见面的分布情况相似。 深度连贯性： 同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同。这样在判断表面间的遮挡关系时，只需

11、取其上一点计算出深度值，比较该深度值即可得到结果。,25,5. 空间分割技术,依据：场景中的物体，它们的投影在投影平面上是否有重叠部分？（是否存在相互遮挡的可能？）对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试。 方法： 将投影平面上的窗口分成若干小区域； 为每个小区域建立相关物体表，表中的物体投影于该区域； 则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较即可。 复杂度比较： 不妨假定每个小区域的相关物体表中平均有h个物体，场景中有k个物体，由于物体在场景中的分布是分散的，显然h远小于k。根据方法所述，其算法复杂度为O(h*h)，远小于O(k*k)。,26,

12、6. 物体分层表示,物体分层表示 表示形式：模型变换中的树形表示方式。 原理：减少场景中物体的个数，从而降低算法复杂度。,27,6. 物体分层表示,方法：将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。,28,消隐,1 概述 2 线消隐 3 提高消隐算法的效率 4 面消隐,29,4 面消隐,1. 画家算法 2. Z-Buffer算法,30,1. 画家算法,由来：画家的作画顺序暗示出所画物体之间的相互遮挡关系。,算法基本原理： 1）先把屏幕置成背景色； 2）将场景中的物

13、体的各个面按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的优先级低，放在表头；距观察点近的优先级高，放在表尾 ）该表称为深度优先级表。 3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表面。 也称表优先级算法。,31,1. 画家算法,关键：如何对场景中的物体表面按深度（远近）排序，建立深度优先级表？ 先讨论在深度优先级排序中两个多边形P和Q之间的关系。多边形可以按其最大或最小z值徘序，不妨假设按多边形的最大z值进行预排序，即zmax(P)zmax(Q)。,32,1. 画家算法,1. 深度重叠测试: 对于简单情况，如图1所示，P、Q两平面满足zmax(P)zma

14、x(Q)，且Zmin(P)Zmax(Q)，则P肯定不能遮挡Q； 如图2所示，虽然P，Q两平面满足zmax(P)zmax(Q)，但Zmin(P)Zmax(Q)，但是如果按照优先级表中顺序(P排在Q之前)将P，Q分别写入帧缓冲器中期的话，则Q将部分地遮挡P，而事实上是P部分地遮挡Q。 再考虑图3等情况。这时需进行投影重叠测试。,33,1. 画家算法,2. 投影重叠判断： P和Q在oxy平面上投影的包围盒在x方向上不相交； P和Q在oxy平面上投影的包围盒在y方向上不相交； P和Q在oxy平面上的投影不相交； P在Q之后。P的各顶点均在Q的远离视点的一侧； Q在P之前。Q的各顶点均在P的靠近视点的一

15、侧；,上面5项只要有一项成立，P就不遮挡Q。 如果所有测试失败，则进行精确的重叠测试。,34,1. 画家算法,3. 精确的重叠测试： 以上所有测试失败，须作进一步判断：对P、Q在xoy平面上的投影做求交运算。,上图给出几个复杂的情况，如果遇到多边形相交或循环相交，无法直接建立正确的深度优先表。解决方法是沿多边形所在平面间的交线循环分割这些多边形，至最后可完全确定其优先级表。见虚线所示。,35,1. 画家算法,排序计算量大； 多边形相交或循环重叠时，必须分割多边形。,36,2. Z-Buffer算法,Z缓冲器算法是所有图像空间算法中最简单的一种隐藏面消除算法。 帧缓冲器：用来存储图像空间中每一个

16、象素的属性（颜色）； Z缓冲器：用来存储图像空间中每一个可见象素所对应物体的深度(或Z坐标)，是一个独立的深度缓冲器。 帧缓冲器和Z缓冲器的存储单元数目相同，并且都等于屏幕上像素的个数。,37,2. Z-Buffer算法,算法思想： 投影，然后计算将要写入帧缓冲器象素的深度(或Z值)，并与已存储在Z缓冲器中该象素的原来深度进行比较 ； 若新象素点深度位于帧缓冲器中原象素点的前面，则将新象素的属性写入帧缓冲器，并将相应的深度(Z值)也写入Z缓冲器；否则，帧缓冲器和Z缓冲器中的内容不变。 本算法的实质是对给定的像素(x,y)，寻找最小的z(x,y)值。,38,2. Z-Buffer算法,视区：32

17、*32，平行投影，视点在Z轴正向，投影平面为xoy平面。 背景：0；矩形：1；三角形：2。 z缓冲区：32*32*4。,39,2. Z-Buffer算法,设置帧缓冲器为背景颜色(或光强度) 设置Z缓冲器为最大Z值 while 对每一个多边形 dobegin while 对多边形中的每一个元素 do begin 计算该象素的深度z(x,y) /*比较z(x,y)与存储在Z缓冲其中该位置处的深度Z(x,y)*/ if z(x,y)Z(x,y) then 将此多边形的颜色(或光强度) 写入帧缓冲器且Z(x,y)z(x,y) endend end of algorithm,40,2. Z-Buffer算法,算法中有关Z值的计算可以根据平面方程求得。 设平面方程为：ax+by+cz+d=0 则 z=-(ax+by+d)/cc0由于同一条扫描线上的y分量为常量，所以沿扫描线上的象素 x1=x+x y1=y处的深度为：z1 =-(ax1+by+d)/c =-(ax+by+d)/c-(a/c)x =z-(a/c)x若x=1，则 z=z-a/c。 所以，根据扫描线上各点前后的连贯性，运用增量方法计算Z值是极为方便的。,41,2. Z-