（计算机科学与技术专业论文）大规模交叠网格模型优化算法.pdf

一 一 嬲期必 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：耸翌日期：竺! ! ：篷：2 2 一 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 研究生( 签名) ： 摘要 由大量网格模型所构建的三维世界在人们的现代生活中已经扮演着重要的 角色，随着人们对三维世界越来越多需求，出现了大量的网格数据需要处理， 对计算机的存储、计算、显示、传输都带来了很多问题，同时这些网格模型很 大部分是相互交叠的，因此对大量网格模型数据进行优化处理已经刻不容缓。 经过多年的研究，很多学者提出了很多类型的网格简化算法。如区域合并算 法，顶点聚类算法，小波分解，顶点删除算法和渐进网格算法等。这些算法虽 然都有一定的网格模型简化功能，但是只适用于一定的范围，而且计算复杂、 时间消耗大、模型逼近程度差。在三维场景中并不是每个网格都需要绘制，往 往有大量的网格模型内部和模型之间因为重叠，相互遮挡，或者靠的很近，并 不需要存在，故采用网格合并算法优化网格模型。 鉴于对研究中存在的现有问题，本文提出一种针对大规模交叠网格模型的 简单高效的网格优化方法，综合了网格合并和网格简化两种主要的网格优化算 法，大大提高了优化的效率和适用范围。将众多交叠模型中不需要的网格去掉， 可以重复利用网格资源，分享材质和纹理，会为网格优化带来很大的益处，故 而基于网格合并的思想提出一种简单而有效的合并方法。在合并完成后的网格 模型还可以进一步的简化网格，所以在顶点删除简化算法的基础上，提出一种 改进的简化算法。经过改进后的算法不但降低了网格处理时的复杂度，而且尽 可能的保证场景中模型的原有特征。本文的创新之处表现在以下几个方面： 1 ) 本文仔细分析和研究了网格合并算法。经典的网格合并算法包含网格交 叠区域的检测、交叠网格边界的腐蚀、网格拉链的产生、网格缝合、合并后的 光顺平滑处理等多个步骤。复杂的网格合并算法让大规模交叠网格的计算复杂 而效率很低。改进的合并算法提出了一种用包围盒分割网格检测待交叠区域， 用顶点到网格三角形质心判断网格交叠最小距离，采用网格三角形对过渡合并， 在合并后采用拉普拉斯光顺算法对合并区域进行平滑处理，并用一系列参数根 据需要控制网格合并情况的方法。它简化了步骤，提高了合并的效率； 2 ) 本文比较了各种网格简化算法的优劣。相对而言，顶点删除简化算法实 现简单原理清晰易懂，在此基础上提出一种改进的网格顶点删除简化算法，采 用了计算顶点的权值的方法来判定选择进行顶点删除，删除后使用基于最短边 优先三角化的原理对多边形重新拓扑化，完成对网格的优化。 大规模交叠网格模型优化算法结合了网格合并和网格简化的优点，通过简化 两者的计算过程，大大提高优化效率，经过实验证实表明，对于大规模网格模 型具有很好的优化效果。 关键字：交叠网格网格简化网格优化网格合并 a b s t r a c t t h e3 dw o r l dm a d eo f l o t so f m e s hm o d e l sp l a y sa ni m p o r t a n tp a r ti np e o p l e sl i f e b e c a u s eo fm o r ea n dm o r er e q u i r e m e n tf o r3 dw o r l d ，l o t so fm e s hd a t an e e d s p r o c e s s i n g , s t o r i n g , c o m p u t i n g , d i s p l a y i n ga n dt r a n s m i t t i n g , w h i c hb r i n g sm a n y p r o b l e m s a t t h es a m et i m e ，t h e r ea r em a n yo v e r l a p sb e t w e e nt h em e s hm o d e l s s oi ti s n e c e s s a r yt oo p t i m i z et h e s eo v e r l a p p i n gm e s hm o d e l s a f t e rm a n yy e a r so fr e s e a r c h , m a n ys c h o l a r sh a v ec o m eu pw i mk i n d so f o p t i m i z a t i o na l g o r i t h m s ，s u c ha sa r c am e r g ea l g o r i t h m ，v e r t e xc l u s t e r i n ga l g o r i t h m ， w a v e l e td d r , o m p o s i t i o na l g o r i t h n v e r t e xc u l l i n ga l g o r i t h m ，p r o g r e s s i v em e s h e s a l g o r i t h m a l t h o u g ht h e s ea l g o r i t h m sw o r kw e l l ，n l e yc 觚o n l y b eu s e di ns o m ef i e l d s ， a n dt h e ya r ec o m p l i c a t e ，t i m e - c o n s u m i n g ri sn o tn e c e s s a r yt od i s p l a ya l lm e s h e si n 3 ds o l y l e , a n dt h e r ea r em a n yo v e r l a p p i n gm e s h e s , s oc o m b i n i n gm e s h e si sag o o d w a y t os i m p l i f ym o d e l s g i v e nt h e s ep r o b l e r n s ，as i m p l ea n de f f i c i e n tm e s ho p t i m i z a t i o na l g o r i t h mf o r l a r g e - s c a l eo v e r l a p p i n gm e s hm o d e l si sp r o p o s e di nt h et h e s i s t l l i sm e t h o di n t e g r a t e s m e s hm e r g i n ga n dm e s hs i m p l i f i c a t i o nt h et w ok i n d so f m e s ho p t i m i z a t i o na l g o r i t h m s , w h i c hi sm o r ee f f i c i e n ta n da p p l i c a b l e t og e t t i n gr i do f t h eo v e r l a p sb e t w e e nt h em e s h m o d e l si sag o o dw a yt or e u s et h em e s h s oa ne a s ya n dw o r k a b l em e t h o db a s e d0 1 1t h e m e s hm e r g i n gi sp r o p o s e d t h em e s hm o d e l sa f t e rm e r g i n gc a nb es i m p l i f i e df u r t h e r , s oa ni m p r o v e ds i m p l i f i c a t i o na l g o r i t h mb a s e do nt h ev e r t e xc 雹d l i n ga l g o r i t h mi s p r o p o s e d t h ei m p r o v e da l g o r i t h mr e d u c e st h ec o m p l e x i t y , a tt h es a m et i m e i tc a r tk e 印 t h eo r i g i i l a lc h a r a c t e rm o d e l s 蠲s o o na sp o s s i b l e f o l l o w i n g sa r em a i n l yt h ep o i n t so f i n n o v a t i o n ： f i r s to fa l l ，t h em e s hm e r g i n ga l g o r i t h mi sp r o p o s e di nt h et h e s i so nt h eb a s i so f a n a l y s i s 田1 ec l a s s i cm e r g i n ga l g o r i t h mi sc o m p o s e do fm a n yc x n n p l i c a t e ds t e p s ，t h e d e t e c t i o no f o v e r l a p p i n ga r e a ，t h ec o r r o s i o no f m e s hb o u n d a r y , t h ep r o d u c t i o no f s e a m l i n e , m e r g i n gm e s h e sa n ds m o o t h i n gm e s h 砀ec o m p l i c a t em e s hm e r g i n ga l g o r i t h m m a k e st h em a s s i v em e s hm o d e l si n e f f i c i e n c y r n l ei m p r o v e dm e r g i n gm e t h o di n c l u d e s d e t e c t i n gt h eo v e r l a p p e da r c au s i n gi n t e r s e c t e db o u n d i n gb o x ，a n dd e t e r m i n i n gt h e l e a s td i s t a n c eb e t w e e nt h ev e r t e xa n dc e n t e ro fm a s s , m e r g i n gt h em e s ht h r o u g ht h e n l t r i a n g l ep a i r , s m o o t h i n go u tt h em e r g i n gp a r tb ym e q 8o fl a p l a c i a ns m o o t h i n g a l g o r i t h m ，a n dc o n t r o l l i n gt h ep r o c e s so fm e r g i n gb y r i s eo fas e r i e so fp a r a m e t e r s t h i sm e t h o dm a k e st h ep r o c e s ss i m p l e ra n dm o r ee f f i c i e n t s e c o n d l y , ac o m p a r i s o nb e t w e e nt h ek i n d so f m e s hs i m p l i f i c a t i o na l g o r i t h m si s m a d ei nt h et h e s i s c o m p a r a t i v e l ys p e a k i n g , t h ev e r t e xc u l l i n ga l g o r i t h mi ss i m p l ea n d e a s yt oa c h i e v e o nt l l eb a s i so f t i l i sm e t h o dai m p r o v e dv e r t e xc u l l i n ga l g o r i t h mi s c o m eu p t h ep r o c e s sc o n s i s t so f t h ev e r t e xd e l e t i o nb a s e do nt h ew e i g h to f v e r t e x ，a n d d i v i d i n g t h eh o l e sp r o d u c e da f t e rv e r t e xd e l e t i o nb a s e do nt h ep r i n c i p l et h a tt h es h o r t e s t i sc h o s ef i r s t l y , f i n a l l yf i n i s h i n gt h em e s ho p t i m i z a t i o n t h em a s s i v eo v e r l a p p e dm e s hm o d e l so p t i m i z a t i o na l g o r i t h mh a st h ea d v a n t a g e s o f m e s hm e r g i n ga n dt h ea d v a n t a g e so f m e s hs i m p l i f i c a t i o n i ti m p r o v e st h ee f f i c i e n c y t h r o u g hs i m p l i f y i n gp r o c e s s a n d t h ee x p e r i m e n ts h o w st h a tt h ei m p a c to f o p t i m i z a t i o n i sv e r yg o o d k e yw o r d s ：o v e r l a p p i n gm e s h e s ，m e s hs i m p l i f i c a t i o n , m e s ho p t i m i z a t i o n , m e s h m e r g i n g i v 一 一_ 一一 _ _一 目录 摘! 要i a b s t r a c t i i i 第l 章绪论l 1 1 研究背景及意义1 1 1 1 网格模型的应用l 1 1 2 网格模型优化的意义2 1 2 相关研究技术介绍3 1 2 1 三维数学概念3 1 2 2 三维网格基础知识。4 1 2 3 网格模型优化技术5 1 3 研究目的与主要成果7 1 4 本文的研究章节安排8 第2 章常用网格模型简化算法9 2 1 弓i 言9 2 2 网格简化的原则和误差度量9 2 3 常用的经典网格模型简化算法1 0 2 3 1 顶点聚类法1 0 2 3 2 几何元素删除法l l 2 3 3 网格模型细分法厶1 5 2 3 4 小波分解法。l5 2 3 5 重新布点法1 6 2 3 6 层次表示法1 6 2 3 7 渐进网格法1 7 2 4 总结1 8 第3 章改进的网格合并算法2 0 3 1 经典的网格合并算法2 0 3 1 1 网格合并区域腐蚀算法。2 0 3 1 2 网格边界缝合算法2 2 3 2 待合并区域的提取。2 5 3 2 。1 包围球2 5 3 2 2 离散凹凸包围盒2 5 3 2 3 轴对齐包围盒2 6 3 2 4 方向包围盒2 7 3 3 改进的网格合并算法2 7 3 3 1 交叠网格的待合并区域检测2 7 3 3 2 基于三角面的网格合并31 3 4 本章总结3 8 第4 章大规模交叠网格模型优化算法4 0 4 1 网格模型光顺算法。4 0 4 1 1l a p l a c e 光顺算法4 0 4 1 2 t a u b i n 光顺算法4 1 4 1 3 d e s b r u n 光顺算法。4 2 4 1 4 双边滤波光顺算法4 2 4 2 大规模网格模型优化算法思路4 3 4 3 大规模交叠网格的合并j 4 4 4 3 1 大规模交叠网格合并原理“ 4 3 2 网格合并的控制4 5 4 4 交叠模型合并区域的拉普拉斯光顺平滑优化4 6 4 5 改进的基于顶点删除网格模型简化算法4 7 4 5 1 顶点的权值计算4 8 4 5 2 基于最短边原理的三角剖分4 9 4 5 3 顶点删除简化网格5 1 4 6 大规模网格优化算法分析与实验例图5 2 4 7 本章小结5 4 第5 章总结与展望5 5 5 1 课题总结5 5 5 2 展望5 5 j c 谢5 7 参考文献5 8 附录：攻读硕士学位期间参加的项目及发表的论文6 2 武汉理工大学硕士学位论文 10 i 研究背景及意义 1 i i 网格模型的应用 第1 章绪论 用带有一定属性的三维网格数据来表示的事物模型逐渐代替这人们原来所 用的二维的图像，人们也不能再满足于简单的二维图像，大量的用网格所表示 的模型被运用到了虚拟现实、工程建设、游戏、医疗成像等人们生活服务的范 围。它随着现代技术的越来越成熟，已经从原来的只是应用于工程建设而逐渐 走进了与人们的息息相关的生活中。 网格模型可以为人们模拟出较为真实的虚拟世界，虚拟现实技术已经步入了 非常成熟的阶段，通过虚拟世界的传感器为用户和观察者的视觉、听觉、触觉 等各种感官提供交流渠道。虚拟三维显示是虚拟系统中非常重要的一步，三维 场景的真实感受让虚拟现实变得更加精彩。虚拟现实让虚拟制造、虚拟生物医 学工程、军事演习、教学等等变得更加有意义。 游戏产业也在日益磅礴发展中，通过各种网格技术所处理的网格模型可以呈 现各种效果，将许多不可能的特效得以应用到游戏中，比如生成层次网格模型、 增强网格模型、渐变网格模型，可以将庞大的地图应用到游戏中去，而且运行 也很流畅，可以将简单的网格模型增强细化为复杂细致的网格模型，渐变网格 模型将生成在不同时间点的网格模型成为了现实。网格技术的发展让绚丽多彩 的魔法、万人战国的特效成为了可能，大量的网格模型会在同一屏幕中出现在原 有的技术中是不可能的，因为超过几万人网格模型的网格数量是相当大的，每个 模型以最小的网格数量计算，一个在游戏场景中的玩家a v a t a r 的网格数量为一百 个网格节点，那么计算机在每一帧的显示中都会处理成千万的复杂网格数据， 就算是一台多核的计算机也会处理很困难的。革新后的网格技术让这些都变成 了可能，而且让游戏在流畅运行的同时也让很多特效变得简单易行，这些技术 大量运用到了游戏引擎中，不少著名的游戏公司开发出了杰出的游戏产品，如 暴雪公司所开发的u n r e a l 是现代最具代表性的游戏引擎，由它开发的几部作品 如 0 ，那么肯定该点p 是在平面的前方而且在平面的正半空间里。 如果栉p + d 0 ，那么说明该点p 是在平面的后方而且在平面的负半空间里。 创建一个平面有两种方法，一种是直接用已知的法线和点创建平面。如假设 法线n 和在平面上的已知点，。，就能求出d 由刀p + d = 0 ，则刀p = 刁， 嘲p = d 。通过上述确定面的方式便可以绘出一个平面。另一种方法是通过三 个点创立一个平面。假设有点p 。、p 。和p ：，那么可以通过该三个点计算得到平 面上的两个向量： “2 p t p o ，= p 2 一p o 那么就可以通过平面上的两个向量u 、v 进行叉乘，得到平面的法线向量n ， i l l - - 一u x v 。由此可得- ( n p o ) = d 1 2 2 三维网格基础知识 ( 1 ) 三维坐标系与点 绘制三维图形往往离不开三维坐标系，在空间几何中，经常采用笛卡尔坐标 系作为参照系来表示图形，表示二维图形则用二维笛卡尔坐标系，三维图形则 用三维笛卡尔坐标系。根据z 坐标轴相对x ，y 坐标轴方向的不同，可将坐标系分 为左手坐标系和右手坐标系。他们的区别之处是将右手四指顺着x 轴的正向到y 轴的正向进行旋转然后握紧，如果大拇指所指的方向和z 轴的正方向相同，则成 为右手坐标系，如果方向相反则成为左手坐标系。在三维绘制中人们常采用左 手坐标系，而在工程中常使用右手坐标系。 在选取好坐标系后，空间中的任何一点都可以用坐标值似弘= ) 来表示同时 4 一一一一一 武汉理工大学硕士学位论文 从坐标原点到空间中的任何点有一条有向线段，用它来表示空间方向，它的表 示方法与点坐标类似。 ( 2 ) 三角形 在很多三维场景中，三角形是构成实体的基本单元，因为一个三角形也正 是一个平面，而且以三角形面为单位所进行的渲染效率是最高的。同时大量的 三角形组合在一起，就构成了复杂的多边形或者曲面等网格模型。 ( 3 ) 法线 一个三角形是由三个点构成的，这些点一般被称作顶点( v e r t e x ) 。三角形 平面往往有正反两面，他们是由顶点的排列顺序所决定：顶点按照顺时针方向排 列时的表面叫正面，其中与三角形平面垂直而且指向该正面的矢量称为平面的 法线。通过三角形的三个顶点可以求出三角形的法线舻( p 2 一p o ) x ( p 广p 。) 如图 l _ 4 所示 n p 0 p l 图1 - 4 三角形顶点及法线 1 2 3 网格模型优化技术 大规模网格模型的处理包含了很多部分，包括网格模型数据采集及去除噪 声、格模型的分割、网格模型的合并、网格模型数据的简化、网格简化完成后 的误差测量、网格重建、分析使用等等步骤。在本文所主要研究在大规模网格 模型处理中由于很多的网格模型是有很多小的网格所构成的，而且相互接触很 紧，出现很多冗余的网格，完全可以采用一点的手段将这多余的网格删除，通 过网格合并的方法合并可以合并的网格。 在计算机图形领域中，三维模型数据通常都是多边形网格组成的，这是由于 多边形网格相对其他的数据结构要简单很多，但又可以表达出模型的灵活性。 网格模型是用网格顶点进行连线而完成，这些顶点和所连接的边线共同构成了 多边形，三角形是最简单的多边形，而且任何多边形都可以分解为多个三角形 来表示这种特点使得三角网格为多边形网格中使用最为广泛的一种，它以物 5 武汉理工大学硕士学位论文 体空间的几何信息为基础，可以选取观察角度和方位，对模型进行任意观察、 编辑、裁剪等多种操作，具有很好的交互性，而且在几何数学的辅助下可以很 方便的进行几何的变形、旋转、透视等变换操作。简单的三角形网格便于利用 图形硬件的加速。 用三角面与点之间距离判断目前大多采用的是射线方法，在图形处理中， 如何判断两个物体相互挨着有多近，是否相撞，是否有相交之处，是否有重叠 部分? 就是通过判断两个模型网格这些都需要一定的判断方法，目前常使用的 方法有射线法，包围盒法，基于多叉树的点面的距离计算法等。本文就采用了 射线法计算出两个模型相交部分顶点与面相互之间的距离，决定哪些点是需要 合并的，哪些面是可以共用的。 网格融合技术的目的是基于多边形网格的几何模型，用现有的模型通过融 合构造出兼有他们特点的新的模型。网格合并就是网格融合技术的核心内容， 如何判断是需要合并的部分，如何合并就是本文所主要研究的主要内容。目前 主流的网格合并算法有m e s hz i p p e r 算法，网格缝合算法，它主要用于有扫描仪 所产生的模型与另一模型的合并产生成另一个连续的多面体模型。它们主要包 括了移除两个网格的重叠多余部分，对两个网格相互裁剪，去除裁剪过程中多 余的三角面，网格模型边界处理，网格合并后的网格平滑处理。网格光顺算法 将合并后的网格顶点进行重新调整，常用的经典光顺算法有拉普拉斯光顺算法、 t a u b i n 光顺算法和双边滤波光顺算法等f 5 9 j 。 网格简化是网格处理用又一重要的课题，也是网格优化处理中很常用的一 种方法。用相对简单的模型来代替原始模型，如何用更少的网格节点代替表示 原有的模型，却又不影响原有模型的形态信息，这是网格模型简化的处理原则。 网格模型简化算法有很多，他们都是针对一定的情况采用了不同的处理方法， 有一定的使用范围，有针对单独静态简化处理网格的，有针对处理产生动态多 分辨率网格模型的，有专门处理地形网格的，有处理场景网格的。不论哪种方 法都是在设法减少该模型的面片数、边数以及顶点数如图1 5 ，化简对网格模型 的处理有很深远的影响。 6 武汉理工大学硕士学位论文 图1 5 网格顶点和面片的减少 1 3 研究目的与主要成果 在网格模型的使用过程中，一个网格模型其实是由很多的细小网格构成的， 网格模型的错杂摆放和编排成为了一个具有很大网格顶点数量的网格模型，这 样的模型在网格渲染时，是通过内存读取网格顶点数据传入到显卡缓存中，通 过渲染管线渲染显示在屏幕上，这是很复杂的处理过程，尽管现在的显卡有很 强的处理能力，但是面对大量的网格需要渲染是件很困难的事情。网格模型的 优化在三维模型的存储、编辑、显示、传输等都有很重要的意义，如何解决保 证用户需求的情况下，可以很好的通过减少网格几何数据来做到网格模型的简 化便于处理。在三维场景中大量的网格模型是由众多的网格共同组成的。在这 些由很多m e s h 所组成的网格模型中有很多的网格是相互交叠，而且它们是可以 共用的，这样将可以网格合并的网格合并后的结果是可以很好的解决网格数量 过大的问题，然后通过网格简化的方法进一步调整网格的优化，这样对大规模 的网格模型优化是有很大的简化意义。本文的研究目的就是要针对目前在场景 中存在的由大量网格所构成的网格模型，而且这些网格相互交叠，如何让这些 网格模型得到简化，让这复杂的模型容易处理。 通过本文的研究，提出一种通过网格合并的方法，简化网格模型，让这些单 独而重复的网格模型变成更少的网格所组成的网格模型，在网格合并算法的基 础上提出一种新的大规模网格模型合并的算法，首先用包围盒检测出网格相互 交叠处，针对网格合并的条件提出一种基于射线的距离检测方法，删除冗余网 7 武汉理工大学硕士学位论文 格再用网格缝合的方法进行网格合并，最后在网格合并后才采用简单高效的网 格简化算法进一步简化网格的算法结构。实验证明这种新的网格优化算法针对 大规模网格模型有很好的优化效果，让网格模型的网格数量得到适当的减少， 但对网格模型的原有形状并没有很大的影响，通过改进后的算法效率更高，更适 用于大规模的网格模型交叠优化。 1 4 本文的研究章节安排 本文第1 章首先对论文提出的研究课题作了细致的研究背景及现状分析，分 析要解决这样的问题所需要采用的方法和技术，提出了自己的解决问题的研究 办法，以及这个问题的解决所起到的现实意义。 论文第2 章对常用的网格模型优化算法的介绍，分析了常用的网格优化算法 各自所适用的范围和特点，对后面网格合并和网格模型进一步优化起到了很好 的借鉴作用。主要介绍了网格优化处理算法和网格模型优化时候要进行的误差 控制，对一些经典的网格优化算法进行介绍，如顶点聚类、重采样、项点删除、 边折叠【5 7 】1 5 8 1 、小波分析、区域合并，以及逐步求精与动态优化中的渐进网格、 层次表示法等多种基本思想和算法研究。 文章的第3 章主要对网格合并所采用的技术网格边界腐蚀算法 7 3 和网格缝合 算法进行分析。并且提出了一种改进的简化网格合并算法，采用包围盒分割法 检测网格模型间的交叠部分，采用顶点到三角面质心的方法判断交叠有效区域， 然后再使用交叠三角形对的合并算法对网格进行合并。这种网格合并算法只需 要三步就可以完成，大大简化了网格合并的步骤，提高了网格合并的效率。 论文第4 章是对大规模交叠网格模型的优化算法进行详细阐述和分析，重点 讲述了合并完成就使用拉普拉斯光顺算法对合并区域进行平滑处理，最后分析 了经典的光顺算法，并对合并后的网格模型使用改进的顶点删除简化算法进一 步优化，针对网格简化时出现的空洞，提出了改进的凸多边形三角化剖分算法， 在一定程度上改进了网格优化的效率。使其成为一个尽可能简单的网格模型， 依然具有原来的网格模型特征和形态，这样的组合优化方法是最为高效、保持 模型原有特性的有效算法。 第5 章是对大规模网格优化算法的总结和展望，对论文的总体结论，并对外 来网格优化的方向进行了分析。 8 武汉理工大学硕士学位论文 2 1 引言 第2 章常用网格模型简化算法 网格模型的简化常指的是三角网格的简化，因为多边形网格最终都可以转 换为三角形网格来处理，它的种种优点特性让它成为了三维图形领域里最常用 的表示方法，从2 0 世纪7 0 年代到今，网格模型简化技术发展非常迅猛，有很 多学者针对不同的情况提出了很多网格模型化简的问题。网格模型简化的真正 意图是在保持简化模型尽量逼近原始模型的情况下，删除多余的顶点或者暂时 只绘制所需要的那一部分网格。网格简化是有一定的简化原则和误差度量的。 迄今为止已经有学者提出很多的网格简化算法。比如：顶点聚类简化法、小波 分解法、顶点删除法、三角形折叠简化法、边折叠简化法和区域合并简化法等 等。在这些方法中删除简化算法成为了一类非常重要的简化算法，有很多的简 化算法都是删除简化算法来展开的。 2 2 网格简化的原则和误差度量 网格模型的简化并不是尽量的删除网格节点，减少三角面片就可以简化网 格，简化的原则是要在尽量保证网格模型特征的情况下，减少原始网格模型的 三角面片和顶点的数目。要同时尽量保证简化模型的顶点数目要少，简化后的 模型与原模型的误差要最小。这两点在考虑简化算法优劣的时候都是重要的衡 量标准。 误差测量是有相应的比较分析方法量化出简化后的模型与原有模型间的差 异，求出模型的差异比例。几何误差测量【9 l 和外观相似度测量这两种方法被人们 常用。几何误差测量法是一种较为常用的办法，因为人们视觉习惯用外观相识 度来进行测量，但是由于需要当人们从不同的视角去看，而且角度又有很多， 结果就完全不同，这样会带来大量的计算问题。定义 以( m ) = m i l l0 v w 4 表示顶点v 到模型m 之问的距离，其中0o l i 表示向量长度，两模型之间的几何 9 武汉理工大学硕士学位论文 e 一( m 。，m ：) = x 姒( ( 豫或( 肘。) m ，啪a x 或( m ：) ) ) 这个误差是被用来衡量简化后的模型和原模型之间的最大偏差。上面定义的度 量方式是基于厶范数，同样这两个模型间的平均偏差也可定义基于厶范数的误 差测量为： e 嘴( m i , m 2 ) 2 i i 俺三。d ：( m z ) + ：i ：。三：d i ( m 。 上式中朋和耽是肘，和：的面积。 误差测量在实际运用中计算的代价是很高的，常常采用对网格模型局部化 的测量求出近视的方法，来减少计算量，而且可以把搜索的最近点的范围限定 在模型的一个局部范围n 内，即距离值d ( v ，加代替d ( v , m ) ，在局部范围内逼近 原模型，从而进一步提高运算效率。 2 3 常用的经典网格模型简化算法 目前，三角网格模型的简化技术在很多行业领域都被广泛使用，三角网格 模型简化技术有效的降低了网格存储空间，大大提高模型渲染显示，模式识别 等操作的效率，加快了网格模型的网络传输速度。按照能否实时产生多分辨率 网格模型，常用的经典网格简化算法可分为两类：静态简化法和动态简化法0 4 1 。 顶点聚类法、几何元素删除法、细分法、小波分解法、重新布点法等属于静 态简化法。层次表示法和渐进网格法等等动态的简化算法。 2 3 i 顶点聚类法 顶点聚类方法【5 】的原理是使用一个包围盒将原始网格模型包围起来，然后采 用空间划分法把包围盒分解成很多个区域。原始模型的所有节点就分别落在这 些划分出来的区域内，然后将局域类的所有顶点通过一定的合并原理合并为一 个新的顶点，根据原始网格模型的拓扑关系对产生的新顶点重新三角化，产生 简化的网格模型， 图2 1 展示了顶点聚类法的实现步骤和原理，顾名思义，就是将一定范围内 的顶点进行聚合成为一个顶点，合并后的顶点明显简化了网格顶点的数量。那 1 0 武汉理工大学硕士学位论文 么什么范围内的顶点该进行合并聚类呢? 从图上可以看出将一个网格模型用栅 格进行包围划分，网格的顶点就会落入这些划分的小栅格内，在同一个划分区 域中的共同点归并为一个顶点，删除原有顶点，就产生一个新的顶点，然后重 新连接模型拓扑结构。 广 ， 、 、 ； ) t ， t 刁 广 l j 广 ， 、 1l i ) f 、 一， 广1 lj 图2 1 顶点聚类法 网格聚类法有如下一些优点： ( 1 ) 算法实现简单，容易实现，效率也较高。 ( 2 ) 算法适用性较广，对原始网格模型的拓扑结构没有很严格的限制。 ( 3 )由于在删除顶点，有可能改变了网格模型的原有拓扑结构，偏离了原 始网格模型的外观。 ( 4 ) 简化的网格模型精度与包围盒的划分尺度有很大关系。如果包围盒的 划分尺度很小，小到让每一个点都分别落在单独的区域里，就和原始 模型是一摸一样的，具有1 0 0 的精度，随着划分尺度的变大，模型 精度逐渐下降。 顶点聚类算法经过很多的改进，效率也有所改进，l o w 和t a n 提出了浮动栅 格聚类算法【1 9 】，又有学者提出了o u t o f - c o d 2 0 简化算法，l u c b k c 提出了层 次动态聚类简化算法【2 。 2 3 2 几何元素删除法 几何元素删除法是通过删除网格几何元素来达到简化模型的目的，包含顶点 删除法、边折叠法、三角形删除法等。它们都是在保持几何误差的情况下，对 网格几何元素影响模型几何特征较小的图元进行删除，几何元素删除法是目前 使用最为广泛的方法之一。 武汉理工大学硕士学位论文 2 3 2 1 顶点删除法 顶点删除法【8 】是一种比较简单的基于删除原理的简化算法，其原理是用点到 平面距离的阀值来判断顶点与周围三角面是否共面，并且如果删除这点并不会 影响原始模型的拓扑结构，将这个多余的顶点给剔除掉，同时也剔除与该顶点 相互连接的三角形，这步操作后会让网格模型的面产生一个空洞，需要对这个 空洞进行拓扑化，就会产生一个新的模型【5 3 】，重复上面的步骤，直到简化完成， 如图2 2 所示。 图2 2 顶点删除法 顶点删除法的特点包含如下几点： ( 1 )可以减少较为平坦且近乎共面的网格平面的顶点，大量减少信息。 ( 2 )生成的简化网格模型质量较好。 ( 3 )生成的简化模型很少改变原始模型的拓扑结构。 顶点删除法经过改进，在1 9 9 2 年s c h r o e d e r 提出了的改进的顶点删除算法， 它可以对网格的内部、边界、焦点和不连续等多个地方的顶点进行删除。c o h e n 提出了简化信封( s i m p l i f i c a t i o ne n v e l o p e s ) 算法【4 】，这种算法简化效果很好，但 是速度较慢。 2 - 3 2 2 边折叠简化法 在计算机图形学中，三角形边折叠简化是一种重要的简化算法。它的实质是 顶点删除，该算法的基本原理是按照一定的规则删除网格中的边，这规则为： 首先从网格模型中选出两个顶点ky ，判断他们是否相邻且满足删除距离，如果 满足则删除连接这两个顶点的边( x ，y ) ，然后删除与这条边相连的三角形，那 么这两个顶点会变成一个新的顶点z ，重复以上步骤，直到完成简化，如图2 3 所 示，顶点v 1 与v 2 合并为顶点v ，同时删除与顶点v l 和v 2 相关联的两个三角形， 这样便减少了一个顶点两个三角面片，达到了网格简化的目的。 1 2 武汉理工大学硕士学位论文 图2 3 边折叠删除法 边折叠算法具有如下特点： ( 1 ) 算法适用较广，可以对任何拓扑结构进行简化。 ( 2 ) 可以在不改变拓扑结构的情况下，进行很好的简化。 ( 3 ) 模型简化效果较好。 ( 4 ) 容易生成不同精度的网格模型，并实现相互转换。 1 9 9 3 年h o p p e 等人提出了基于能量的边折叠简化算法【3 1 ，该算法提出一个 由三部分组成的能量函数，分别为距离分量历、顶点数目分量b 以及弹性分量邑。 用总能量公式层= 西+ b + 巴表示，三个分量分别表示简化模型和原始模型间的最 大误差，用于衡量模型中的顶点个数和衡量简化模型的各顶点间的距离【3 2 1 。这 种算法包括三种基本行为：即删除边、拆分边和交换边。算法原理为：从三种基 本行为中选一种适合的进行，然后将执行这中行为后的结果值e 与总值& 进行 比较与e ，当e e ，就完成这个步骤，否则不执行。一直对所有待删除的边 进行操作，直到能量值不再发生变化，找出新的顶点位置。这种算法显然比一 般的边折叠简化算法优秀，因为它可以通过多个变量进行控制，使得三角面曲 率大的地方产生多一些网格，三角面曲率小的地方则少产生一些网格。 在1 9 9 6 年，h o p p e 等提出了一种渐进的简化算法【l ，它的原理是在网格绘 制的同时，一步一步的进行顶点分割产生不同精度的网格模型，这种算法的效 果比较明显，但是时间复杂度较高，实现和使用都比较困难。1 9 9 6 年r o n f a r d 7 1 提出了用顶点到面片的距离的最大值当作折叠的收缩误差衡量标准 1 9 9 7 年g a r l a n d 提出了采用二次误差检测的边折叠算法q - s l i m 2 1 ，它的原理 是借用顶点到三角面的距离平方和这一标准，当作是否进行边折叠的判断标准。 通过误差矩阵选择模型中误差较小的顶点进行边折叠。这种算法具有运算速度 快，简化质量高等优点，