第7章 消隐问题

1、1第第7章章 消隐问题消隐问题7.1 基本概念基本概念7.2 消隐基本技术消隐基本技术7.3 消隐算法消隐算法2观察空间的定义及转换观察空间的定义及转换三维裁剪三维裁剪投影投影消隐消隐消隐消隐投影投影光照效果生成光照效果生成投影投影线框图线框图消隐图消隐图真实感图形真实感图形三维形体三维形体3线框图线框图消隐图消隐图真实感图形真实感图形4线框图的二义性线框图的二义性 消隐技术消隐技术就是要解决形体的二义性问题，通过就是要解决形体的二义性问题，通过消隐线或消隐面方法，提高图形的真实感。消隐线或消隐面方法，提高图形的真实感。 消隐是消隐是产生真实感的方法之一。产生真实感的方法之一。5 按消隐对象分

2、类按消隐对象分类消隐线算法和消隐面算法。消隐线算法和消隐面算法。 早期图形显示器是用线条表示图形，消隐主要早期图形显示器是用线条表示图形，消隐主要是消隐线问题。使用光栅显示器后，物体可用连续是消隐线问题。使用光栅显示器后，物体可用连续变化的色调来描述，消隐算法的研究渐渐转向消隐变化的色调来描述，消隐算法的研究渐渐转向消隐面的问题。面的问题。 7.1 基本概念基本概念一、消隐算法分类一、消隐算法分类6 按消隐空间分类按消隐空间分类物空间算法和像空间算法。物空间算法和像空间算法。 物空间算法物空间算法是在描述物体的物理坐标系中实现的，是在描述物体的物理坐标系中实现的，以场景中的物体为处理单元，以场

3、景中的物体为处理单元，通过一个面与其余面通过一个面与其余面的可见性比较进行。特点是算法可以达到相当高的的可见性比较进行。特点是算法可以达到相当高的精度。精度。 for (场景中的每一个物体场景中的每一个物体) 将其与场景中的其它物体比较，确定其表将其与场景中的其它物体比较，确定其表面的可见部分；显示该物体表面的可见部分；面的可见部分；显示该物体表面的可见部分； 7 像空间算法像空间算法是在观察物体的屏幕坐标系中实是在观察物体的屏幕坐标系中实现的，现的，以窗口内的每个像素为处理单元以窗口内的每个像素为处理单元 。特点是。特点是算法精度低，只能达到屏幕精度为止，但速度往算法精度低，只能达到屏幕精度

4、为止，但速度往往更高。往更高。 for (窗口内的每一个像素窗口内的每一个像素) 确定距视点最近的物体，以该物体表确定距视点最近的物体，以该物体表 面的颜色来显示像素面的颜色来显示像素8二、算法复杂度二、算法复杂度 假设场景中有假设场景中有k个物体个物体，平均每个物体表面，平均每个物体表面由由h个多边形个多边形构成，显示区域中有构成，显示区域中有m * n个像素个像素，则：则： 第一种算法的复杂度为：第一种算法的复杂度为： O(kh)(kh) 第二种算法的复杂度为：第二种算法的复杂度为：O(mnkh)9物空间消隐算法物空间消隐算法: 是就一个物体表面的是就一个物体表面的h个多边形个多边形中的每

5、个面中的每个面与其余与其余h-1个面进行比较，精确地求出物体上每个面进行比较，精确地求出物体上每个棱边或每个面的遮挡关系。算法的计算量正比个棱边或每个面的遮挡关系。算法的计算量正比于于h2，即算法复杂度为：即算法复杂度为：O(h)2) 。 则，则，k个物体个物体的算法复杂度为：的算法复杂度为：O(kh)2) 。10象空间消隐算法象空间消隐算法： 这类算法对屏幕上的每个象素进行判断，以这类算法对屏幕上的每个象素进行判断，以决定物体上哪个多边形在该象素决定物体上哪个多边形在该象素 点上是可见的。点上是可见的。若屏幕上有若屏幕上有mn个象素个象素点，每个物体表面上有点，每个物体表面上有h个多边形，则

6、该类消隐算法计算量正比于个多边形，则该类消隐算法计算量正比于mnh。 k个物体个物体的算法复杂度为：的算法复杂度为： O(mnkh) 。11 各种消隐算法均采用一定形式的几何排序。各种消隐算法均采用一定形式的几何排序。通过排序，可搜查出位置上靠近观察者的几何通过排序，可搜查出位置上靠近观察者的几何元素，确定几何元素之间在位置上的遮挡关系，元素，确定几何元素之间在位置上的遮挡关系，解决消隐计算的主要问题。各种算法都有各自解决消隐计算的主要问题。各种算法都有各自的排序方法和排序次序。排序次序影响算法的的排序方法和排序次序。排序次序影响算法的效率。效率。 三、算法排序三、算法排序127.2 消隐基本

7、技术消隐基本技术 为了提高消隐算法的效率，为了提高消隐算法的效率，各种消隐算法各种消隐算法常常采用一些有效的采用一些有效的消隐消隐基本基本算法。算法。利用连贯性利用连贯性将透视投影转换成平行投影将透视投影转换成平行投影包围盒技术包围盒技术背面剔除背面剔除空间分割技术空间分割技术物体分层表示物体分层表示13 物体连贯性物体连贯性面的连贯性面的连贯性 区域连贯性区域连贯性 扫描线的连贯性扫描线的连贯性 深度连贯性深度连贯性一、利用连贯性一、利用连贯性14二、包围盒技术二、包围盒技术 一个形体的包围盒指的是包围它的简单形体。一个形体的包围盒指的是包围它的简单形体。比如，比如，2D的矩形，的矩形，3D

8、的的立方块、长方体、球等。立方块、长方体、球等。目的：目的： 避免盲目的求交测试；避免盲目的求交测试； 各物体间的比较等。各物体间的比较等。一个好的包围盒要具有两个条件：一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；包围和充分紧密包围着形体；对其的测试比较简单。对其的测试比较简单。例：例：矩形包围盒及长方体包围盒提高算法效矩形包围盒及长方体包围盒提高算法效率率15三、背面剔除三、背面剔除 外法向外法向 外法向与投影方向（观察方向）的夹角外法向与投影方向（观察方向）的夹角 前向面与后向面（背面）前向面与后向面（背面）剔除依据：剔除依据： 物体表面是封闭的，背面总是物体表面是封闭的，背面

9、总是 被前向面所遮挡，从而始终是被前向面所遮挡，从而始终是 不可见的。不可见的。16 视线视线- -法线夹角法法线夹角法N N 面的法向量面的法向量K K 面上一点指向观察点的向量面上一点指向观察点的向量 = = coscos-1-1( )( )0= 0= 时时 可见可见 = = = 0N . K 0 2视点17四、空间分割技术四、空间分割技术依据：依据：场景中的物体，它们的投影在投影平面上场景中的物体，它们的投影在投影平面上 是否有相互遮挡的重叠部分？是否有相互遮挡的重叠部分？ 对于根本不存在相互遮挡关系的物体，应对于根本不存在相互遮挡关系的物体，应 避免这种不必要的测试。避免这种不必要的测

10、试。方法：方法：将投影平面上的窗口分成若干小区域；为将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断哪个物体该区域有相交部分；则在小区域中判断哪个物体可见时，可见时，只要对本区域的相关物体表中的物体进只要对本区域的相关物体表中的物体进行比较即可行比较即可。18复杂度比较：复杂度比较： 假定每个小区域的相关物体表中平均假定每个小区域的相关物体表中平均有有h个个物体，场景中有物体，场景中有k个物体，由于物体在场景中的分个物体，由于物体在场景中的分布是分散的，显然布是分散的，显然h远小于远小于k

11、。 根据物空间消隐方法所述，其算法复杂度为根据物空间消隐方法所述，其算法复杂度为O(h2),远小于远小于O(k2)。19五、物体分层表示五、物体分层表示表示形式表示形式：模型变换中的树形表示方式：模型变换中的树形表示方式原理：原理：减少场景中物体的个数，降低算法复杂度。减少场景中物体的个数，降低算法复杂度。方法方法： 将父节点所代表的物体看成子节点物体的将父节点所代表的物体看成子节点物体的包围盒，当两个父节点之间不存在遮挡关系时，包围盒，当两个父节点之间不存在遮挡关系时，就勿对两者的子节点做进一步测试。就勿对两者的子节点做进一步测试。 父节点之间的遮挡关系可以用它们之间的包父节点之间的遮挡关系

12、可以用它们之间的包围盒进行预测试。围盒进行预测试。20六、将透视投影转换成平行投影六、将透视投影转换成平行投影 消隐与透视关系较密切，体现在消隐与透视关系较密切，体现在： 1）消隐必须在投影之前完成；）消隐必须在投影之前完成；2）物体之间的遮挡关系与投影中心（视点）物体之间的遮挡关系与投影中心（视点） 的选取有关；的选取有关； 3）物体之间的遮挡关系与投影方式有关。）物体之间的遮挡关系与投影方式有关。21 7.3 消隐算法消隐算法一、一、Z（深度）缓冲器算法深度）缓冲器算法(depth-buffer method)由来：由来： 帧缓冲器帧缓冲器保存各像素颜色值保存各像素颜色值 z 缓冲器缓冲器

13、保存各像素处物体深度值保存各像素处物体深度值 z缓冲器中的缓冲器中的像素像素单元与帧缓冲器中的单元与帧缓冲器中的像素像素 单元一一对应单元一一对应 一种典型的、也是最简单的图象空间消隐算法。一种典型的、也是最简单的图象空间消隐算法。22思路：思路： 先将先将z 缓冲器中各单元的初始值置为缓冲器中各单元的初始值置为-1(规范规范观察体的最小观察体的最小n值）值）。 当要改变某个像素的颜色值时，首先检查当当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来保存的前多边形的深度值是否大于该像素原来保存的Z缓冲器中的深度值，缓冲器中的深度值，如果大于如果大于，说明当前多边形，说明当

14、前多边形更靠近观察点，用它的颜色替换像素原来的颜色；更靠近观察点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前多边形被前面所绘否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值制的多边形遮挡了，是不可见的，像素的颜色值不改变。不改变。23YXOZjip1p2屏幕屏幕物物体体R24算法描述：算法描述：for ( v= 0;vvmax;v+) for (u= 0; u Z缓冲器的第缓冲器的第(u,v)单元的值单元的值) 置帧缓冲器的第置帧缓冲器的第(u,v)单元值为当前多边形颜色；单元值为当前多边形颜色； 置置Z缓冲器的第缓冲器的第(u,v)单元值为单

15、元值为d; 25优点优点： 简单稳定，利于硬件实现简单稳定，利于硬件实现缺点缺点：1）需要一个额外的需要一个额外的Z 缓冲器缓冲器 2）在每个多边形占据的每个像素处都要在每个多边形占据的每个像素处都要 计算深度值，计算量大计算深度值，计算量大26二、扫描线二、扫描线Z缓冲器算法缓冲器算法 (scan-line method)由来：由来： Z缓冲器算法中所需要的缓冲器算法中所需要的Z缓冲器容量较缓冲器容量较大，为克服这个缺点可以大，为克服这个缺点可以将整个绘图区域分割将整个绘图区域分割成若干个小区域成若干个小区域，然后一个区域一个区域地显，然后一个区域一个区域地显示，这样示，这样Z缓冲器的单元数

16、只要等于一个区域内缓冲器的单元数只要等于一个区域内像素的个数就可以了。如果像素的个数就可以了。如果将小区域取成屏幕将小区域取成屏幕上的扫描线，上的扫描线，就得到就得到扫描线扫描线Z缓冲器算法缓冲器算法。27算法描述算法描述for ( v= 0;vvmax;v+) for (u= 0; u Z缓冲器的第缓冲器的第u单元的值单元的值) 置帧缓冲器的第置帧缓冲器的第(u,v)单元值为当前多边形颜色；单元值为当前多边形颜色； 置置Z缓冲器的第缓冲器的第u单元值为单元值为d; 28扫描线间隔扫描线间隔连贯性算法连贯性算法使每一使每一间隔间隔中最多只有一个多边形是可见的中最多只有一个多边形是可见的XZ12

17、3OXZ1 2 3 4OXYO扫描线扫描线29三、深度排序算法三、深度排序算法/画家算法画家算法 ( depth-sorting method )关键：关键：如何对场景中的物体按深度（远近）排序，如何对场景中的物体按深度（远近）排序， 建立深度优先级表？建立深度优先级表？排序条件排序条件( (二面片二面片) ) 投影的包围盒无重迭投影的包围盒无重迭 次序任意次序任意包围盒重迭但包围盒重迭但Z Z向能分清远近向能分清远近 次序确定次序确定包围盒重迭但投影不重迭包围盒重迭但投影不重迭 次序任意次序任意将其中之一分割后再比较将其中之一分割后再比较30 一种针对多边形的排序算法一种针对多边形的排序算法

18、 假定在规范化投影坐标系假定在规范化投影坐标系uvn中中,投影投影方向是方向是n轴的负向，轴的负向，因而因而n坐标大距观察坐标大距观察者近。记者近。记nmin(P) nmax(P)分别为多边形分别为多边形P的各个顶点的各个顶点n坐标的最小值和最大值，坐标的最小值和最大值，算法步骤如下：算法步骤如下：31Step 1:将场景中所有多边形存入一个线性表将场景中所有多边形存入一个线性表(链表或数链表或数 组组)，记为，记为L;Step 2: 如果如果L中仅有一个多边形，算法结束；否则根据每中仅有一个多边形，算法结束；否则根据每 个多边形的个多边形的nmin对它们预排序。不妨假定多边形对它们预排序。不

19、妨假定多边形P 落在表首，即落在表首，即nmin(P)为最小。再记为最小。再记Q为为L P(表表 中其余多边形）中任意一个；中其余多边形）中任意一个；Step 3: 判别判别P, Q之间的关系，有如下二种：之间的关系，有如下二种：step 3.1: 对有的对有的Q，有有nmax(P) nmin (Q), 需进一步判别：需进一步判别：32step 3.2.1 若若P,Q投影投影P,Q的包围盒不相交，则的包围盒不相交，则P,Q在表中在表中 的次序不重要，令的次序不重要，令L = L P, 返回返回step 2;否则否则 进行下一步。进行下一步。step 3.2.2 若若P的所有顶点位于的所有顶点位

20、于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;否否 则在它们所相交的区域中任取一点，计算则

21、在它们所相交的区域中任取一点，计算P,Q在在 该点的深度值，如果该点的深度值，如果P的深度小，则的深度小，则P,Q关系正确，关系正确， 令令L = L P, 返回返回step 2;否则交换否则交换P,Q,返回返回step 3.nQPnPQnPQ33本算法不能处理的情况：本算法不能处理的情况：多边形循环遮挡多边形循环遮挡多边形相互穿透多边形相互穿透 解决办法解决办法：分割成两个：分割成两个34四、区域子分算法四、区域子分算法/Warnock 算法算法area-subdivision method由来：由来： Z缓冲器算法与扫描线缓冲器算法与扫描线Z缓冲器缓冲器算法中算法中都是将像素孤立来考虑，未

22、利用相邻像素之都是将像素孤立来考虑，未利用相邻像素之间存在的属性的连贯性，即区域的连贯性，间存在的属性的连贯性，即区域的连贯性，所以算法效率不高。实际上，可见多边形至所以算法效率不高。实际上，可见多边形至少覆盖了绘图窗内的一块区域。如果能将这少覆盖了绘图窗内的一块区域。如果能将这类区域找出来，则避免了在每个像素处计算类区域找出来，则避免了在每个像素处计算深度值，消隐问题就解决了。深度值，消隐问题就解决了。35算法基本思路算法基本思路： 首先将场景中的多边形投影到绘图窗口内首先将场景中的多边形投影到绘图窗口内（假设它为边长为（假设它为边长为k的正方形），判断窗口是否的正方形），判断窗口是否足够简

23、单足够简单，若是则算法结束；否则将窗口进一步，若是则算法结束；否则将窗口进一步分为四块（左上，右上，左下，右下）。分为四块（左上，右上，左下，右下）。 对此四个小窗口重复上述过程，直到窗口仅对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素，计算它们的深度值，以最近的颜色显示该像素即可。该像素即可。36何谓窗口足够简单？何谓窗口足够简单？ 存在下列情况之一即可称为窗口足够简单：存在下列情况之一即可称为窗口足够简单：1）窗口为空，即多边形与窗口的关系是）窗口为空，即多边形与窗口的关系是分分离离的；的；2）窗口内仅含一个多边形，即有一个多边）窗口内仅含一个多边形，即有一个多边形与窗口的关系是形与窗口的关系是包含或相交包含或相交。此时先对多边形投。此时先对多边形投影进行裁剪，再对裁剪结果进行填充；影进行裁剪，再对裁剪结果进行填充；3）有一个多边形的投影）有一个多边形