（计算机应用技术专业论文）全可逆递进网格构造算法研究.pdf

摘要 在计算机图形系统中，三维物体通常用多边形网格，尤其是三角面片组成的网格 来表示。为了满足日益增长的图形真实感的需要，模型和几何场景变得高度细节化。 尽管图形绘制系统的性能在近几年有明显的提高，但是总有一些场景太过复杂，不能 实时绘制。为了解决这个难题，人们提出了l o d 多细节层次模型技术，试图解决复杂 场景与绘制系统实时绘制能力不匹配的矛盾。 本文提出了一种基于边折叠的全可逆递进网格快速构造算法，用以构造多细节层 次模型，主要开展了以下研究： 在二次误差网格简化算法基础上，提出了基于顶点局域面积度量的边折叠网格 简化算法，利用该算法对三维网格进行简化； 在网格简化实现过程中，需要保持网格模型的边界，本文提出了一种效率更高 的判断网格边界边的方法； 改进了基于顶点局域面积度量的网格简化算法，将之应用于全可逆递进网格的 构造算法中。同时提出了基于项点邻居三角形索引表的递进网格二义性消除方 法。 利用v i s u a lc + + n e t 结合o p e n g l 开发了全可逆递进网格构造算法的演示平 台。该平台包括网格简化演示模块与全可逆递进网格构造演示模块。 关键字网格简化，递进网格，l o d ，全可逆递进网格 a b s t r a c t i nt h ec o m p u t e rg r a p h i cs y s t e m ，t h et h r e e - d i m e n s i o nm o d e lo f t e nr e p r e s e n t e da s p o l y g o nm e s he s p e c i a l l y t r i a n g l em e s hw h i c hc o m p o s e do ft r i a n g l e s h i 曲l yd e t a i l e d g e o m e t r i cm o d e l sa r en e c e s s a r yt os a t i s f yag r o w i n ge x p e c t a t i o nf o rr e a l i s mi nc o m p u t e r g r a p h i c s a l t h o u g ht h ep e r f o r m a n c eo ft h eg r a p h i cs y s t e mw a si m p r o v e do b v i o u s l yi nt h e p a s ty e a r s ，b u tt h e r es t i l le x i s ts o m e s e t t l e sa r et o oc o m p l e xt or e a l t i m er e n d e r i na d d r e s s i n g t h i sp r o b l e m ，l o dt e c h n o l o g yw a si n t r o d u c e d ；l o dw a se x p e c t e dt os o l v et h et m s u i t e d c o n t r a d i c t i o nb e t w e e nc o m p l e xs c e n 鼯a n dt h er e a l t i m er e n d e r i n ga b i l i t yo ft h er e n d e r i n g s y s t e m i nt h i sp a p e r , t h ea u t h o rb r i n gf o r w a r dae n t i r er e v e r s i b l ep r o g r e s s i v em e s hc o n s t r u c t i o n a l g o r i t h m sb a s e do ne d g ec o l l a p s et oc o n s t r u c tl e v e l so fd e t a i l f i r s t ，t h i sp a p e rb r i n g s f o r w a r dan e ws 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 nq u a d r i ce r r o rm a t r i xu s i n gl o c a lr e g i o n a r e am e a s u r eo fv e r t e x ，a n du s i n gi tt os i m p l i f yt h em o d e l s s e c o n d ，m a k ei m p r o v e m e n to n t h ea l g o r i t h mt os u i tf o rt h er e v e r s i b l ep r o g r e s s i v em e s hc o n s t r u c t i o na n di n t r o d u c e dan e w m e t h o dt os o l v et h et w o n e s sp r o b l e mo f t h ee n t i r er e v e r s i b l ep r o g r e s s i v em e s hc o n s t r u c t i o n t h i sp a p e ra l s ob r i n g sf o r w a r dan e ve f f i c i e n t l ym e t h o do fb o u n d a r ye d g ej u d g e m e n t i n a d d i t i o n ，w em a k er e a l i z a t i o no ft h er e v e r s i b l ep r o g r e s s i v em e s hc o n s t r u c t i o nd e m os y s t e m u s i n gv i s u a lc + + n e ta n do p e n g l t h ed e m oa l s oc o n t a i n st h em o d u l eo fm e s h s i m p l i f i c a t i o n k e yw o r d sm e s hs i m p l i f i c a t i o n ，p r o g r e s s i v em e s h ，l o d ，e n t i r er e v e r s i b l ep r o g r e s s i v e i l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在在论文中作了明确的说明。 作者签名：呈社童 日期。学上月乒日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据 国家或湖南省有关部门规定送交学位论文。 名：翩蚪 中南大学硕 ：学位论文第一章绪论 1 1 概述 第一章绪论 为了使计算机绘制的场景具有真实感，几何模型变得高度细节化。利用建模方法 构造出的高度细节化三维模型，其数据容量十分巨大。在计算机图形学中，为了对其 进行有效绘制，三维模型通常用多边形方式网格( m e s h ) 来表示，如图l l 所示。 ( a ) 茶壶( ”帆船 图1 - 1模型的三角网格表示 此外，高度细节化的三维模型也可以通过物理扫描设备如三维模型扫描系统进行 扫描获取。不管使用何种方式，这类复杂的网格模型都不易于存储、传输和绘制，并 由此引发了如下相关问题的研究1 】： 。 网格简化：利用建模和扫描系统所获取的网格模型，很少有出于绘制效率上的考 虑而对其进行优化。另外，在很多场合中，经常需要一些与原始网格模型相差不大但 三角面片数远小于原模型的近似模型来代替显示减少不必要的绘制开销。以前，该过 程需要用户的人工干预来完成。为了让图形系统自动完成以加快绘制速度，就需要通 过网格简化来生成不同分辨率程度的模型以适应各种不同的应用需求。 l o d ( l e v e l s o f - d e t a i l ) ：l o d 是指对同一个场景或场景中的不同物体，使用不 同细节的描述方法进行绘制。这些不同细节的模型一般通过一定的简化算法来生成， 即利用网格简化算法对模型进行简化并用简化后的模型近似代替原始网格模型进行绘 制，或者预先定义一组不同细节的简化网格模型，然后根据场景和视点的不同要求进 中南大学硕i 学位论文第一章绪论 行有选择的绘制。 递进传输( p r o g r e s s i v e t r a n s m i s s i o n ) ：图形系统中，当个网格在渲染流水线被传 送时，该网格的渐进传输将比普通传输方法为好，这将降低图形系统的内韶数据传送 开销。一个比较好的方法是利用之前所述的l o d 方式进行渐进传输 网格压缩( m e s hc o m p r e s s i o n ) ：为了降低复杂网格模型所占用的存储空间，应该 对其存储空间进行最小化。解决该问题有两种方法，一种是利用网格简化算法减少原 始网格模型的顶点及其面片的数目。另一种方式便是网格压缩：对一特定的网格模型， 使其存储空间最小化。 选择性精化( s e l e c t i v er e f i n e m e n t ) ：l o d 方式表示方法中的每个网格模型，都是 独立于视点的。也就是说，如果图形系统已经绘制了该模型，用户不管从何种角度观 察该模型，图形系统都不会对其进行重新绘制，前提是该模型没有运动或者变换。有 时，需要对模型的某一特定的区域进行精细绘制。例如，在陆地上空漫游飞行，表示 陆地的网格模型中的离用户视点较近并且处于用户视野内的那块区域就需要精细绘 制。 在实际应用领域，一方面为了满足日益增长的图形真实感的需要，模型和三维场 景等变得越来越高度细节化，往往需要几万乃至上百万个的三角面片才能精确刻画出 物体的细节特征，如巨型建筑、三维漫游场景；另一方面，在网络传输和模型场景的 实时绘制场合中，对绘制速度与绘制效果上的要求越来越高。这类复杂的模型和场景， 对图形系统的绘制、存储能力，网络的传输带宽等提出了巨大的挑战。 随着芯片制造工艺的进步，c p u 与g p u ( g r a p h i ep r o c e s s i n gu n i t ，图形处理单元) 的性能获得巨大的提升，使得c p u 能够借助g p u 强大的图形绘制能力绘制精美的二 维与三维场景。然而，各种软件及应用诸如3 d 游戏、c g ( c o m p u t e rg r a p h i c ，计算机动 画) 、大型漫游系统、实时仿真系统等的复杂性远远超出了c p u 与g p u 性能提升的幅 度。简而言之，硬件性能的提升远远跟不上应用的需求。 为了解决上述矛盾，提升图形系统的绘制性能，人们对上述相关技术尤其是l o d 技术进行了深入的研究。通常，在用一般的网格简化算法构造l o d 模型时，需要生成 多个不同的简化模型以满足进行不同层次细节绘制的需要，并且为了使l o d 模型的过 渡具有连续性，需要非常多的层次。要对如此多的不同层次细节模型进行有效的存储、 2 中南大学顾十：学位论文第一章绪论 传输和网格传输就变得相当的困难。为此，m i c r o s o f t 公司的h h o p p e 于1 9 9 3 年提出 了递进网格( p r o g r e s s i v em e s h ，p m ) 概念【l i ，为解决上述问题提供了一种统一的解决方 案。 备注：如无特殊说明，文中所引用的网格模型图例与递进网格序列均由本文实现的全可逆递进 网格构造算法演示系统生成 1 2 l o d 技术 1 2 1l o d 简介 l o d ( l e v e l so f d e t a i l ) 多细节层次模型是指对同一个场景或场景中的物体， 使用具有不同细节描述方法得到一组模型，供绘制时选择使用。l o d 模型被大量用在 复杂3 d 场景实时绘制、飞行模拟、3 d 动画、交互式可视化和虚拟现实等应用系统中。 l o d 方法的基本思想是：对场景中的不同物体或物体的不同部分，采用不同的细 节描述方法，在绘制时，如果一个物体离视点比较远，或者这个物体比较小，就用较 粗糙的l o d 模型绘制。反之，如果一个物体离视点比较近，或者物体比较大，就用较 精细的模型来绘制。同样，如果场景中有运动的物体，也可以采用类似的方法，对处 于运动状态中或运动速度较快的物体，采用较粗糙的l o d ，而对于静止活运动速度较 慢的物体，采用较精细的l o d 模型进行绘制。 显然，l o d 技术充分利用了人们的视觉特性。为物体提供不同的l o d 描述是控 制场景复杂度和加速图形绘制速度的一个非常有效的方法，是解决复杂场景与计算机 计算能力、图形绘制系统实时绘制能力不匹配的一种有效途径。 为物体提供不同的l o d 描述是控制场景复杂度和加速图形绘制速度的一个非常有 效的方法口1 。l o d 技术的产生可以追溯到1 9 7 2 年，c l a r k 认为当物体覆盖屏幕较小区 域时，可以使用该物体的较粗糙的模型，并给出了一个用于可见面判断算法的几何层 次模型，以便对复杂场景进行快速绘制p 1 。1 9 8 2 年，r u b i n 4 j 结合光线跟踪算法，提出 了复杂场景的层次表示算法及相关的绘制算法，从而使计算机能以较少的时间绘制复 杂场景。c r o w t 5 l 用一个实例说明了同一物体采用不同的l o d 模型所具有的优点。 1 2 2 l o d 应用 l o d 模型在使用时，充分考虑了人们对图像的视觉效果，l o d 方法目前广泛应用 于多种不同的应用中。 中南大学硕 学位论文第一章绪论 ( 1 ) 虚拟现实 虚拟现实系统特别强调真实感图形的实时生成，因而l o d 模型得到了广泛应用f 6 l ， 很多虚拟现实系统都把场景用l o d 模型描述，虚拟现实建模语言v r m l 也包括对l o d 描述的支撑。 ( 2 ) 交互式可视化 科学计算可视化中的等值面抽取算法产生由大量三角面片组成的三角网格，要对 这样的网格进行交互式考察，一种有效的方法是使用多边形网格简化技术，生成不同 l o d 模型，根据不同的需要进行选用。 ( a ) 原始模型( b ) 简化模型1( c ) 筒化模型2( d ) 简化模型3 图l - 2 l o d 模型在可粳化中的应用 ( 3 ) 飞行模拟、3 d 动画和交互式仿真 飞行模拟器是最早使用l o d 技术的实用系统，在3 d 动画、交互式仿真等交互式 图形应用中也经常用到l o d 模型描述方法。另外，在地形可视化应用中，地形网格中 的面片数目十分庞大，经常使用l o d 方法来描述地形数据。 ( 4 ) c a d 和虚拟快速成型系统 在c a d 和虚拟快速成型系统中，为了支持实时预观察，可以把c a d 模型用多个 l o d 模型或多分辨率表示。 【a ) 原始模型( ”简化模型1( c ) 简化模型2( d ) 简化模型3 ( 5 ) 网格图形应用 图l - 3 l o d 模型在c a d 中的应用 4 中南人学硕1 ：学位论文第一章绪论 在一些网格图形应用中，如三维网络游戏，经常需要通过网络进行图形数据的传 输，为了避免接收方等待过长时间，可以先传送简化模型( 较粗糙的l o d 模型) 。 1 2 3 l o d 实例 我们用一个l o d 实例，来说明同一物体采用不同的l o d 描述方法所具有的优点。 ( a ) 原始模型( b ) l o d 层次1( c ) l o d 层次2 ( d ) l o d 层次3 图1 4小猫模型的l o d 表示 图l - 4 为小猫模型的l o d 表示。图1 - 4 ( a ) 为原始网格模型，图1 - 4 ( b ) 一图1 4 ( d ) 分 别表示了该模型的3 个l o d 层次，其中，从层次l 到层次3 依次简化了原始模型中2 0 、 4 0 、6 0 的三角面片。观察该图可以发现，对于视点远近不同的模型，采用l o d 绘 制方式后，在提高实时绘制速度的同时，视觉效果上几乎没有任何退化。 综上所述，l o d 技术是解决复杂场景与图形绘制系统实时绘制能力不匹配的一种 有效途径，将会得到更加广泛的应用7 1 。 1 3 网格简化 l o d 模型通常通过网格简化算法来生成。网格简化的目的是把一个用多边形网格 ( 通常是三角网格) 用一个近似模型表示，近似模型基本保持原始模型的特征，包括 集合特征和视觉特征，但顶点数目和三角形数目都少于原始网格。 1 3 1 网格 网格( t r i a n g l em e s h ) 是一个由三维空间中一些三角化的面片互相通过它们的边连 接在一起所构成的分段线性表面】。参见图1 1 。网格在数学上可表示为m = ( k 功， 其中k 是一个单纯复形，表示边、顶点、三角面片的连接关系。矿= ，1 ，v 2 ，v m ) ，m r 3 是网格m 中顶点位置的集合，定义了网格在三维空间中的形状。 单纯复形足由一个顶点集合 1 ，埘 与该顶点集合的所有非空子集构成，称其中 5 中南人学硕f ：学位论文第一章绪论 的每一个非空子集为k 的单形。称单形 i e k 为顶点，单形 f ，) 为边，单形 f ，j ，| ) 为 面。 对于网格m 中的任意一条边 f ，歹) e k ，如果该边只为一个三角形 f ，j ，k e k 所有， 则称该边为边界边，该边的两个顶点为边界顶点，该边所在的三角形 f ，工料e k 为边界 三角形。 ， 1 3 2 网格简化 网格简化( m e s hs i m p l i f i c a t i o n ) 就是通过一定的算法，减少原始网格的三角面片及 其顶点的数目，同时在简化模型中尽量保留原始模型的形状。通过网格简化，可以生 成多个不同分辨率的简化模型，达到加快实时绘制速度的效果。 1 3 3 网格简化的意义 利用网格简化算法在对网格模型进行简化的过程中是要耗费处理器时间的，表面 上增加了实时绘制的步骤。实际上，通过网格简化能够极大的提高图形绘制系统的实 时绘制性能。因为有了l o d 技术，图形绘制系统仅需要绘制新出现的部分场景而不需 要重新绘制整个场景，从而能使计算机能以较少的时间绘制复杂场景。 1 4 网格简化算法 网格简化的目的是把一个用多边形网格( 通常是三角网格) 表示的模型用一个近 似模型来表示，近似模型基本保持原始模型的特征，包括几何特征和视觉特征，但顶 点数目和三角形数目都少于原始网格。 从9 0 年代开始，国外研究人员提出了多种网格简化方法，包括顶点删除、三角形 删除、边折叠、三角形折叠和近平面合并等。国内研究人员近几年也提出开展了一些 卓有成效的研究工作i s , 9 , 1 9 , 2 0 0 4 0 5 0 6 ，3 5 娜1 ，有些对已有的网格简化算法进行改进，有些是 提出新的网格简化算法。 1 4 1 网格简化算法类型 网格简化算法有多种类型，主要分为如下几类： 一、拓扑结构保持型算法、拓扑结构非保持型算法 1 拓扑结构保持型算法 在拓扑结构保持型简化算法中，必须保持模型的拓扑结构。如果模型包含退化情 形，如三角形重叠、某条边由两个以上的面片共享，那么就不能进行处理。绝大多数 简化算法都属于这种类型。 6 中南人学硕l ：学位论文第一章绪论 2 拓扑结构非保持型算法 拓扑结构非保持型简化算法并不保持模型的全局或局部拓扑结构，只要求简化模 型的其图形生成效果与原始模型一致。由于该类算法的约束条件少，因此模型的简化 程度很高。在保持较高帧率且允许图形的视觉效果可以一定程度下降时，可以使用这 类算法。但是该类算法所生成的简化模型效果可能会很差。 二、自适应细分型采样型几何元素删除型 1 自适应细分型 这种方法要求首先建立原始模型的最简化形式，然后根据一定的规则通过细分把 细节信息增加到简化模型中，从而得到较细的l o d 表示。这种方法很少使用，原因是 在一般情况下，构造原始模型的最简模型相当困难，它主要适用于均匀的网格，如高 度场。 2 采样 这种方法类似于图象处理中的滤波方法，有时不能保持拓扑结构不变。该方法对 原始模型的几何表示进行采样，通常的做法是在原始模型的表面上选择一组点，对选 择出来的点进行网格绘制。 3 几何元素删除型 几何元素删除型算法通过重复的把几何元素( 点、边、面) 从三角形中“移除” 来得到简化模型。移除分三种情形：一种是直接删除，另一种是指通过合并2 个或多 个面来删除边或面，第三种是指对边或三角形进行折叠。移除操作不断进行，直至模 型不能被简化或达到用户指定的近似情形为止。 三、局部算法全局算法 局部算法是指应用一组局部规则，仅考虑模型的某个局部区域特征对模型进行简 化。该类算法的例子有s c h r e o r d e r 的顶点删除1 0 1 ，r o s s i g n a c 的顶点折叠【1 i 】，h o p p e 和 g u e z i e c 的边折叠 1 2 ：3 1 ，h a m a n n 的三角形删除1 14 1 。 全局算法是指对整个物体模型或场景模型的简化过程进行优化，而不仅仅根据局 部的特征来确定删除不重要的图形元素。全局的简化算法主要有t u r k 提出的在表面上 重新分布顶点方法【1 5 】；c o h e n 提出的包络网络【1 6 】以及e c k 的小波表示方法1 1 7 】。 有些算法很难具体归入哪一类型，其既有局部特性，也有全局特性【舡4 2 j 。如h o p p e 提出的全局能量函数最优化方法【l 】 7 中南人学硕t 擘位论文第一章绪论 1 4 2 网格简化算法概述 一、自适应细分型算法 d e h a e m e r 提出的算法是自适应细分算法的典型代表，该算法假定输入模型来自于 三维扫描仪的输出，利用了输入数据的规整性f 1 8 】。根据用户指定的误差容限，通过多 次细分来自动生成一个简化模型。该算法具有拓扑结构保持特征，缺点在于仅适用于 j 下规网格，而且，计算初始时供细分用的简化模型比较困难。 二、采样型算法 r o s s i g n a c 提出的多分辨率三维近似算法是一种采样算法，该方法的基本思想是： 用一个包围盒把原始网格模型包围起来，通过等分包围盒的各棱边将包围盒等分成若 干个小的长方体，这样原模型的所有顶点就分别落在这些长方体内；扫描这些长方体， 如果某个长方体内有顶点，则把该长方体内的所有顶点删除并生成一个新顶点，这个 新顶点是所有被删除顶点的加权平均。 该算法的优点在于它适用于任意类型的输入模型，甚至可以是一些不够成网格的 多边形集合。另外，它也是一种非常有效的快速简化方法。其缺点是不保持原模型盼 拓扑结构，因而所产生的模型的视觉效果不佳。 三、几何元素删除型算法 1 几何元素直接删除型 几何元素直接删除型算法包括：顶点删除和三角形删除，这类算法的基本思想是 通过评价顶点或三角形的重要性，如果某一个顶点或三角形不重要，那么就直接删除 它，并对得到的空洞进行重新三角化。 s c h r o e d e r 提出的三角形网格简化算法的基本思想是：先对三角形网格中的顶点进 行分类，用距离误差分别计算顶点的重要性，删除不重要的顶点，并对删除顶点后留 下的空洞进行重新三角化。这个算法的计算量小，时间复杂度为线性，有很好的保持 细节特性，能保持模型的拓扑结构，简化模型的顶点为原始模型顶点的子集。该算法 虽然能够做到大量删减三角面片的目的，但由于采用局部近似误差度量，多次迭代后 会产生误差积累，从而影响简化模型的质量。另外，该算法需要重新局部三角化且仅 适用于流型物体。 t u r k 提出的基于重新划分网格的简化算法是将一定数量的新点随机分布到原始网 格上，新点与原有顶点生成一个中间网格，然后删除中i b j 网格中的原有顶点，并对产 生的多边形区域进行重新三角化，形成以新点为顶点的三角网格，该算法仅适用于比 s 中南大学硕i 二学位论文第一章绪论 较光滑的网格模型且计算量很大，也需要局部重新三角化。 c o h e n 提出的基于包络网络的简化算法的主要特点在于不使用误差度量，而是通 过几何结构( 内外两层包络网络) 来控制简化过程。该算法首先构造两层包络网络( 通 过偏移顶点来完成) ，然后对于原始网格中的每个顶点，完成以下步骤：移去该顶点以 及相邻的面偏，如果可行，对形成的空洞进行重新三角化，并保证形成的面片不与内 外包络网络相交，否则放弃删除。该算法的优点在于能够保持模型的拓扑结构，有效 的保留其基本特征，对棱角特征也能很好的保留，能有效的约束全局误差，支持自适 应的近似。该算法的最大缺点在于仅适用于二维流形，不适用于任意多边形网格模型 ( 如面片有自交情形) ，另外，包络网络难以构造。 国内也对网格简化算法进行了深入的研究，如基于重新三角化操作的网格简化算 法【1 3 】、改进的基于三角形移除准则的网格简化算法【2 1 、基于超包络网络的网格简化算 法等1 4 1 。 2 近平面合并型 近平面合并算法的基本思想是把近似位于同一个平面上的相邻三角形进行合并， 形成一个大多边形，再用数目较少的三角形网格来表示这个多边形 1 5 , 1 6 。近平面合并 算法的一个典型例子是k a l v i n 在1 9 9 6 年提出的基于区域生长的贪婪式简化算法【1 6 】。 3 边折叠型 使用边折叠进行网格简化的算法很多，边折叠操作容易构成连续的多个l o d 表示 模型，便于多分辨率模型的管理。 h o p p e 在1 9 9 3 年提出的网格优化算法【1 1 是最早引入边折叠简化元操作的算法。该 算法源于一个表面重构算法，既包括网格匹配过程，也包括网格简化过程。算法通过 使二个全局能量函数最小化来简化模型。该算法由于要建立和求解复杂的全局能量优 化方程，因而计算复杂性高，很难达到实时。 g a r l a n d 提出的网格简化算【2 3 】法可以对原始模型产生高质量的近似结果。算法使用 迭代的边折叠进行简化操作，并用二次误差度量方法来计算近似误差。该算法既可以 作用于流形物体，也可作用于非流形物体，能保持相对高的简化质量。 1 4 3 基于边折叠的网格简化算法 基于边折叠( e d g ec o l l a p s e ) 的网格简化算法是一类重要、有效的简化方法，该类 型的简化方法是m i c r o s o f t 公司的h h o p p e 于1 9 9 3 年首先提出的，适用于任意的二维 流形网格模型。根据如何评估删除某条边后所造成的总体误差，边折叠简化算法可以 9 中南人学坝i 学位论文第一章绪论 分为两大类：间接计算折叠误差法与直接计算折叠误差法。 在h o p p e 提出的简化算法中，分别计算集合误差和属性误差，然后将这两个误差 相加得到一个总体误差，对总体误差进行最小化，从而得到简化网格模型。该算法可 以获得较为优化的简化结果，但由于该算法需要计算个全局误差函数，并采用非线 性优化方法寻找一些新点，使全局误差函数最优，因此运行速度缓慢。 为了减少运算量，提高简化速度，g a r l a n d 等采用直接计算总体误差的方法进行简 化误差的评估以指导边的折叠顺序，在该算法中，以判断某个顶点到所有与其相关的 三角面片的距离的平方和作为误差度量，同时作为折叠边相关的两个顶点是否可以被 删除的准则。g a r l a n d 用一个二次误差矩阵( q u a d r i ee r r o rm a t r i x ，q e m ) 代替全局函 数来度量顶点的折叠误差，该算法的优点是计算简单，简化速度快，该算法在用于多 细节层次模型的生成时能取得比较好的效果，缺点是低分辨率下简化模型的三角分布 比较均匀，简化效果不佳，不能突出模型的特征。且其误差度量只是一个相对值，没 有明确的几何意义。 虽然q e m 算法有很多不足，但该算法仍然成为基于边折叠网格简化的重要算法。 目前提出的很多网格简化算法都是基于该算法进行改进的。如文献【2 4 基于q e m 算法， 引入子分规则来计算新的顶点位置，减小了简化网格和原始网格之间的误差。文献 2 5 1 提出了基于三角面片法向的改进算法。文献 2 6 】在q e m 算法基础上，提出了基于顶点 尖特征度的简化算法，通过对曲率变化较大的区域上的点增加一个惩罚项，增大它的 误差度量，从而改变边折叠的次序，使得原始网格模型的尖锐特征得以保留，改进了 简化效果。 比较上述几类简化算法，基于边折叠的网格简化算法具有简单、几何意义直观、 适用范围广等优点，且在简化过程中无需进行重新三角化操作【3 4 】。因此，基于边折叠 的简化算法成为目前网格简化研究的主流算法，是网格简化研究的热点。 1 5 全可逆递进网格 递进网格是实现l o d 连续过渡的一种很好的表示方法。在递进网格表示方式中， 一个任意的网格m 被表示成一个简化网格m o 和一组记录了网格简化信息的序列，简 化网格m o 通过将这一组序列中的信息逐个添加到自身，得到m l ， 如，直至j 】l 靠， 便可以动态、实时、无损的恢复为原始网格肘= 矗。 作为可逆递进网格的推广，全可逆递进网格可描述为将原始网格通过简化算法不 l o 中南大学硕l 。学位论文 第一章绪论 断进行简化，得到一个最终简化网格( b a s em e s h ，基网格) ，这一简化过程称为递进网 格在简化方向上的构造过程。如果将简化过程中的简化信息不断的向最终简化网格添 加，就能无损、连续的恢复为原始网格，这一恢复过程称为递进网格在恢复方向上的 构造过程。这两个过程合称为全可逆递进网格的构造。 全可逆递进网格具有很好的实时恢复性能，只要从简化模型序列当中任意给出一 个简化模型，通过全可逆递进网格构造算法，该简化模型既可以不断被简化得到更低 分辨率的简化模型，也可以逐步添加简化信息从而恢复为原始网格模型。 1 6 本文研究内容 本文研究了一种新的基于边折叠操作的网格简化算法。该网格简化算法基于 g a r l a n d 提出的q e m ( q u a d r i ce r r o rm a t r i x ，二次误差矩阵) 算法，通过在折叠代价计 算过程中引入局部区域面积度量方法( l o c a lr e g i o na r e am e a s u r e ，l p u 4 m ) 来改变模型特 征和平坦区域上的顶点的折叠次序。同时，我们对折叠目标顶点的位置确定方式做了 新的尝试。 作为递进网格概念的推广，本文提出了一种全可逆递进网格的构造算法。该构造 算法基于本文提出的网格简化算法，通过往一个任意的简化网格不断添加网格简化信 息从而快速的恢复为原始网格。 同时，利用v i s u a lc + + n e t 2 0 0 3 与o p e n g l ( o p e l l g r a p h i cl i b r a r y , 开放式图形库) 、 s t “s t a n d a r dt e m p l a t el i b r a r y , 标准模板库) 实现了算法的演示平台。实验结果表明， 本文算法较q e m 算法不仅简化速度更快，而且克服了q e m 算法在简化模型中网格分 布比较均匀、无法突出模型重要特征的不足，并且在简化程度较大的情况下仍能保持 原始网格的几何特征和视觉特征。同时，作者改进简化算法将其应用于可逆递进网格 的构造算法中，得到了很好的效果。 本文共分5 章，介绍如下： 第一章：介绍了国内外网格简化算法的研究现状，提出本文的研究内容和创新点。 第二章：详细叙述重要的网格简化算法q e m 算法，在此算法基础上给出了本 文提出的基于l r a m 的边折叠简化算法。结合实验结果与q e m 算法进行了详细比较， 归纳出本文提出的网格简化算法的优点，并对算法进行了简单的复杂性理论分析。 第三章：详细叙述全可逆递进网格的表示形式与构造算法，结合算法的实现过程， 列举有代表性的演示实验，对实验结果进行分析。 1 1 中南人学颂i 学位论文 第一幸绪论 第四章：详细叙述全可逆递进网格构造算法演示平台的丌发过程。通过概念模型、 协作图、设计类图等方式表现规范丌发的过程和理解系统的体系结构。介绍了开发过 程中所用的丌发工具与技术难点。 第五章：对本文所做的工作进行总结并提出了今后的研究方向。 1 7 本文的创新点 1 提出了新的基于顶点局域面积度量的边折叠简化算法，与二次误差网格简化算 法相比，该算法简化速度更快并且简化效果更好。 2 提出了一种效率更高的网格边界边的保持与判断方法。 3 在基于顶点局域面积度量的边折叠简化算法基础上，提出了一种全可逆递进网 格构造算法。与一般递进网格构造算法相比，该构造算法消除了顶点分裂时所产生的 二义性。 2 丌发了网格简化和全可逆递进网格构造的演示系统。该演示平台能够方便地进 行网格简化并且能够对全可逆递进网格的整个构造过程进行实时、连续的动画演示， 在演示的同时能够动态地显示模型信息。 1 2 中南人学硕l 学位论文第二章网格简化算法及其实现 第二章基于局域面积度量的网格简化算法及其实现 2 1 概述 基于边折叠的简化方法是网格简化算法研究的热点，近年来所提出的网格简化算 法都是基于边折叠的。在基于边折叠的简化算法中，边的折叠顺序由其折叠代价的大 小决定，折叠代价的大小由边的周边信息通过误差度量得到。因此，在这些基于边折 叠的简化算法中，其不同之处主要在于： 1 如何选择顶点对进行迭代折叠( 边的选择方法) ； 2 如何度量折叠产生的误差来控制简化过程( 边的折叠顺序) 。 本章在介绍在网格简化算法中具有重要地位的q e m 算法之后，详细阐述本文提出 的基于顶点局域面积度量的边折叠简化算法，最后给出本文算法与q e m 算法对不同模 型在简化结果和简化速度上的比较。 2 2 边折叠 边折叠操作是基于边折叠的网格简化算法的基本操作。考察一次边折叠操作，其 形式可表示为( ，w ) 一1 ，。即把该边的两个端点1 ，一、v z “折叠”到某一个顶点位置v 。 在基于边折叠的网格简化算法中，有两类边折叠形式，称为“一般边折叠”与“广义 边折叠”。 2 2 1 一般边折叠 一般边折叠方式是基于边折叠的网格简化算法的最常见，也是最基本的折叠方式。 如图2 - - 1 所示。 b e f o r e a t i e r 图2 - 1一般边折叠示意图 中南人学硕l 学位论文 第二章网格简化算法发j 实现 这种边折叠方式的折叠过程如下：将边( ，v 2 ) 收缩到一个顶点v ，同时将和该边 两个顶点相邻的所有顶点与产生的新顶点相连接，并删除所有的无效边。在图2 一l 中，无效边即为阴影三角形所在的边。 2 2 2 广义边折叠 广义边折叠的折叠过程如图2 2 所示。在这种边折叠方式中，当两个顶点的距离 小于某个指定的阈值时，则直接将这两个顶点连接在一起。该种折叠方式没有无效边， 而且连通了模型中的两个不相连区域。这种方式下，有可能改变网格的拓扑结构。 2 3 q e m 算法 勺一谢 0 专型! 鼍上，。 ”底 b e f o r e a f t e r 图2 - 2广义边折叠示意图 为了解决h o p p e 提出的简化算法中存在的计算效率慢的问题，g a r l a n d 于1 9 9 7 年 提出了基于二次误差矩阵( q u a d n ee r r o rm a t r i x ，q e m ) 的边折叠简化算法。该算法是基 于边折叠网格简化的重要算法。 网格简化过程中，简化模型必须与原网格尽量相似，这取决于边折叠的顺序和边 折叠后生成的新顶点的位置。如何选择合适的边进行折叠及如何生成新的顶点，有一 个选择误差度量标准的问题。 本节叙述q e m 算法的相关思想及其实现。 2 3 1 折叠代价的计算 在q e m 算法中，g a r l a n d 用顶点的二次误差度量来衡量该次边折叠的代价，根据 折叠代价的大小来决定边折叠的次序。其基本思想为：用4 维齐次坐标表示一个顶点 的位置，设v 是三维空问中的一个顶点，坐标为 h ，v y ，v z ，l 】7 定义p 缸h 甜( v ) 为所有包含 顶点，的三角形的集合。p 为包含顶点1 ，的三角形所在的平面方程甜6 卅c z + d - - o ，且口， b ，c 的平方和为1 ，p 可表示为【，b ，c ，明7 。定义顶点v 的二次误差度量( v ) 为顶点v 到 这些三角形所在平面的距离的平方和： 1 4 中南大学j 爱十学位论文 第一二章蹦格简化算法及儿实现 其中， ( v ) = d ；( v ) =( y 7 p ) 2 =c艘t)v=vt(plane，k(v)p。planesp c p l a n e ，彦 文件格式 0 项点个数 。 符 形顶点的肇标属性 式 ( 浮点型或整型) 的 卢 明 三角面片个数 顶点表 三角面片表 图4 - 1p l y 文件格式 一个p l y 文件由三部分构成：文件头、顶点表、三角面片表。文件头主要是一些 文件信息的声明，如文件格式、该模型所包含的顶点个数、顶点坐标的表示方式、模 型所包含的三角面片个数等。顶点表是对模型中所有项点的枚举，每一行标明一个顶 点的工、y 、z 坐标值。类似地，三角面片表是对模型中所有三角面片的枚举，其每一行 均表示一个三角面片，该三角面片由顶点表的顶点索引表示。 4 2 2 开发环境 平台以v i s u a lc + + j 咂t2 0 0 3 作为开发环境，是m i c r o s o f t 公司推出的最新的应用 程序开发工具。 v i s u a lc + + n e t2 0 0 3 是一个全新的可视化的c + + 编程环境，它为我们提供了一种 方便、快捷的w i n d o w s 应用程序开发工具，使用了w i n d o w s 图形用户界面的许多先进 特性和设计思想，采用了弹性的、可重用的、完整的面向对象程序语言。同时，使用 该开发工具进行软件开发，将会极大的提高编程效率。 v i s u a lc + + n e t2 0 0 3 支持c + + 语言的全部特性，如模板、名字空间和操作符重载 等。实际上，v i s u a lc + + n e t2 0 0 3 是c + + 语言的一种版本，但它与传统的c + + 语言有 很大的差别。一个v i s u a lc + + n e t2 0 0 3 程序首先是应用程序框架，这一框架是整个应 用程序的“骨架”。骨架上没有任何东西，需要程序员在骨架中加入自己的程序以满足 特定的丌发需要( 3 0 l 。 中南人学硕t 学位论文第州市伞日，逆递进网格构造算法演爪甲舟的开发0 实现 4 2 2 开放式图形库 o r ，e n g l 是近几年发展起来的一个性能卓越的三维图形标准 3 1 , 3 2 1 ，它是在s g i 等多 家世界闻名的计算机公司的倡导下，以s g i 的g l 三维图形库为基础制定的一个通用 共享的开放式三维图形标准。目前，包括m i c r o s o f t 、s g i 、m m 、d e c 、s u n 、h p 等 大公司都采用了o p e n o l 作为三维图形标准，以o p e n g l 为基础开发的较为著名的产 品包括动画制作软件s o f ti m a g e 和3 ds t u d i om a x 、仿真软件o p e ni n v e n t o r 、v r 软件 w o r l dt o o lk i t 、c a m 软件p r o e n g i n e e r 等等。值得一提的是，出于o p e n g l 的巨大影 响，m i c r o s o f t 公司在w i n d o w s 操作系统中也提供了o p e n g l 的实现。另外，随着支持 o p c n g l 三维图形加速卡的推出，o p e n g l 已在微机中广泛地应用，同时也为广大用户 提供了在微机上使用以前只能在高性能图形工作站上运行各种软件的机会。 o p c n g l 是一个三维的计算机图形和模型库，是一个图形硬件的软件接口，目前的 最新版本是1 4 。o p e n g l 被设计成独立于硬件，独立于窗口系统，在运行各种操作系 统的各种计算机上都可用，并能在网络环境下以c s 模式工作，是专业图形处理、科 学计算等高端应用领域的标准图形库。 4 2 3 标准模板库 在处理三维数据与显示三维模型时，经常需要创建同一个类的实例或者调用计算 过程相同但数据类型不同的某个过程，此时，利用s t l 可方便的实现上述操作，并且 不易出错。 s t l 是由a l e x a n d e rs t e p a n o v 于1 9 7 9 年开始构思的，并于1 9 9 3 年键入a n s i o s i c + + 标准委员会讨论，讨论后一致通过让s t l 成为c + + 标准的一部分。s t l 由此进入 c + + 标准化的正式流程，并最终成为1 9 9 8 年9 月定案的c + + 标准规格中c + + 标准程序 库的一个最重要的组成部分【3 3 1 。 s t l 包含六大组件，彼此可以组合套用： 1 容器( c o n t a i n e r s ) ：各种数据结构，如v e c t o r ，l i s t ，d e q u e ，s e t ，m a p 用来存放 数据，从实现角度看，s t l 容器是一种类模板( c l a s st e m p l a t e ) 。 2 算法( a l g o r i t h m s )