（计算机应用技术专业论文）三角网格模型的简化与光顺.pdf

摘要 三角网格模型的简化与光顺 摘要 专业：计算机应用技术 研究生：石坚 导师：须文波教授 董洪伟副教授 近年来，随着计算机技术和三维扫描技术的发展，出现的一种新的多媒体数据类型数字几 何模型。三角网格成为表示数字几何模型的主要方式，并且在娱乐、网络以及制造业中得到了广泛 的应用而数字几何处理是解决这种新兴多媒体类型闯鹿的主要手段，数字几何处理算法因而也成 为计算机多媒体和图形学领域的一个重要研究方向。学者们提出了许多数字几何处理算法，如曲面 重构、网格简化、网格编辑、阿格变形、曲面光顺、网格参数化等。本文对其中的两种算法，三角 网格简化和三维曲面光顺进行了研究。完成的工作主要包括以下几个方面： 以三角形折叠方式为基础，提出了一种新的基于离散曲率的三角网格简化算法算法以网格表 面的加权离散曲率为依据，对三角形进行折叠操作，同时给出了基于离散曲率和球面近似的新 顶点的获取方法，实验结果证明了算法的有效性。 将多项选择技术用到了本文的网格模型三角形折叠简化算法中，该技术将传统的贪心算法框架 下的三角形折叠简化算法应用到了多项选择框架下，加快了三角形折叠算法的执行速度，进一 步提高了该算法的执行效率，同时又再次证实了该技术在网格简化算法中的应用是可行的 提出了一种保特征的网格光顾算法，算法能够在快速的去除噪声的同时，保持网格模型的结构 特征。算法首先对网格中每个三角形的法矢进行光顺，并且求得顶点的法矢；接着根据当前点 到邻接点的距离以及当前点的法矢与邻接点的法矢的夹角对顶点移动的方向进行调整，使顶点 分布更加均匀；最后利用高斯函数求得光顺权值对网格模型进行光顺实验结果证明了。算法 能够有效的保持网格模型的结构特征，同时具有选代次数少，体积收缩小执行效率高的特点 关键词z 数字几何处理，网格简化，离散曲率，多项选择算法，罔格光顾，特征保持 江南大学硕士学位论文 t r i a n g l em e s hs i m p l i f i c a t i o na n d s u r f a c e s m o o t h i n g a b s t r a c t s u b j e c t ：c o m p u t e ra p p l i e dt e e l m o l o g y g r a d u a t es t u d e n t ：s h ij i a n t u t o r ：p r o l e s s o rx uw e n b o a s s i s t a n tp r o f e s s o rd o n gh o n g w e i i nr e c e n ty e a r s , w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n d3 ds c a n n i n gt e c h n o l o g y , d i g i t a l g e o m e t r ym o d e lh a sb e n an e wt y p eo fm u l t i - m e d i a m e s hm o d e l s 批o n eo ft h em o s tp o p u l a rm e t h o d s t o r e p r e s e n td i g i mg e o m e t r ym o d e la n dh a v eb e e nw i d e l yu s e d i n m a n y 丘e 烛s u c h i n t e r n e t , e n t e r t a i n m e n ta n dm a n u f a c t u r ei n d u s t r i e s d i g i t a lg e o m e t r yp r o c e s s i n g ( d g p ) i st h em a i nt o o lt od e a lw i t h t h et y p eo fm u l t i m e d i aa n dh a sb e c o m eo n eo ft h em o s ti m p o r t a n tr e s e a r c h 五e l 凼i nm u l t i m e d i aa n d c o m p u t e rg r a p h i c s m a n yd i g i t a lg e o m e t r yp r o c e s s i n ga l g o r i t h m s , s u c ha s $ u l f a r e c o n s t r u c t i o n ，m e s h s i m p l i f i c a t i o n ，m e s he d i t , m e s hm o r p h i n g ，s n e a c as m o o t h i n ga n dm e s hp a r a m e t e d z a t i o n ，h a v eb e e n p r o p o s e di nt h ep a s tt w od e c a d e s t w oo ft h e s ea l g o r i t h m s , m e s hs i m p l i f i c a t i o na n ds u r f a c es m o o t h i n g , w i l l b er e s e a r c h e di nt h ep a p e r m a i na c h i e v e m e n t so fo u rw o r ka ma sf o l l o w s ： a m e s hs 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 ng u t _ f a c ec t l r v a t u r ee s t i m a t i o ni sp r o p o s e di nt h ep a p e r a n di ti si 血p i e m e n t e do nt h eb a s i so ft r i a n g l ec o l l a p s e a c c o r d i n gt ot h ed i s c r e t ec u r v a t u r eo nt r i a n g l e m e s h e s , m o r ei m p o r t a n tf e a m r e sc a nb ep r e s e r v e di nr e g i o n so fh i g hc u r v a h t r ea f t e rs i m p l i l i c a t i o n a m e t h o dt og e tt h en e wv e r t e xa f t e rt h ec o l l a p s eo fat r i a n g l eb a s e do nd i s c r e t ec u r v a t u r ea n ds p h e r i c a l s u r f a c ee s t i m a t i o ni sa l s 0g i v e ni nt h ep a p e r e x p e r i m e n t si l l u s t r a t et h ee f f i c i e n c yo f o u ra l g o r i t h m t r i a n g l ec o l l a p s es i m p l i f i c a t i o na l g o r i t h mi se s t a b l i s h e do nt h e f r a m e w o r ko fm u l t i p l e - c h o i c e a l g o , i t h m ( m c a ) e o m p a r e at o w h i c hi s i m p l e m e n t e d o i lt h et r a d i t i o n a lf r a m e w o r ko fg r e e d y o p t i m i z a t i o n i ti m p r o v e st h ee f f i c i e n c yo fa l g o r i t h ma n dc e u 丑i u l st h a tm c a b e u s e di nm e s h s i m p l i f i c a t i o n a ne f f i c i e n tm e s hs m o o t h i n gm e t h o di sp r o p o s e d o u rm e t h o d s m o o t hs u r f a c eq u i c k l y , w h i l e p r e s e r v i n gf e a t u r e s f i r s t l y , w es m o o t ht h en o r l n a lo fe v e r yt r i a n g l ei nt h em e s ha n dg e tt h en o r m a lo f e v e r yp o i mi nt h em e s ha f t e rt r i a n g l en o r m a ls m o o t h i n g s e c o n d l y , w ei m p r o v et h em o v i n gd i r e c t i o n o fe a c hv e r t e xa c c o r d i n gt ot h ed i s t a n c e sb e t w e e nc u r r e n tv e l m xa n da d j a c e n tv e r t i c e s , a n dt h ea n g l e s b e t w e e nt h en o r m a lo fa 埘n tv e r t e xa n do fa d j a c e n ty e t r i c e & t h i r d l y , w eg e tt h ew e i g h to fe a c h v e r l e xi nt h e i t e r a t i o n u s i n gg a n a s i a n w ep r o v i d e as e r i e so fe x a m p l e st od e m o n s t r a t et h e e f f e c t i v e n e s so fo u rm e t h o dw i t hf e w e ri t e r a t i o nt i m e sa n dl e s sv o l u m es h r i n k a g e k e y w o r d s ：d i g i t a lg e o m e 时p r o c e s s i n g ，m e s hs i m p l i f i c a t i o n ，d i s c r e t ec u r v a t u r e ，m u l t i p l e - c h o i c ea l g o r i t h m o c a ) ，m e s hs m o o t h i n g ，f e a t u r ep r e s e n , i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名： 日期：夕固年月7 e j 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：丕旦 导师签名：兰兰! 丝 日期：如矽年歹月场日 第一章绪论 第一章绪论 2 0 世纪中后期以来，数字多媒体技术得到了迅猛的发展，分别在上世纪7 0 年代出现了数字声音， 年代诞生了数字图像、9 0 年代又有了数字视频这是多媒体技术的三次重大革新。声音技术的发 展催生了广播、电话、收音机等行业的繁荣，使人类远距离获取信息成为现实但是人类对声音信 息总是将信将疑，更信奉眼见为实，图像技术的发展和广泛应用满足了人类的这一心理要求，也培 育了数码摄影、电脑图片、平面媒体等行业图像技术满足了人类对静态的细节、特征、纹理的欣 赏要求，但是它们不能准确地描述和记录现实世界中已然存在的动态画面满足不了人类对实时、 动感的追求视频技术的发展和应用，能够使人类多姿多彩的生活得以再现。但是图像和视频只能 从一个侧面将物体和环境展示给人类。人类对新鲜事物的追求是永无止境，希望能够全方位、浸入 式、交互式地与环境交流，就必须发展新的多媒体技术因而继数字声音、数字图像、数字视频之 后，种新的多媒体数据类型数字几何模型应运而生这是多媒体领域里的又一次重大革新， 是继前三种多娱体数据类型后出现的又一种重要的数字媒体的载体，它将对多媒体产业以及人类生 话带来根本性的变化 1 1 三维几何的数字化 1 1 1 数字几何模型的出现 几何模型成为一种新的多媒体数据之前，几何造型技术已经发展了很多年，但是由于计算机技 术和扫描技术的限制以及手工制造几何模型的烦琐，大大阻碍了三维几何模型的应用近年来，随 着三维阵列扫描技术的飞速发展以及算法技术的进步，将现实中的物体数字化为数字几何模型已成 为可能，并且在制造业、影视制作以及视频游戏等行业中得到广泛的应用。最著名的例子是斯坦福 大学的数字米开朗基罗工程1 ”，该项目通过一整套三维扫描硬件和三维重建软件系统完成了一些大 型雕塑的数字化，生成的晟复杂的三维模型包括了2 0 亿个多边形以及7 0 0 0 幅彩色图像 图1 1 数字米开朗基罗工程 江南大学硕士学位论文 另外，随着计算机运算能力和存储能力的大幅度提高以及各种图形加速卡的出现。使得在个人 计算机上处理三维几何数据变得很越来越容易，同时网络技术的飞速发展也使我们有理由相信数字 几何将继声音、图像和视频之后掀起新一轮多媒体数据革新浪潮 1 1 2 数字几何模型的获取和表示 ( 1 ) 数字几何模型的获取 获取数字几何模型的方法可以分为正向工程和逆向工程，翦者，利用传统的几何造型技术对三 维模型直接进行设计，并把模型表示为n u l u 强、三角网格、四边形网格、细分曲面等形式，在工业 设计中，体现为组件的设计、制造、组装、性能测试等。每个组件都保留有原始的设计图，其好处 在于可以对未知物体比如机械零件和建筑物等的设计加入个性的创意，而坏处在于该方法很难通过 这些简单的曲线曲面设计来表示一个现实生活中已经存在的并具有丰富细节的物体，比如雕像、人 脸、古董等等鉴于这些困难，人们提出了通过照相机获取单张或多张相片基于这些相片进行建 模和图像合成，获取物体的三维几何信息的方法，这种方法称为基于图像的建模与绘制( i m g cb a s e d m o d e l i n g d r c n d e 血g ，m m r ) 该方法具有建模容易，绘制快，真实感强等特点，实践表明，基于 图像的建模方法对于那些规则的物体，特别是大型的简单的建筑物的几何形状获取和估计具有较大 应用价值，结合图像配准、参数化、基于图像的绘制等等技术可以获取和实现大型场景的漫游。 但对于具有精致的表面细节和几何信息丰富的物体。该类方法同样无法精确重建几何。对于这类物 体的几何获取和重建利用激光测距三维扫描仪来获取物体表面离散点，并通过散乱点重构算法来 构造三维数字模型l 是当前最为合理和有效的方法。随着三维扫描仪硬件设备和处理软件地不断更 新，以三维扫描仪为硬件基础的三维数据获取系统既可获取几何信息又可获得表面纹理颜色信息。 另一方面硬件价格的不断下降，为三维扫描技术的推广和普及带来了机遇最近十年以来，基于该 类硬件的软件处理技术成为研究者的关注热点。 ( 2 ) 数字几何模型的表示 在计算机图形学中，数字几何模型的属性包括几何属性和外观属性。本文主要研究几何模型的 几何属性，即几何模型的外观形状。描述物体形状的方法有很多种，如体素表示法、c s g 树表示法 以及边界表示法计算机图形学中提出了很多种表示曲面的边界表示法，包括隐函数曲面、参数曲 面、细分曲面，多边形网格以及点表示方法等。所有这些表示的目的在于能够简便地生成不同形状 的物体表面。多年来。多边形绘制技术一直受到高度的重视其他曲面表示方法，诸如隐式曲面、 n u r b s 等，最终都被转化为多边形表示以便采用常规图形绘制硬件进行绘制。这是由于多边形网格 模型具有以下优点： 1 ) 多边形形状简单，便于计算和处理： 2 ) 多边形可阻任意精度逼近一个曲面物体，并可以表示拓扑非常复杂的物体； 3 ) 只需存储各多边形顶点的位置坐标及属性即可表示物体的几何信息，在计算多边形内任一可 见点的光亮度时，所需的信息可由顶点的信息插值得到，这使得对多边形网格的绘制可采用硬件加 速技术来实现。图形硬件的高速发展以及对几何表面多边形化算法的深入研究进一步巩固了多边形 网格在图形绘制及造型中的地位。 本文研究的对象就是多边形网格模型，由于任意多边形可以方便地被剖分为三角形，并且现在 研究和应用地最广泛的多边形网格即为三角形网格因此本文的主要针对三角形网格模型进行研究。 2 第一章结论 ( a ) 几何模型 ( b ) 点模型c o ) 网格模型 图1 2 三维几何模型的表示 1 2 数字几何处理的研究现状 。数字几何在工业界得到了越来越广泛的应用，同时这一趋势也推动了学术界对数字几何处理的 研究。顾名思义。数字几何是指通过对真实物体的表面进行采样而得到的几何数据，数字几何处理 就是利用计算机对三维几何数据进行处理它的基本表示形式有： 1 ) 直接由采样数据形成的三维点云； 2 ) 多边形网格。 另外。在每一数据点通常还附有颜色、光泽度以及透明度等属性数据。这样一些几何数据与属 性数据共同为三维场景与动态环境的建模提供了各种不同层次的信息。 数字几何处理利用计算机对这种三维几何数据进行处理，以达到不同应用所要求的数据转换、 模型表示或场景绘制等目的。但是，数字几何数据具有与数字音频、数字图像与视频数据完全不同 的特殊性质。这是由于： 1 ) 它所表示的物体表面通常是任意弯曲，复杂和缺乏连续参数化的，很难找到一种内在的函数 形式对其进行描述。 2 ) 几何数据本身以及各种属性数据都是非规则采样的。对于多边形网格模型，其连接关系尤其 复杂 3 ) 对于室内环境和建筑物等对象，其数据表面的形状变化多样，拓扑结构错综复杂。 4 ) 随着三维激光扫描技术的进步，模型的数据量大幅度增长，其增长速度远远超过了现有处理 硬件所能提供的计算能力。因此获取一个有效的数字几何处理的工具是计算机图形学领域中一个巨 大的挑战。 一般来说，现有的数字几何处理算法可以分为三类：( 1 ) 基于子分阿格( s u b d i v i s i o nm e s h e s ) 的方法；( 2 ) 基于松弛算子( r e l a x a t i o no p e r a t o r ) 的方法；( 3 ) 几何图像( g e o m e 竹i m a g e ) 的方 法。 3 江南大学硕士学位论文 ( a ) 网格参数化 ( b ) 网格压缩 ( c ) 网搔变形 图1 3 数字几何处理 基于子分网格方法i 州的理论基础是子分小波( s u b d i v i s i o n w a v e l e t s ) ，也是目前虽为成功的数字 几何处理框架，很多数字几何处理应用( 特别是几何数据压缩) 在这个框架可以高教率地实现，但 这种方法的连续性很难证明，并且不能处理几何信号的某些低频分量。基于子分网格技术的典型d g p 应用包括多分辨率编辑、几何压缩和网格变形等，其中最成功的d g p 应用是k l o d a k o v s k y 等人提出 的累进几何压缩州 基于松弛算子的方法1 7 - 9 1 可以在推广到三维网格的离散傅立叶变换( d i s c r e t ef o u r i e rt r a n s f o r m , 4 第一章绪论 d f t ) 中找到理论基础。尽管三维网格的d f t 理论上是完备的。但是由于直接计算d f t 的时间代价 太高，这种方法无法支持大多数傅立叶频率域内的应用，一般只用来做网格光顺造型 几何图像【1 0 l 通过把任意网格参数化到平面上生成能存储模型各种属性的图像，这种方法很好地 解决了网格模型的绘制和压缩，但能否支持其它应用还有待进步的研究 通常，广义的数字几何处理主要包涵以下几个领域分支：数据获取、几何表示、光顺去噪、参 数化、重建、拟合和插值、重网格化、传输压缩、编辑、几何建模、动画和变形等等。图1 3 列出 了部分数字几何处理的效果图。一个三维扫描仪获取的原始模型经过这一系列的数字凡何处理之后， 再通过纹理映射给模型表面赋予顶点颜色、光泽度和透明度等属性值，可以让计算机生成的物体达 到以假乱真的真实感效果 三角网格简化和三维曲面光顺是数字几何处理中两个重要的研究方向，也是本文所要研究内容， 下面我们将简要介绍一下三角网格简化和三维曲面光顺的研究现状。 1 2 1 三角网格的简化 在逆向工程和计算机图形学中表示的三维几何模型通常是有大量的三角面片或称为三角网格组 成的，随着计算机技术和三维扫描技术的发展，能够获取的三维数据量变得越来越庞大，构造的网 格模型的数据量也随之大大增加，这对于数据的存储和网络传输都是一个巨大的负担同时也为后 续的数字几何处理增加了工作量和难度。同时在某些场合。并不需要如此多的数据来表示三维模型， 例如，对于同一个几何模型由于人类视觉的局限当其离视点较远时完全可以用较少的数据量来 表示，因此有必要对网格数据模型进行简化以减少存储和传输的负担，同时便于后续操作 ( 1 ) 基本思想 三角网格简化技术要解决的问题是：给定一个初始三角网格模型 要得到一个新的三角网格 模型肼，m 的三角片数量应少于| | l f 的三角片数量，而且应尽可能保持与原三角网格模型肘相似 ( 2 ) 算法的分类 三角网格的简化算法按照其基本操作的不同大致可以分为以下几类： 顶点聚类算法 顶点聚类算法 i i - l s l 是将整个网格模型划分成若干个小的区域，并且将同一区域内的若干个顶点 用一个代表顶点取代，该算法具有快速、简单、易于实现的优点，但同时它也存在着无法保持网格 模型特征、易于破坏模型结构等明显的缺点，如分别属于两个平面而又邻近的两个顶点容易被错误 的合并为一个顶点从而改变模型的拓扑结构 删除法 删除法d 6 2 0 ! 是指通过评价网格模型中模型要素的重要性，从原始网格模型中逐一减少模型要素， 从而达到简化模型目的的方法。根据所删除的模型要素的不同，又可以分为顶点删除法、边折叠法 和三角形折叠法等。该类方法能够有效的保持网格模型原有的拓扑结构是目前应用最为广泛的网 格简化算法。 重新布点法 重新布点法b 1 1 是指通过在网格表面重新分布顶点，平坦区域分布较少的点，特征区域分布较多 的点，然后根据这些新顶点重构网格模型的算法 细分法 细分法是指从一个粗糙的模型不断对其进行细分使之不断接近原始网格模型的算法 5 江南大学磺士学位论文 1 2 2 三维曲面的光顺 图1 4 三角网格的简化 通过三维扫描仪或其它手段获取的三维数据由于设备精度和人为操作等各种原因包含着各式 各样的噪声并不能非常正确地反映原始模型真实的状况因此，为了便于对三维数据模型进行后 续处理，必须对原始数据模型进行去噪声处理 ( 1 ) 光顺 在信号处理理论中。噪声常被认为是一种随机高频信号，其频率大于某个人为设定的阈值，并 可通过各种空域和频域滤波器对其进行平滑滤波，这个概念也经常在图像处理中出现，图像去噪的 过程即为去除夹杂在原始图像中噪声的过程而光顺是一个工程上的概念，包括光滑和顺眼两方面 的含义光滑是指空间曲线和曲面的连续阶，数学上一阶导数连续的曲线即为光滑的曲线，而顺眼 是人的主观感觉评价。对于平面曲线光顺需要满足以下几点：1 ) 二阶光滑，即曲率连续；2 ) 没 有多余拐点；3 ) 曲率变化均匀曲面的光顺更要求曲面上每一条曲线都是光顺的在数学上判断 曲面是否满足上述条件的依据是曲率信息。而对于离散数字模型，我们难以严格要求其满足光顺条 件，只是认为当模型的曲面曲率变化比较均匀时即为光顺 ( 2 ) 区分噪声和特征 实际上，噪声和特征都是三维数字模型的某种几何属性。从不同的理论层面，噪声和特征的区 分具有不同的标准。类似图像处理，对于三维模型我们亦可通过阈值来区分高频信息和低频信息 而在曲面论中，极小曲面的充要条件是平均曲率处处为零。通过在法向方向移动可以达到曲面光顺 的目的，在这过程中噪声自动被扩散消除。网格顶点的离散平均曲率只与一阶邻域顶点相关因此 可以认为网格上的局部小扰动是噪声，而具有一定的局部连贯性且表现为整体轮廓的信息视为特征。 ( 3 ) 三维模型光顺算法的主要目标为： 有效去除三维模型中的各种形式的噪声： 在模型变得光顺的同时保持模型固有的几何特征： 。 光顺过程中使体积收缩最小，同时防止模型变形； 算法具有较低的时间复杂度和空问复杂度 ( 4 ) 算法的分类 能量最小化方法 该方法 2 2 1 通过使某个能量函数最小化，从而达到曲面光顺的目的，最常见的包括薄板能量最小 化和薄膜能量最小化等。 类似l a p l a c i a n 光顺的迭代算法 该类方法通过一个离散算子，将网格中的噪声扩散到邻接区域中去，从而达到去除噪声的目的， 如1 b 方法【纠、平均曲率流算法i “l 等。该类方法通常需要多次迭代，但是由于其具有线性的时间和 空间复杂度，并且易于实现，因而成为目前应用最为广泛的曲面光顺技术。 其它方法 除了以上的方法外，学者们还提出了一些其它的方法。诸如某几类方法的组合。非迭代算法等 等。 6 第一章绪论 1 3 数字几何处理的应用 图1 5 三维模型的光顺 数字几何处理有着非常广泛的应用。与人类的科研活动及日常生活息息相关 ( 1 ) 动画制作。现代的动画形象对外部造型要求越来越高特别是对媒体角色的逼真度提出了苛 刻的要求在一部动画片中，动画及环境角色可能成千上万，数字几何处理提供了直接从现 实模型到数字模型的方法，这样一个直观商小、稳定可靠的造型工具将推动动画制作技术迈 向新的台阶 ( 2 ) 逆向工程。逆向工程是从已有的实体模型重建曲面模型，现行的处理方法通过三维扫描仪输 入实体数据然后用解析曲面模型来拟合或逼近这些数据。 ( 3 ) 人体医学影像。当前有大量的仪器设备可以获取人体表面及内部数据而医务人员只能通过 二维图像进行症断。利用数字几何处理的结果，可以将从仪器获取的数据恢复三维形状，对 外科手术的精确定位能起到关键作用，同时对整形外科也将会产生巨大的影响 ( 4 ) g i s 。大规模g i s 的数据通常是卫星深度图像。数据量巨大。利用数字几何处理的结果能够 大量简化模型，缩小数据量，复原三维地貌。在城市地理信息系统中，要得到比较真实的建 筑物模型，一种快捷的方法是用高速三维测量仪获取数据，进行三维合成 ( 5 ) 文物的保护和修复对于文物，处于保护的需要，一般不能用接触的方式获取它们的三维数 据，只能用非接触式的三维扫描仪定期获取数据，进行比较，判断毁损程度，以决定是否需 要进行修复。对于已毁损的文物，可通过数字几何处理技术得到它的三维模型，首先在电脑 里进行复原，晟后确定复原方案。 1 a 本文工作 本文回顾了数字几何处理的发展及应用领域，列出了各类数字几何处理算法，并且对其中 的两种算法一三角网格简化算法和曲面光顾算法进行了研究，提出了新的三角网格简化算法 和曲面光顺算法全文按照下列结构组织： 第一章回顾了数字几何处理的出现及发展以及在各行各业中的应用，同时介绍了国内外 数字几何处理的研究状况，说明了本文所完成的工作。 第二章介绍了三角网格简化算法的研究现状，分析了各类简化算法的特点 第三章提出了一种基于离散曲率的三角形折叠简化算法。 第四章介绍了多重选择技术，井将本文提出的三角网格简化算法在该技术框架下实现 第五章阐明了曲面光顺的必要性，分析了曲面光顺算法的研究现状以及各类曲面光顾算法 的特点并介绍了几种主要的曲面光顺算法 第六章提出了一种保特征的曲面光顺算法。 第七章给出了全文工作的总结，并对未来的工作进行了展望 7 江南大学硕士学位论文 第二章三角网格简化算法简介 本章首先阐述了了网格简化算法的概念和定义。接着介绍了前人提出的各种网格简化算法，包 括顶点聚类法、删除法、重新布点法、细分法，分析了它们的特性和执行效率。 2 1 引言 近年来，三角网格数据在逆向工程、虚拟现实、网络图形和三维动画中得到越来越广泛的应用 随着计算机技术的应用和发展，人们对计算机造型和绘制技术的要求不断提高。计算机模拟场景的 规模越来越大，景物的细节也越来越丰富。另外，三维扫描仪得到的数据构建的三角网格模型，由 于其采样密度均匀，因而造成了数据量庞大，受到存储和传输带宽的限制，使得其很难在实际应用 中直接使用。并且随着三维扫描仪的大规模普及和发展，扫描获取的几何体的细节以及外形的日渐 丰富，所获取的数据规模也越来越大。因而对三角网格模型进行简化成为急需研究的问题之一，从 而也成为计算机图形学研究的热点问题之一 2 1 1 网格简化的目的 网格简化的目的是把一个多边形潮格表示的模型用一个近似模型表示，近似模型基本保持了原 模型的可视特征，但顶点数目少于原始网格的顶点数目。通常的做法是把一些不重要的图元( 顶点、 边或三角形) 从多边形网格中移去。 2 2 相关工作 目前，国内外研究人员在各自不同的领域中提出了许多三角网格模型的简化技术这些领域涉 及地图学、地理信息系统、虚拟现实、计算机视觉、计算机图形学、计算机辅助几何设计、有限元 分析、近似理论等。这些三角网格模型简化技术有效的降低模型的存储空间，加快了模型在网络上 的传输速度，提高有限元计算、消隐计算、模式识别等操作的效率。不同的网格简化算法大致可以 分为以下几类：项点聚类法、删除法、重新布点法、细分法。 下面将分别介绍这几类算法 2 2 1 顶点聚类法 顶点聚类法的基本思想是：对于给定的多边形表面。把模型所在空问分成多个小格( 小格尺寸 小于用户指定的近似误差阈值c ) ，为每个小格计算一个代表顶点。把原始模型落在这个小格内的项 点都合并到代表顶点上如果一个三角形有两个或三个顶点位于同一个小格内，多余的顶点就会被 删除，网格从而得到简化 聚类算法的主要特点有： ( 1 ) 编程实现和使用最简单，效率非常高。 ( 2 ) 健壮性好，对输入网格的拓扑结构没有限制。 ( 3 )可能在简化过程中改变两格的拓扑结构当同一个小格内，有来自原始模型上两个或者 更多个不相邻区域的项点时，就会导致拓扑结构改变。修改拓扑结构有利于进行大幅度 8 第二章三角同格简化算法简介 ( 4 ) 简化，对由很多不同部分组成或是带有孔洞的模型，保持拓扑结构会使简化幅度受到很 大限制。但改变拓扑结构可能对简化模型的外观产生不利影响 简化模型的精度依赖于小格的尺寸用户可以通过定义小格的大小，保证一个全局近似 误差范围。但对于给定的误差范围，聚类算法很难达到最优简化大面积的平面会保留 过多的三角形。微小的尖锐特征则容易被删除 司r 于 r i l ， j 、 1 上 l r。 i l ， 丫 k ( a ) 简化前( b ) 简化后 图2 1 顶点聚类算法二维示意图 r o s s l g n a c 和b o r r e l 首先提出的顶点聚类算法1 1 1 噪用均匀栅格划分模型衡量每个顶点的重要性， 在较大的面或者较高的曲率处的顶点重要性较高。选取小格中重要性最高的顶点作为该小格的代表 顶点顶点为n 时，时间复杂度为o ( n 1 ，简化质量较低。 l o w 和t a n 的浮动栅格聚类算法i l 珥对模型的划分是分步进行的。每次以重要性最高的顶点为中 心建立一个小格。格中其它项点都合并到中心点，重复上述步骤直至满足要求。算法减轻了简化结 构对模型位置和朝向的敏感性，对顶点重要性的计算做了修改。视觉和质量都得到了改善。时间复 杂度为o ( n l o g n ) l i n d s t r o m 对r o s s i g n a c 和b o r r e l 的算法进行了扩展，提出了o u t - o f - c o r e 算法 1 3 1 ，对规模极大以 致无法完全读入内存的模型进行简化。采用g a r l a n d 的o e m - q u a d r i c 误差度量指导代表顶点的选取， 代表顶点设置再到小格内所有三角形所在平面距离平方和最小的位置简化结果质量较好时间复 杂度为0 0 ) 。 上述算法都属于静态简化算法，它们预先生成一个或一组简化模型。在实际应用中根据需要 选择合适的模型进行绘制，编程实现简单，得到较好的硬件支持。动态简化算法则先创建适当的数 据结构。在实际应用时从该数据结构中提取所需层次细节，生成适合当前需要的简化模型，从而使 简化质量更好，并能实现不同的层次之问的平滑过渡。 l u e b k e 提出的层次动态简化( h i e r a r c h i c a l d y n a m i c s i m p l i f i c a t i o n 。h d s ) l l q ，就是一种动态聚类 算法。它用八叉树代替均匀栅格，通过合并八叉树单元来实现基于视点的自适应简化任何顶点聚 类算法都可以应用在这个方法的框架中。h d s 不保持拓扑结构编程简单，但简化质量不高。 对于超大规模模型，l i n d s t m m 还提出了一种混合方法1 1 5 1 ，先采用o u t - o f - c o r e 算法获得一个可 以读入内存的中问结果。再用h d s 算法对这个中间结果实现基于视点的自适应简化。 2 2 2 删除法 删除法是指从初始三角网格模型开始，删除模型中的一个或几个要素，同时删除包含该要素的 三角片，直到满足用户的要求。典型的有顶点删除法、边折叠法和三角形折叠法删除法是目前应 用最为广泛的一种网格模型简化方法 9 江南大学硕士学位论文 ( a ) 顶点删除法 p ( b ) 边折叠法 图2 2 删除法 ( 1 ) 顶点删除法( v e r t e xd e c i m a t i o n ) 顶点删除法删除网格模型中的一个顶点以及包含该顶点的三角片后形成一个空间空洞多边形 然后对该空洞多边形进行三角化形成新的网格模型，重复上述步骤，直至满足用户要求。 该算法的特点是： ( 1 ) 易于减少近似共面区域的多边形数量，大量减少冗余信息。 ( 2 )生成模型质量较好。 ( 3 )大多数不允许改变模型的拓扑结构 ( 4 ) 不同算法的实现难度和处理速度相差较大 s c h r o e d e r 删除法 顶点删除法的代表是s c h o e d e r 等在1 9 9 2 年提出的网格简化算法【1 6 l 。该算法将三角网格模型中 的所有顶点分为5 类，如图2 3 所示。图2 j ( d ) 和图2 3 ( e ) 中加租的边表示包含该条边的两个 三角片在该条边处的二面角大于某指定值。 侈p c a ) 内部点( b ) 非流形点c o ) 边界点 ( d ) 不连续点( d ) 角点 对于内部点，算法采用顶点到邻接点的平均平面的距离作为删除该内部点引起的误差，如图2 4 ( a ) 所示。该平面经过一点石。法矢为二弓和二的定义如下式： 石一晋，丙- 馨， 二。耐n ( 2 - 1 ) 吲 其中：石：为某个三角片的型心；4 为三角片的面积；i 为三角片的法矢 对于边界点和不连续点。s c h r o e d e r 采用该顶点到由两个邻接边界点所构成的直线的距离作为删 除该边界点所引起的误差，如图2 4 ( b ) 所示s c h n x d e r 法不处理图2 3 ( b ) 所示的非流形点的情 况 1 0 第二章三角网格简化算法简介 卤锣 ( a ) 内部点 ( b ) 边界点 图2 4 删除某点引起的误差 在进行三角网格简化时。首先由用户指定一个误差闺值，然后算法遍历网格模型中所有的顶点， 针对不同类型的顶点，计算删除该顶点后引起的误差，若该误差小于用户指定的误差阈值，则将该 顶点和包含该顶点的三角片删除，并对形成的孔洞多边形重新进行三角化。直至模型中不再包含可 以删除的顶点。 算法在时间和空间上的效率都比较高，实现也应用也教简单，简化质量好，可以应用在大规模 网格上但对于表面光滑有困难另外需要注意的是，算法在检测某个顶点是否能被删除的时候， 计算的是当前简化网格模型与上一步简化网格模型之间的误差是否超出阈值，而不是计算该简化网 格模型与初始网格模型之问的误差是否超出阈值。这就容易引起误差积累。另外，算法在选择删除 顶点时是无序的，这样做的效果并不十分理想 简化信封( s i m p l i f i c a t i o ne n v e l o p e s ) 算法 c o h e n 提出了简化信封算法p 7 l 。对于给定输入表面m ，以偏移 和+ e 分别建立表面m 的信封 表面m 和m + 对原始顶点只有当删除后形成的新三角形不与m + 或m + 相交时，才可以删除。算 法的简化结果较好，表面质量较高。近似误差严格控制在给定的阈值内，但是速度较慢，占用的空 间也很大 ( 2 ) 边折叠法( e d g cc o l l a p s e ) 边折叠操作是选择两个相邻的顶点“和y 删除它们之间的边( ，p ) 和这条边上的两个三角形， 两个顶点合并到一个位置w 。对于不同的算法，新顶点w 的选择方案有多种 边折叠算法的特点是： ( 1 ) 简化模型的质量比较好。 ( 2 )健壮性好，可以在任何拓扑结构上进行简化。 ( 3 ) 多数可以闭合模型表面的孔洞，从而改变拓扑结构，进行大幅度简化 ( 4 ) 生成不同精度的模型，容易实现相互切换 ( 5 )不同算法的实现难度和处理速度相差很多 h o p p e 算法 h o p p e 等人在1 9 9 3 年提出了一种基于边折叠的三角网格简化算法i 。算法定义了一个能量函数， 该函数包含三个分量。 ( 1 ) 距离分量矗该分量用于街量简化网格模型与初始网格模型之间的最大误差。误差越 大，丘m 也越大 ( 2 ) 顶点致目分量_ ，该分量用于衡量网格模型中的项点个数。顶点个数越少，越小 c 3 ) 弹性分量昱知，该分量用于衡量简化网格模型中各项点之问的距离。各顶点之间的距离 与初始值相差越大，e ；咖也越大。 总的能量函效为： e = e 缸+ e n 单+ e 币。h i ( 2 - 2 ) h o p p e 算法的基本思路是对网格模型重复进行三种单元操作，直至能量函数达到最小值如图 2 5 所示，三种单元操作为：删除边、拆分边、交换边。 1 l 江南大学硕士学位论文 ( a ) 删除边 ( b ) 拆分边( c ) 交换边 图2 5h o p p e 法三种单元操作 h o p p e 算法由两个嵌套的循环组成外循环依次对所有的待删除边进行如下的操作： ( 1 ) 决定执行那种单元操作； ( 2 ) 计算执行单元操作后的能量函数值e ； ( 3 ) 若e e 。则执行该操作否则不执行 直至能量函数值不再发生变化内循环用于在决定执行那种单元操作后，优化出新顶点的位置。 同其它网格简化算法相比，h o p p e 的算法在简化网格的质量上具有较大的优越性：在模型曲率 较大的地方分布了较多的三角片；沿曲率较小的方向可以分布较长的三角片：较好地保持了特征边 附近的形状等。另外，h o p p e 法得到的简化网格的顶点不一定在初始网格模型上。 1 9 9 6 年，h o p p e 等又提出了渐进网格算法，算法把多边形模型表示成一个最粗糙的网格和一系 列顶点分裂( 边折叠的逆操作) 操作在实时绘制过程中可以通过逐次加入细节生成不同复杂度的 简化模型。简化质量非常好，但实现和使用困难，运行时问长。而且不允许改变拓扑结构 q - s l i m 算法 g a r l a n d 等人在1 9 9 7 年提出了q - s l i m 算法【i ，l 。算法采用二次误差度量( q u a d r i ce r o tm e t r i e s , q e m ) 来度量误差，即顶点到其邻接三角形平面距离的平方和来度量误差算法首先计算所有顶点 的o 矩阵，每次选择误差最小的边进行折叠，用折叠边两顶点的0 矩阵作为新顶点的0 矩阵，新项 点的位置是误差值晟小。q - s l i m 算法简单、高速、简化质量高。g a r l a n d 等人后来又把算法扩展到高 维以保持纹理和颜色等特征 后来，有人提出了o s l i m 算法的改进算法“m e m o t y l e s s ”算法改进了q - s l i m 算法算法不考 虑全局误差，仅根据当前简化表面的特征计算局部误差。用保体积的约束选择被折叠的边和新顶点 的位置。算法简化质量较好，效率较高。 离散微分误差度量算法也是对0 s l i m 算法的改进，度量折叠误差时，除了计算q e m 外，还引 入了一阶和二阶离散微分度量，较好的保持了尖锐几何特征