计算机图形学-消隐

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

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

3、可见部分的复杂程度而增加。 z xy 7 1 概述 n消隐的分类 1. 按消隐对象分类： n线消隐 (Hidden-line)： n对象：隐藏线，主要应用于早期的线框模型； n面消隐 (Hidden-surface)： n对象：隐藏面，应用于面模型、实体模型，用于真实 感绘制； 8 1 概述 2. 按消隐算法的实现空间分类： n对象空间的消隐算法 n以场景中的物体为处理单元；求出所有点、边、面遮挡关 系（求出物体表面的可见部分）。 nRoberts算法，光线投射算法 n图像空间的消隐算法 n以视区内的每个像素为处理单元；对视区内每个象素进行 判断，决定哪个多边形在该象素可见。 nZ-buffe

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

5、兼顾 两者。 10 消隐 1 概述 3 提高消隐算法的效率 4 面消隐 11 2 线消隐 n隐藏线的产生是因为在给定的观察方向下，某些棱(或棱的一部 分)被表面多边形遮挡，因此多面体隐藏线消除可以归结为一个 根本问题： n在给定的观察方向下，给定一条空间线段和一个多边形，判 断线段是否被多边形遮挡。如果遮挡，求出遮挡部分。 n对造型的要求： n要求造型系统中有面的信息，最好有体的信息； n如果存在多个实体，它们互不相交； n求交的线段和面(多边形)在空间不相交； 多边形网格模型可以满足要求。 线面相交 12 2 线消隐 n多面体隐藏线消除的步骤如下： (1)将线段p1p2和多边形投影到投影 平

6、面上得到线段p1p2和多边形； (2)计算线段p1p2和多边形各条边 的交点； (3)交点将p1p2分成若干个子线段，特 别地当交点不存在时，子线段只有 一个，即p1p2自身。现在每个子线 段上的所有点具有相同的隐藏性； (4)分别判断各个子线段的隐藏性： E 13 2 线消隐 (4)分别判断各个子线段的隐藏性： 取子线段的中点，判断该点是否在 多边形内： a.如不在多边形内，子线段与多边形 是分离的，不存在隐藏关系，子 线段是可见的； b.如在多边形内，从子线段中点向视 点引射线，如果射线与多边形 相交，求交点深度值，判断该子 线段是否被多边形遮挡，否则该 子线段可见。 E 14 2 线消隐

7、 n线段和一个多边形进行隐藏性 判断时，涉及到的运算包括： n投影变换 n平面上线段和多边形的求交 n判断点是否在多边形内 n空间中射线和平面求交。 n如果将多面体的每条棱与每个 多边形都按上面的方法消除隐 藏线，那么计算量将非常大。 n如何提高算法效率？ n减少计算的对象。 A B C D E F G H I J K 15 消隐 1 概述 2 线消隐 4 面消隐 16 3 提高消隐算法的效率 1. 消除自隐线、面 2. 深度测试 3. 包围盒技术 4. 利用连贯性 5. 空间分割技术 6. 物体分层表示 17 1. 消除自隐线、面 n对于多面体的任一个面，可以根据 其外法向n和视矢量E的夹角

8、来进行 可见性检测。 n法向n：规定每个多边形的法向都是 指向物体外部的。 n前向面： (-90,90)时，表示 该表面可见，称为前向面。 n后向面： 90, -90时，表示 该表面不可见，称为后向面 。 n E 前向面 后向面 n n剔除依据：后向面总是被前向面所遮挡，从而不可见。不 会由于后向面的遮挡，而使别的棱成为不可见的。因此计 算时，可以把这些后向面全部去掉，这并不影响消隐结果。 n E 18 1. 消除自隐线、面 n图中的JFAE、HCBG 和DEABC所在的面均 为后向面。其它为前向 面。 A B C D E F G H I J n 19 2. 深度测试 n在观察坐标系下判断线段

9、与 多边形的前后关系。快速排 除不需求交的情况。 n如：多边形完全在线段之后 (线段的两端点均比多边形 靠近视点)，则线段完全可 见，无需就线段和多边形的 遮挡关系进行进一步判断。 COP 20 3. 包围盒技术 n一个形体的包围盒指的是包 围它的简单形体。 n一个好的包围盒要具有两个 条件： n包围和充分紧密包围着形 体； n对其的测试比较简单。 n应用：避免盲目求交。 21 3. 包围盒技术 n包围盒不相交，线段和多边形也不相交，线段完全可见， 无需就线段和多边形的遮挡关系进行进一步判断。可推广 到面与面的遮挡快速判断。 n例如：两个空间多边形A、B在投影平面上的投影分别为A， B ，因为

10、A 、B的矩形包围盒不相交，则A、B不相交， 无须进行遮挡测试。右图：包围盒相交，投影也相交；包 围盒相交，投影不相交。 A A B B 22 4. 利用连贯性 n事物的属性之间有一定的连贯性，其属性值 通常是平缓过渡的，如颜色值、空间位置关 系等。 n物体连贯性 n面的连贯性 n区域连贯性 n扫描线的连贯性 n深度连贯性 23 4. 利用连贯性 n物体连贯性： n如果物体A与物体B是完全相互分离的，则在消隐时，只需 比较A、B两物体之间的遮挡关系就可以了，无须对它们的 表面多边形逐一进行测试。例如，若A距视点较B远，则在 测试B上的表面的可见性时，无须考虑A的表面。 n面的连贯性： n一张面

11、内的各种属性值一般都是缓慢变化的，可采用增量 形式对其进行计算。 24 4. 利用连贯性 n区域连贯性： n区域指屏幕上一组相邻的像素，它们通常为同一个可见面 所占据，可见性相似。 n区域连贯性表现在扫描线上的每个区间内通常只有一个面 可见。 n扫描线的连贯性： n相邻两条扫描线上，可见面的分布情况相似。 n深度连贯性： n同一表面上的相邻部分深度是相近的，而占据屏幕上同一 区域的不同表面的深度不同。这样在判断表面间的遮挡关 系时，只需取其上一点计算出深度值，比较该深度值即可 得到结果。 25 5. 空间分割技术 n依据：场景中的物体，它们的投影在投影平面上是否有重叠 部分？（是否存在相互遮挡

12、的可能？）对于根本不存在相互 遮挡关系的物体，应避免这种不必要的测试。 n方法： n将投影平面上的窗口分成若干小区域； n为每个小区域建立相关物体表，表中的物体投影于该区域； n则在小区域中判断那个物体可见时，只要对该区域的相关 物体表中的物体进行比较即可。 n复杂度比较： n不妨假定每个小区域的相关物体表中平均有h个物体，场 景中有k个物体，由于物体在场景中的分布是分散的，显 然h远小于k。根据方法所述，其算法复杂度为O(h*h)， 远小于O(k*k)。 26 6. 物体分层表示 n物体分层表示 n表示形式：模型变换中的树形表示方式。 n原理：减少场景中物体的个数，从而降低算法复杂度。 小汽

13、车小汽车 车身车身左前轮左前轮左后轮左后轮右后轮右后轮右前轮右前轮 车头车头车尾车尾 27 6. 物体分层表示 n方法：将父节点所代表的物体看成子节点所代表物体的包 围盒，当两个父节点之间不存在遮挡关系时，就没有必要 对两者的子节点做进一步测试。父节点之间的遮挡关系可 以用它们之间的包围盒进行预测试。 小汽车小汽车 车身车身左前轮左前轮左后轮左后轮右后轮右后轮右前轮右前轮 车头车头车尾车尾 28 消隐 1 概述 2 线消隐 3 提高消隐算法的效率 29 4 面消隐 1. 画家算法 2. Z-Buffer算法 30 1. 画家算法 n由来：画家的作画顺序暗示出所 画物体之间的相互遮挡关系。 n算

14、法基本原理： 1）先把屏幕置成背景色； 2）将场景中的物体的各个面按其距观察点的远近进行排序，结 果放在一张线性表中；（线性表构造：距观察点远的优先级 低，放在表头；距观察点近的优先级高，放在表尾 ）该表称 为深度优先级表。 3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表 面。 n也称表优先级算法。 31 1. 画家算法 n关键：如何对场景中的物体表面按深度（远近）排序，建立 深度优先级表？ n先讨论在深度优先级排序中两个多边形P和Q之间的关系。 多边形可以按其最大或最小z值徘序，不妨假设按多边形的 最大z值进行预排序，即zmax(P)zmax(Q)。 z x Q P P Q z x

15、 z x P Q z x P Q z x P Q P Q z x 32 1. 画家算法 1. 深度重叠测试: 对于简单情况，如图1所示，P、Q两平面满足zmax(P) zmax(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等情况。这时需进行投影重叠测试。 z x Q P 图1 P Q z x 图2 P Q z x 图3 33 1. 画家算法 2.

16、投影重叠判断： P和Q在oxy平面上投影的包围盒在x方向上不相交； P和Q在oxy平面上投影的包围盒在y方向上不相交； P和Q在oxy平面上的投影不相交； P在Q之后。P的各顶点均在Q的远离视点的一侧； Q在P之前。Q的各顶点均在P的靠近视点的一侧； y y y 上面5项只要 有一项成立， P就不遮挡Q。 如果所有测试 失败，则进行 精确的重叠测 试。 z x P Q z x P Q z x P Q 34 1. 画家算法 3. 精确的重叠测试： 以上所有测试失败，须作进一步判断：对P、Q在xoy平 面上的投影做求交运算。 n上图给出几个复杂的情况，如果遇到多边形相交或循环相交， 无法直接建立正

17、确的深度优先表。解决方法是沿多边形所在平 面间的交线循环分割这些多边形，至最后可完全确定其优先级 表。见虚线所示。 35 1. 画家算法 n排序计算量大； n多边形相交或循环重叠时，必须分割多边形。 36 2. Z-Buffer算法 nZ缓冲器算法是所有图像空间算法中最简单的一种隐藏面消除 算法。 n帧缓冲器：用来存储图像空间中每一个象素的属性（颜色）； nZ缓冲器：用来存储图像空间中每一个可见象素所对应物体的深 度(或Z坐标)，是一个独立的深度缓冲器。 n帧缓冲器和Z缓冲器的存储单元数目相同，并且都等于屏幕上像 素的个数。 屏幕帧缓冲器Z缓冲器 每个单元存放对 应象素的颜色值 每个单元存放对

18、 应象素的深度值 37 2. Z-Buffer算法 n算法思想： n投影，然后计算将要写入帧缓冲器象素的深度(或Z值)，并 与已存储在Z缓冲器中该象素的原来深度进行比较 ； n若新象素点深度位于帧缓冲器中原象素点的前面，则将新 象素的属性写入帧缓冲器，并将相应的深度(Z值)也写入Z 缓冲器；否则，帧缓冲器和Z缓冲器中的内容不变。 n本算法的实质是对给定的像素(x,y)，寻找最小的z(x,y)值。 38 2. Z-Buffer算法 n视区：32*32，平行投影，视点在Z轴正向，投影平面 为xoy平面。 n背景：0；矩形：1；三角形：2。 nz缓冲区：32*32*4。 X y z P2(10,25,10) P1(10,5,10) P4(25,5,10) P5(15,15,15) P6(25,25, 5) P7(30,10, 5) P3(25,25,10) X y 39 2. Z-Buffer算法 1.设置帧缓冲器为背景颜色(或光强度) 2.设置Z缓冲器为最大Z值 3.while 对每一个多边形 do begin 4. while 对多边形中的每一个元素 do begin 5. 计算该象素的深度z(x,y) /*比较z(x,y)与存储在Z缓冲其中该