第8章 消隐问题.ppt

1、图形学与虚拟环境 郑州大学信息工程学院 赵新灿,1,第8章 消隐问题,8.1 基本概念,8.2 消隐基本技术,8.3 消隐算法,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,2,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,3,线框图,消隐图,真实感图形,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,4,线框图的二义性,消隐技术就是要解决形体的二义性问题，通过消隐线或消隐面方法，提高图形的真实感。,消隐是产生真实感的方法之一。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,5,按消隐对象分类消隐线算法和消隐面算法。,早期图形显示器是用线条表示图形，消隐主要 是消隐线问题。使用光栅显示器

2、后，物体可用连续 变化的色调来描述，消隐算法的研究渐渐转向消隐 面的问题。,8.1 基本概念一、消隐算法分类,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,6,按消隐空间分类物空间算法和像空间算法。,物空间算法是在描述物体的物理坐标系中实现的，以场景中的物体为处理单元，通过一个面与其余面的可见性比较进行。特点是算法可以达到相当高的精度。,for (场景中的每一个物体) 将其与场景中的其它物体比较，确定其表 面的可见部分；显示该物体表面的可见部分； ,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,7,像空间算法是在观察物体的屏幕坐标系中实 现的，以窗口内的每个像素为处理单元 。特点是 算法精

3、度低，只能达到屏幕精度为止，但速度往 往更高。,for (窗口内的每一个像素) 确定距视点最近的物体，以该物体表 面的颜色来显示像素,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,8,二、算法复杂度,假设场景中有k个物体，平均每个物体表面 由h个多边形构成，显示区域中有m x n个像素， 则： 第一种算法的复杂度为： O(kh)(kh) 第二种算法的复杂度为：O(mnkh),图形学与虚拟环境 郑州大学信息工程学院 赵新灿,9,物空间消隐算法: 是就一个物体表面的h个多边形中的每个面 与其余h-1个面进行比较，精确地求出物体上每 个棱边或每个面的遮挡关系。算法的计算量正比 于h2，即算法复杂度

4、为：O(h)2) 。 则，k个物体的算法复杂度为：O(kh)2) 。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,10,象空间消隐算法： 这类算法对屏幕上的每个象素进行判断，以 决定物体上哪个多边形在该象素 点上是可见的。 若屏幕上有mn个象素点，每个物体表面上有h 个多边形，则该类消隐算法计算量正比于mnh。 k个物体的算法复杂度为： O(mnkh) 。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,11,各种消隐算法均采用一定形式的几何排序。 通过排序，可搜查出位置上靠近观察者的几何 元素，确定几何元素之间在位置上的遮挡关系，解决消隐计算的主要问题。各种算法都有各自的排序方法和排序次

5、序。排序次序影响算法的效率。,三、算法排序,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,12,8.2 消隐基本技术,为了提高消隐算法的效率，各种消隐算法常 采用一些有效的消隐基本算法。,利用连贯性 将透视投影转换成平行投影 包围盒技术 背面剔除 空间分割技术 物体分层表示,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,13,物体连贯性 面的连贯性 区域连贯性 扫描线的连贯性 深度连贯性,一、利用连贯性,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,14,二、包围盒技术,一个形体的包围盒指的是包围它的简单形体。 比如，2D的矩形，3D的立方块、长方体、球等。,目的： 避免盲目的求交测试；

6、 各物体间的比较等。,一个好的包围盒要具有两个条件： 包围和充分紧密包围着形体； 对其的测试比较简单。,例：矩形包围盒及长方体包围盒提高算法效率,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,15,三、背面剔除,外法向 外法向与投影方向（观察方向）的夹角 前向面与后向面（背面）,剔除依据： 物体表面是封闭的，背面总是 被前向面所遮挡，从而始终是 不可见的。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,16,视线-法线夹角法 N 面的法向量 K 面上一点指向观察点的向量 = cos-1( ) 0= 时 可见 = = 时 不可见,N. K,|N|K|,图形学与虚拟环境 郑州大学信息工程学院

7、赵新灿,17,四、空间分割技术,依据：场景中的物体，它们的投影在投影平面上 是否有相互遮挡的重叠部分？ 对于根本不存在相互遮挡关系的物体，应 避免这种不必要的测试。,方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断哪个物体可见时，只要对本区域的相关物体表中的物体进行比较即可。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,18,复杂度比较： 假定每个小区域的相关物体表中平均有h个 物体，场景中有k个物体，由于物体在场景中的分 布是分散的，显然h远小于k。 根据物空间消隐方法所述，其算法复杂度为 O(h2),远小于O(k2)

8、。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,19,五、物体分层表示,表示形式：模型变换中的树形表示方式 原理：减少场景中物体的个数，降低算法复杂度。,方法： 将父节点所代表的物体看成子节点物体的包围盒，当两个父节点之间不存在遮挡关系时，就勿对两者的子节点做进一步测试。 父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,20,六、将透视投影转换成平行投影,消隐与透视关系较密切，体现在： 1）消隐必须在投影之前完成； 2）物体之间的遮挡关系与投影中心（视点） 的选取有关； 3）物体之间的遮挡关系与投影方式有关。,图形学与虚拟环境 郑州大

9、学信息工程学院 赵新灿,21,8.3 消隐算法,一、后向面判别 快速简单地判别多面体后向面（back face）的物空间算法基于前-后测试的基础上。 设点（x,y,z）满足： Ax+By+Cz+D0 该多边形为后向面,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,22,若观察向量平行于Z轴，则平面法向量C满足C0,则该多边形为一后向面。无法观察C=0的所有多边形面，则C0即可判断其为后向面。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,23,二、Z（深度）缓冲器算法(depth-buffer method),由来： 帧缓冲器保存各像素颜色值 z 缓冲器保存各像素处物体深度值 z缓冲器中的

10、像素单元与帧缓冲器中的像素 单元一一对应,一种典型的、也是最简单的图象空间消隐算法,它在投影面上的每一像素位置比较场景中所有面的深度。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,24,思路： 先将z 缓冲器中各单元的初始值置为-1(规范 观察体的最小n值）。 当要改变某个像素的颜色值时，首先检查当 前多边形的深度值是否大于该像素原来保存的Z 缓冲器中的深度值，如果大于，说明当前多边形 更靠近观察点，用它的颜色替换像素原来的颜色； 否则说明在当前像素处，当前多边形被前面所绘 制的多边形遮挡了，是不可见的，像素的颜色值 不改变。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,25,图形学与

11、虚拟环境 郑州大学信息工程学院 赵新灿,26,算法描述：,for ( v= 0;vvmax;v+) for (u= 0; uumax; u+) 将帧缓冲器的第(u,v)单元置为背景色； 将Z缓冲器的第(u,v)单元置为-1(可见的最小深度值) ,for (每个多边形） for (多边形在投影平面上的投影区域内的每个像素(u,v) ) 计算多边形在当前像素(u,v)处的深度值d； if (d Z缓冲器的第(u,v)单元的值) 置帧缓冲器的第(u,v)单元值为当前多边形颜色； 置Z缓冲器的第(u,v)单元值为d; ,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,27,优点： 简单稳定，利于硬件实

12、现 缺点：1）需要一个额外的Z 缓冲器 2）在每个多边形占据的每个像素处都要 计算深度值，计算量大,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,28,三、A缓存算法,深度缓存算法的一个缺点是：在每个像素点只能找到一个可见面，即它只能处理非透明表面，而无法处理多个表面的累计强度值。 A缓存（A-buffer）算法是深度缓存算法的延伸，这种深度缓存的扩充是一种反走样、区域平均、可见性检测方法。该过程的缓存区域为累计缓存（accumulation buffer），因为它除了深度值外还用于存储各种表面数据。A缓存算法对深度缓存进行了扩充，使其每一位置均对应于一个表面链表。因此，不仅可以考虑各像素点

13、处多个表面的强度值，还可以对对象的边界进行反走样处理。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,29,A缓存中每个单元包含两个域： 深度域-存储一个正的或负的实数 强度域-存储表面的强度信息或指针值,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,30,四、扫描线Z缓冲器算法 (scan-line method),由来： Z缓冲器算法中所需要的Z缓冲器容量较 大，为克服这个缺点可以将整个绘图区域分割 成若干个小区域，然后一个区域一个区域地显 示，这样Z缓冲器的单元数只要等于一个区域内 像素的个数就可以了。如果将小区域取成屏幕 上的扫描线，就得到扫描线Z缓冲器算法。,图形学与虚拟环境 郑

14、州大学信息工程学院 赵新灿,31,算法描述,这个像空间的隐面消除算法沿各扫描线计算并比较场景的深度值。逐条处理各条扫描线时，首先判别与其相交的所有表面的可见性，然后计算各重叠表面的深度值以找到离观察平面最近的表面。一旦确定了某像素点所对应的可见面，可以得到该点的强度值，并将其置入帧缓存。 为了加速查找与扫描线相交的表面，可以在处理时建立一张活化边表。该表仅包含与当前扫描线相交的边，并将它们按x升序排列。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,32,给定场景中任一多边形面顶点位置的深度值，可以计算包含该多边形的平面上所有点的深度。,对任一扫描线，线上相邻点间的x水平位移为1，相邻扫描线

15、间的y垂直位移也为1 。若已知像素点（x，y）的对应深度为z，则相邻点（x+1，y)的深度值z可由等式得到：,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,33,扫描线与S1、S2在观察表面上的投影相交 虚线表示隐藏面的边界,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,34,算法描述,for ( v= 0;vvmax;v+) for (u= 0; uumax; u+) /对绘图窗的每一条扫描线初始化 将帧缓冲器的第(u,v)单元置为背景色； 将Z缓冲器的第u单元置为-1（可见的最小深度值 ） ,for (每个多边形) 求出多边形在投影平面上的投影与当前扫描线的相交区间 for (该区间内

16、的每个像素(u,v) ) 计算多边形在该像素处的深度值d； if (d Z缓冲器的第u单元的值) 置帧缓冲器的第(u,v)单元值为当前多边形颜色； 置Z缓冲器的第u单元值为d; ,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,35,扫描线间隔连贯性算法,使每一间隔中最多只有一个多边形是可见的,扫描线,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,36,五、深度排序算法/画家算法 ( depth-sorting method ),关键：如何对场景中的物体按深度（远近）排序， 建立深度优先级表？,排序条件(二面片) 投影的包围盒无重迭 次序任意 包围盒重迭但Z向能分清远近 次序确定 包围盒重迭

17、但投影不重迭 次序任意 将其中之一分割后再比较,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,37,深度排序（depth-sorting）算法同时运用物空间与像空间操作，以实现以下基本功能： （1）将表面按深度递减方向排序； （2）由深度最大的表面开始，逐个对表面进行扫描转换； 排序操作既可在像空间和也可在物空间完成，而多边形面的扫描转换仅在像空间完成。 按深度在帧缓存上绘制多边形面可以分几步进行： 假定沿负Z轴方向观察，表面按它们Z坐标的最低值排序，深度最大的面S需要与其他表面进行比较，以确定是否在深度方向上存在重叠，若没有重叠，则对S进行扫描转换。,图形学与虚拟环境 郑州大学信息工程学院

18、 赵新灿,38,可对与S在深度上有重叠的所有表面进行以下测试，只要其中任意一项成立，则无需重新排序。测试按难度递增顺序排列： （1）两表面在xy平面上投影的包围矩形无重叠； （2）相对于观察位置，面S完全位于重叠表面之后； （3）相对于观察位置，重叠表面完全位于面S之前； （4）两表面在观察平面上的投影无重叠； 如果对于某一重叠表面，所有四项测试均不成立，则需要在有序表中调换S和S的顺序。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,39,一种针对多边形的排序算法 假定在规范化投影坐标系uvn中,投影方向是n轴的负向，因而n坐标大距观察者近。记nmin(P) nmax(P)分别为多边形P的

19、各个顶点n坐标的最小值和最大值，算法步骤如下：,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,40,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), 需进一步判别：,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,41,step 3.2.1 若P,Q投影P,

20、Q的包围盒不相交，则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的深

21、度小，则P,Q关系确， 令L = L P, 返回step 2;否则交换P,Q,返回step 3.,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,42,本算法不能处理的情况： 多边形循环遮挡 多边形相互穿透 解决办法：分割成两个,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,43,六、BSP树算法,BSP树算法是一种判别对象可见性的有效算法。该算法特别适用于场景中对象位置固定不变，仅视点移动的情况。 其主要操作是在每次分割空间时，判别该表面相对于视点与分割平面的位置关系，即位于其前面还是后面。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,44,七、区域细分算法/Warnock 算法are

22、a-subdivision method,由来： Z缓冲器算法与扫描线Z缓冲器算法中都是将像素孤立来考虑，未利用相邻像素之间存在的属性的连贯性，即区域的连贯性，所以算法效率不高。实际上，可见多边形至少覆盖了绘图窗内的一块区域。如果能将这类区域找出来，则避免了在每个像素处计算深度值，消隐问题就解决了。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,45,算法基本思路： 首先将场景中的多边形投影到绘图窗口内（假设它为边长为k的正方形），判断窗口是否足够简单，若是则算法结束；否则将窗口进一步分为四块（左上，右上，左下，右下）。 对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多

23、边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,46,何谓窗口足够简单？ 存在下列情况之一即可称为窗口足够简单： 1）窗口为空，即多边形与窗口的关系是分离的； 2）窗口内仅含一个多边形，即有一个多边形与窗口的关系是包含或相交。此时先对多边形投影进行裁剪，再对裁剪结果进行填充； 3）有一个多边形的投影包围了窗口，并且它是最靠近观察点的，以该多边形颜色填充窗口。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,47,多边形表面与观察平面可能关系,包围表面-完全包含该区域的表面； 重叠表面-部分位于该区域内，部分位于该区域外； 内含表

24、面-完全在该区域内的表面； 分离表面-完全在该区域外的表面；,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,48,如何判别多边形与窗口的分离与包围关系？ 编码方法：1）区域编码 2）多边形顶点编码 3）多边形边的编码 4）多边形的编码,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,49,区域终止分割条件,该区域没有内含、重叠或包围表面（所有表面均为区域的分离表面） 该区域只有一个内含、重叠表面或包围表面； 该区域有一个在其边界内遮挡了其他所有表面的包围表面；,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,50,思考： 区域细分算法中多边形投影与窗口 的关系中包含与相交关系是如何判别的？,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,51,八叉树算法,当按照八叉树表示来描述观察体时，通常按由前往后的顺序将八叉树节点映射到观察体表面，从而消除隐藏面。 空间区域的前部（相对于视点）为体元：0，1，2，3。体元的前表面均可见，这些体元的后面和后部体元（4，5，6，7）都可能被前部的表面所遮挡。 实际上是对八叉树的深度优先遍历。,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,52,图形学与虚拟环境 郑州大学信息工程学院 赵新灿,53,五、光线投射算法 （ray casting）,算法思路：将通过绘图窗口内每一个像素的投影线与场景