（计算机应用技术专业论文）lod模型网格简化方法的研究.pdf

中国民航大学硕士学位论文 摘要 随着建模技术的发展和三维数据获取设备的完善，大型三维模型已经十分常见， 这些模型满足了人们在精确度、真实感等方面日益增长的需求。但是这些模型数据量 很大，给其存储、传输以及渲染等方面带来诸多困难。解决这些问题的一个途径就是 对复杂三维模型进行简化和多分辨率建模，用比较简单的几何模型来代替复杂的原始 模型，以减少数据量，加快处理速度，节约存储空间。 本文主要工作可以概括为以下几个方面： 首先对网格模型简化算法中常用的典型误差度量方法进行了比较分类。由于不同 的领域对网格模型化简的精度有不同的要求，化简的模型也具有不同的属性，所以模 型简化算法都各自具有不同的特征。虽然各种模型简化算法的原理不同，但是也有相 似之处。一般都包含了两个方面：一是简化方法中采用的误差控制方法，二是算法中 采用的模型简化方法。 其次，目前的网格简化算法多以边折叠为基本操作，采用的误差度量方法计算复 杂且耗时，同时不能支持连续平滑的网格绘制。本文针对各种不同算法相似的两个方 面，以三角形折叠简化方法为基础，在上述误差度量方法比较分析的基础上，改进得 到了基于三角形周长和基于组合三角形周长与点到平面距离的两种新的三角形折叠代 价计算方法，进而实现了三角形折叠连续多分辨率网格简化算法。实验证明：本文的 两种新的误差度量方法，综合衡量折叠三角形的面积以及三角形周长和点到平面的距 离，尽量使面积大、周长长、点到平面距离小的的三角形面保留，从而避免模型视觉 特征的急剧改变；同时，这两种算法计算比较简单，易于实现，能够产生较好的简化 效果。 最后，本文描述了所设计和实现的连续多分辨率网格简化实验平台。该平台主要 利用渐进网格实现了连续多分辨率的层次模型之间的过渡。使用该平台，用户可以根 据自己的需要，选择不同的分辨率，比较分析相应的简化结果。 关键词：网格简化；多分辨率l o d ；三角形折叠；三角形面积；三角形周长； 渐进网格 中国民航大学硕士学位论文 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fm o d e l i n gt e c h n i q u e sa n dd a t aa c q u i s i t i o nd e v i c e s ， t h e r ea r em o r ea n dm o r el a r g es c a l e3 dm o d e l s t h e s em o d e l sc a na c c o m m o d a t et h en e e d f o rd e t a i l s ，b u tt h e i rd a t aa r es ol a r g et h a ti ti sv e r yd i f f i c u l tt os t o r e ，t r a n s m i ta n dr e n d e r t h e m o n ew a yt os o l v et h i sp r o b l e mi st os i m p l i f yt h e s ec o m p l e x3 dm o d e l sa n dt o p e r f o r mm u l t i r e s o l u t i o nm o d e l i n g ，a c c o r d i n g l yr e d u c i n gt h ed a t a , a c c e l e r a t i n gt h ep r o c e s s s p e e da n ds p a r i n gs t o r a g es p a c eb yr e p l a c i n gt h eo r i g i n a lc o m p l e xm o d e lb yas i m p l eo n e t h i sp a p e rc a r lb es u m m a r i z e da sf o l l o w i n g ： a tf i r s t ，w ec o m p a r e dw i t hm e t h o d so fe r r o rc o n t r o l l i n gi nd i f f e r e n ta l g o r i t h m s d i f f e r e n ta p p l i c a t i o nf i e l d sh a v ed i f f e r e n tp r e c i s i o nd e m a n d sa n dd i f f e r e n tm o d e l sh a v e d i f f e r e n ta t t r i b u t e s ，s o e v e r ys i m p l i f i c a t i o na l g o r i t h mh a si t so w nc h a r a c t e r e v e r y s i m p l i f i c a t i o na l g o r i t h mh a sd i f f e r e n td e m e n t s ，b u ti ti ss i m i l a rt h a tt h e ya l li n c l u d et w o p r o b l e m s g e n e r a l l yt h e r ea r et w op r o b l e m s ：t h eo n ei se r r o rc o n t r o l l i n gm e t h o da n dt h e o t h e ri sm o d e ls i m p l i f y i n gm e t h o d t h e r e f o r ew es o r tt y p i c a le r r o rc o n t r o l l i n gm e t h o d s m o s to ft h es i m p l i f i c a t i o na l g o r i t h mi sb a s e do ne d g ec o l l a p s e t h ec o m p u t a t i o no ft h e c o l l a p s e c o s ti s a l w a y se l a b o r a t e ，a tt h e s a m et i m ei tc a n n o td r a wac o n t i n u a l m u l t i r e s o l u t i o n sm e s h w i t ht h et w os i m i l a rp o i n t s ，w ep u tf o r w a r dt w on e we r r o r c o n t r o l l i n gm e t h o d sb a s e do nt h ew e i g h t e dt r i a n g l e sg i r t ha n dt h ed i s t a n c eb e t w e e np o i n t a n dp l a n ew i t hc o n t i n u a lm u l t i - r e s o l u t i o n sm e s h p r o v e db ye x p e r i m e n to u rn e wa l g o r i t h m b a l a n c e st h et r i a n g l e sa r e a , g i r t h ，a n dd i s t a n c ew h i c hc 柚r e m a i nt h et r i a n g l ew i t hb i g g e r a r e aa n dl o n g e rg i r t ha n dd i s t a n c et oa v o i dt h es h a r pc h a n g eo ft h em o d e l sv i s u a le f f e c t o u ra l g o r i t h m sa r ee a s yt oi m p l e m e n t ，a n dc a np r o d u c eh i g hq u a l i t ya p p r o x i m a t i o n so ft h e o r i g i n a lm o d e l f i n a l l yw ed e s c r i b eat e s t i n gf l a to nt h eb a s eo ft h en e ws i m p l i f i c a t i o na l g o r i t h m w i t h p r o g r e s s i v em e s h ，t h ef i a ti m p l e m e n t st r a n s i t i o n sa m o n gt h ec o n t i n u a lm u l t i r e s o l u t i o n s m e s h e s u s e rc a nc h o o s ed i f f e r e n tr e s o l u t i o nt og e tm o r en e a t l ya n db e t t e ra p p r o x i m a t i o n k e y w o r d s ：m e s hs i m p l i f i c a t i o n ：m u l t i - r e s o l u t i o nl o d ：t r i a n g l ec o l l a p s e ：t r i a n g l e s a r e a ：t r i a n g l e sg i r t h ；p r o g r e s s i v em e s h i i 中国民航大学硕士学位论文 中国民航大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得中国民航大学或其它教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 毕日 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅 和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授 权中国民航大学研究生部办理。 研究生签名：挚牡导师签名：纽鸯日 期：竺喳：堡矿! 中国民航大学硕士学位论文 1 1 研究背景 第1 章绪论 计算机图形学，从诞生发展到现在，已经在许多领域发挥着越来越重要的作用。 在日渐广泛的计算机图形学应用中，为了保证形体的真实感和层次感，往往需要高度 复杂、高度细节化的三维网格模型，以实现和完成各种不同的目标和效果。这样导致 了这些计算机图形学的许多应用中使用的三维几何数据的数量规模和复杂程度在急剧 地增长着。 对于很多应用来讲，通常要求能够实时地观测和操纵这些三维几何模型。这使得 人们要花费更多的代价去存储这些数据，而且它们对现有的三维图形引擎的处理能力 和速度提出了巨大的挑战。随着网络图形学的发展，越来越多的需要通过网络，特别 是国际互联网，来存取那些存放在异地的三维几何数据。这使得原本已经有限的网络 带宽变得更加的紧张。总之这些复杂的模型对计算机的存储容量、处理速度、绘制速 度和传输效率等都提出了很高的要求，给模型的存储、传输、计算、绘制等带来了困 难。然而在很多情况下，高分辨率的模型并不总是必要的，模型的准确度以及需要处 理的时间也要有一个折衷，因此必须用一些相对简单的模型来代替原始模型，这就是 对三维网格模型进行简化。 网格模型简化是指在尽可能保持原模型几何形状不变的前提下，采用适当的算法 减少该模型的面片数、边数和顶点数。早在2 0 世纪7 0 年代，c l a r k 1 j 学者提出了细节 层次模型l o d ( l e v e lo fd e t a i l ) ，他指的是对场景中的不同或物体的不同部分，采用 不同的细节描述方法。在绘制时，如果一个物体离视点比较远，或者这个物体比较小， 就可以用比较粗的l o d 模型绘制。反之，如果这个物体离视点比较近，或者物体比 较大，就必须用较精细的l o d 模型来绘制。同样，如果场景中有运动的物体，也可 以采用类似的方法，对处于运动速度快或处于运动中的物体，采用较粗的l o d ，而对 于静止的物体，采用较细的l o d ，充分考虑了人们对图像的视觉效果。 本文侧重于l o d 模型网格简化方法的研究。因为网格模型大部分由三角面片表 示，而且即使原始模型不是三角面片，也可以对其进行三角化，所以本文将三角网格 作为实验对象进行网格简化算法的研究。本文选题来源于国家自然科学基金项目“民 航飞行视景模拟的真实感与快速绘制研究( 6 0 7 2 1 6 9 ) ”。 1 2 国内外研究动态分析 1 2 1l o d 网格模型简化方法概述 网格模型简化的本质是：在尽可能保持原始模型特征的情况下，最大限度地减少 中国民航大学硕士学位论文 原始模型的三角形和顶点数目。它通常包括两个原则【2 】：顶点最少原则，即在给定误 差上界的情况下，使得简化模型的顶点数最少；误差最小原则，给定简化模型的顶点 个数，使得简化模型与原始模型之间的误差最小。 1 2 - 2 模型基本概念 为了下面叙述的方便，首先说明一些基本概念【3 l ： 定义1 三角形网格 空间中的一组三角形，沿公共边及在顶点处相邻接，这样的一组三角形定义为三 角形网格t m ，t m 可由顶点集v - “，屹，) 和三角形集合t 佤，五，已) 所组成 的二元组似r ) 来表示。 定义2 邻接点 对于网格中的顶点毛，与该项点同在一条边上的顶点成为顶点玉的邻接点，邻接点 组成的集合是顶点薯的邻接点集。 定义3 邻接三角形 对于网格中的任一三角形互，与该三角形有公共边或公共顶点( 至少共享一个顶点) 的三角形都是该三角形的邻接三角形，组成的集合是三角形z 的邻接三角形集。 定义4 相邻三角形 如果网格中的三角形弓与三角形互具有一条公共边，则称三角形巧，乃是相邻的， 否则是非相邻的。 定义5 三角形环 对t m 中任一三角形王，邻接三角形集合称为与三角形互相关的三角形板p ，把 三角形集合c 一层伍称为三角板只的三角形环。对t m 中任一顶点玉，所在三角形 集合称为与顶点相关的三角形板只。图1 - 1 所示。 筒毯 ( a ) 连通的三角形环( b ) 非连通的三角形环( c ) 周期的三角形环 图1 - 1 具有连通，非连通，周期三角形环的三角形板 定义6 连通和非连通区域 如果对每一对属于c 的三角形五。，五，存在三角形砭，z 孵一。属于c ，满足条 件：r e , 和气+ ，是相邻的，其中f t 1 ，2 ，肼一1 ，那么称e 是连通的，否则，称c 是非连 通的。 2 中国民航大学硕士学位论文 定义7 相邻和周期 如果存在三个三角形瓦，z ，五属于c ，满足条件：互，z 、，是相邻的，其中 ulz 1i + i 皿棚j f 一0 工2 ，那么称c ；是周期的，否则称为非周期的。图1 1 ( c ) 所示。 1 2 3 研究现状 国内外对模型简化的研究已有了一系列的成果。网格模型简化算法分类有多种， 例如根据模型简化的过程可以分为逐步求精和几何化简；根据视点相关性可以分为视 点无关的化简和视点相关的化简等等【4 1 。 在这里，我们主要介绍基于几何元素删除的网格模型简化算法和动态网格化简中 的渐进网格算法，因为后面将要介绍的我们改进得到的方法也是一种基于几何元素删 除的网格化简算法。这些方法的共同特点是以几何元素的删除实现模型的简化，即根 据原模型的几何拓扑信息，在保持一定的几何误差度量的前提下删除对模型几何特征 影响相对较小的几何“图元一：( 点，边，面) 。这些方法有很多学者在研究中。下面将 分别介绍顶点删除法、边折叠法( 顶点对的删除) 、三角形化简方法渐进网格算法等。 1 顶点删除法 1 9 9 2 年s c h r o e d e r l 5 j 提出了顶点删除的网格简化算法，此后，基于边折叠，基于三 角形删除等几何元素的删除方法相继提出。 在三角网格中，若一顶点与它相关联的周围三角面片经判定可以被认为是共面的 ( 这可以通过设定点到平面距离的阈值来判断) ，且这一点的删除不会带来拓扑结构的 改变，那么就可将这一点删除，同时所有与该顶点相连的砸均被从原始模型中删除， 然后对其邻域重新三角化，以填补由于这一点删除所带来的空洞( 如图1 2 所示) ，继续 这种操作直到三角网格中无满足上述条件的顶点为止【6 】。 图1 2 】页点删除 这种算法较快，不需要占用太多的内存，但是由于重新三角化需要将局部表面投 影到一个平面，这种算法只适用于流形，而且它在保持表面的光滑性方面存在一定困 难。随后又有算法对其进行改进，提出了更精确的误差精度，可以生成较高质量的模 型，但是需要花费更多的时间和空间。国内在这方面有高山，卢汉清【7 】的研究。 2 边折叠简化法 边折叠简化法( 图1 3 ) 是指，在每一次简化操作中以边作为被删除的基本元素， 在进行多次的选择性边折叠后，面片就可以被简化到我们想要得任何程度了。点分裂 就是边折叠的逆变换，可以用来恢复被简化掉的信息。h o p p e l 8 】通过边折叠和点分裂构 3 中国民航大学硕士学位论文 建了渐进网格( p r o g r e s s i v em e s h ，简称p m ) 模型，实现了多分辨率的层次细节模型的 实时生成。 图1 3 边折叠 边折叠的关键是折叠的次序以及边折叠后新顶点的位置。h o p p e 9 毛e1 9 9 3 年采用 了能量优化的方式来确定折叠次序和新顶点的位置，所用能量优化计算复杂，需要时 间较长，但是生成的模型效果却是所有化简方法中最好的；g a r l a n d 和h e c k b e r t 1 0 】在 1 9 9 7 年提出了一种基于二次误差测度( q u a d r i ce r r o rm e t r i c , 简称q e m ) 的化简算法， q e m 算法误差测度是基于顶点到平面距离的平方和，该算法速度快，简化生成的模型 质量仅次于h o p p e 能量优化方法，是一种有效的化简算法；h o p p e 1 1 】将法向量，颜色 以及纹理信息加入到q e m 算法中，然后采用叫做翼边的( w e d g e ) 的数据结构来加以 实现，也得到了较好的效果；l i n d s t r o m 和t u r k l l 2 】在1 9 9 8 年用化简前后的体积和面积 的变化作为误差测度，也得到了与q e m 类似的数学表达，这种方法在计算边折叠队 列和新顶点位置时只需要网格模型面的连接信息和顶点位置，所以此算法占用内存量 小，运算速度快。c o h e n 1 3 】等人采用边折叠简化结合连续映射来简化多边形网格；a n d r e g u e z i e c i l 4 j 定义了边的重要度，按照重要度从小到大的顺序来对合法的边进行删除： a l g o r r i 1 5 】贝i j 通过确定模型的特征边来进行边折叠操作；李现民【1 6 】采用改进的蝶形细分 算法来计算新顶点的位置，效果较好，但是时间复杂度较高。 3 三角形折叠简化法 在简化时三角面( 图1 4 ) 作为被删除的基本元素，是边折叠算法的延续。 图1 4 三角形折叠 h a m 锄i l7 j 首先提出三角形折叠简化方法，基本过程是将三角形的权重定义为等角 度与曲率的乘积，然后对网格模型上的所有三角形按权重进行排序，并依次折叠，这 样细长且低曲率的三角形首先被删除；t r a ns g i e n g l l8 】等人定义每个三角形权重为该 三角面的面积与曲率等因素的乘积，这种算法复杂度较高，但是它可以较好的保持外 形；i s l e r 1 9 j 等人将边折叠与三角形折叠结合起来构造了半实时多分辨率模型；周昆【3 】 4 中国民航大学硕士学位论文 将三角形折叠与q e m 算法结合起来，并给出了一种传递简化误差的方法：另外，根 据细分曲面的特性，李桂清l2 0 】等人给出了一种基于细分规则的三角形折叠算法，算法 给出了一种基于点到平面距离的有效的误差控制方法，并能在用户指定的误差范围内 通过使原始网络中的三角形折叠达到大量简化的目的；刘坚，丁友东1 2 1 j 在其基础上提 出了一种带属性的三角形网格简化方法；孙永辉【2 2 】对原算法的误差矩阵的计算进行了 改进，提出了一种简单的误差控制方法；朱春【冽计算三角形顶点到相关平均平面的距 离的最大值，结合三角形的面积、表面属性和预设特征给出三角形权值，确定折叠次 序，并能够用累进网格实现连续的层次细节模型。 4 渐进网格法 h o p p e 8 j 于1 9 9 6 年提出，其原理是对一个原始网格模型，如果将每次执行的折叠 操作用一种类记录下来，当化简完毕后即得到一个折叠操作序列，详细记录了有关折 叠操作的信息，这样，以后便可以得到原始网格模型到最简模型之间任意几何层次的 网格模型。p m 可以在实时绘制时，通过逆向跟踪简化信息序列，对每条简化信息执 行点分裂逆操作，逐步恢复所删除的模型细节，实时得到原始模型的连续精度的简化 模型，实现了l o d 模型的平滑过渡。p m 很大程度上克服了以往模型的平滑过渡方面 的不足，可以支持不同细节的网格模型的实时生成。但是缺乏有力的数据结构的支持。 渐进网格算法同样可以应用到三角形折叠算法中，类似于边折叠时累进网格的构 造。该算法1 4 】是以三角形折叠操作为基础，和基于边折叠的渐进网格的构造方法类似， 都是将折叠操作记录下来，以便于控制网格几何层次的跳转。周扬等j 实现了该过程， 详细过程如下：如图1 5 ，对三角形z 进行折叠操作，将变化的顶点，三角形记录下来， 存储在类死6 比中，从原始网格模型m ，每执行一次三角形折叠操作，就把网格变化的 部分( 顶点，三角形，顶点三角形之间的关联) 更新，同时记录在类t a b l e 中，如此 反复操作，直到将原始网格模型m 化简到最简网格模型m 。，得到类死6 跆的序列，这 个序列便可以用到恢复和化简网格。 渐进网格算法是一种动态化简方法，在本文中借鉴渐进网格的动态显示网格的优 点，主要将渐进网格应用于存储和显示多分辨率的层次网格。陶志良1 2 5 j 针对p m 的二 义性，提出了支持快速恢复的可逆地进网格；费广正【冽则利用渐进网格进行多层次模 型编辑；卢章平1 2 7 】在分析已有渐进网格生成算法的基础上，提出一种基于“边折叠”网 格化简方法的累进网格生成算法，构造了累进网格的表示新方法。算法消除了累进网 格技术中的二义性，具有支持多种网格类型、保持相邻层次细节模型间的平滑过渡等 特点。 5 中国民航大学硕士学位论文 图1 - 5 三角形折叠操作，( h ， ，2 ，v 3 ) 捌2 v _ 1 3 本文主要工作及内容组织 本文将重点介绍各种误差度量在不同模型简化算法中起到的作用、应用的范围和 效果。在此基础上详细介绍改进后的新算法、论证改进算法的实用性以及将改进算法 应用到不同的模型简化算法中。首先，在众多学者前辈的误差度量理论基础上，经过 大量的实验，对实验结果进行分析，证明了哪种误差度量适合特定哪几种模型简化算 法，从而为论证改进算法的成立提供了实验基础。然后，我们对误差度量做了改进， 同样进行了大量的实验工作之后，取得了一些有意义的、创新性的成果。最后，我们 将这种误差度量引入到另一种模型简化方法中，证明该误差度量也是适用的。 本文内容组织如下： 第二章对典型网格简化算法中用到的误差度量方法通过实验比较分析实验结果， 为以后的研究做好铺垫。 第三章针对三角形折叠算法的合适的误差度量方法的选取及新顶点的选择进行研 究，基于实验分析得到了两种新的三角形折叠算法，并给出了实验结果证明改进算法 的优点以及适用模型的类型。 第四章描述了所设计的、支撑本文研究工作的实验平台，包括平台的具体实现过 程和结构。 最后第五章总结本文得出的结论，提出进一步的研究内容。 6 中国民航大学硕士学位论文 2 1 引言 第2 章典型误差度量方法比较研究 误差度量准则可以对确定合理的简化顺序，控制模型简化过程的进行，使得简化 过程有理论的依据，预测简化结果的质量；也可以在给定屏幕误差下确定使用何种分 辨率的网格模型；还可以保持场景中图形质量和绘制速度的平衡，确定误差范围与三 角形数目的对应关系。因此，一个有效的模型简化方法离不开一个正确误差度量准则 的选择。 通常，几乎所有的模型简化应用领域中，人们采用基于几何形状的误差度量来评 价模型简化方法的优劣，其中主要有三种典型的度量方法一距离度量、曲率度量、 特征角度量。 为了得到各种误差度量的作用，我们进行了大量的实验。实验中所用的模型文件 选取自斯坦福大学测试网格化简算法的标准模型库。各种误差度量都是针对网格简化 算法中的基本操作三角形折叠，用来代替被折叠三角形的新顶点都选取为中心， 利用渐进网格来实现l o d 不同分辨率之间的平滑过渡。本文中的所有实验测试都是 在p c 机上用c + + 语言实现测得的。在实现方法时，由于要处理的网格含有大量的三 角形，我们设计了比较合理的数据结构，使得算法能处理数据量大的模型，而且处理 时间不会太慢。详细的实现细节将在第五章中介绍。实验相关数据及分析将在下面详 细介绍。需要说明的是，本文中所有的实验结果中之所以会出现空洞一样的现象不是 说明了三角形折叠法会产生空洞，而是因为在模型化简中有些新形成的三角形法向量 反向变化了，所以在实验结果中显示不出来。 误差度量方法主要比较方法的化简率和方法适用模型大小。兔子和龙模型的数据 量( 三角形数目) 在6 万至2 0 万个之间，模型表面细节丰富，具有代表性，因此统一选 取兔子和龙模型进行实验数据统计。 2 2 距离误差度量 2 2 。1 定义 在高度场数据中，一个点( x ，y ) 的距离误差度量可定义为式2 1 1 4 1 ： i h ( x ，y ) 一筇) ，) ，) l ( 2 1 ) 其中h ( z ，y ) 为原模型中( x ，y ) 点处的高度值，o s ) o ，y ) 为近似模型中( x ，y ) 点处 的高度值。这种误差度量局部误差小，所产生的近似模型的质量越高。此种方法简单 快速，且只用到局部信息，得到了广泛的应用。 7 中国民航大学碰学位论文 例如在s c m o c d e r 5 】的顶点删除算法中，使用顶点到平均平面的距离作为局部误差 度量方法；周昆1 3 j 的三角形折叠法中采用折叠后新顶点到邻接三角平面的距离作为误 差度量方法。 2 2 上计算方法 目前最有效的距离误差度量为周昆的算法。他对原始网格中的每个三角形z ，通 过求与其三个顶点相关的三角形集合的并集得到与该三角形相关的三角形集合c 。误 差标准选用在对该三角形执行折叠操作后得到的新点- 【而。见。铂1 r 到该三 角形集合中每个三角形所在平面的距离的最大值，这个距离越小越好。 2 2 3 实验结果与分析 实验测试周昆算法唧中距离误差度量。该算法的模型曲面边界保持得很好。模型 简化率可以达到8 8 ，当简化率达到9 9 时简化模型还可以保持大致轮廓。 下面对结果进行统计分析。图2 - 1 ，2 - 2 是对兔子和龙模型的化简效果图。对兔子 模型来说，细节保持可以达到9 5 ，兔子的嘴巴和眼睛还依稀可见；龙模型的简化率 可以达到9 7 ，龙角、龙眼、龙爪等细节部分仍然保留着。当兔子模型简化率为9 8 9 4 时，简化模型的轮廓与原始模型差不多；龙模型简化率最大到9 9 1 4 时，依然可以保 持轮廓。简化模型的化简过程中出现了少许的三角形空洞( 三角形法向量反向) 。 圈圈圈 原始模型 ( 6 9 4 5 1 个三角形) 简化模型1 c ，4 1 个三角形，简化s o ) 简化模型2 f 1 3 9 9 8 个三角形简化8 0 铆 囝圈囝 简化模型4简化模型5简化模型6 ( 3 4 7 8 个三角形) ( 1 1 1 6 个三角形) ( 7 3 6 个三角形) ( 简化9 5 )( 简化9 8 )( 简化9 8 9 4 ) 图2 - 1 误差度量为距离对兔子模型的简化 由此可知，模型数据量越大，可达到的犀大简化率也会越高。距离误差度量适合 大规模的网格模型化简，也适合三角形折叠方法。同时每个简化模型的边缘保持平滑。 周昆的算法中距离误差度量简单易行、快速、简化率极高。 中目民航大学硕学位论立 简化模型4 ( 3 7 1 9 个三角形简化9 8 1 简化模型5 f 1 7 3 8 个三角形简化9 91 4 1 简化模型6 ( 6 0 8 个三角形，简化9 96 9 9 8 幽2 - 2 误差度艟为距离对龙模型的简化 2 3 曲率误差度量 2 3 1 定义 曲率误差度量【吲，由h a m m a n l l 7 1 首先使用。它将三角形误差度量定义为网格模型 中国民航大学硕士学位论文 中三角形的离散曲率，通过三角形曲率的大小来判断三角形近似曲面是否可以折叠。 这种方法可以反映曲面的弯曲程度，也就是说模型简化先折叠平坦部分( 曲率小的部 分) ，尽可能保留弯曲部分( 曲率大的部分) 。 2 3 2 计算方法 曲率误差度量方法的详细计算过程【1 7 l 如下： 网格中每个顶点曲率计算是按照高斯近似方法【2 8 2 9 删求解得到。设网格中任一顶 点x 。，顶点坐标为“，y i ，刁) ，求解其曲率的具体算法如下： 步骤i 计算顶点x ；确定的三角形板的平均平面p 的平面方程； 找到顶点x ；周围的所有三角形，分别计算周围三角形的法向量n 。，利用式2 2 得 到平面p 的法向量，结合顶点置坐标“，y i ，乙) ，建立平面p 平面方程如式2 3 所示： 肌确 ( 2 2 ) 俾一k ) = 唿0 一再) + 一咒) + 吃g 一弓) ( 2 3 ) 步骤2 分别求出该顶点x ；周围其他邻接点x ，o ，y ，z ，) 到p 的有向距离d ，； 血：+ 两；+ 1 2 ：+ d 哆。 蘑嚣。如+ 锄+ q 柏 ( 2 4 ) 步骤3 按照式2 5 选择一个垂直于的向量ao 口2 ( 一o y + 力：) ，k ，力j ) r 肛j ，刀j 乒0 ( 刀，一以+ ) ，刀y ) r 厶，n y 乒0 ( 刀z n z - ( n x + n , ) ) t n ：，以：乒0 ( 2 5 ) 步骤4 计算平面p 上的两个正交向量以和b z5 在平面p 上建立局部坐标系，该局部坐标系的原点是x ，u 轴和y 轴是正交单位 向量以和屯。如式2 6 所示： 卜南 仁6 ， l 乞= nx b , 步骤5 求出顶点x ，所有邻接点x o ，y ，z ，) 在平面p 上的投影点x 0 ； 顶点x ；与在平面p 上的投影点x 0 之间的差为咖，= x j - x f ，向量咖，在正交单位 向量以和也上的投影即为投影点x 0 的局部坐标“，v j ，如式2 7 所示： x o t x j - d j ( 2 7 ) 1 0 中国民航大学硕士学位论文 厂d v j b h - ( 2 8 ) 1 v 。叱屯 卜田， 步骤6 求解顶点x 。的曲率限制函数； f ( u ，v ) - ( c 2 d “2 + 2 c l l 口l ，+ c 0 2 1 ，2 ) 2 ，并表示成矩阵形式，得到矛盾矩阵方程如公式2 9 黪2 u l v l 澍 l c 2 0 l 叫 ， 合高斯约当消去法原理求解转换后的正规矩阵方程，求得系数矩阵c ( c ，c m c ) 。 c 仞= c 形) ( 2 1 1 ) d j 图2 3 顶点曲率求解过程的几何形式 2 3 3 实验结果与分析 实验单独测试h a m m a n l l 7 1 算法中所用到曲率误差度量。模型化简时，对于简单模 型猫都会简化失真，复杂模型更会失真。简化过程首先折叠曲率小的部分，如猫的背 部。但是如图2 4 模型不是均匀化简，只化简猫身而猫脸没有化简，这样简化模型会 失真。 中国民航大学砸士学位论文 囵图图 原始模型 ( c 5 6 - i 个三角形1 简化模型1 ( 5 5 3 个三角形1 c 简化1 7 ) 简化模型2 ( 4 2 9 个三角形1 ( 简化3 7 ) 图2 4 误差度量为曲率对猫模型的简化 曲率误差度量计算过程复杂，所用时间多，同时实验效果没有距离和面积误差度 量效果好，简化率低。因此这种度量方法已经不适用于现在大规模的网格模型数据的 化简。但是就其原理来看，它可以作为一个影响视觉因素同其他的误差度量方法组合。 2 4 特征角度量 2 4 1 定义 特征角为顶点处任意两个相邻三角形的法向量之间的夹角中的最大者。例如 h a m a u n 1 1 采用角度作为三角形权重的一个影响方面，并指导着三角形折叠之后形成的 空洞的三角化。 2 4 2 计算方法 这里用于比较的是h a m a n n 州提出算法中的三角形角度权重。单独列出进行详细 的三角形误差度量计算。 本文总结任一三角形r 三个顶点是x ，x 。，x j 的内角口i ，口2 ，口3 为； 一- 帅州管筹嚣冀挣 苟 吒一怪量罱爿， 岛一一柽荆， 则三角形角度权重为： a ( t ) - 2 ( ( 3c o s “) ) 一1 ) i 1 其中儡是三角形r 的一个内角。 ( 2 1 4 ) ( 2 1 5 ) 中目民航大学碗学位论女 2 4 3 实验结果与分析 实验单独测试h 彻a 【1 1 算法中所用到角度误差度量。如图2 - 5 模型不是均匀化简 的猫脸没有化简。并且如果一个三角形的角度余弦值小，在进行该三角形折叠后影 响到的局部区域的三角形角度会变小，这样循环下去会对一个局部区域进行三角形折 叠，模型化简效果会很差，简化率极低。因此简单模型如猫不能很好的简化，复杂模 型也会简化失真。 图囵 2 5 典型误差度量方法耗时分析 由于实验中用到的网格简化算法基本操作相同，不同的是算法中使用不同的误差 度量方法。因此这里的各种算法之间的时问区别是由误差度量的计算复杂度引起的。 一龟一 jl i i l 中国民航大学硕学位论文 三种不同的局部误差度量中，特征角误差度量方法最容易，距离误差度量方法次 之，曲率度量最复杂，表21 实验耗时数据也说明了这点。 表21 进行一次折叠运行时问对比 距离度量 曲率度量特征角度量 所用时间( s )所用时问( s 1 所用时间( s ) 02 0 6 7 9 2 6 已提出的不同误差度量方法的组合 2 6 1 三角形曲率与等角度余弦乘积 h a m a n n 1 7 1 首先应用到三角形删除算法中。从原理上考虑，误差度量计算、半平面 测试和三角剖分都计算复杂，耗时长。虽然模型简化效果好，但是所耗时间长，不能 满足凹面镂空模型和平滑的连续分辨率模型过渡，只针对凸面模型化简。 三角形的重要度计算式21 6 为： 矽盯) - c 仃) 一口)( 2 1 6 ) 其中缈叮) 为三角形的重要度，c 仃) 为三角形的曲率重要度，爿口) 为三角形的特 征角重要度。 按照参考文献1 1 1 所述误差度量方法，将该方法应用到三角形折叠算法中。经过实 验得到效果图2 7 。模型化简不均匀，陷入局部化简中，简化模型严重失真。这里再 次证明了特征角度不适用于三角形折叠算法。选种误差度量只被用在三角形删除算法 中。 困图 简化模型1简化模型2 ( 4 8 5 个三角形茼化2 8 )( 3 9 2 个三角形，简化4 2 ) 图2 1 7 误差度量为曲率和等角度乘积对猫模型的简化 2 6 2 三角形曲率与三角形面积乘积 t r a ns g i e n g b s l 等人首先应用到三角形折叠算法中。算法化简过程中体现了三角 中国民航大学砸学位论文 形折叠算法的优点不需要对将要删除的三角形进行半平面测试的判断、不会形成空洞， 因此也不需要对空洞进行三角剖分。 三角形的重要度计算式2 1 7 为： 口) - c ( r ) s ( r ) ( 2x t ) 其中w ( r ) 为三角形的重要度，c 叮) 为三角形的曲率重要度，s 口) 是三角形r 的 面积。 同样按照参考文献所述算法，经过实验得到效果圈2 - 8 。模型化简率不高、计 算复杂、耗用时间长，也不能满足平滑的连续分辨率模型过渡。 图图 简化模型1简化模型2 ( 5 4 0 个三角形，简化2 0 ) ( 4 5 4 个三角形，简化2 7 ) 圈2 误差度量为曲宰和面积乘积对猫模型的简化 2 6 3 其他可能的误差度量组合 本章介绍了三种常用的误差度量方法，如果两两组合，有三种方法：距离与曲率， 距离与特征角，曲率与特征角( 已有人提出) 。针对前两种组合方式，经过大量实验验 证，模型化简效果和速度都比距离误差度量差。本文中只说明误差度量组合的可能， 不再详细说明效果差的实验结果。 2 7 本章小结 本章介绍了常用的各种网格简化算法中的误差度量方法，通过实验测试得到了使 用不同度量方法的效果，分析之后总结出了度量方法的优缺点，为以后的算法改进提 供了依据。 中国民航大学硕士学位论文 第3 章改进的基于三角形折叠网格简化算法 针对不同对象l o d 网格模型连续简化方法包括三个方面：一是选择适当的误差 度量计算方法；二是选择合适的化简过程；三是选择一个适合的显示和存储数据结构。 从以上三个方面考虑来简化模型，得到两种改进的可以适用于三角形折叠网格简化算 法的误差度量方法。 3 1 算法设计思想 在几何元素删除算法中三角形折叠简化方法一次三角形折叠元操作可以减去上一 个层次模型中的三个三角形，效率比边折叠和顶点删除高，因此选用三角形折叠作为 元操作。在三角形删除算法中( 第1 章介绍) ，需要判断将要删除的三角形是否符合半 平面测试，即删除这个三角形后受影响的网格部分依然可以三角化。这样删除三角形 之后会形成的空洞，对空洞进行三角剖分。从原理上考虑，误差度量计算、半平面测 试和三角剖分都计算复杂，耗时长。虽然模型简化效果好，但是所耗时间长。不能满 足凹面模型简化和平滑的连续分辨率模型过渡。设想若能减少计算量，算法的效率将 大大提高，同时或许可以满足连续多分辨率网格模型的显示。 三角形折叠算法( 如图1 4 ) 中，改进了三角形删除算法中形成的空洞的三角剖分方 面。三角形折叠算法中将被删去的三角形缩小成一个点，这样就避免了空洞的产生和 三角剖分的大计算量，因此，三角形折叠算法比三角形删除算法效率高。经过后来学 者的改进，在误差度量方面有很大的提高。在三角形折叠操作主要有两个问题，一个 是该三角形折叠操作的代价是多少，即该操作带来的误差是多少，另一个问题是如何 选择新顶点来代替被折叠的三角形，使得折叠操作的误差尽可能小。 三角形删除和三角形折叠算法都是一种静态的折叠算法，无法实现实时的绘制图 像，也不能在多分辨率层次间进行转换。因此引入动态化简算法_ 渐进网格算法。 算法中用到的数据结构有网格类( 包括三角形类和顶点类) 、折叠类，详细说明参 看4 2 节。 3 1 1 基于三角形折叠的网格简化算法描述 步骤1 读入原始网格； 步骤2 对原始网格中的每个三角形z 计算其重要度，即误差度量值； 步骤3 对原始网格中的每个三角形正计算其折叠后生成的新顶点的位置y 。，； 步骤4 按重要度从d , n 大排列三角形； 步骤5 从三角形序列中取出重要度最小的三角形执行折叠操作，更新网格类和 更新受影响的局部三角形序列，存储本次折叠操作的相关信息而构成渐 1 6 中国民航大学硕士学位论文 进网格( 参看3 1 2 节) 。 步骤6 若三角形序列为空或误差己达到用户要求，则转步骤7 ；否则，转步骤5 ； 步骤7 结束。 3 1 2 渐进网格构成的算法描述 用渐进网格来存储和显示网格模型可以达到平滑连续分辨率的显示效果。算法描 述如下： 步骤1 将本次折叠操作中被折叠的三角形索引号，构成被折叠三角形顶点索引 号存储于网格类中的三角形类中； 步骤2 将代替被折叠三角形的新顶点存储于网格类中的顶点类中，其中包括新 顶点的索引号，新顶点的坐标值； 步骤3 更新本层渐进网格所显示的网格信息，其中包括本次折叠操作被折叠的 三角形和被改变的三角形； 步骤4 若本次折叠操作所涉及到的网格信息已经存储和更新完毕，则转步骤5 ； 否则，转步骤1 ； 步骤5 结束。 3 2 选择合适的误差度量 选择合适的误差度量对于模型简化有着非常重要的意义。下面针对各种新的误差 度量进行大量实验，验证各种误差度量效果，以求找到有效的误差度量方法。 3 2 1 基于三角形面积 本文单独将三角形面积作为误差度量。我们定义面积误差度量为网格模型中三角 形的重要度为本身的面积，它也可以影响人的视觉感觉。如果一个三角面片的面积小， 则表明折叠这个三角形也不会对原模型产生很大的误差，这样使得折叠误差最小。 任一三角形r 三角形的三个顶点是x ，x ：，x ，三角形正的面积误差度量为 1 。 仃) s f f ) t 刊( x l x ：) 3 一x 2 ) 0 ( 3 1 ) 二 其中形仃) 为三角形的误差度量，s f f ) 为三角形的面积。计算过程为矩阵计算。 实验测试面积误差度量。该算法的模型曲面边界保持得很好。模型简化率可以达 到9 5 ，当简化率达到9 9 时简化模型还可以保持大致轮廓。 下面对结果进行统计分析。简化模型的边缘平滑，细节保持可以达到9 5