（计算机应用技术专业论文）基于切向的网格平滑算法研究.pdf

河海大学硕i 。毕业论义 摘要 自由曲线和曲面在汽车、家电外形设计和反求工程中有着广泛的应用。在c a d 系 统中，经常用参数蓝线曲面来插值、逼近、拟合测量得到的数据点。然而，由于计算和 测量数据都不可避免的存在误差，由这些数据设计得到的曲线曲面一般都需要进行光顺 处理，以得到符合设计者要求的“美观的”的曲线曲面。对曲线曲面进行光顺处理，是 c a d 中一个重要研究方向。 尽管实际工程中，分段多项式面片在自由曲面造型设计中仍有着广泛的适用，随着 计算机软硬件技术的发展，用三角网格曲面来对各种复杂三维实体进行重建已经得到了 广泛的利用。通过计算机构造得到的几何实体往往包含不合人意的噪声和小的扰动，如 何在保证曲面原有几何特征的基础上去除这些噪声和扰动是一个重要的课题。 本文给出了一系列网格平滑的算法，并给出了防止过度平滑及加强曲面特征曲线的 方法。对多边形曲面的平滑和去噪声有两种最常用的方法：最小能量函数法( 通过曲面 的微分几何特征构建函数) 和拉普拉斯平滑方法。在文中，分别讨论了拉普拉斯平滑及 其改进算法、平均曲率流、p d e 方法及基于方向的平滑算法。选取实际几何造型进行平 滑处理，分析其去除噪声、扰动和高曲率的情况，曲面的几何特征的保持情况等。比较 了各算法的运行时间，如何以最快的时间达到最好的平滑效果是工程设计上所希望得到 的。 本文主要提出了基于主方向的平滑算法，并结合平均曲率流算法和法向滤波算法进 行了改进。此平滑算法能够较好的保持曲面的几何特征，防止曲面特征磨光的情况，并 能使得曲面原有的特征曲线得以保持。此算法仍是个线性算法，效果不错，运行速度 较快。 【关键词】三角网格曲面、平滑、平均曲率流、滤波、主方向、拉普拉斯算子 河海大学硕士毕业论文 a b s t r a c t f r e e - f o r mc u r v e sa n ds u r f a c e sa r ew i d e l yu s e di ns h a p e d e s i g na n d r e v e r s e e n g i n e e r i n g i nc a ds y s t e m ，p a r a m e t r i cc u r v e sa n d s ur f a c e sa r eu s u a l l ya p p l i e dt o i n t e r p o l a t e ，a p p r o x i m a t ea n d f i tt h eg i v i n gd a t a n e v e r t h e l e s s ，a se r r o re x i s t sw h i l e m e a s u r i n g a n dc a l c u l a t i n gd a t a ，i ti sn e c e s s a r yt od o f a i r i n go p e r a t i o n so n t h ec u r v e s a n ds u r f a c e so b t a i n e db yt h e s ed a t a ，t h u st og e tt h ea e s t h e t i cc u r v e sa n ds u r f a c e s ， f a i r i n gc u r v e sa n d s u r f a c e si sb e c o m i n go n eo ft h em o s t i m p o r t a n tp r o b l e m s i nt h e r e s e a r c ho fc o m p u t e r a i d e dd e s i g n a l t h o u g hp i e c e w i s ep o l y n o m i a lp a t c h e s a r es t i l lt h e d o m i n a t i n gf r e e f o r m s u r f a c er e p r e s e n t a t i o ni ne n g i n e e r i n ga p p l i c a t i o n s ，t h eu s eo ft r i a n g l em e s h e sh a s b e c o m e i n c r e a s i n g l yi m p o r t a n t - - e s p e c i a l l y w i t ht h er i s i n gc o m p l e x i t yo f3 dm o d e l s a c o m p u t e rg r a p h i c so b j e c tr e c o n s t r u c t e df r o mr e a l - w o r l dd a t ac o n t a i n su n d e s i r a b l e n o i s ea n ds m a l l s c a l eo s c i l l a t i o n a ni m p o r t a n tp r o b l e mi sh o wt or e m o v et h en o i s e a n do s c i l l a t i o n sw h i l ep r e s e r v i n gd e s i r a b l eg e o m e t r i cf e a t u r e so ft h eo b j e c t t h e p a p e rp r e s e n t sas e to fm e s hs m o o t h i n gt o o l sd e v e l o p e dt oi n c r e a s em e s h r e g u l a r i t y ，r e d u c eo v e r - s m o o t h i n g ，a n de n h a n c e c r e a s el i n e s t w oo ft h em o s t p o p u l a ra p p r o a c h e s f o rs m o o t h i n ga n dd e n o i s i n gp o l y g o n a ls u r f a c e sa r e m i n i m i z i n g e n e r g yf u n c t i o n a la s s o c i a t e dw i t hd i f f e r e n t i a l g e o m e t r i cs u r f a c e c h a r a c t e r i s t i c sa n d l a p l a c i a ns m o o t h i n g i nt h i sp a p e r ，w ed i s c u s sl a p l a c i a ns m o o t h i n ga n dm o d i f i e d m e t h o d s 、m e a nc u r v a t u r ef l o w 、p d em e t h o da n dt h e s m o o t h i n gm e t h o db a s e d o n d i r e c t i o n s s m o o t hg e o m e t r ym o d e l s b yd i f f e r e n ta l g o r i t h m ，a n a l y s e st h es m o o t h i n g s u r f a c e sa n dc o m p a r et h ee f f i c i e n c y w eh o p et os m o o t hm e s hs u r f a c e si nl e s st i m e a n dp r e s e r v ed e s i r a b l eg e o m e t r i cf e a t u r e so ft h eo b j e c t w e p r e s e n tas m o o t h i n ga l g o r i t h mb a s e do nt h em a i nd i r e c t i o nc o m b i n e dw i t h m e a nc u r v a t u r ef l o wa n dn o r m a lf i l t e rm e t h o d o u rm e t h o dp r e s e r v e sd e s i r a b l e g e o m e t r i c f e a t u r e sa n dp r e v e n tf r o mo v e r - s m o o t h i n g i t sl i n e a ra n df a s t 【k e y w o r d s lt r i a n g l e m e s hs u r f a c e 、s m o o t h i n g 、t h em e a n c u r v a t u r ef l o w 、f i l t e r 、 m a i nd i r e c t i o n 、l a p l a c i a no p e r a t o r 2 河海大学硕士毕业论文 第一章绪论 1 1 引言 随着计算机的软件及硬件技术水平的发展和普及，计算机图形学( c g ) 、计算机辅 助设计与制造( c a d c a m ) 技术也得到了迅猛的发展，它们推动了许多领域的设计革命， c a d c a m 技术的发展和应用水平已经称为衡量一个国家现代化水平的重要标志之一。 计算机辅助几何设计( c a g d ) 作为c a d 的一个重要分支，主要研究在计算机图像系统的 环境下对曲线、曲面及三维实体信息的表示、逼近、分析和综合。产品设计的形状、大 小及类型的多样性和复杂性需求推动了c g & c a g d 技术的发展。 计算机图形学( c g ) 是研究由非图像的信息产生图像，并研究其各种应用的- - r - j 学 科。计算机图形学是- - i - j 综合性的新兴学科，它的研究对象是图形，是借助计算机产生 图形图像的艺术和科学。计算机辅助几何设计( c a g d ) 是随着航空、汽车等现代工业发 展与计算机的出现而产生与发展起来的- r 新兴科学。在1 9 7 1 年，英国的f o r r e s t 1 首 次提出了c a g d 是对几何外形信息的计算机表示、分析和综合，研究的是计算机表示以 及用计算机控制有关形状信息的问题。苏步青【2 1 进一步指出，c a g d 是代数几何、微分 几何、函数逼近论、计算数学和数控技术的边缘科学。其应用范围除了航空、造船、汽 车这三大制造业外，还涉及c a d ，c a m 、建筑设计、生物工程、医疗诊断、航天材料、 电子工程、机器人、服装鞋帽模型设计等技术领域。随着计算机图形学的发展，c a g d 还广泛应用于计算机视觉、地形地貌、军事作战模拟、动画制作、多媒体技术等领域。 1 2 研究背景 c a d 中由已知曲线或曲面的数学方程生成的曲线曲面称为规则曲线曲面，例如柱、 锥、球面等，常用隐函数或二次方程的显函数来表示。但在汽车、轮船、飞机、模具、 艺术品等产品设计中，存在大量的曲线曲面是不能用二次方程来描述，这类曲线曲面称 为自由曲线( f r e ef o r mc u r v e s ) 和自由曲面( f r e ef o r ms u r f a c e s ) ，这些是计算机辅助 几何设计所研究的主要几何形状。用参数形式来表示自由曲线曲面是一种重要的几何造 型方法，其广泛应用于汽车、家电外形设计及反求工程中。而近几年，在国内国际，采 用网格近似表示曲面的几何造型技术得到了越来越广泛的使用。从而，网格细分、光顺、 6 河海大学硕士毕业论文 简化等技术也得到了很大的发展。 在计算机辅助几何设计中，自由曲线曲面往往由离散数据通过指定的调配函数表示 成连续的参数形式。但这种连续的信息一旦用于实际，如在计算机屏幕上或在绘图仪上 绘制出来，或者用数控机床进行加工，还需要将连续的模型离散化。这是一个“离散一 连续一离散”的过程。然而，以连续表示作为中间媒介有时并非必要，而且还增加麻烦， 降低效率。相反，放弃连续模型，直接从离散数据表示、操作曲线曲面更适合于显示、 加工和求交计算等，也更适合于外形设计。直接从离散到离散的造型方法与传统方法不 同，它通常没有显式表达式，仅提供一个算法描述过程，用以产生加密的离散点列或点 阵来表达曲线曲面的信息。在计算机图形学和几何造型中，经常用三角网格来描述物体 模型。这主要是因为一些图形硬件支持三角形的绘制。另外很多可用的数据都是网格 数据( 如用测量方法得到的地形数据是正规四边性网格数据或散乱点数据，可视化中很 多初始数据也是以网格数据的形式存在的) 。 网格模型通过曲面重建得到，曲面重建是根据已有曲面去构造反映其形状的数学模 型，在工程上又称之为逆向工程( r e v e r s ee n g i n e e r i n g ) 。曲面重建的基本要求是准确易 行。准确：要求建立起来的数学模型比较准确地反映原来曲面的形状，或者较好的逼近 原来的曲面，此时需要用细分和平滑的技术；易行：要求所建立起来的数学模型易于进 行各种操作，或者能较方便地适用于计算机进行血面的存储、分析、计算和绘制等，即 可对重建得到的网格进行简化。对曲面重建得到三角网格模型的处理方法主要有三大 类：缅分、简化和平滑。 运用曲面细分的方法可为拓扑网加入新的点形成新的拓扑网，不断递归地进行此过 程，一层层的拓扑网就形成了拓扑网的序列。在一定条件下，拓扑网的序列将收敛于一 张通过采样点的插值曲面。 曲面重建需要采集大量的数据，建成的模型一般都很复杂。随着测量设备精度的提 高，由三维模型重构方法得到的三角形网格模型通常由上万个、几十万个，甚至几百瓦 个三角形面片组成。这样大量的数据给图形的实时显示、数据的存储与传输都带来麻烦 和困难。为此，需要对重建得到的复杂的数学模型进行简化，以减少数据量，减少数据 模型的复杂程度。一般称此工作为曲面简化。其代表性的方法有：去点法、去边法、优 化法、最大多边形法和多分辨率方法。 在计算机辅助几何设计中，消除几何实体造型的某些不合人意的特征的方法称之为 平滑处理。曲线曲面的平滑处理是c a g d 的一项重要内容。商家在设计产品时，产品的 8 河海大学硕士毕业论文 外观是否美观，对产品的销售有重要影响( b u r c h a r d 【3 】) 。因此设计者需要对起初得到 的比较粗糙的几何造型进行处理。在计算机辅助设计和计算机图形学领域，光滑表面的 设计与实现有着重要意义，然而实际重建出的模型却往往含有不必要的噪声。这些噪声 可能来自于模型中存在的一些尖锐特征、小洞、高曲率等，也可能是由于模型生成算法 本身存在局限，采样率低也会造成模型的精度不够。如何消除这些噪声并保持模型的几 何特征已成为目前计算机图形学中的一个热门课题。 1 3 本文的主要研究内容 本文研究的主要内容主要包括一下几个方面： 介绍网格曲面的各种平滑算法及其具体应用。迄今为止，人们已经提出了多种平滑 算法。如工程上用的最广的l a p a l a c e 平滑算法【4 l 、基于法向的平滑算法【5 】、基于平均 曲率流的平滑算法【6 】及各向异性的平滑算法f 1 等。对重建三维模型进行平滑处理时， 希望能在保证曲面原有特征的情况下，使曲面显得更为光顾。同时，希望算法能尽可能 的简单快捷。因而，需要针对具体的情况，根据实际需要，对三角网格曲面采用最合适 的平滑算法。 对平滑算法进行比较，阐述本文算法提出的实际意义。 详细介绍本文算法。 通过实际例子比较各平滑算法。分析各算法的性能。 1 4 论文结构 本文主要讨论由曲面重建得到的三角网格模型的的平滑方法。由于计算和测量实际 数据点时不可避免的会存在误差，同时，在实际重建时，也会出现不光顺的情况，所以 需对网格曲面进行处理。 本论文共分五章，各章内容安排如下： 第一章绪论。介绍本文的研究背景和研究内容。 第二章介绍前人工作，对平滑算法进行比较、分析。 第三章提出以切向为基准对三角网格曲面进行平滑处理。 第四章通过具体例子比较各种平滑算法的运算速度和处理效果。 7 河海大学硕士毕业论文 第五章对全文的工作、创新点和理论、实际意义做一个总结，并且展望今后的 研究工作。 8 河海大学硕士毕业论文 第二章三角网格曲面的平滑算法 2 1引言 在计算机辅助设计和计算机图形学领域，光滑表面的设计与实现有着重要意义。然 而，通过实际采样点重建得到的几何实体造型往往会存在不合人意的噪声或小的扰动。 如何在保证造型必要的几何特征的基础上去除噪声和扰动已成为目前计算机图形学中 的一个热门课题。 2 1 1 相关工作 目前，对多边形曲面的平滑和去噪【9 】有两种最常用的方法：最小能量函数法( 通过 曲面的微分几何特征构建函数) 【1 0 】和l a p a l a c e 平滑方法。最小能量法通常计算量大而 且复杂，并且，最小能量法难以对某些局部形状的需要进行调节与控制。l a p a l a c e 平 滑具有简单、快捷的优点，因而在工程上通常采用此种平滑方法。拉普拉斯平滑流可以 看成是一个简化的二次函数的梯度下降流，因而，可对拉普拉斯平滑流作改进。 t a u b i n 1 1 提出给算子一正一负两个权重，其中负的权重在数值上比正的权重大。 此种平滑算法不会引起曲面的收缩变形，塔通过负的权重来控制曲面的收缩。当正负两 个权重的值在数值上相等时，t a u b i n 的思想就变为双拉酱拉斯平滑，双拉普拉斯平滑 可看成是对能量函数快速下降方法的一种近似离散方法。 对l a p a l a c e 算法的更进一步的发展是通过平均曲率流【1 2 】来对网格作平滑处理。 基于数学和材料科学提出平均曲率流的概念，平均曲率流是面积函数的梯度下降流，因 此采用平均曲率流能达到很好的效果。离散的平均曲率流将顶点沿着法向量的方向，以 离散尽是平均曲率的速率进行移动。人们推导出了准确且实用的离散近似平均曲率向量 计算方法，其适用于规则网格和不规则网格。因而，在对几何造型平滑处理时，平均曲 率流和其改进方法得到了越来越多的使用。 网格曲面是一种细分的具有连通性的结构，因而，作者给出的网格平滑算法都是离 散的方法。网格光顺不同于平滑曲面的光顺，用网格来逼近某个曲面，是一种离散的曲 面造型方法。对三角网格曲面进行光顺，有两方面的要求：外部光顺和内部光顺。外部 光顺性质要求由三角网格逼近得到的近似曲面的瞌率分布比较均匀，这就需要对曲面上 高曲率部分进行处理，k o b b e l t 1 3 等人就采用了p d e 方法【1 4 】对平均曲率作优化。但 9 河海大学硕士毕业论文 对应给定拓扑结构和连通性的网格【1 5 j ，仅外部光顺是不够的，网格顶点的分布还需满 足一定的要求，作者称之为内部光顺【1 6 l 。对几何造型做平滑处理时，如果不把内部光 顺考虑在内，就很难得到一个稳定的网格平滑算法。对网格光顺处理时，需同时考虑这 两方面的光顺性。 2 1 ，2 曲面光顾标准 在工程应用中，由分段多项式生成曲面片仍然是自由曲面重建的主要方法，但随着 三维模型复杂性程度的提高，三角网格曲面得到了越来越广泛的使用。在c a d 系统中， 光滑曲面的设计与实现有着很重要的意义，但实际重建得到的三维网格造型往往有噪 声，如何去除这些噪声并保存模型的几何特征的研究具有重要意义。 在计算机辅助设计中，曲面是光顺的，除了满足c 1 连续条件外，还需使得选定的 曲面光顺度量函数取值最小。选取光顺度量函数，使其取到最小值，是一种传统的保证 蓝面光颁性质的方法。对曲面光烦标准的研究已经有了很长时间，大致有以下三种： 1 能量标准 许多曲面的光顺方法，和曲线的光顺方法完全类似，要求曲面对应的二次能量函 数最小化，曲面的曲率分布趋于平缓，这种光顺方法能保证曲面的几何不变性，且求 解的一般是一个线性问题。 2 高次标准 由于二次度量标准存在一个很大的缺点，它往往会导致曲面的过度平坦，从而使得 曲面的某些特征被模糊处理了。针对这种情况，研究者采用了更高次的度量标准，采用 这种标准，仍能保持几何不变性，一般需解决一个非线性问题，或者采用参数化拟合并 转化为线性问题【1 7 1 。 3 基于方向的标准 近来，人们提出了基于方向的光顺度量方法，其目的是把各向异性的性质应用于 曲面形状的改变，即在某个参数化方向上，曲面的调整幅度要大于其他地方，这种调 纂方法，有利于曲面上某些特征的加强。 2 2 几种平滑算法 河海大学硕士毕业论文 在本节中作者介绍几种三角网格曲面的平滑算法：l a p a l a c e 平滑、t a u b i n 平滑、 双l a p a l a c e 平滑和平均曲率流方法，并分析其优缺点。 2 2 1 l a p a l a c e 平滑 拉普拉斯平滑应用到有噪声的三维多边形网格，可以迅速有效地消除噪声。拉普 拉斯平滑算法具有简单、快捷等特点，在网格曲面光顺中得到了广泛的应用。其基本 思想是将网格中的每个顶点移向其周围领域重心的位置。对于网格中的每个顶点，定 义一个“伞状”算子： 肌索军坦廿 ( 2 2 ” 其中q f 为p 的一重领域上的网格点，w i 0 ，然后可以对三角网格曲面上的任意内部 点进行更新： 只。= p + 五p( 2 2 2 ) 其中五为一个很小的正数，应用( 2 2 2 ) 对网格点不断更新，网格曲面会趋于平缓，称这 种算法为拉普拉斯平滑算法。 q i 圈1l a p l a c e 平滑算法图解 权重w 的选取方法有很多种，最简单的方法是令= 1 ，则： p = 去；q l p 3 ) 其中行为p 的一重领域上的网格点的个数。也可选取w j = l i p q 旷，此种选取方 法往往能带来更好的平滑的效果。 河海大学硕士毕业论文 需要提出的是，若选取w = l ，l a p a l a c e 平滑会是的三角瞬格的分布趋于均匀，而 选取w i ；胪一q 则会破坏网格的均匀分布的特性。然而，采用第一种权重选取方法 对非均匀分布网格模型进行平滑处理时会导致曲面变形，从而破坏了曲面原有的特征。 拉普拉斯平滑算法具有简单、快捷等特点，在工程中得到广泛的使用，但用此算 法对三维网格模型多次处理后，曲面会出现变形、收缩等情况，且曲面的某些特征会 给过度磨光。 2 2 2t a u b i n 的方法 由于拉普拉斯平滑算法容易引起曲面的收缩，t a u b i n 对其算法进行了改进。给算 子一正一负两个权重，通过负的权重来控制曲面的收缩变形。 k 三o p 乏翌娑叫p ( 2 2 4 ) = 一扯一a & p 一础p 舯胪胁0 脚5 袁e w i 蛆珊。 当选取w = 1 或w i = i i ? - e , i i 。时，平滑效果最好。相比l a p a i a 平滑，t a u b i n l 舫 法能更有效的控制曲面的收缩变形的情况。但同样的，如果对于网格点分布不均匀的 几何模型，其平滑效果并不是非常理想。 2 2 3 双拉普拉斯平滑 双拉普拉斯平滑是t a u b i n 方法的一个特例，其选定_ = 五 0 ，双拉普拉斯平滑是 对能量函数快速下降方法的一种近似离散方法。 t a u b i n 和双拉普拉斯平滑算法都是在拉普拉斯算法的基础上改进而来的，从某种 程度上克服了拉普拉斯算法的局限性，但在对曲面的特征的保持等方面还是有所欠缺。 2 2 4 平均曲率流算法 d e s b r u n 1 7 首先用曲率流来引导对网格模型的平滑，将顶点沿着法向量的方向， 以平均曲率的速率进行移动。定义h ：e 离散平均曲率，n 是网格点的单位法向量，平均 曲率流方法可趴看作是拉普拉斯平滑的推广。其网格点如下更新： = p + m t ( p ) r ( p )( 2 , 2 5 ) d e s b r u n 1 8 等人给出了准确且实用性强的近似计算平均曲率向量的离散方法。对于网 1 2 河海大学硕士毕业论文 格点p ，兵j 丘1 以半均固翠同囊为： 砺= 一百v a ( 2 2 6 ) 其中4 ；4 为包含网格点户的三角网格的面积之和。通过推导，d e s b n 【1 9 】等人给 出了用网格点p 的一重领域来表示的法向平均曲率向量的近似离散公式： 日( p ) 菇( p ) = ( c o t 啦+ c o t 屈) ( q 一尸)( 2 2 7 ) 其中，屈表示与边( q ，p ) 相对的两个角，如图所示。 圈2 平均曲率流算法图解 式( 2 2 7 ) 对于计算不规则网格的平均曲率向量同样准确且实用。虽然平均曲率流方法有 很好的平滑效果，但同时，其使得网格分布变得更为不均匀。 2 2 5 改进的平均曲率流算法 d e s b r u n 同时还对平均曲率流算法进行了改进，采用后向欧拉方程，通过求解稀疏 线性系统，加速收敛过程，减少迭代次数，取得了较好的效果。但是，对于用到简单 的后向欧拉方程来进行平滑处理，如果不考虑其稳定性，并没有明显优于欧拉公式。 对于迭代次数比较多的时候，欧拉公式不稳定，而后向欧拉公式不精确。如果纯粹考 虑稳定性，最好使用c r a n k - n i c h o l s o n 方法f 2 | 。 对网格曲面作平滑处理，需要考虑两个方面：外部光顺和内部光顺。即希望曲面 平滑且网格能均匀分布。由于平均曲率流的平滑方法使得网格点的分布更加不规则， 因而对其进行改进，通过法向厅来平滑多边形表面，切向g r 来均匀网格。采用离散 平均曲率流【2 1 】和拉普拉斯箅子【2 2 】对网格作规贝4 化处理f 2 3 】。一个可行的实现方法是 河海大学硕士毕业论文 令： 厢= 肺和g - = c 【p 一( a p a ) a 】( 2 2 8 ) 这里p = 击q l p ，c 是一个正的常数，可以证明a p - ( a p 元沛是一个在切平 j 面上的方向矢量，通过此近似表示方法可以对网格点进行更新： 卜+ 五 日( ) 元( ) - i - c 【( ) 一( ( ) - 筇( ) ) _ i i ( ) 】) ( 2 2 9 ) 对于网格点均匀分布的曲面，采用上面公式得到的平滑效果和平均曲率流方法一 样。对于不规则网格 2 4 1 ，采用平均衄率流方法使得网格点的分布更不均匀，不能够满 足网格曲面内部光顺的要求。而采用改进的平均曲率流算法，通过切向调节调整网格点， 使得网格点的分布趋于均匀，从而得到更好的效果。 这里可以定义常数c 作为一个曲面的曲率函数来达到更好的网格点分布情况。根据 作者的经验，采用下面的平滑设计方法能产生较好的效果： 令历2 旷 目作为平均曲率向量腑和历之间的角c o s o = 扁廊l l 。在三维 空间中，向量历的定义类似于二维空间的中间方向的概念。算法的根本思想是沿着中间 方向移动顶点，这样法向速度就等于平均曲率。然而，对于鞍点的中间方向向量币和平 均曲率向量廊沿法向方向可能正好相反( 例如：0 石2 ) ，如图， 作者可以利用下面的方法： 釉 圈3 改进的平均曲率流 湃海大学硬士毕业论文 卜+ 舻( ) 其中f = 矿c o s 0 占 矿c o s 0 - e 引c o s 6 1 s f ( 2 2 1 0 ) 窖是一个很小的正常数。如果法向量和中间向量几乎垂直成一直角，不需要移动顶 点。根据作者的经验，选择占= 0 1 能产生比较好的结果，并且与网格点的分布无关。 上面定义的速度函数f 是不连续的，平滑时可能产生潜在的不需要的噪声。然而， 就目前而言，在数学实验中还没有遭遇到这样的问题。 2 2 6 法向滤波平滑算法 y a g o u 2 5 等人提出了通过法向滤波来进行网格光顺的方法。考虑三角网格，设r 是一个三角面片，赢叮) 是t 的单位法向，a ( t ) 表示t 的面积，c ( t ) 是t 的中心点。定 义口) 是和r 有公共边的三角面片的集合。采用如下方法作法向滤波并更新顶点： 1 、计算每个三角网格r 的法向j i ( r ) 。 2 、计算每个三角网格t 的单位加权法向量历仃) ： 即) 2 爱1 而善掳鸱) 卜黼 3 、更新网格点p ： 卵+ 南娴v ( d 其中d = ( p c 币( 刁( r ) 2 ：2 7p d e 方法 网格曲面的光顺算法主要有能量最小化算法和拉普拉斯光顺算法两大类。采用能 量最小化算法，计算量比较大，并且难以达到局部光顺的要求。s c h n e i d e r 等人把能量 函数最小化问题转化为一个求解p d e 的问题，得到的p d e 是四次的，为了提高算法的 速度，把四次的p d e 问题分解成两个二次问题。 1 5 苈一旧陵刚 磐。 河海大学硕士毕业论文 ( ! )a 。日( 尊 ) = o ，吼是内都点 ( ) 丑( g 。一) = h ( q 。) 此p d e 算法的局限性是只能对规则网格进行处理。s c h n e i d e r 2 6 2 7 2 8 2 9 3 0 】 等人在此基础之上对p d e 算法作了改进，使其能对不规则网格也能作平滑处理。 2 3 算法分析与结论 上文作者给出了各种平滑算法，针对不同的网格曲面，采用各平滑算法可能会得到 不一样的结果。一般，对网格曲面作平滑处理，作者希望解决一个线性问题，所有的平 滑算法都是基于解决个线性问题的基础之上。 拉普拉斯平滑方法在实际工程中应用的比较广泛，它能比较快速的对网格曲面作平 滑处理，但其也存在缺点，例如。容易引起收缩、几何特征过度磨光等。因而t a u b i n 等人对拉普拉斯平滑流【3 1 l 作了改进，尽可能避免这种情况的产生。而平均曲率流的提 出，则是网格平滑算法的又一个里程碑，它可以有效去除曲面上的高曲率分布【3 2 l ，从 而达到光顺的效果。而平均曲率的简单准确的求解公式的提出，使得平均曲率流算法变 得简单易行。但在平滑不规则网格曲面时，平均曲率流算法使得网格点的分布更加趋于 不均匀，因而提出了改进算法，增加切向的调整因子【3 3 1 ，在下文中，作者也提出了一 个改进算法，希望增加主方向的调整因子，来控制曲面的内部平滑的情况。近来，基于 方向的标准在平滑算法中得到了广泛的应用，希望把各向异性的性质用于曲面形状的改 交，有利于曲面某些方向上特征的增强。基于法向的滤波算法【3 4 j ，就是在这种思想基 础上形成的。而本文提出了基于主方向滤波的算法【3 5 】以及各改进算法也是基于这样的 考虑基础上的。 河海大学硕士毕业论文 第三章基于主切向的网格平滑算法 3 1 引言 随着计算机软硬件的发展，网格曲面造型技术得到了长足的发展，相应的，人们对 曲面的复杂性、美观等方面的也提出了更高的要求。人们希望根据实际测量的数据点重 建得到“合人心意”的几何实体，然而，由于测量得到的数据难免存在误差，以及重建 技术本身的局限性，得到的几何造型往往存在不如人意的地方，在曲面上会有小的扰动 或者噪声。这些噪声可能来自于模型中存在的一些尖锐特征、小洞、高曲率等，也可能 是由于模型生成算法本身存在局限，采样率低也会造成模型的精度不够。医而需要对曲 面做平滑处理，如何在保证曲面的本身特征的情况下消除特征已经成为当前计算机图形 学研究的一个热门话题。 尽管分段多项式面片1 3 6 1 仍然是实际自由曲面重建工程中的主要方法，三角网格曲 面也得到了越来越广泛的重视，尤其常用于设计一些比较复杂的3 d 模型。自由曲面重 建过程要求得到美观的几何实体( 整体曲率分布均匀等) ，作者称之为平滑处理。对于 三角网格曲面这种优化处理包含两个方面：首先，网格曲面应该满足外部光顺，例如， 此通过三角网格近似构造得到的曲面的曲率分布应该均匀。其次，网格还需具备内部光 顺的性质，即根据实际需要，曲面中网格点的分布及备小面片的形状应尽可能的好。对 三维网格模型作平滑处理时，希望尽可能的满足曲面的两方面的光顺的要求。 大多数平滑算法在处理网格曲面时，只考虑了曲面的外部光顺的性质，忽略曲面的 内部光顺，然而，曲面的外部光顺和内部光顺是不能分割的，外部光顺会影响曲面的网 格点的分布情况，因而会导致出人意料的结果。解决这种矛盾的一种想法是希望通过曲 面的内在特征来平滑，能分别处理曲面的外部光顺和内部光顺，然而，不幸的是，通过 此种方法得到的不是一个线性问题。一般来说，解决一个线性问题效率比较高且易理解， 而解决一个非线性问题则相当复杂。即使对于一个简化的曲面能量最小函数，仍没有得 到广泛适用的解决方法。 3 2 前人工作 上章已经介绍了前人在曲面平滑方面做的工作。大多数平滑算法都是线性的，线性 算法比较简单而且快捷，但由于其简单性，也会产生一系列问题。例如：外部平滑和最 1 7 河海大学硕士毕业论文 终得到的两格曲面的形状与参数的选取紧密相关，采用线性方法，往往不能区分外部平 滑和内部平滑。如果作者做了内部平滑，则不得不改变参数的选取，因此也影响了曲面 的外部平滑。 曲面光顺的最基本的构建方法往往基于最小化某个光顺准则，常用的方法是最小能 量方法。将此应用于网格曲面，k o b b e l t 3 7 提出了最小能量方法的离散处理。在过去几 年中，除了能量最小化方法，人们已经提出了各种线性网格曲面平滑方法。 应用离散传播流是平滑多边形曲面的一个非常有效方法，拉普拉斯通过下面公式反 复迭代更新网格点： p 。= p + 矬 考虑稳定的因素，发散因素五应满足0 0 a ) w ，。 c 、计算每个三角网格r 的单位加权法向量麻( r ) ： 删。蘑1 而仉蚤黟则r ) 郦，+ 一勰 d 、更新网格点p ： 2 _ + 南钺聊( 3 + 川d 河海大学硕士毕业论文 其中名 0 ，v 叮) = ( p c 威( r ) 垮g ) 。 3 改进的平均曲率流平滑算法 d e s b r u n 提出用平均曲率流和拉普拉斯算子对网格曲面作平滑及规则化处理，令： 席= 厥和g f = c 【凹一( 凹蠢) 蠢( 3 3 6 ) 其中户= 圭q p ，c 是一个正的常数，可知p 一( a y _ i | ) 再仅是一个在切平面上的 方向矢量。而本文通过离散求得的主方向来对网格点进行更新：得到如下表达式： 只。= p + 敏蹶+ c 彳)【3 3 7 ) f 的选取如( 3 3 5 ) 。类似于平均曲率流平滑算法，对于网格点均匀分布的曲面，平滑效 果并没有显著的区别。但对于不规则网格，采用平均曲率流方法使得网格点的分布更 不均匀，容易出现变形的情况。而采用改进的平均曲率流方法，能调整网格分布情况， 但由于其切向的选取并没有选择主方向，平滑时不能完全体现曲面的特征。对于本文 算法，由于选取主方向作为调整的方向，由于其表示啦率变化最快钓方向，钝使得曲 率的分布更趋于均匀，以达到曲面平滑的效果。而且，对整个网格曲面采用主方向进 行调整，能保持曲面原有的几何特征，防止凡何造型的菜些特征剐过度磨光。 类似于改进的平均曲率流平滑，通过常数c 的定义可得到更好的网格点的分布情 况，一股来说，可采用下面的平滑设计方法： 令而= ( q 一勉一小口作为平均曲率向量【5 q 1 蕊积豌之阃的角 c o s 9 = 而脚i f 。算法的根本思想是沿着历移动顶点，这样法向速度就等于平均曲率 【5 1 1 。然而，对于向量廊和平均曲率向量腑沿法向方向可能正好相反( 例如：占 ，2 ) ， 可以利用下面的方法： = + 舻( )( 3 3 8 ) 其中f = j 日i 历 c o s o i 丑| 赢 z 1 玎一o c o s 口 o 矿c o s o s t f c o s o t 慨删s t 丁为很小的正数，由用户定义。由更改过的函数可以看出，只有当0 f ( 尸) i | r 时才 调整网格点。 显然，这种比较简单直接的改进算法适用于任何一种平滑算法。r 是一个很小的正 数，进一步，作者可以考虑r 和每个顶点都相关，对于每个网格点p 给出对应的r ( 力。 例如可以选取r ( p ) 为p 的一重领域或二重领域的网格点的法曲率的算术平均值1 5 0 等。 3 5 小结 本文给出了一种通过主切线方向来调节网格点的平滑算法，其基本思想是把各向异 性的性质用于曲面形状的改变。此种平滑算法能有效避免曲面收缩等情况，能在保持曲 面原有特征的情况下对网格曲面作光顺处理。本文在提出切向滤波的基础上，还提出了 对平均曲率流算法和法向滤波算法的改进，使得曲面的光顺能更好的使用于任意网格且 在对三维几何实体【5 7 】作处理时，即能满足内部光顺，又能达到外部光顺的要求。 本文算法适用于一些较复杂的网格模型，且能较好的保持曲面的原有特征。今后需 考虑的是如何针对具体的情况，选取特殊的权重，以达到更好的保持曲面的几何特征甚 至加强某些特征，增强算法的适应性。同时，算法的时间复杂度也是一个需要考虑的问 2 5 河海大学硕士毕业论文 题，如何提高算法的时间运行速度是一个值得关注的问题。 河海太学硕士毕业论文 第四章算法研究与比较 4 1 算法分析 通过三角网格重建技术得到的曲面难以避免会出现扰动、噪声和高曲率等情况，人 们给出了相应的网格曲面的平滑算法。同传统的自由曲线、曲面不同，网格曲面没有连 续的函数表示形式，其本身是一种离散的表示方法，则其特征值的求解也是离散的方法， 例如平均曲率、主蓝率等。因而其平滑算法也建立于离数的基础之上。 目前，对于网格曲面的平滑算法主要有拉普拉斯算法思想和最小能量函数法两类， 且两者具有一定的联系。在计算机辅助设计中，曲面是光顾的，除了满足c 1 连续条件 外，还需使得选定的曲面光顺度量函数取值最小。选取光顺度量函数，使其取到最小值， 是一种传统的保证曲面光顾性质的方法。 拉普拉斯平滑算法具有简单、快捷的特点，可以迅速有效的去除噪声，但是也容易 引起曲面收缩变形，当网格点分布不均匀，或者迭代次数比较多的时候，曲面容易变形。 t a u b i n 在拉普拉斯算法思想的基础上作了改进。给出一正一负两个权因子【5 8 1 。通过负 的权因子来控制曲面的收缩变形。双拉普拉斯平滑是对能量函数快速下降方法的一种近 似离散方法，相当于t a u b i n 算法的一个特例， d e s b r u n 首先提出用曲率流来引导对网格模型的平滑，将顶点沿着法向量的方向， 以平均曲率的速率进行移动。即使迭代次数比较多，平均曲率流方法能有效避免收缩变 形的情况，然而，当曲面是不规则网格曲面时，网格点的分布会变的更不规则【5 9 l ，从 而不能满足哇甘面的内部光顺的要求。进一步，可对平均曲率流算法作改进，通过增加切 向的调节来控制网格点的分布，取得了不错的效果。 采用能量最小化算法，计算量比较大，并且难以达到局部光顺的要求。s c h n e i d e r 等人把链量函数最小化问题【6 0 1 转化为一个求解p o e m 闳题，得到的p d e 是四次的，采 用p d e 来处理规则网格和不规则网格的平滑。 近来，人们提出了基于方向的光顺度量方法，其目的是把各向异性的性质应用于曲 面形状的改变，即在某个参数化方向上，曲面的调整幅度要大于其他地方，这种调整方 法，有利于曲面上某些特征的加强。例如y a g o u 等人提出的通过法向滤波来进行网格光 顺的方法。 本文考虑通过主方向滤波算法对网格进行平滑处理，有利于主曲率方向特征的加 2 7 河海大学硕士毕业论文 强，同时可结合平均曲率流算法和法向滤波算法，取得了很好的效果。 4 2 算法平滑效果比较 任何一种平滑算法都不可能适用于所有曲面，对于网格曲面的平滑算法，前人已经 做了不少工作，取得了突出的成就。不同的平滑算法，有的可能在处理速度上具备明显 的优点，算法非常简单且易于实现。有的算法在处理规则网格曲面f 6 1 】时取得比较好的 效果却不适用于不规则网格【8 2 l 。有些平滑效果比较好，但是会出现磨光、收缩、变形 等情况。反之，则可能得不到比较平滑的曲面。对于某些复杂曲面来说，由于需要考虑 曲面不同部分的情况，对算法的要求会比较高，希望曲面能具有局部调节的功能，而目 前大部分平滑算法不具备这样的性质。 如何针对特殊的情况和要求，采用比较好的平滑算法，一直是实际工程上希望得到 解决的问题，也是计算机图形学的一个重要发展方向。在本节中，作者针对不同的曲面， 采用各种平滑算法，分析其平滑效果，并进行比较。 4 2 1 简单均匀网格的平滑处理 1 球模型 首先，考虑对比较简单的均匀网格作平滑处理。图( a ) 给出已经处理好的比较平滑 的网格曲面。对图( a ) 的数据点稍作扰动，得到如图( b ) ，对网格曲面( b ) 作平滑处理。 河海大学硕士毕业论文 衰1 简单的均匀期格作平滑处理( 球模型) 从上图各平滑算法比较可以看出，拉普拉斯平滑之后，曲面收缩变形的比较 厉害，而t a u b i n 平滑算法虽然有效地控制了曲面的收缩，但是曲面相比较初始曲 面，仍产生了扭曲变形的情况。采用平均衄率流算法，使得曲面上的曲率分布趋 于均匀，同时，曲面的网格点的分布更为不均匀，因而在曲面上仍有出现棱角f 6 3 】 的情况。采用基于切向滤波的算法，使得曲面的切向沿着特征线分布，取得了不 错的效果。 对于下图给出的网格数据点，其棱