第八章面消隐精选文档.ppt

《第八章面消隐精选文档.ppt》由会员分享，可在线阅读，更多相关《第八章面消隐精选文档.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章面消隐本讲稿第一页，共三十一页基本概念产生真实感的方法之一：反映三维场景中的相互遮挡关系面消隐与线消隐 表面模型与线框模型 物体表面：平面与曲面 面消隐对象：由平面多边形构成的多面体本讲稿第二页，共三十一页基本概念消隐算法的分类1）类：以窗口内的每个像素为处理单元；for(窗口内的每一个像素)确定距视点最近的物体，以该物体表面的颜色来显示像素 2）类：以场景中的物体为处理单元；for(场景中的每一个物体)将其与场景中的其它物体比较，确定其表面的可见部分；显示该物体表面的可见部分；本讲稿第三页，共三十一页基本概念算法复杂度 假设场景中有k个物体，平均每个物体表面由h个多边形构成，显示区域中

2、有m x n个像素，则：第一种算法的复杂度为：O(mnkh)第二种算法的复杂度为：O(kh)*(kh)本讲稿第四页，共三十一页提高消隐算法效率的常见方法利用连贯性将透视投影转换成平行投影包围盒技术背面剔除空间分割技术物体分层表示本讲稿第五页，共三十一页提高消隐算法效率的常见方法1利用连贯性 物体连贯性 面的连贯性 区域连贯性 扫描线的连贯性 深度连贯性本讲稿第六页，共三十一页提高消隐算法效率的常见方法2将透视投影转换成平行投影 消隐与透视关系密切,体现有：1）消隐必须在投影之前完成；2）物体之间的遮挡关系与投影中心（视点）的选取有关；3）物体之间的遮挡关系与投影方式有关本讲稿第七页，共三十一页

3、提高消隐算法效率的常见方法4包围盒技术 定义：一个形体的包围盒指的是包围它的简单形体。比如，该技术常用于：避免盲目的求交测试；各种物体间的比较等。一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；对其的测试比较简单。例：使用矩形包围合及长方体包围合来提高算法效率本讲稿第八页，共三十一页它的基本思想是，在复杂形体外包一个容易求交的包围盒，例如它的基本思想是，在复杂形体外包一个容易求交的包围盒，例如长方体或球面等。在光线与该复杂物体求交之前，先判其是否与长方体或球面等。在光线与该复杂物体求交之前，先判其是否与包围盒相交，若与包围盒不相交，说明它与包围盒中的复杂形体包围盒相交，若与包围盒不相交

4、，说明它与包围盒中的复杂形体也不相交，从而节约了时间。只有当光线与包围盒有交时，才有也不相交，从而节约了时间。只有当光线与包围盒有交时，才有必要与复杂形体进行求交运算。若原复杂形体由多个部分组成，必要与复杂形体进行求交运算。若原复杂形体由多个部分组成，还可以为每个部分定义一个包围盒，从而形成一棵包围盒树。线还可以为每个部分定义一个包围盒，从而形成一棵包围盒树。线面求交时先从树根结点开始判断包围盒，若光线与根结点的包围面求交时先从树根结点开始判断包围盒，若光线与根结点的包围盒不相交，则与原物体不相交，否则再判断光线与每棵子树的包盒不相交，则与原物体不相交，否则再判断光线与每棵子树的包围盒是否相交

5、，这样可以按层次访问包围盒，免除了许多不必要围盒是否相交，这样可以按层次访问包围盒，免除了许多不必要的求交计算。只有当访问到树的叶子节点时，才需进行必要的求的求交计算。只有当访问到树的叶子节点时，才需进行必要的求交计算。交计算。本讲稿第九页，共三十一页提高消隐算法效率的常见方法5背面剔除 外法向 外法向与投影方向（观察方向）的夹角 前向面与后向面（背面）剔除依据：物体表面是封闭的，背面总是被前向面所遮挡，从而始终是不可见的。本讲稿第十页，共三十一页提高消隐算法效率的常见方法6空间分割技术依据：场景中的物体，它们的投影在投影平面上是否有重叠部分？（是否存在相互遮挡的可能？）对于根本不存在相互遮挡

6、关系的物体，应避免这种不必要的测试。方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较即可。本讲稿第十一页，共三十一页它的基本原理是，将物体所在的空间剖分为若干个小它的基本原理是，将物体所在的空间剖分为若干个小体素，为每个体素建一张表以保存在该体素中或部分体素，为每个体素建一张表以保存在该体素中或部分在该体素中的物体。若一个物体在几个体素中，则每在该体素中的物体。若一个物体在几个体素中，则每个体素的表中都要记录该物体。光线射出后，先与其个体素的表中都要记录该物体。光线射出

7、后，先与其遇到的第一个体素中的所有物体求交，若有交且交点遇到的第一个体素中的所有物体求交，若有交且交点在该体素中，则此体素中的最近交点就是系统中所有在该体素中，则此体素中的最近交点就是系统中所有物体的最近交点，这样就没有必要与其它体素中的物物体的最近交点，这样就没有必要与其它体素中的物体求交。若在第一个体素中无交，则再判下一个体素，体求交。若在第一个体素中无交，则再判下一个体素，直至找到交点或穿出剖分空间为止。由于只有射线穿直至找到交点或穿出剖分空间为止。由于只有射线穿过的体素中的物体才可能参与求交，从而大大地减少过的体素中的物体才可能参与求交，从而大大地减少了求交次数。空间剖分法特别适合于离

8、散法造型系统了求交次数。空间剖分法特别适合于离散法造型系统中的形体或由多个简单形体构成的复杂形体。这样每中的形体或由多个简单形体构成的复杂形体。这样每个体素中的物体求交速度都很快，而且避免了绝大多个体素中的物体求交速度都很快，而且避免了绝大多数不必要的求交计算。数不必要的求交计算。本讲稿第十二页，共三十一页提高消隐算法效率的常见方法6复杂度比较：不妨假定每个小区域的相关物体表中平均有h个物体，场景中有k个物体，由于物体在场景中的分布是分散的，显然h远小于k。根据第二种消隐方法所述，其算法复杂度为O(h*h),远小于O(k*k)。本讲稿第十三页，共三十一页提高消隐算法效率的常见方法7物体分层表示

9、表示形式：模型变换中的树形表示方式 原理：减少场景中物体的个数，从而降低算法复杂度。方法：将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。本讲稿第十四页，共三十一页光线投射算法算法思路：将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交。如果有交点，用深度值最大的交点（最近的）所属的多边形的颜色显示相应的像素；如果没有交点，说明没有多边形的投影覆盖此像素，用背景色显示即可。本讲稿第十五页，共三十一页光线投射算法算法描述：for(v=0;vvmax;v+)for

10、(u=0;uumax;u+)形成通过像素(u,v)的投影线；for(场景中每一个多边形）将投影线与多边形求交；if (有交点）以最近交点所属多边形的颜色显示像素(u,v)else 以背景色显示像素(u,v)；本讲稿第十六页，共三十一页光线跟踪算法使计算机产生图形的真实感大幅度提高，但卓越的图形绘制效果与昂贵的的计算开销形成了鲜明的对比。为了使这一算法真正实用化，减少运算量势所必行，从此，许多人开始研究光线跟踪的加速方法。光线跟踪中最费时的运算是线面求交，有关资料表明，如果不采取加速措施，线面求交约占整个光线跟踪时间的95以上。因此，减少运算量的关键在于提高线面求交的速度或减少线面求交的次数。本

11、讲稿第十七页，共三十一页画家算法由来：画家的作画顺序暗示出所画物体之间的相互遮挡关系算法基本思路：1）先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的称优先级低，放在表头；距观察点 近的称优先级高，放在表尾。该表称为深度优先级表）2）然后按照从表头到表尾的顺序逐个绘制物体。本讲稿第十八页，共三十一页画家算法关键：如何对场景中的物体按深度（远近）排序，建立深度优先级表？一种针对多边形的排序算法如下：假定在规范化投影坐标系uvn中,投影方向是n轴的负向，因而n坐标大距观察者近。记nmin(P)nmax(P)分别为多边形P的各个顶点n坐标的最小值和最大值，

12、算法步骤如下：本讲稿第十九页，共三十一页画家算法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的包围盒不相交，则P,Q在表中的次序不重要，令L=L P,返回step 2;否则进行下一步。step 3.2.2 若P的所有顶点位于Q所

13、在平面的不可见的一侧，则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 P,返回step 2;否则交换P,Q,返回step 3.本讲稿第二十页，共三十一页画家算法本算法不能处理的情况：多边形循环遮挡多边形相互穿透 解决办法：

14、分割成两个本讲稿第二十一页，共三十一页Z缓冲器算法由来：帧缓冲器 保存各像素颜色值 z缓冲器-保存各像素处物体深度值 z缓冲器中的单元与帧缓冲器中的单元一一对应思路：先将z缓冲器中个单元的初始值置为-1(规范视见体的最小n值）。当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值（保存在该像素所对应的Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改变。本讲稿第二十二页，共三十一页Z缓冲器算法算法描述：for(v=0;vvmax;v+)for

15、(u=0;u Z缓冲器的第(u,v)单元的值）置帧缓冲器的第(u,v)单元值为当前多边形颜色；置Z缓冲器的第(u,v)单元值为d;本讲稿第二十三页，共三十一页Z缓冲器算法优点：简单稳定，利于硬件实现缺点：1）需要一个额外的Z缓冲器 2）在每个多边形占据的每个像素处都要计算深度值，计算量大本讲稿第二十四页，共三十一页扫描线Z缓冲器算法由来：Z缓冲器算法中所需要的Z缓冲器容量较大，为克服这个缺点可以将整个绘图区域分割成若干个小区域，然后一个区域一个区域地显示，这样Z缓冲器的单元数只要等于一个区域内像素的个数就可以了。如果将小区域取成屏幕上的扫描线，就得到扫描线Z缓冲器算法。本讲稿第二十五页，共三十

16、一页扫描线Z缓冲器算法算法描述for(v=0;vvmax;v+)for(u=0;u Z缓冲器的第u单元的值）置帧缓冲器的第(u,v)单元值为当前多边形颜色；置Z缓冲器的第u单元值为d;本讲稿第二十六页，共三十一页区域子分算法由来：Z缓冲器算法与扫描线Z缓冲器算法中都是将像素孤立来考虑，未利用相邻像素之间存在的属性的连贯性，即区域的连贯性，所以算法效率不高。实际上，可见多边形至少覆盖了绘图窗内的一块区域。如果能将这类区域找出来，则避免了在每个像素处计算深度值，消隐问题也就解决了。本讲稿第二十七页，共三十一页区域子分算法算法基本思路：首先将场景中的多边形投影到绘图窗口内（假设它为边长为k的正方形）

17、，判断窗口是否足够简单，若是则算法结束；否则将窗口进一步分为四块（左上，右上，左下，右下）。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。本讲稿第二十八页，共三十一页区域子分算法何谓窗口足够简单？存在下列情况之一即可称为窗口足够简单：1）窗口为空，即多边形与窗口的关系是分离的；2）窗口内仅含一个多边形，即有一个多边形与窗口的关系是包含或相交。此时先对多边形投影进行裁剪，再对裁剪结果进行填充；3）有一个多边形的投影包围了窗口，并且它是最靠近观察点的，以该多边形颜色填充窗口。本讲稿第二十九页，共三十一页区域子分算法如何判别多边形与窗口的分离与包围关系？编码方法：1）区域编码 2）多边形顶点编码 3）多边形边的编码 4）多边形的编码本讲稿第三十页，共三十一页本讲稿第三十一页，共三十一页