（计算机软件与理论专业论文）复杂模型的多分辨率简化算法.pdf

摘要 摘要 复杂模型的多分辨率简化算法 朱晓燕顾耀林 专业：计算机软件与理论 随着计算机技术的飞速发展，计算机的应用领域正以空前的规模扩展着，计算机图形学在这种大力推 广中也起到了很大的推动作用。在计算机图形学和几何造型中，常会遇到一些较为复杂的模型。处理这些 模型时，在显示、传输、硬件需求等方面会遇到困难。考虑到多层次模型在图形简化、多细节层次技术等 方面的优良性能和对渐进传输的潜在支持，本文对复杂模型多分辨率简化进行了研究。 首先，本文对网格模型简化方法进行了研究，着重讨论了基于边崩溃和基于三角形折叠的渐进网格算 法和多分辨率简化技术。然后，在基于渐进网格的多层次模型方面，本文对基于边崩溃和基于三角形折叠 的两种渐进网格模型简化算法进行了改进，经过多分辨率技术分解之后，复杂模型被表示为一个低分辨率 网格模型，同时记录下相关的细节；接着，在此基础上进行了进一步研究，考虑颜色、纹理等属性的基础 上进行简化，得到多细节层次模型。最后，介绍了涉及视锥、背离面和屏幕投影误差的视相关网格化准则， 并根据它们发展了渐进简化算法。 三维模型在各行各业的应用越来越广泛，但是伴随而来的是模型数据量和复杂程度的急剧增加，因此 利用多层次模型简化方法来表示模型，从而降低数据的存储量，减轻网络的传输负荷，缓解硬件的压力， 加快处理速度等等变得备受关注。 关键词：网格简化渐进网格边崩溃多分辨率 江南大学硕士学位论文 a b s t r a c t s i m p l i f i c a t i o n a l g o r i t h mf o r c o m p l e x m o d e l s b a s e d o n m u l t i r e s o l u t i o n z h u x i a o y a ng u y a o | i n m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y a st h er a p i dd e v e l o p m e n to f c o m p u t e r , c o m p u t e rt e c h n i q u eh a sb e e nw i d e l ya p p l i e di ne a c hs o c i a lr e a l m i n t h ep r o m o t i o no f m o d e r nc o m p u t e rt e c h n i q u e ，c o m p u t e rg r a p h i c sh a sp l a y i n ga l li m p o r t a n tp a r ti ni t i nc o m p u t e r g r a p h i c sa n dg e o m e t r ym o d e l ，w eo f f , o nm e e ts o m ec o m p l e xm o d e l s w h e nw ed e a lw i t ht h e s ec o m p l e xm o d e l s , t h e r ea r e m a n yd i f f i c u l t i e si n c l u d i n gd i s p l a y , n e t w o r k 仇a n s m i s s i o n , h a r d w a r e a n ds oo n c o n s i d e r i n gt h es u c c e s s o fm u l t i r e s o l u t i o nm o d e l si nm e s hs i m p l i f i c a t i o n , l o dt e c h n o l o g ya n dt h ep o t , n t i a ls u p p o r tf o rp r o g r e s s i v e t 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 ym u l t i r e s o l u t i o ns i m p l i f i c a t i o no f c o m p l e xm o d e l s i nt h eb e g i n n i n g , i nt l l i sa r t i c l e w eh a v ea n a l y z e dt h eb a s i ct e c h n o l o g i e so fm e s hs i m p l i f i c a t i o na n d m u l t i r e s o l u t i o nt e c h n o l o g i e s s p e c i a l l y , w eh a v ed i s c u s s e dt w ok 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 s b a s e do ne d g e sc o l l a p s e d ；t h eo t h e ri sb a s e do nt r i a n g l ec o l l a p s e d t h e n ，w ei m p r o v et h et w ok i n d so fm e s h s i m p l i f i c a t i o na l g o r i t h m si nt h ep r o c e s so 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 do np r o g r e s s i v em e s h e s b y d e c o m p o s i n gw i t ht h e s em e t h o d s ，t h e s ec o m p l e xm o d e l sa r cr e p r e s e n t e dl o w - r a s o l u t i o nm e s h e s a n dt h e ye a r lh e n o t e di n t e r r e l a t e dd e t a i l s a n d ，o nt h eb a s i so fa b o v ea l g o r i t h m s ，w es t u d yt h es i m p l i f i c a t i o na l g o r i t h mw i t h a 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 el o dm o d e l sb ys i m p l i l y i n gm o d e l si nt h ec 黜o fc o l o r sa n dt e x t u r e sa r e t h o u g h t f i n a l l y , i ti n t r o d u c e se f f i c i e n tv i e w - d e p e n d e n tm e s h i n gc r i t e r i ab a s e do nt h ev i e w - f i u s t u m ，b a c k - f a c ea n d s c r e e n - s p a c eg e o m e t r i ce r r o r a n dt h es i m p l i f i c a t i o na l g o r i t h mo np r o g r e s s i v em e s h e si sd e v e l o p e da c c o r d i n gt o t h e s ec r i t e r i a w i t ht h ep o p u l a ra n dd e v e l o p m e n to f3 dm o d e l s ，i ta e c o m p e n i e sw i t hag r e a td e m a n do ns t o r a g ea n d c o m p l e x i t yh a n d l i n g t h e r e f o r e ，i tw h i c hi sp r e s e n t e dm o d e lw i t hm u l t i r e s o l u t i o ns i m p l i f i c a t i o nt e c h n o l o g yi s b e c o m i n ga f a v o r i t ef o c u s t h r o u g ht h e s e , s t o r a g es i z ea n dt h ec o m p u t a t i o nt i m ec a nb er e d u c e d ；t h eb t w d e nf o r n e t w o r kt r a n s m i s s i o na n dh a r d w a r ec a nb el o w e r 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 , p r o g r e s s i v em e s h , e d g ec o l l a p s e ，m u l t i r e s o l u t i o n i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：日期：瑚年月日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 繇粒导师魏丞世 日期：0 年月j 日 烨 第一章绪论 第一章绪论 随着计算机技术的飞速发展，计算机图形学取得了巨大的进展，己经进入了三维真实感图形时代，在 电视广播、网络、多媒体等社会各领域发挥了重要的作用。为了模拟出具有真实感的效果并解决由此给硬 件带来的压力，越来越多的人投入到多分辨率技术的研究中，并取得了一些成果，目前已有部分技术应用 于计算机动画、医学以及运动学等领域中，创造了一定的社会效益和经济效益。 1 1 模型简化简介 模型简化是指采用适当的算法减少模型的面片数、边数和顶点数。虽然组成模型的面片数减少后，其 表示精度必然下降，但只要采取的简化方法适当，仍然可以保证对象模型的图像具有良好的形状逼近。 随着物体模型复杂性的增加，表示物体之所需多边形数目远超过图形硬件的能力。建立三维模型所得 到的模型描述通常由上万个、几十万个、甚至几百万个面片组成，为满足计算机分析、显示与存储的要求， 一个自然的解决方法是在不严重损失物体视觉特征的前提下，对物体的网格模型进行简化，用较少数目的 面片来表示物体。物体模型的不同简化版本构成物体的细节层次( l e v e l so fd e t a i l ，简称l o d 模型) 或多分辨 率表示。 细节层次模型是指对同一个场景或场景中的物体，使用具有不同细节的方法得到一组模型，供绘制时 使用。它的目的不是为了从初始模型中移去粗糙的部分，而是为了保留重要的视觉特征来生成简化的模型， 其理想的结果应该是一个初始模型序列的简化，这样简化模型才可以应用于不同的实时加速。为了实现连 续帧的绘制，细节层次简化方法必须均衡考虑模型的细节度和绘制速率。 多分辨率技术就是将一个复杂物体表示成一系列精细程度不同的三维模型，在使用时考虑到人们对模 型的视觉效果，当物体离视点的距离较近时，调用相关分辨率较高的模型，反之则调用分辨率较低的模型， 在保证一定视觉精度的同时还能获得较理想的速率。 多分辨率技术与细节层次技术密不可分，但是二者也存在着些许差别： ( 1 ) 细节层次模型和多分辨率造型都能为同一场景中的物体提供所个不同细节、不同精度的表示。在 细节层次模型中，肌是一个固定的常数；而在多分辨率造型中，卅是不固定的，它随物体表面的面片数 目的增加而递增。 ( 2 ) 细节层次模型的生成是一个预处理过程，预处理过程中产生若干个不同细节的表示，细节层次模 型是这若干个不同表示的简单集合；而多分辨率造型则提供了一种紧凑的数据表示方法，能动态地、实时 地根据用户的需要，生成不同细节、不同精度的网格描述。 ( 3 ) 细节层次模型只是若干个不同细节的网格描述的简单集合，它的存储量与其中包含的不同细节的 网格描述的数目成正比；而多分辨率造型则去除了不同细节的网格描述之间的冗余信息，结构紧凑，存储 量相对较小。 1 2 研究背景和现状 随着计算机软、硬件技术的发展，在三维图形学、计算机辅助设计、地理信息系统和医学影像系统中 所能构造与应用的几何模型越来越精细和复杂。我们可以使用三维扫描仪和c t 等设备获取逼真的几何数 据。然而，在精确表示模型的同时，用来描述这些模型的数据量也越来越庞大。一方面，这些大规模复杂 的三维模型对计算机的存储容量、图形处理能力都提出了更高的要求。另一方面，三维可视化系统在互联 网平台的应用也十分广泛，大规模三维复杂模型实时传输的需求给网络传输带来了很大的压力。因此，也 江南大学硕士学位论文 吸引的众多研究人员从事该方面的研究。 1 2 1 网格模型简化的背景和现状 从研究领域来看，网格造型技术已从传统的研究网格表示、网格求交和网格拼接，扩充到网格变形、 网格重建、网格简化、网格转换和网格位差。 网格重建是指要为已存在的网格建立模型，即根据已有的网格去构造反映其形状的数学模型。网格 重建需要采集大量的数据，建成的模型一般很复杂。这样大量的数据给图形的实时显示、数据的存储与传 输都带来了困难。为此，需要对重建得到的复杂的数学模型进行简化，以减少数据量和数据模型的复杂程 度。网格简化正是解决上述问题的方法。由三维重建所得到的离散曲面或由造型软件所输出的网格中，在 保证必要精度的前提下去除冗余信息，以利于图形显示的实时性、数据存储的经济性和数据传输的快速 性。对于多分辨率曲面模型而言， 该技术还有利于建立网格的层次逼近模型，进行网格的分层显示、传 输和编辑。 由于任意多边形网格都可以转化为三角网格，故对三角网格的简化方法具有一般性的意义。为了对网 格模型进行简化，s c h r o e d e r “1 在9 0 年代初提出了平面准则，即在局部范围内拟合一张平面，删除那些到该 平面的距离小于制定精度的采样点，并对保留的点重新三角化。这样就用数量较少的大三角形来取代数 量较多的小三角形，从而可获得不同复杂层次的同一场景模型的三角形网格描述。类似地，还有h a m a n n ”“ 在1 9 9 4 年提出的曲率准则，即删除曲率小于制定误差的点。h o p p e s j 6 j 等则采用能量函数最优化方法来化简 模型，通过引入距离能量、表示能量和弹簧能量，使得简化模型是原模型的优化逼近。试验表明，该方法 效果较为理想。t u r k 等提出了基于网格重构的多边形模型简化方法，该方法把一组新顶点分布到原模 型上，再以原网格三角形顶点的曲率与三角形面积作为因子决定新顶点的位置。k a l v i n ”1 等采用三角面片 合并方法，以原模型中的一个多边形面片作为“种子”，按照一组合并条件不断合并“种子”四周的面片， 直到再无面片满足合并条件。f o r s e y “等将网格简化与曲面拟合技术相结合，来产生b e z i e r 曲面表示的规则 四边形网格的简化模型。d e l m e m e r “”等则在f o r s e y i 作的基础上，提出规则四边形网格模型的简化模型自 动生成方法。 上述方法生成的简化模型与原模型保持一致的拓扑几何关系。但实际上，简化模型只要其图形效果与 原模型保持一致即可。据此，一种用多分辨率近似法自动生成形体的简化方法“被提出了，即首先赋予 网络各项点一个权值，特征变化较大处的顶点的权值也较大；然后剖分形体所占的空间，同一剖分单元中 的顶点的权值决定该单元中代表顶点的权值；最后依据原模型中各面片顶点的代表点是否相同来合并相关 面片。另外非常重要的一点是，简化过程中简化模型与原始模型之间的误差应该是可以控制的，如 g a r l a n d “”“”“”等通过二次误差来度量边崩溃简化方法中崩溃一条边给模型所带来的误差量； h o p p e “”“。“2 ”在其原有算法基础上提出了基于边崩溃方法的渐进网格生成方法。 此外，c o h e n ”“等通过对模型顶点的位置、曲率和颜色进行采样，把模型表示成由该三种属性组成 的三元组，而后根据预定的屏幕像素误差进行简化，简化后的模型能较好地保持原模型地三种属性。 g r o s s “”、l o u n s b e r y 1 、d e r o s e ”和e c k 1 等将小波技术应用于网格简化，其基本思想是：运用小波的 方法将三角网格分解为低分辨率和细节两部分，两部分分别通过低通和高通滤波方法获得，通过略去细节 信号的方法便可实现模型简化的目的。还有，提出了基于顶点聚类。“的简化方法，通过顶点聚类合并简 化网格模型。基于视点。“”的三角网格模型简化方法也被提了出来，此类算法对网格模型位于视锥 内外的区域选择不同的细节层次。另外，还有采用自适应剖分方法1 对多边形化网格进行简化等等。 国内学术界也在网格简化领域开展较有成效的研究工作。周昆，石教英等”1 利用八叉树对网格进行自 适应划分，提出一种基于顶点聚类的三角形折叠网格简化算法，该方法通过点到平面的距离进行误差控制。 潘志庚、马小虎”等提出一种基于三角形删除准则的网格模型简化方法，该算法减少了计算最，并有较高 的删减率。周晓云”1 等将特征角准h 归i a m 格简化过程中，作为简化模型误差度量的测度。李现民等” 将细分思想引用于边崩溃后新顶点的计算，提出了基于蝶形细分规则的网格简化方法。还有许多其他算法 1 4 0 jl 4 1jy 如基于重新划分的三角形网格简化的改进算法，基于能量评估的网格简化算法等都有被提出。 2 第一章绪论 1 2 2 多分辨率技术的背景和现状 从不同分辨率、不同角度分析和处理问题是人类的一种重要思维方式，也是处理复杂问题的一种有效 手段。由于需要解决的模型越来越复杂，规模不断扩大，根据不同的需求，建立系统的不同分辨率的模型 并将这些模型有机结合起来是复杂系统建模和技术发展的必然趋势。 多层次模型是指物体模型的多个细节层次网格表示形式，相当于该物体模型的多个不同分辨率模型的 集合。多层次模型又可分为离散多层次模型和连续多层次模型。对复杂网格进行简化，得到不同细节层次 的多个三角网格模型，称之为离散多层次模型。连续多层次模型则是一种紧凑的模型表示方法，可生成任 意多个不同分辨率的模型。基于这两种不同模型，面向多层次模型的压缩又可分为面向离散多层次模型的 压缩和面向连续多层次模型的压缩。 多分辨率技术的产生可以追溯n 1 9 7 6 年，c l a r k m l 认为当物体覆盖屏幕较小区域时，可以使用该物体描 述较粗的模型，并给出了一个用于可见面判断算法的几何层次模型，以便对复杂场景进行快速复制。在1 9 8 2 年，r u b i n “结合光线跟踪算法，提出了复杂场景的层次表示算法及相关的绘制算法，从而使计算机能以 较少的时间绘制复杂场景。c r o w 用一个实例说明了同一物体采用不同的l o d 模型所具有的优点。 9 0 年代初，图形学方向上派生出虚拟现实和科学计算可视化等新研究领域。虚拟现实和交互式可视化 等交互式图形应用系统要求图形生成速度达到实时，而计算机所提供的计算能力往往不能满足复杂三维场 景的实时绘制需要，因而研究人员提出多种图形生成加速方法1 ，l o d e 型则是其中一种主要的方法。这 几年在全世界范围内形成了对多l o d 自动生成技术的研究热潮，并且取得了很多有意义的研究结果。 1 9 9 1 年，d e h a e m e r 和j 用自适应递归方法，提出了基于规则四边形网格表示物体的简化多边形网格的方 法。g r e g 给出了基于网格重新划分的多边形网格模型简化方法。r o s s i g n a c 使用多分辨率近似法自动生成物 体的简化模型，该方法并不保持原有模型的拓扑结构。 1 9 9 5 年，h e 使用信号处理方法来消除模型的高频细节，从而得到简化模型。e c k 利用小波变换把多 面体模型表示为多分辨率形式，由此可生成一系列连续的多l o d 模型。1 9 9 6 年，c o h e n 1 使用内外两个包 络网格来控制简化过程，该方法可保持模型的拓扑结构。h o p p e 基于网格优化方法，提出了渐进网格的概 念以及生成方法，该方法搜索平面区域和特征边，使用边崩溃操作来完成简化功能；之后又对渐进网格进 行扩展，形成对任何网格都适用的且与视点有关的渐进网格。l i n d s t r o m 1 对规则网格表示的地形模型提出 了一种实时连续l o d 绘制方法，在三维地形仿真中得到成功应用。r o n f a r d ”针对非常复杂的场景，使用区 域合并操作来进行模型简化，该方法根据与原始形状的几何偏差度量进行边合并。g u e z e i c 1 提出了一种误 差可控的模型简化方法，边崩溃操作与r o n f a r d 所用的边崩溃方法类似，而误差控制方法则与c o h e n 所用的 方法类似。x i a ”提出了一种动态的、与视点相关的多边形网格模型简化方法。 网格模型简化技术和多分辨率技术的产生和发展是一致的，相辅相成，不可分割的。 1 3 广泛应用 多分辨率技术在计算机图形学和多媒体方面正被广泛地应用着，如三维动画设计、虚拟现实技术、体 育运动、医学诊断等方面都被涉及到。 ( 1 ) 三维动画设计 计算机三维动画技术最初是因为影视业发展的要求产生的，其实质就是：在场景中随时间变化，使用 平移、旋转等变换改变整个物体或物体的某个部位的位置。一般情况下，物体主要是指人和其他动物。近 几年来，由于科学技术的不断进步和相关产业的不断完善，计算机动画已成为综合运用计算机图形学、物 理学、美术学等学科或领域的一种高新技术，已经越来越成功的运用到科学研究、广告及影视制作中。在 计算机动画设计中，如何运用多分辨率技术逼真快速地绘制三维物体场景已经变成当前的一个热点研究课 题。我们如今看到很多影视作品的特技效果不得不归功于该项技术的发展。 ( 2 ) 虚拟现实 3 江南大学硕士学位论文 虚拟现实最近几年来得到了迅速的发展，它是指用立体眼睛或传感手套等一系列传感辅助设施来实现 的一种三维现实，人们通过这些设施以自然的技能向计算机送入各种动作信息，使人们获得三维的视觉， 听觉及触觉等感觉的世界，随着动作信息的不同，感觉也随之改变。 随着虚拟现实中的实时漫游以及科学可视化中各种实时动态显示的普遍出现，数据的形式越来越多 样，数据量也越来越大，从而导致了三维物体的复杂度己超出了一般图形硬件的实时绘制能力，而多分辨 率技术可以在不影响生成图像质量的前提下以不同的细节程度来表达同一个三维物体模型，达到满足实时 显示的目的。 ( 3 ) 体育事业 在体育方面，该技术的应用也越来越受到重视。赛场上，训练中都可以运用到，比如赛场上，通过模 拟分析能给出更公平、公正的成绩；训练中，运动分析就是从图像序列或视频中获取人体的运动信息，并 对它进行分析、识别等工作。体育运动中经常用运动分析运动员各种技术动作以及技术动作与外界条件之 间的关系，特别是在现代竞技体育中。各国都在研究如何运用科学原理来提高运动员的成绩。 随着我国体育事业的蓬勃发展，运动员调练方法的科学化、规范化己成为当务之急。为了满足教练员、 运动员、科研人员进行形态分析及定量运动生物力学分析的需要，可以利用计算机，将三维人体的运动模 拟技术与运动生物力学分析方法相结合之后，开发出相应的运动训练模拟分析系统，从而为教练员的训练 方法改进、体育院所的科研和教学工作提供一种有力的工具，发挥作为先进科技应用系统的作用。 ( 4 ) 医学研究 医学诊断所面对的问题是如何获得高质量的人体医学图像及处理这些图像，从而提取出有效的科学数 据以便对人体骨骼、肌肉和内脏等进行研究。而采用多分辨率技术就可以让医生在计算机上看到病人的三 维器官模型，包括骨骼、肌肉和经络等，除了供观察之外，还可以用它来模拟一些物理过程并对病变部位 进行分析。 还有，在医学上，医生的培训是一项投资大、周期长的工作，因为不能随意让实习医生上手术台。多 分辨率技术可以给出人体有用的解剖学数据，既缩短了实习医生培训周期，又节约了人力、物力和财力。 当然，多分辨率技术应用并不局限于以上几个方面，还可以应用于军事侦察、地形勘测、教师教学， 环保事业，以及服装设计等领域。由此可见该技术具有巨大的发展潜力和应用价值，当然这还需要广大的 研究学者的加入和大量的研究经费的支持。 1 4 论文范围与课题意义 本文对网格模型简化方法进行了研究，着重讨论了基于边崩溃和基于三角形折叠的渐进网格算法和多 分辨率简化技术。在基于渐进网格的多层次模型方面，本文对基于边崩溃和基于三角形折叠的两种渐进网 格模型简化算法进行了改进，在复杂模型的多分辨率简化技术基础上延伸，致力于使其戍用于更具一般性 的模型，并改进误差度量方法，提高简化后模型效果。最后，考虑颜色、纹理等属性和视相关的基础上进 行模型简化，得到多细节层次模型。 当今，虽然图形硬件的能力在不断提高，但由于数据获取手段的进步和显示质量要求的不断提高，硬 件的显示能力与需要显示的模型数据之间始终存在着差距。因此，通过软件手段，针对数据的特点对其进 行简化，根据需要，在模型的不同区域使用不同的分辨率来表示。由于多层次模型的特点，它在复杂三维 场景快速绘制、飞行模拟器、地理信息系统、交互式可视化和虚拟现实等领域应用的广泛需求，所以得到 了学术界的普遍关注，该技术具有巨大的发展潜力和应用价值。 1 5 本文主要工作 多分辨率技术的发展离不开计算机图形学的理论基础支持。在图形学领域，图形学的建模思想、坐标 变换、三维观察、光照以及消隐等技术直接影响并作用于多分辨率技术的分析和解决过程中。前人在这个 4 第章绪论 领域所做的研究和实验，得出的理论和经验，都为本文研究提供了很大的帮助。 本文在研究多分辨率技术时，分别从多层次模型理论分析、研究和实现三个方面进行了研究。概括起 来，主要有以下几个方面的工作： 学习分析了当前主要的网格模型简化技术。网格模型简化是尽量保持原模型的可视特征条件下， 减少模型的多边形数目，实际上就是用尽可能少的表面采样点来表示原始模型中尽可能多的细节 信息。 研究了基于渐进网格的多层次模型，并对实现基于渐进网格的多层次模型简化算法进行了改进， 并在此基础之上提出了一种误差控制方法，提高简化后模型显示效果。 对多层次模型进行进一步的探讨，将三维图形所包含的边缘、纹理等属性考虑进去，采用一种带 属性的网格模型简化算法对三维图形进行分辨率分析。 在模型简化算法中，加入模型的视觉特征，利用视点相关，建立视点与网格精度的对应关系 1 6 内容组织 各章节内容分布如下： 第一章是绪论，主要介绍了课题的相关背景。从基本概念入手，分别从网格模型简化和多分辨率技术 两个方面较为透彻地分析了国内外学术界相关技术的研究背景和研究现状；然后介绍了其广泛的应用领 域；最后结合该领域中较有代表性的研究成果引出本文所要探讨的主要问题。 第二章是系统地回顾了近年来提出的网格模型简化的一些主要算法及其特点。从本文最终研究目的角 度出发，结合相关知识，着重研究探讨了几种所需的网格模型简化的方法。 第三章是研究探讨渐进网格多层次模型。本章在研究了基于边崩溃的渐进网格模型和基于三角形折叠 的渐进网格模型的基础上，分别提出了算法改进方案并加以实践。最后，通过相关模型验证其有效性。 第四章是第三章的延伸。本章在前面相关章节讨论的基础上，更进一步，加入了颜色、纹理等属性的 考虑，主要讨论了误差评估、检测点的选取和重新分配等问题。最后通过模型进行实验。 第五章是在网格模型简化算法中，加入模型的视觉特征，利用视点相关，建立视点与网格精度的对应 关系。在进行基于边崩溃简化的算法中，运用视锥准则、背离面准则和屏幕投影误差进行网格处理。 第六章是结论，同时介绍了今后需要进一步完善的工作。 5 第二章网格模型简化方法的研究 第二章网格模型简化方法的研究 网格模型简化方法”1 在动画制作、激光扫描数据、地形表示、合成曲面等方面有大量的应用。网格简 化方法还给出了很多误差标准来衡量逼近曲面的拟合程度。只要给定一个足够大的近似误差，大多数方法 都可得到任何层次上的简化网格。 2 1 三角形网格图形 多边形网格是计算机图形学中三维实体的重要表示方法。三维扫描技术的不断发展使三维网格模型日 益广泛地应用于制造业、娱乐业及互联网。同时，计算机获取的三维模型越来越复杂，数据量越来越庞大 庞大的数据量对于数据处理、图形绘制、快速原型制造等都是巨大挑战，所以数据简化，尤其是网格简化 成为一个必须的环节。网格简化的目标是在尽量保持模型逼真度的前提下，大幅减少三角形面片的数目。 而衡量一个简化模型逼真度的准则是它与原始模型之间总体特征的近似度，即原始模型表面的初始细节特 征在简化模型上同样可以体现。 多边形网格属于曲面模型，是一个由许多平面多边形通过公共顶点和边围成的封闭或者半封闭的曲 面。三角形网格是最基本的多边形网格，网格中的每个多边形都能划分成三角形。如图2 1 所示。 ( 8 ) 一个简单的图形( b ) 一个复杂的图形：兔子( c ) 兔子的部分表面 图2 - 1 三角形网格图形 三角形网格由于其规则的表不方式，对于显不和计算都有极商的效翠，因此成为现代最沉行的三维幽 形表示方式之一。本文研究的三维图形就是指以三角形网格形式表示的三维曲面图形。 三角形网格图形可以有多种内部数据结构表示，其中较为普遍的表示是将三角形网格朋表示为一个 顶点的集合v 和一个三角形面的集合f ： f = 织，只，最，e v = v o ，k ，k m = 杪，f 顶点k 存储了三维空间坐标： 7 江南大学硕士学位论文 k = ky ，毛j 为了提高存储效率，实际存储时并不存储三角形顶点坐标本身，而是存储顶点在集合v 中的索引值： f = h ，v k ，v i ) 0 v ，h ，h 刀 相邻的三角形通过公共顶点互相连接，并且通常假定所有互相连接的三角形的朝向( o r i e n t a t i o n ) 是一致的。如图2 - 2 中( a ) 所示。 三角形面中每两个相邻的顶点构成边，通常每条边连接两个三角形面，只有一个面的边构成网格的边 界( b o u n d a r y ) 。如图2 - 2 中( b ) 所示。 ( a ) 朝向( o r i e n t a t i o n ) ( b ) 边界( b o u n d a r y ) 图2 - 2 三角形的朝向和边界 2 2 几种网格模型简化方法的研究 不同学者基于不同思想各自提出了一些各具特色的网格简化方法，各种方法在某一方面，或者是某几 个方面都有其特点和优点，并在相关领域有着重要的应用。下面探讨几种常用的网格模型简化方法，同时 着重探讨研究的是与本文研究内容相关的几何元素直接删除方法、基于边崩溃和基于三角形折叠等方法。 2 2 1 近平面合并方法 近平面合并方法”“的基本思想是在初始网格上搜索共面或近似共面的面片将其合并，形成一个更大 的多边形，然后用数目较少的网格来表示这个多边形，以达到简化的目的。该方法的重点是共面测试过程。 超平面方法通过有限误差和更精确的局部三角化扩展了近平面合并方法，并且提供更加健壮的重新三角化 方法。 典型例子是k a l v i n 提出的基于区域生长的贪婪式简化算法，主要步骤如下： 首先超平面( 指相邻三角形合并后得到的面) 生长，将原始模型表面分解为多个超平面； 然后边界拉直，即对相邻超平面共享的边界进行简化； 最后实现超平面的重新三角形化。 该方法不仅适用于任意地用三角面片表示的复杂模型，而且还可以适用于其他多边形网格表示的模 型，简化速度明显快于其他同类算法。另外它提供了一个较理想的手段来保证简化模型与原模型的误差( 全 局误差) ，并且简化模型的项点为原始模型点集的子集。 8 第二章网格模型简化方法的研究 2 2 2 几何元素直接删除方法 几何元素直接删除方法主要包括：顶点删除( 如图2 3 所示) 和三角形删除( 如图2 - 4 所示) 。这类 方法的基本思想是通过评价顶点或三角形的重要性，如果该顶点或三角形不重要，那么就直接删除它，并 对得到的空洞进行三角化。 顶点删除方法按一定的准则删除一些不必要的采样点，以减少数据量。s c h r o e d e r 等率先提出了基于 顶点删除的网格模型简化方法，基本步骤如下： 计算网格各给定顶点的局部几何和拓扑信息，并对网格顶点进行分类； 再根据不同顶点的评判标准决定该顶点是否予以删除，比如如果点到平均平面的距离小于给定的近 似误差，那么就删除该顶点； 如果删除该顶点，则采用递归环分割方法对删除顶点后所留下的孔洞重新进行三角剖分。 重复上述操作，直到网格中没有满足上述条件的点为止。 该算法的计算量相对较小，时间复杂度为线性，较好地保持了细节特性，保持了拓扑结构，简化模型 的顶点是原始模型顶点的子集。但是，由于该算法采用局部近似误差质量，在多次迭代后误差会累积，从 而影响简化后模型的质量，另外这个算法适用于流形物体。 与顶点删除方法相类似的三角形删除方法，在这里简单介绍一下。比较典型的是h a m a n n 给出了一种 基于三角形删除的模型简化方法，该方法首先对模型中的所有顶点计算曲率，再由顶点的曲率决定所有三 角形的权值，权值最小的三角形被删除，最后对被删除三角形后留下的区域重新进行三角剖分，并且对所 有新引入的三角形计算权值。迭代以上过程，直到简化的模型符合要求。 图2 - 3 顶点删除 图2 - 4 三角形删除 9 江南大学硕士学位论文 2 2 3 边崩溃方法 使用边崩溃进行模型简化的算法很多“”“”1 ，边崩溃型容易构成连续过渡的多个l o d 表示模型。 边崩溃方法按一定的准则崩溃由曲面重建方法建立起来的网格中的一条边。具体做法是通过反复执行崩溃 网格中一条边的元操作来简化网格模型。如图2 - 5 所示。在该方法中，必须解决的两个问题是：如何选取 崩溃边及如何确定替代崩溃边的新顶点。 此类方法中，比较典型的是g a r l a n d 提出的网格简化方法。该方法使用重复的边对( e d g e p a i r ) 崩 溃操作来简化模型，并用二次误差度量方法来计算近似误差。这种方法可以对原始模型产生高质量的近似 结果。该方法为网格中的每个顶点计算一个( 基本) 误差矩阵，通过两端点的误差矩阵可计算出一条边的 误差矩阵，再通过一定规则确定的崩溃顶点的位置便可得到崩溃该边的“代价”。元操作每次都通过线性 优化方法，确定崩溃顶点并选取“代价”最小的边进行崩溃。 具体算法可分为以下几步： 计算原始模型中每个顶点的误差矩阵q ； 选有效的可进行崩溃的顶点对，即边： 为每个顶点对“，v 2 ) 计算最优的用于代替h ，v 2 的新点v ： 把所有顶点按崩溃代价顺序放在堆中，最小代价放在顶部： 重复地把顶点对“, v 2 ) 从堆中输出，进行崩溃，并修改受影响的顶点对的代价。 由上述知识可知，此算法中，关键在于第步的关于顶点误差矩阵g 的计算和第步中关于新顶点1 ， 位置的选取。 误差矩阵计算有多种方法，现以点到相关平面距离的平方和作为误差度量为例。具体求法如下： 在三维欧氏空间内，一个平面可以表示为a x + b y + c z + d = 0 ，平面法向量为以2 如，b ，c y ，且有 口2 + 6 2 + c 2 = 1 。点7 2 k y ，z y 到该平面的距离的平方为： d 2 ( v ) = b 7 v + d ) 2 = k + 砂+ 凹+ d ) 2 。 ( 2 1 ) 对于某顶点相关的三角形集合，该顶点的二次误差测度 印) = 2 i d 2 i ( v ) = e i ( n r v + 。 ( 2 2 ) 注意到d 2 0 ) = v t 0 7 ) l ，+ 2 协y v + d 2 ，可以定义三元组q = 0 ，b ，c ) 。其中， a = ，研7 ：b = d n ：c = d 2 。q 称作二次误差测度或二次矩阵，二次误差测度值酏) = ，7 a v + 2 b 7 v + 。也 称作二次误差。 当然，除了使用点到相关平面距离的平方和作为误差度i - 2 _ ) l , ，还有以点到相关直线的距离的平方和 作为误差度量的。 关于新顶点位置的选取，通常有两种方法： a 直接选择法，即直接将”= v l 或v = v 2 或”2 ( v l + v 2 ) 2 。这种计算相对简单，但所计算的 二次误差不一定最小。 1 0 第二章两格模型简化方法的研究 b 优化选择法，即计算空间位置”，使崩溃操作引起的误差代价最小。可以在两点连线上寻找1 ， 也可以在全空间寻找y 。此方法能得到最小误差代价，但会增加额外的计算量。 基于二次误差度量的几何简化方法的优点是具有极高的计算速度和较小的内存消耗，而且得到的简化 网格具有较高的质量。该算法既可以作用于流形物体，也可以作用于非流形物体，还可以把一些模型中不 相连的区域进行合并。 2 2 5 包络网格方法 图2 - 6 三角形折叠 为了有效地约束近似误差，c o h e n 提出了一种基于包络网格的模型简化方法。该方法的主要特点在于 并不使用误差度量，而是通过几何结构( 内外两层包络网格) 来控制简化过程。该算法的基本步骤为： 江南大学硕士学位论文 构造内外两层包络网格( 通过偏移顶点来完成) ； 对于初始网格中的每个顶点，完成以下步骤： a 进行判断，是否可以移去该项点以及相邻的面片； b 如果可以移去，则进行移去操作，并对顶点和相邻面片移去后形成的空洞进行三角化，并保证形成 的面片不与内外包络网格相交； c 否则放弃删除。 该算法的优点在于能够保持拓扑结构，有效地保持基本特征，对棱角也能很好地保持，它能有效地约 束全局误差，支持自适应的近似。该算法的最大缺点在于仅适用于二维流形，不适用于任意多边形网格模 型( 如面片有自交情况) ，另外包络网格难于构造。 2 2 6 多分辨率方法 多分辨率方法。“”1 也可称为多层次方法。在逻辑上它是为要重建的曲面建立一个从简单到复杂的数 学模型的序列。人们可以根据需要，选用序列中的某个元素表示的模型作为曲面的数学模型进行分析并显 示。模型序列中的各元素之间具有递推的关系。在网格优化算法的基础上，h o p p e 在1 9 9 6 年提出了一种 渐进网格( p r o g r e s s i v em e s h ) 的方法，从而支持多分辨率表示。它首先搜索平面区域和特征边，然后通 过使用边崩溃操作来进行模型简化。当边崩溃产生一个新顶点时，移去两个面和一个顶点，结果将产生一 个简化的网格和一系列的顶点分裂操作( 边崩溃的逆操作) ，可用于把细节增加到被简化的网格上，使用 这种渐进网格，可抽取多个连续的细节层次。该方法不仅简化了初始网格，还可实现对网格的逐次传输、 可编辑等功能。 渐进网格简化算法通过优化能量函数来达到简化网格的目的，以具有代表性的h o p p e 的算法为例。算 法主要有以下几个步骤： 使用基于能量方程表示的最小简化代价对边进行排序，并放入一个表中； 对表中前面的边进行边崩溃操作( 如图2 5 所示) ，记录下对应的顶点分裂操作； 新顶点可选在边的两个端点或边的中点： 重新计算那些受简化元操作影响的边的代价函数； 重复，直到表为空，或者简化代价超出给定值。 这个算法的优点在于可以生成连续细节层次，支持模埠! 的渐进传送和有选择细化，并且还考虑到面片 上彩色和纹理信息的处理，多个细节层次所占用的存储空间很小。算法的局限性在于仅能处理二维流形。 1 9 9 7 年，h o p p e 1 又一次对算法进行改进，使得算法能完成与视点有关的细化。 h o p p e 的渐进网格方法在选择一条边进行崩溃时均考虑了一些严格的全局优化策略，需要很大的运算 量，所以需要先对模型进行预处理，因此很难用于实时简化。在此基础上有一些改进算法，这些改进算法 主要的工作是为了实现动态实时显示，在选择崩溃边时没有使用h o p p e 算法中的一些严格的全局优化策略， 比如有的学者提出了不再对模型考虑边删除误差的全局优化，转而考虑模型的局部特征，即仅考虑每个顶 点周围的一些顶点、边或面的信息，通过对它们的某种度量作为误差判断准则，从而大大地降低每一步选 择崩溃边的计算代价。每个顶点的局部信息包括：周围项点的位置、包含该顶点的边及其长度、包含该顶 点的三角形及其法向量等信息。在利用这些信息时，兼顾考虑了将边长或在某条边处的曲率或两者的组合 作为边删除策略的方法。比如淮永建等在复杂几何模型动态视相关的简化中是通过崩溃边的长度和表面曲 率来计算边代价，建立边崩溃的优先序列。 以上几种方法与本文的研究内容较为密切，故进行了重点研究。接下来，再简单提及其他几种方法。 2 2 7 基于小波分析的方法 小波( w a v e l e t ) 是进行多分辨率分析( n u l t i r e s o l u t i o na n a l y s i s ，m p a ) 的经典方法。小波的概念 1 2 第二章网格模型简化方法的研究 最初源于对地震波的研究，2 0 世纪7 0 年