（计算机应用技术专业论文）三维图形多分辨率模型技术的研究.pdf

一一 塑垩 一 一 一一 摘要 在计算机图形学和几何造型中，物体经常用三维图形来表示。三维图形作为 信息的载体有其突出的优点，但在实际应用中，也存在着严重的传输瓶颈。考虑 到三维图形多分辨率模型在图形简化、多细节层次技术等方面的优良性能和对渐 进传输的潜在支持，本文对三维图形的多分辨率模型进行了深入的研究。 本文研究了两种基本的三维图形多分辨率模型，即基于小波的多分辨率模型 和基于累进网格的多分辨率模型，并对两种多分辨率模型进行仿真实现。在基于 小波的多分辨率模型方面，本文对任意网格的小波多分辨率分析进行研究和仿真， 实现了准均匀b 样条方法对三维图形的多分辨率表示。在基于累进网格的多分辨 率模型方面，本文对两种网格简化算法进行了改迸。一种是对法向边收缩算法进 行改进，一种是对三角形折叠算法进行改进，并通过一组实例来对这两种改进算 法的性能迸行了分析和对比。最后，研究了带属性的网格简化算法，把颜色、纹 理等属性考虑进去，对三维图形进行简化，得到多细节层次模型序列。 随着互联网的普及和发展，三维图形在网络中的传输将越来越流行。但由于 i n t e m e t 带宽通常总是落后于应用需求，因此利用三维图形的多分辨率模型对三维 图形进行高效的压缩和渐进传输可以有效她缓解目前由于网络带宽不足所导致的 佳输瓶颈。 关键词：三维图形多分辨率模型细节层次细分4 、波累进网格网格简化 一一 垒! ! ! 竺! ，_ _ _ _ h _ _ - _ _ _ j _ _ - _ _ 一一一一 a b s t r a c t i nc o m p u t e rg r a p h i c sa n dg e o m e t r ym o d e l ，o b j e c t sa r eo f t e nr e p r e s e n t e db y3 d g r a p h i c s t h o u g h3 dg r a p h i c sh a sm a n yo u t s t a n d i n gp r o p e r t i e s a sac o m m u n i c a t i o n m e d i a ，i ts u f f e r ss e r i o u st r a n s m i s s i o nb o t t l e n e c ki np r a c t i c a la p p l i c a t i o n r e g a r d i n g t h es u c c e s so f3 dm u t i r e s o l u t i o nm o d e l si nm e s h s i m p l i f i c a t i o n ，l o d t e c h n o l o g ya n dt h ep o t e n t i a ls u p p o r tf o rp r o g r e s s i v et r a n s m i s s i o n ，i nt h i sd i s s e r t a t i o n ， w es t u d i e dm u t i r e s o l u t i o nm o d e lo f 3 d g r a p h i c s f i r s t l y , w es t u d i e dt w ok i n d so fb a s i cc o n s t r u c t i o n so f 3 dm u l t i r e s o l u t i o nm o d e l s b a s e do ns u b d i v i s i o nw a v e l e ta n dp r o g r e s s i v em e s hr e s p e c t i v e l y a n dw eg e n e r a t e d m u l t i r e s o l u t i o nm o d e l sf o rt w om e t h o d s h at h e p r o c e s s o f i m p l e m e n t i n g m u l t i r e s o l u t i o nm o d e l sb a s e do ns u b d i v i s i o nw a v e l e t ，w ei m p l e m e n t e da n ds t u d i e d m u l t i r e s o l u t i o n a n a l y z e o f a r b i t r a t ym e s h ，a n di m p l e m e n t e d 3 d g r a p h i c s m u l t i r e s o l u t i o nr e p r e s e n t a t i o n su s i n gq u a s i u n i f o i t nb - s p l i n es u r f a c e s i nt h ep r o c e s s o f i m p l e m e n t i n gm u l t i r e s o l u t i o nm o d e l sb a s e d o n p r o g r e s s i v em e s h ，w ei m p r o v e dt w o k i n d so fm e s hs i m p l i f i c a t i o na l g o r i t h m s ，o n ei si m p r o v e de d g e sc o n t r a c t e db a s e do n n o r m a l s ，t h eo t h e ro n ei si m p r o v e dt r i a n g l ec o l l a p s e da l g o r i t h m w ec o m p a r e dt h e p e r f o r m a n c eo f t h e s ei m p r o v e d a l g o r i t h m sb yr e p r e s e n t i n gs o m ee x a m p l e s f i n a l l y ，w e s t u d i e dt h em e s hs i m p l i f i c a t i o na l g o r i t h mw i t ha d d i t i o n a lp r o p e r t i e s w eg e n e r a t e d l o dm o d e l s b ys i m p l i f y i n gm o d e l s i nt h ec a s eo fc o l o r sa n dt e x t m - ea r e t h o u g h t w i t ht h ep o p u l a ra n d d e v e l o p m e n to fi n t e r n e t t h et r a n s m i s s i o no f 3 d g r a p h i c si n t h ei n t e r n e tw i l lb em o r ep o p u l a r b u tt h eb a n d w i d t ho fi n t e r n e ts e e m sc a r ln e v e r s a r i s f y t h ed e m a n do f a p p l i c a t i o n s ，w e b e l i e v et h ee f f i c i e n t c o m p r e s s i o n a n d p m g r e s s i v e t r a n s m i s s i o nb a s e do nm u l t i r e s o l u t i o nm o d e l so f3 d g r a p h i c s c a n e f f i c i e n t l yr e l a xt h et r a n s m i s s i o nb o t t l e n e c ko f c u r r e n ti n t e m e t k e y w o r d s ： 3 d g r a p h i c s m u l t i r e s o l u t i o nm o d e ll e v e lo fd e t a i l s s u b d i v i s i o nw a v e l e t p r o g r e s s i v em e s h m e s h s i m p l i f y 声明 独创性( 或创新 生) 声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得 的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论 文中不包含其它人已发表或撰写过的研究成果；也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志为本研究 所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 丘蛀苯壹兽 日期： 兰! ! ；! b ! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位论文期间论文工作的知识产权单位属西安电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大 学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文 的全部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密 的论文在解密后遵守此规定) 。 - 本学位论文属于保密，在年解密后适用本授权书。 本人签名：圣4 ：垂董全 导师签名：塞丑咝 日期：璺堕! f ： 日期：壁垒主! ! ： 第一章绪论 ! 三维图形多分辨率模型技术的研究 第一章绪论 随着计算机技术的飞速发展，计算枫图形学取得了巨大的进展，其已经进入 了三维真实感图形时代，在电视广播、网络、多媒体等社会各领域发挥了重要的 作用。为了模拟出具有真实感的三维图形，越来越多的人投入到三维图形的多分 辨率模型技术的研究中，并取得了一些成果，目前已有部分技术应用于计算机动 画、医学以及运动学等领域中，创造了一定的社会效益和经济效益。 1 1 多分辨率模型技术历史与现状 在计算机动画、科学可视化和虚拟现实等交互式计算机图形学的应用中，物 体的几何模型常采用三角形网格表示，以便图形硬件能直接处理。随着物体模型 复杂性的增加，表示物体之所需多边形数目远超过图形硬件以交互帧更新率进行 绘制的能力。由三维模型重构方法得到的三角形网格模型通常由上万个、几十万 仓甚至几百万个三角形片组成，为满足计算机分析、显示与存储的要求，一个自 然的解决方法是在不严重损失物体视觉特征的前提下，对物体的网格模型进行简 化，用较少数目的三角形片来表示物体。物体模型的不同简化版本构成物体的细 节层次( l e v e l so fd e t a i l ，简称l o d 模型) 或多分辨率表示。 多分辨率模型是指物体模型的多个细节层次网格表示形式，相当于该物体模 型的多个不同分辨率模型的集合。多分辨率模型又可分为离散多分辨率模型和连 续多分辨率模型。 对复杂网格进行简化，得到不同细节层次的多个三角网格模型，称之为离散 多分辨率模型。连续多分辨率模型则是种紧凑的模型表示方法，可生成任意多 个不同分辨率的模型。基于这两种不同模型，面向多分辨率模型的压缩又可分为 面向离散多分辨率模型的压缩和面向连续多分辨率模型的压缩。本文所讨论的主 要是连续多分辨率模型。 多分辨率模型技术的产生可以追溯到1 9 7 6 年，c l a r k 1 1 认为当物体覆盖屏幕 较小区域时，可以使用该物体描述较租的模型，并给出了一个用于可见面判断算 法的几何层次模型，以便对复杂场景进行快速复制。在1 9 8 2 年，r u b i n 【2 】结合光 线跟踪算法，提出了复杂场景的层次表示算法及相关的绘制算法，从而侵计算机 能以较少的时间绘制复杂场景。c r o w 3 悃个实例说明了同一物体采用不同的c o d 模型质具有的优点。 !三丝堕堡垒坌鳖奎竖型垫查塑婴至一一 9 0 年代初，图形学方向上派生出虚拟现实和科学计算可视化等新研究领域a 虚拟现实和交互式可视化等交互式图形应用系统要求图形生成速度达刘实时，而 计算机所提供的计算能力往往不能满足复杂三维场景的实时绘制需要，因而研究 人员提出多种图形生成加速方法【4 】，l , o d 模型则是其中一种主要的方法。这几年在 全世界范围内形成了对多l o d 自动生成技术的研究热潮，并且取得了很多有意义 的研究结果。 1 9 9 1 年，d e h a e m e r 鄙利用自适应递归方法，提出了基于规则四边形网格表示 物体的简化多边形网格的方法：在1 9 9 2 年，s c h r o e d e r 【6 】提出了基于顶点移去的 网格简化算法。g r e g 给出了基于网格重新划分的多边形网格模型简化方法。1 9 9 3 年，h o p p e 8 瞧出了一种整体网格优化方法，它包括网格匹配过程和网格简化过程。 r o s s i g n a c 9 】使用多分辨率近似法自动生成物体的简化模型，该方法并不保持原有 模型的拓扑结构；1 9 9 4 年，h a m a n n 1 0 】给出了一种基于三角形移去的模型简化方法。 9 9 5 年，h e 【1 1 】使用信号处理方法来消除模型的高频细节，从而得到简化模型。 e c k 1 2 1 利用小波变换把多面体模型表示为多分辨率形式，由此可生成一系列连续 的多】，0 d 模型。1 9 9 6 年，c o h e n 1 3 帔用内外两个包络网格来控制简化过程，该方 法可保持模型的拓扑结构。k a l v i n 1 4 l 利用面片合并的方法来自动生成物体的简化 模型。h o p p e i ”】基于网格优化方法，提出了累进网格的概念以及生成方法，该方 法搜索平面区域和特征边，使用边收缩操作来完成简化功能。l i n d s t r o m 15 】对规 则网格表示的地形模型提出了种实时连续l o d 绘制方法，在三维地形仿真中得 到成功应用。r o n f a r d i ”1 针对非常复杂的场景使用区域合并操作来进行模型简 化，该方法根据与原始形状的几何偏差度量进行边合并。g u e z e i c i 弓) 提出了一种 误差可控的模型简化方法，边折叠操作与r o n f a r d 所用的边折叠方法类似，而误 差控制方法则与c o h e n 所用的方法类似。x i 9 1 提出了一种动态的、与视点相关 的多边形网格模型简化方法。a g n r i t 2 0 1 使用一聚类过程来确保简化操作仅在某些 区域道行，聚类是通过查找特征边和平面区域来完成的。 在1 9 9 7 年，h o p p e i 2 1 对累进网格进行扩展，形成对任何网格都适用的且与视 点有关的累进网格。g a r l a n d 2 2 1 使用二次误差度量束控制表面网格的简化，该方 法可快速产生两质量的近似模型。 跟随国际上的发展，国内近几年也开展了一些卓有成效的研究工作。潘志庚 捉j 上；了种基于三角形移去准则的多面体模型简化方法【2 3 1 ，与f i a m a n n 10 】的方法比 较，该方法具有删减程度高并且计算量少两个优点；周晓云提出了种基于特征 角准则的多面体简化方法【2 4 1 ，算法适用于对网格进行少量的删减；陈礼民提出了 一种基于快速形成近平面的简化算法驯。算法具有保细节、保真和快速等优点： 陶志良对基于重新划分的网格简化算法进行改进【2 6 1 ，简化了分稚点的操作。 由于三维图形的复杂性，与从事其他领域研究的人数相比，国内外做这方面 第一章绪论 研究工作的人还是比较少，而且人们对它也不断提出更高的要求。如：表面属性( 如 颜色，纹理等) 的统一处理、多分辨率模型的管理、模型近似误差度量标准。这一 切都需要大量研究人员的介入，随着研究的深入，该领域会取得更多的成果。 1 2 多分辨率模型技术应用前景 多分辨率模型技术在计算机图形学和多媒体方面具有广泛的应用领域，如三 维动画设计、虚拟现实技术、体育运动模拟与分析、医学诊断等等。 三维动画设计 计算机三维动画技术最初是应影视业发展的要求产生的，其实质就是：在场 景中随时间变化，使用平移、旋转等变换改变整个物体或物体的某个部位的位置。 一般情况下，物体主要是指人和其他动物。近几年来，由于科学技术的不断进步， 计算机动画已成为综合运用计算机图形学、物理学、美学等学科或领域的一种高 新技术，已经越来越成功的运忍到科学研究、广告及影视制作中。在计算机动画 设计中，如何运用多分辨率模型技术逼真快速地绘制三维物体场景正在变成当前 的个热点研究课题。 二虚拟现实 虚拟现实最近几年来得到了迅速的发展，它是指用立体艮睛或传感手套等一 系列传感糖助设旌来实现的一种三维现实，人们通过这些设施以自然的技能向计 算机送入各；f 中动作信息，使人们获得三维的视觉，听觉及触觉等感觉的世界，随 着动作信息的不同，感觉也随之改变。 随着虚拟现实中的实时漫游以及科学可视化中各种实时动态显示的普遍出 现，数据的形式越来越多样，数据量也越来越大，从而导致了三维物体的复杂度 已超出了般图形硬件的实时绘制能力，而多细节层次技术可以在不影响生成图 像质量的前提下以不同的细节程度来表达同一个三维物体模型，达到满足实时显 示的目的。 三体育运动模拟与分析 运动分析就是从图像序列或视频中获取人体的运动信息，并对它进行分析、 识别等工作。体育运动中经常用运动分析运动员各种技术动作以及技术动作与外 界条件之间的关系，特别是在现代竞技体育中，各国都在研究如何运用科学原理 来提高运动员的成绩。 随着我国体育事业的蓬勃发展，运动员训练方法的科学化、规范化已成为当 务之急。为了满足教练员、运动员、科研人员进行形态分析及定量运动生物力学 分析的需要，可以利用计算机，将三维人体的运动模拟技术与运动生物力学分析 三维图形多分辨率模型技术的研究 方法相结合之后，开发出相应的运动训练模拟分析系统，从而为教练员的训练方 法改迸、体育院所的科研和教学工作提供一种有力的工具，发挥作为先进科技应 用系统的作用。 四医学诊断 医学诊断所面对的问题是：如何获得高质量的人体医学图像及处理这些图像， 从而提取出有效的科学数据以便对人体骨骼、肌肉和内脏等进行研究。而采用多 细节层次技术就可以让医生在计算机上看到病人的三维器官模型，包括骨骼、肌 肉和经络等，除了供观察之外，还可以用它来模拟一些物理过程并对病变部位进 行分析。 在医学上，医生的培训是一项投资大、周期长的工作，因为不能随意让实习 医生上手术台。多分辨率模型技术可以给出人体有用的解剖学数据，既缩短了实 习医生培训周期，又节约了人力、物力和财力。 当然，多分辨率模型技术应用并不局限于以上几个方面，还可以应用于军事 侦察、地形勘测，以及服装设计等领域。由此可见该技术具有巨大的发展潜力和 应用价值，当然这还需要广大的研究学者的加入和大量的研究经费的支持。 1 3 本文的主要内容 多分辨率模型技术的发展离不开计算机图形学的理论基础支持。在图形学领 域，图形学的建模思想、坐标变换、三维观察、光照以及消隐等技术直接影响并 作用于多分辨率模型技术的分析和解决过程中。前人在这个领域所做的研究和实 验，得出的理论和经验，都为本文研究提供了很大的帮助。 本文在研究多分辨率模型技术时，分别从多分辨率模型理论分析、研究和实 现三个方面进行了研究。概括起来，主要有以下几个方面的工作： l 研究了两种典型的三维图形多分辨率模型，即基于细分小波的多分辨率模 型和基于累进网格的多分辨率模型； 2 实现了基于任意网格的细分小波的多分辨率模型，并采用准均匀b 样条方法 对三维图形进行多分辨率表示； 3 实现了基于累进网格的多分辨率模型，并对实现基于累进网格的多分辨率 模型的两种模型简化算法进行了改进。一种是改进的基于法向的边收缩算 法，一种是改进的三角形折叠算法，并在此基础之上提出了一种简单可行 的误差控制方法： 4 对多分辨率模型进行进一步的研究，将三维图形所包含的颜色、纹理等属 性考虑进去，采用了一种新的带属性的三角网格模型简化算法对三维图形 第一章绪论 迸行多分辨率分析。 本文借助c + + 语言和o p e n g l 图形库作为工具在微机上实现了上述算法，本文 的研究工作得到了陕西省自然科学基金资助( 基金编号o g x o g 2 ) 。 本文的文章结构组织如下： 第一章绪论对三维图形多分辨率模型技术的发展历史和现状进行了综述。 t 第二章研究了三维图形的多分辨率模型技术。 第三章研究实观了细分小波的多分辨率模型。 第四章采用了准均匀b 样条方法对三维图形进行多分辨率表示。 第五章研究实现了累进网格的多分辨率模型，并对算法进行改进。 第六章采用了一种新的带属性的三角网格模型简化算法对多分辨率模型 技术进行进一步的研究。 结束语为本文的工作总结，在简要回顾了本篇论文工作的基础上，对三维图 形的多分辨率模型技术以后的发展提出自己的一些看法。 6 三维图形多分辨率模型技术的研究 第二章三维图形的多分辨率模型 三维数据存在于许多应用领域之中，例如计算机视觉中激光扫描设备产生的 行列( r a n g e ) 数据，科学计算可视化中的体数据，遥测技术中由卫星照片得到的地 形数据，计算机图形学中的细分或参数化曲面等。这些数据都要经过计算机处理， 然后在屏幕上显示。由于各自的表达形式不同，为了提离显示硬件系统的通用性 和效率，这些数据通常都转化为多边形网格( m e s h ) ，特别是三角形网格的形式。 三角形网格图形的一个不足是数据量十分巨大，每个三角形都需要数十甚至 数百个比特来表示，而单个网格的三角形数目就可能达到十万甚至百万的数量级。 这就给图形的绘制( r e n d e r i n g ) ，存储，传输和编辑造成很大的困难。 从2 0 世纪9 0 年代起取得突破的三维网格图形多分辨率模型，将网格图形表 达为基本网格和系列细化图形的系数，使对网格数据的处理转化为对细节系数 的处理，从而为解决网格图形数据量造成的许多问题提供了有力的工县。 2 1 三角形网格图形 多边形网格属于曲面模型，是一个由许多平面多边形通过公共顶点和边围成 的封闭或半封闭的曲面。三角形网格是最简单的多边形网格，网格中的每个多边 形都是三角形。( 图2 1 ) 。 ( a ) 一个简单的图形 ( b ) 一个复杂的幽形b u n n y( c ) b u n n y 的部分表面 图2 1 三角形网格图形 三角形网格由于其规则的表示方式，对于显示和计算都有极高的效率，因此 成为现代最流行的三维图形表示方式之一。本文研究的三维图形就是指以三角形 网格形式表示的三维曲面图形。 三角形网格图形可以有多种内部数据结构表示，其中目前最普遍的表示是将 三角形网格m 表示为一个顶点的集合v 和个三角形面的集合只 f = f o ，e 。一c ) v = v o ，巧，k 第二章三维图形的多分辨率模型 m = ，f 。 顶点矿存储了三维空问坐标： _ = x ，j ，乙】 为了提高存储效率，实际存储时并不存储三角形顶点坐标本身，而是存储顶 点在集合矿中的索引值： z = ( v ，吒，h ) ，0 v ，咋， 玎 相邻的三角形通过公共顶点互相连接，并且通常假定所有互相连接的三角形 的朝向( o r i e n 抬t i o n ) 是一致的。如图2 2 中( a ) 所示。 三角形面中每两个相邻的顶点构成边，通常每条边连接两个三角形面，只有 个面的边构成网格的边界( b o u n d a r y ) 。如图2 2 中( b ) 所示。 ( a ) 朝向 图2 2 三角形的朝向和边界 ( b ) 边界 2 2 细分小波多分辨率模型 小波( 始蹭抬0 是进行多分辨率分析( 胁t i r e s o u t i o na 船弦趣m t z 4 ) 的经 典方法。小波的概念最初源于对地震波的研究，2 0 世纪7 0 年代初后期，法国科 学家m o r l e t 在进行地震数据分析时提出了小波变换【2 8 l ，发现任意信号都可以使 用一个被称为小波母函数的函数通过平移( t r a n s a t i o n ) 和伸缩( s c a l i n g ) 进行分 析；此后，m e y e r 和m a l l a t 提出了多分辨率分析的概念，统一了正交小波基的 构造。多分辨率分析和小波的基本思想是将一个复杂的函数分解为一个“简单的” 函数和一系列小波系数，从而将对函数本身的处理，转化为对小波系数的处理。 由于小波具有优良的时频特性，因此多分辨率分析在很多领域得到了广泛的应用 2 9 1 涉及的领域包括曲线造型、曲线曲面编辑、体绘制、动画控制、图像编辑、 体变形和累进传输等。 传统的小波和多分辨率分析是定义在无限或者具有简单边界的均匀采样的一 维直线，二维平面和三维空间上的。然而三维网格图形是定义在三维空间的曲面， 并且具有任意的拓扑结构。这就使得传统小波构造中平移和伸缩等基本概念很难 推广到曲面。 1 9 9 4 年l o u s b e r y 对一类特殊的网格图形即细分网格( s u b d i v i s i o nr a g s 进行了 三维图形多分辨率模型技术的研究 多分辨率分析，构造了k - d i s c - 细h , l 、波 3 0 , 3 1 ( s u b d i v i s i o n w a v e l e t ) ，从面将小波推广 到了三维曲面。此后s c h r o d e r 等人引入“提升”( l i f t i 嘲的概念获得了更一般的细 分小波构造方法口2 ，”j 。通过细分小波分鳃，可以将满足细分连续性( s b u d i v i s i o n c o n n e c t i v i t y ) 的三维网格转化为由一个基本网格( b a s em e s h ) 和一系列小波系数组 成的细分多分辨率模型。由于小波系数代表细节，通过小波系数的加入和移出， 就能获得任意分辨率模型。 2 2 1 小波与多分辨率分析 小波与多分辨率分析是两个相互联系的概念。 2 2 1 1 小波的定义 我们称满足条件：d ； ) 【2d 国 m 的平方积函数9 ( f ) ( 即妒( f ) r ( 胄) ) 为 - - 4 基d 、波或小波母函数( 伊a ( c o ) 是伊 ) 的而谢盯变换形式) 。 令纯，一2 丽苦p ( 字) 称为由母函数妒生成的依赖于参数a ，b 的连续小波。 设厂( f ) r ( r ) ，定义其小波变换为： 帅，6 ) w ) 2 高d ( 等) 西 僻1 ) 由小波变换结果可以复原信号： 乃) 2 麦肛( x ) 窘彩 ( 2 _ 2 ) 其中：c ，= 氅挚出 对连续小波进行离散化，可得的离散小波变换为： ( 厂) = e ( t ) f ( t ) d t ( z 一3 ) 其中，妒。( f ) ：盘詈p ( 口“- 一”6 ) ， m ， 2 离散小波变换中，当疗= 2 ，b = 1 时，存在某些小波函数伊( 工) r ( 矗) ，使得函 竺 数系 2 2 妒( 2 “，一 ) 卜m ， z 构成了r ( 月) 的一组f 交基，可以对( r ) 中的任意 函数进行正交分解，且由分解系数很容易恢复原始信号。 第二章三维图形的多分辨率模型 2 2 ，1 2 多分辨率分析简介 一空间f ( r ) 中的多分辨率分析 空间三2 ( r ) 中的多分辨率分析是指2 ( r ) 中满足如下条件的个空间序列 v 。 ，j z ： ( 1 ) 单调性：v ，cv ”，对于任意j z ； ( 2 ) 渐进完全性：nv j = ( 0 ，u 矿，= f ( r ) ； j t 2i t z ( 3 ) 伸缩规则性：对w z ，“( 功v 。营u ( 2 x ) v 川； ( 4 ) 平移不变性：u ( x ) v oju ( x k ) v o ，对于v 女z ： ( 5 ) r i e s z 基存在性： 存在伊( f ) v o 使得细0 一n ) ，h z 是矿。的标准正交基，称妒为该多分辨分 析的生成元。由性质( 3 ) 、( 4 ) 、( 5 ) 可见，f ( o v o 尊f ( 2 ”r ) e v “，且函数系 ( 22 妒( 2 “卜- n ) ) ，删，m z 构成了v 。空间的组标准正交基。为构造e 2 ( 月) 中的标准 正交基，考虑矿”在v ”1 中的正交补空间矽”，即矿“上v ”，且v ”1 = v ”o w ”。 显然，对任意m ，删ez ，子空间矽“与”是相互正交的。且 f ( t 1 wo 铮f ( 2 “t - ) w ”。 由内积n 4 r p r o d u c t i o n ) ： s = = ( p7 ) 7 定义 = ，7 ，得到： ，s k ( p ) ( 2 - 1 4 ) 为求解s ，j ，必须是可逆阵。虽然i ，是稀疏的，但j ，逆阵很可g 是稠密的， 这意味着其支集( s u p p o r t ) 可能是全局的。为提高小波分解的效率，仅使小波 】i f ，7 ( z ) 和部分支集；r e j 中尺度函数正交： e l ( x ) = “( z ) + 5 7 ，( x ) ( 2 1 5 ) k e 口， 满足： = 0 ，k 石， ( 2 - 1 6 ) 2 2 4 小波的分解与重构 多分辨率分析中合成滤波器p j 9 。和分解滤波器z 。的定义为： 第二章三维幽形的多分辨率模型 中7 ( x ) ，7 ( j ) ： o ”( x ) p 7 o 7 p ，q ，】- ( 2 一1 7 ) ( 2 一1 8 ) 进一步由( 2 一l0 ) 得到分解和合成公式： v7 = a y 川 ( 2 一1 9 ) w = b7 矿”。 ( 2 - 2 0 ) v “= p 7 矿+ q 7 7 ( 2 2 t ) 对三维细分网格图形使用( 2 1 9 ) $ u ( 2 2 0 ) 进行小波分解，直到原图形被分解为 反映基本拓扑结构的基本网格们。和代表图形细节的各级小波系数，。 基本网格是最低分辨率的图形。通过( 2 2 1 ) 的重构算法，向基本网格加入小 波系数，就能重构出包括原图形在内的不同分辨率图形。因此基于小波的多分辨 率模型为： 肘o ， o ，1 ) ) 2 3 累迸网格模型 虽然多分辨率分析和小波有着深刻的数学背景，但对三维图形，小波加入可 以看作图形的细化，小波的移出则对应于图形的简化。因此，只要找到组可逆 简化和细化操作，就可以获得一个网格任意分辨率的模型，从而构成广义的多分 辨率模型。累进网格模型( p r o g r e s s i v em e s h ) 就是基于上述思想产生的。 累进网格的多分辨率分析模型是一种连续的分辨率模型，利用多边形简化算 法对网格进行简化后构成了一个个相邻的细节层，而累进网格的多分辨率分析充 分利用模型的相邻细节层次之间的连贯性，低级的细节层只存储与高级的细节层 之间的差异，而不是存储整个模型。累进网格生成过程的基本操作是“边收缩”， 控制边收缩的策略通常是对于逼近误差的优化。 h o p d e 第一次提出了用累进网格来表示模型的多分辨率【”j ，随后他又对算法 做了一些功能的扩展【2 “，使其可以实现与视点相关的多分辨率表示。对个给定 的原始网格，根据某个误差标准，让原始网格中的某些边退化为顶点，以达到边 收缩简化，这样每执行次边收缩操作就得到一个简化模型，把这个边收缩操作 记录下来。当算法得到原始网格模型的最筒表示对，也得到了一个边收缩操作序 列，以这个序列的逆序对最简网格模型执行边收缩操作的逆操作( 顶点分裂) ，就 可以得到原始网格模型和最简网格模型之间的任意层次的网格模型。这就是累进 网格的思想。 累进网格作为一种构造连续l o d 模型的方法已经越来越受到重视，这神方法 = 1l，i 三维图形多分辨率模型技术的研究 不仅能大大节省存储量，而且由简化算法对原始模型做一次处理就可生成。另外， 随着计算机网络的飞速发展，累进网格作为三维图形数据的一种有效增量传输方 法，具有广阔的应用前景。 2 3 1 相关算法的分类 累进网格模型的基本操作是边删除和顶点分裂。推广开来，也就是几何元素 删除。国内外在这方面已经取得了很大的研究成果，结合这些简化算法，按其采 用的简化机制大致可以分为以下三类： ( 1 ) 几何元素直接删除型 几何元素直接删除型算法包括：顶点删除6 3 】和三角形删除，这类算法的 基本思想是通过评价顶点或三角形的重要性，如果这顶点或三角形不重要，那么 就直接删除它，并对得到的空洞进行三角化。 s c h r o e d e r l 5 1 提出的三角形网格简化算法是最经典的网格简化算法，该算法分 为以下几个主要步骤：计算三角网格中每个给定顶点的局部几何和拓扑特征， 并对顶点分类；如果点到平均平面的距离小于给定的近似误差值，那么就删除 这个顶点；对删除顶点后留下的空洞进行局部三角化：重复上述操作，直到 三角形网格中没有满足上述条件的点为止。 这个算法的计算量小，时间复杂度为线性，有很好的保细节特性，能保持拓 扑结构，简化模型的顶点为原始模型顶点的子集。由于算法采用局部近似误差质 量，在多次迭代后误差会积累，从而影响简化模型的质量，另外这个算法仅适用 于流形物体。 为了有效地约束近似误差，c o h e n 1 3 】提出了一种基于包络网格的模型简化算 法。该方法的主要特点在于并不使用误差度量，而是通过几何结构( 内外两层包络 网格) 来控制简化过程。该算法的基本步骤为：构造内外两层包络网格( 通过偏 移顶点来完成) ；对于初始网格中的每个顶点，完成以下步骤：移去该顶点以及 相邻的面片，如果可行，对形成的空洞进行三角化，并保证形成的面片不与内外 包络冈格相交，否则放弃删除。 该算法的优点在于能够保持拓扑结构，有效地保持基本特征，对棱角也能很 好地保持，它能有效地约束全局误差，支持自适应的近似。该算法的最大缺点在 于仅适用于二维流形，不适用于任意多边形网格模型( 如面片有自交情况) ，另外 包络网格难于构造。 ( 2 ) 近平面合并型 近平面合并算法2 5 】的基本思想是把近似位于同一个平面上的相邻三角形 进行合并，形成一个大多边形，再用数目较少的三角网格来表示这个多边形。近 第二章三维图形的多分辨率模犟 旦 平面合并算法的一个典型例子是k a l v i n 1 4 在1 9 9 6 年提出的基于区域生长的贪婪 式简化算法，该算法分为以下3 个步骤：超面( 指相邻三角形合并后得到的面) 生长，将原始模型表面分解为多个超面：边界拉直，即对相邻超面共享的边界 进行简化；超面的重新三角化。 该方法不仅适用于任意用三角面片表示的复杂模型，而且还可以适用于其它 多边形网格表示的模型，简化速度明显快于其它算法。另外它提供了一个较理想 的手段来保证简化模型与原模型的误差( 全局误差) ，并且简化模型的顶点为原始 模型点集的子集。 ( 3 ) 边收缩型 使用边收缩进行模型简化的算法很多盼住1 8 之2 1 ，边收缩型操作容易构成连续 过渡的多个l o d 表示模型，便于多分辨率模型的管理。 h o p p e l 8 1 在1 9 9 3 年提出的网格优化算法是最早引进边收缩简化元操作的算法， 它源于一个表面重构算法，它通过使一个全局能量函数最小化来简化模型。该算 法由于要建立和求解复杂的全局能量优化方程，因而计算复杂性高，很难达到实 时。在这个算法的基础上，h o p p e 在1 9 9 6 年对原算法迸行了改进口5 j ，从而支持多 分辨率表示。它首先搜索平面区域和特征边，然后通过使用边收缩操作来进行模 型简化。当边收缩产生个新顶点时，移去两个面和一个顶点，结果将产生一个 简化的基网格和一系列的顶点分裂操作( 边收缩的逆) ，可用于把细节增加到基网 格上，使用这种累进网格，可抽取多个连续的细节层次。 算法分为以下几个步骤： 使用基于能量方程表示的最小简化代价对边进行排序，并放入一个表中； 对表中前面的边进行边收缩操作，记录下对应的顶点分裂操作； 新项点可选在边的两个端点或边的中点； 重新计算那些受简化元操作影响的边的代价函数： 重复，直到表为空，或者简化代价超过给定值。 这个算法的优点在于可以生成连续细节层次，支持模型的累避传送和有选择 细化，并且还考虑到面片上彩色和纹理信息的处理，多个细节层次所占用的存储 空间很小。算法的局限性在于仅能处理二维流形。1 9 9 7 年，h o p p e 2 1 1 又一次对算 法进行改进，使得算法能完成与视点有关的细化。 g a r l a n d 【2 2 】提出的网格简化算法可以对原始模型产生高质量的近似结果。算 法使用重复的边对( e d g e p a i r ) 收缩操作来简化模型，并用二次误差度量方法来计 算近似误差。该算法可分为以下几步： 计算原始模型中每个顶点的误差矩阵q ： 选有效的可进行收缩的顶点对； 为每个顶点对( v ，) ，计算最优的用于代鹫v l ，的新点v ； 三维图形多分辨率模型技术的研究 把所有顶点按收缩代价顺序放在堆中( v ( q + q 2 ) v 为收缩代价) ，最小 代价放在顶部； 重复地把顶点对( v ，v ：) 从堆中输出，进行收缩，并修改受影响的顶点对的 代价。 该算法既可作用于流形物体，也可作用于非流形物体，可以把一些模型中不 相连的区域进行合并，且能保持相对高的质量。 本文所实现的累进网格模型主要是基