（计算机应用技术专业论文）非结构网格几何质量增强算法研究.pdf

浙江大学硕士学位论文 摘要 摘要 自动网格生成算法产生的初始网格常常包含低质量的网格单元，这影响了后 续数值模拟的精度和收敛性。网格质量增强算法以自动网格生成算法产生的初始 网格为输入，综合运用各种优化方法得到高质量的网格输出结果。它是连接网格 生成与数值模拟的桥梁，在数值模拟全过程中起到非常重要的作用。 本文针对非结构曲面三角形网格和非结构四面体网格这两类最常用的网格 形式，研究了相应的网格几何质量增强算法。主要研究内容包括： ( 1 ) 拓展已有的平面三角网格光滑化算法到三角曲面网格，实现了一类特 征保持的三角曲面网格光滑化算法。通过预先特征提取限制特征点的移动；引入 切平面约束，构建了一类三角曲面网格光滑化问题的优化模型；改进最速下降法， 实现了优化模型的有效求解。 ( 2 ) 结合光滑化算法和基本拓扑操作，实现了一类四面体网格质量增强算 法。通过有效的数据结构设计保证网格拓扑关系的快速查询，提高算法的时间效 率。研究几何光滑化与基本拓扑操作的结合方式，提出了一个综合考虑时间效率 和优化效果的算法流程。 ( 3 ) 改进了原有的多面体构造算法，实现了包含删点功能的多面体构造算 法。调整了原来的小多面体重连算法流程，并将其与基本拓扑操作相结合，实现 了一类新的基于小多面体重连的四面体网格质量增强算法。 关键词：非结构网格，质量增强，几何光滑化，拓扑变换，小多面体重连 浙江大学硕士学位论文a b s t r a c t a b s t r a c t t h eq u a l i t yo fi n i t i a lm e s h e sg e n e r a t e db ya u t o m a t i cm e s hg e n e r a t i o na l g o r i t h m s i su s u a l l yn o tg o o de n o u g hf o rn u m e r i c a ls i m u l a t i o n s ，t h u sa f f e c t i n gt h ea c c u r a c ya n d c o n v e r g e n c eo fn u m e r i c a ls i m u l a t i o n s v a r i o u sm e s hq u a l i t ye n h a n c e m e n ta l g o r i t h m s a r ep r o p o s e dt oc o n n e c tt h em e s h i n gp r o c e s sa n dt h en u m e r i c a ls i m u l a t i o np r o c e s s ， w h i c ht a k ei n i t i a lm e s ha si n p u t ，a n do u t p u tq u a l i f i e dm e s h e s t h e r e f o r e ，t h es t u d yo n m e s hq u a l i t ye n h a n c e m e n ta l g o r i t h m si so fg r e a ts i g n i f i c a n c e i nt h i sd i s s e r t a t i o n ，t h r e e q u a l i t ye n h a n c e m e n ta l g o r i t h m sa r ep r o p o s e da sf o l l o w sf o rt w o m o s tf r e q u e n t l yu s e d t y p e so fm e s h e s ，i e t r i a n g u l a rs u r f a c em e s ha n d t e t r a h e d r a lv o l u m em e s h ( 1 ) ap r e - p r o c e s si ss u g g e s t e dt oa b s t r a c tt h eg e o m e t r i c a lf e a t u r e so ft r i a n g u l a r s u r f a c em e s h e s ，t h u st op r o h i b i tt h em o v e m e n to fm e s hp o i n t ss p e c i f i e da sf e a t u r e si n m e s hs m o o t h i n g t h em o v e m e n to faf r e em e s hp o i n ti sr e s t r i c t e di nt h et a n g e n tp l a n e o fal o c a lm a n i f o l di n c l u d i n gt h ep o i n t w i t ht h i sr e s t r i c t i o n ，am e s hs m o o t h i n g o p t i m i z a t i o nm o d e li sb u i l tf o rt h em o v e m e n to ft h ef r e ep o i n t s ，a n dr e s o l v e db ya d e e p e s td e s c e n ta l g o r i t h m ( 2 ) at e t r a h e d r a lm e s hq u a l i t yi m p r o v e m e n ta l g o r i t h mi sp r e s e n t e db yc o m b i n i n g t h eg e o m e t r i c a ls m o o t h i n ga n dt h eb a s i ct o p o l o g i ct r a n s f o r m a t i o n s o w i n gt oas e to f d a t as t r u c t u r e sf o rt e t r a h e d r a lm e s h ，h i g he f f i c i e n c i e so ft h ei m p r o v e m e n ta l g o r i t h mi s g u a r a n t e e d m o r e o v e r s o m et o p o l o g yo p e r a t i o n sa r ea d o p t e dt oe l i m i n a t ed i f f e r e n t t y p e so f b a de l e m e n t s ( 3 ) an e wt o p o l o g yo p e r a t i o nc a l l e ds m a l lp o l y h e d r o nr e c o n n e c t i o n ( s p r ) i s i n t r o d u c e df o rt e t r a h e d r a lm e s hq u a l i t yi m p r o v e m e n ti no r d e rt ob r e a kt h el i m i t a t i o n s o fb a s i ct o p o l o g yt r a n s f o r m a t i o n s t h es c h e m e so fs m a l lp o l y h e d r o nf o r m a t i o na n d s p e e d u p o ft h es p ra r ed e t a i l e d e x p e r i m e n t ss h o wt h a ts a t i s f a c t o r yt e t r a h e d r a lq u a l i t y i m p r o v e m e n tp e r f o r m a n c ei sa c h i e v e dw i t hc o m b i n a t i o no ft h es p r ，t h eg e o m e t r i c a l s m o o t h i n ga n dt h eb a s i ct o p o l o g i ct r a n s f o r m a t i o n s ， k e y w o r d s ： u n s t r u c t u r e dm e s h ，q u a l i t yi m p r o v e m e n t ，g e o m e t r i c a ls m o o t h i n g ， t o p o l o g i c a lt r a n s f o r m a t i o n ，s m a l lp o l y h e d r o nr e c o n n e c t i o n j i 浙江大学硕士学位论文图目录 图目录 图2 1 模型尖点示意图9 图2 2 复合函数在一维情形示意图9 图2 3 水泵模型l2 图2 4r o c k e r 2 5 模型( 局部) 1 2 图2 5 马模型( 局部) 1 3 图3 1 数据结构继承关系图1 5 图3 2s p i r e 单元17 图3 32 3 、3 2 及2 2 变换示意图1 9 图3 4 四到七边形的每个异构三角划分示意图2 0 图3 5 边变换示意图2 0 图3 6w r e n c h 模型三种优化方式优化前后网格示意图2 4 图3 7g e a r s h a f t 模型三种优化方式优化前后网格示意图一2 6 图3 8p a r t 模型三种优化方式优化前后网格示意图2 9 图3 9w r e n c h 模型用不同质量指标优化前后网格示意图3 1 图3 1 0g e a r s h a f t 模型用不同质量指标优化前后网格示意图3 2 图3 1 1p a r t 模型用不同质量指标优化前后网格示意图3 3 图3 1 2f a l c o n 模型用不同质量指标优化前后网格示意图3 5 图4 1 二维情形下的小多边形划分递归过程示意图3 9 图4 2 二维情形下的小多边形最优划分示意图4 0 图4 3 表征网格面质量的两个距离示意图4 2 图4 4 网格边与不含该边的网格面的两种位置关系示意图4 4 图4 5w r e n c h 模型不同优化方式优化前后网格示意图4 8 图4 6g e a r s h a f t 模型不同优化方式优化前后网格示意图4 9 图4 7r i n g r o l l i n g 模型不同优化方式优化前后网格示意图5 0 i i i 浙江大学硕士学位论文 表目录 表目录 表2 1 优化前后网格质量对比1 1 表3 1 三种优化方式优化效果对比2 2 表3 2 三种优化方式时间性能对比2 2 表3 3 采用不同质量指标优化前后网格质量对比3 0 表4 1 三个模型用不同方式优化后的网格质量对比4 6 表4 2 三种优化方式的时间性能对比4 7 i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得逝江盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂 有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盘姿盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签名： 签字日期：年月日签字日期：年月日 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 研究背景 偏微分方程是对连续物理现象的数学描述。为了在计算机上实现这些物理现 象的模拟，连续的方程必须离散化，在方程的求解域上( 时间和空间) 仅仅需要 有限个点，通过计算这些点上的未知量既而得到整个区域上物理量的分布。目前 求解偏微分方程的主要数值方法n 。5 3 如有限差分、有限体积、有限单元和边界单元 法等都是通过这种方法来实现的。 实现对求解区域的网格剖分是这些数值方法中非常重要的组成部分。当前网 格生成技术睁7 1 已经比较成熟，但自动算法获得的初始网格通常包含有低质量甚至 是畸形的网格单元，这对有限元分析的精度和收敛性有重要影响。因此，研究网 格质量的增强算法非常有必要。 根据内部点的毗邻单元的数目，网格可以分为结构化网格和非结构化网格。 结构化网格的内部点具有相同数目的毗邻单元，具有生成速度快、质量好、数据 结构简单等优点，缺点是只能自动处理比较简单的求解区域。相应的非结构化网 格的内部点具有数目不等的毗邻单元，生成速度慢，但可以适用于复杂的求解区 域。根据在不同方向上是否有不同的伸展度，网格又可以分为各项同性网格和各 向异性网格。本文中主要研究的是非结构化的各向同性网格。 1 2 相关概念和方法 1 2 1 网格几何质量 在网格质量增强算法中的，网格质量指标的选择也很重要，不同的质量指标 甚至会得到完全不同的结果陋州。几何质量关注的是网格的几何特性，特别是网格 单元的几何形态。由于单元的几何形态和数值求解时的离散算法的数值精度和稳 定性通常息息相关，高几何质量的网格是数值模拟必要的输入条件。 浙江大学硕士学位论文第1 章绪论 1 2 2 网格几何质量增强算法 网格几何质量增强算法n 州钔的目的是对于特定的网格几何质量指标，通过一 系列计算，得到质量符合工程应用要求的网格单元。现有的网格质量增强算法有 局部算法和全局算法之分，其中以局部算法为主流。局部算法又包含几何方法和 拓扑方法两类，分别通过移动节点位置和改变局部区域网格拓扑达到提升网格质 量的目的。 1 2 3 几何方法 几何算法又可分为两类，第一类是求平均值的方法，代表方法有l a p l a c i a n 方法和a n g l e _ b a s e d 方法阻等，其中最常用的是l a p l a c i a n 方法。l a p l a c i a n 方 法的计算过程非常简单，只是简单地把网格点的位置移到相邻网格点位置的中 心。这类方法的优点是计算简单，算法效率高，但是由于网格点的移动没有以网 格质量为依据，因此不能保证网格质量一定会被增强，有时会恶化局部网格质量， 甚至产生畸形单元。后来f r e i t a g 。1 4 1 在l a p l a c i a n 方法基础上对节点移动进行 限制，只有当移动后的网格质量优于移动前的网格质量时，才进行网格点的移动， 从而避免了网格质量下降及翻转单元出现的可能，这类方法被称为智能 l a p l a c i a n 方法。这种思路同样适用于很多基于平均化的方法。 第二类方法是基于优化原理的方法口吲，即通过求解以网格节点附近的单元质 量最优为目标的优化问题获得移动后的节点位置，以保证网格质量的增强。 该方法有两个要点：一是单元质量目标函数的选取，二要选用合适的优化方 法。单元质量目标函数的值必须如实代表单元质量的好坏，单元的平移、旋转、 反射、均匀缩放均不应该改变其度量值，否则将带来偏差并使部分低质量的网格 单元得不到优化。在优化方法问题上，可以采用的方法很多，有最速下降法、共 轭梯度法、牛顿法等。 基于优化原理的方法的缺点是计算量大、时间效率低，往往超过l a p l a c i a n 方法的数十倍。后来，f r e i t a g 提出了将l a p l a c i a n 方法与基于优化原理的方法 相结合的方法n h 射，并给出了多种不同的结合方式。该方法在以较少的计算代价 2 浙江大学硕士学位论文第1 章绪论 取得了较好的优化效果，其应用价值已经得到了广泛的认可。 1 2 4 拓扑方法 拓扑方法指的是在同一个三维形体空间( 多面体) 中以一组四面体来代替另 一组四面体来得到网格质量提升。拓扑操作是局部性的，每次的变换只会影响多 面体内的四面体单元的变化、消除或产生。现有的基本拓扑操作n 3 。1 邮主要可以分 为三类：面变换、边变换和边退化。 1 3 目前网格质量增强领域存在的问题 目前网格质量增强领域已有的研究成果已有不少，但是还存在很多问题，大 致可以总结如下： 1 ) 目前已有将几何光滑化应用于平面和三维实体的算法，但还缺乏将几何 光滑化应用于曲面上的成熟算法。主要难点在于由于曲面网格的特殊性，在优化 过程中必须保持曲面特征和形状保持不变，在网格点移动后还必须进行反投影， 而这是在平面和实体网格光滑化算法中不会遇到的问题。 2 ) 在四面体网格质量增强方面己存在两大类比较成熟的优化方法，但是否 将几何方法与拓扑方法相结合，采取怎样的结合顺序以达到时间性能与优化效果 综合最优，目前并没有统一的结论。 3 ) 在四面体网格质量增强领域，一种新的称为小多面体重连( s p r ，s m a l l p o l y h e d r o nr e c o n n e c t i o n ) 的拓扑方法已经被提出，目的是打破基本拓扑变换 形成的多面体包含四面体单元数目太少的限制，进一步提升网格质量。但原有的 小多面体重连操作中的空腔构造过程是不删点的，不适用于局部网格点分布过密 的情形，并且原来的小多面体重连算法仅将小多面体重连与几何光滑化相结合， 以当前四面体网格中体积边长比最小的四面体网格单元为核构造小多面体并寻 找最优的四面体划分，如果质量得不到增强就结束。该流程时间效率高，全局质 量最差的四面体网格单元得到优化，但整体网格质量并没有得到明显增强。 3 浙江大学硕士学位论文第1 章绪论 1 4 研究内容和论文结构 本文针对1 3 节提及的三个问题，有针对性地研究了三类改进算法： 1 ) 针对1 3 节中的第一个问题，讨论了一类曲面三角网格光滑化算法【15 1 。为 了保持曲面的空间形体不变，结合已有的曲面特征研究，提出一套曲面特征自动 识别加手工操作的提取策略。将基于优化原理的光滑化算法应用于曲面网格上， 并结合切平面约束条件和投影操作，实现特征保持的三角曲面光滑化算法。 2 ) 针对1 3 节中的第二个问题，讨论了一类结合几何方法与基本拓扑操作的 四面体网格质量增强算法n 3 。1 钔。在现有的几何方法和基本拓扑操作的基础上，通 过大量例子测试，提出了一个结合几何方法与基本拓扑操作的四面体网格质量增 强算法流程。在此算法流程上设计了不同的质量指标，并得出了不同指标的优化 特性。 3 ) 针对1 3 节中的第三个问题，将不删点的空腔构造算法替换为删点的空腔 构造算法，并改变了原来的算法流程，将小多面体重连与几何光滑化、基本拓扑 变换相结合，提出一个新的基于小多面体重连n 6 。1 7 1 的四面体网格质量增强算法。 基于本章中有关网格质量增强算法的综述，在第二章中提出了特征保持的三 角曲面光滑化算法；在第三章中提出了结合几何方法与基本拓扑操作的四面体网 格质量增强算法；在第四章中提出了基于小多面体重连的四面体网格质量增强算 法；最后在第五章中对本文的整体研究工作进行了总结和展望。 4 浙江大学硕士学位论文第2 章特征保持的三角曲面网格光滑化算法 第2 章特征保持的三角曲面网格光滑化算法 2 1 前言 由绪论的讨论可以知道，现有的网格质量改进算法有局部算法和全局算法之 分，其中以局部算法为主流。局部算法又包含拓扑变换和光滑化两类，分别通过 改变局部区域网格拓扑和移动节点位置达到提升网格质量的目的。光滑化算法又 可分两类，第一类是求平均值的方法，代表方法有l a p l a c i a n 方法和a n g l eb a s e d 1 0 】 方法等，这类方法计算简单，算法效率高，但不能保证网格质量一定会被改进， 有时会恶化局部网格质量，甚至产生畸形单元。第二类方法是基于优化原理的方 法【2 。5 】，即通过求解以网格节点附近的单元质量最优为目标的优化问题获得移动后 的节点位置，以保证网格质量的改进，其缺点是计算效率较低。 f r e i t a g 等【2 。5 】对基于优化原理的网格光滑化算法做过深入研究，并实现了针对 平面三角形网格和三维四面体网格的光滑化程序o p t m s ，但并未将相应算法拓 展到曲面问题。 本章拓展平面光滑化算法到曲面问题，针对曲面问题的特殊难点提出了相应 的求解算法： ( 1 ) 通过预先特征提取限制特征点的移动； ( 2 ) 引入切平面约束，构建了一类三角曲面网格光滑化问题的优化模型； ( 3 ) 改进最速下降法，实现了优化模型的有效求解。 本章结构如下：2 2 节介绍曲面特征分类及识别方法；2 3 节介绍曲面网格质 量指标选取的原则和分类；2 4 节介绍梯度计算；2 5 节和2 6 节为曲面保形的优 化模型建立及求解；2 7 节和2 8 节为数值实验和本章小结。 2 2 曲面特征分类及识别方法 曲面网格光滑化须保持曲面特征n5 1 ，即网格模型中特定的网格边和网格点。 本文算法中，将网格边分成3 类：边界边、脊线边和自由边。只有一个邻接单元 的网格边是边界边；两个相邻单元法向量的夹角大于某个阀值的网格边是脊线 浙江大学硕士学位论文第2 章特征保持的三角曲面网格光滑化算法 边。本文统称边界边和脊线边为特征边，其他边为自由边。 网格点分成4 类：边界点、脊线点、角点和自由点。边界点是边界边的端点； 脊线点是2 条相邻特征边的共享点；角点则指那些被1 条或多于2 条特征边包含 的网格点，此外，两条特征边构成尖角处的节点以及模型中的尖点( 如圆锥的顶 点) 也被定义为角点。通常情况下，边界点和脊线点在曲面网格光滑化时可沿着 约束线移动，角点则严格规定不可移动。为简化算法实现，本文统称边界点、脊 线点、角点为特征点，并规定特征点不可移动。 需要说明的是基于网格点法向量的模型尖点特征识别，如图2 1 所示，如果 网格点法向量与相邻网格单元的法向量的夹角口大于给定阈值，该点为角点，不 可移动。网格点法向量的计算有很多算法，在这里我们选用基于角度的平均权重 ( m w a ，m e a nw e i g h t e db ya n g l e ) 算法n5 1 8 1 ，即在得到相邻网格单元的法向量后， 以网格单元中以该网格点为顶点的角为权值，计算该网格点的法向量，如公式 ( 2 1 ) 所示。 n = n , i = 0i = 0 公式( 2 1 ) 乃、再( ，1 ) 曲面特征识别很复杂，目前尚无完全自动化的解决方案。本文采用简单高效 的基于阈值的算法，通常可识别全部曲面特征，但对复杂模型，可能存在误判或 漏判情形，这可通过界面交互方式由用户纠正。 2 3 网格质量指标选取的原则和分类 基于优化原理的优化方法相比较于基于平均值的优化方法有一个很明显的优 点，根据不同的应用背景可以仅仅选择不同的质量函数而不需要修改问题的模 型。不同质量函数的侧重点不同，优化后的网格质量提升显著的方面也有所不同， 可以根据实际需求选择合适的质量函数阳3 。例如选择周围网格单元内角的s i n 值 作为质量函数，可以显著的消除周围网格单元的最大最小角，并减少小角度内角 的数量，这对于旨在消除小角度内角的实际应用来说无疑很合适。当然也可以选 择周围网格单元最小内角的平均值最为质量函数，这可以最大程度的提高周围网 6 浙江大学硕士学位论文 第2 章特征保持的三角曲面网格光滑化算法 格单元最小内角的平均值，但是在消除最大最小角方面就不如s i n 那么理想。 2 4 梯度计算 基于优化原理的优化过程中，必然会常常用到对应的质量函数的梯度信息。 如何快速准确的计算出在待优化的网格点出对应质量函数的梯度，是优化过程中 非常重要的组成部分。 一般的，计算梯度有两种方式：第一种是通过梯度定义离散近似的求解 ( g ，g ，g ：) ，其中 p ：f ( x + a x , y + a y , z + a z ) - f ( x , y , z ) 6 。 缸 类似地，可计算g 。和g ：的值。只要缸、a y 和止足够小，就可以近似认为求得 的就是在该点的梯度。 第二种方法则是严格的按照梯度的定义精确求解： 耵= ( 瓦a f ，誓，誓) 我们采用第二种方案精确地求解梯度n 引，优点是可以提高搜索方向的有效性， 加速算法的收敛速度。同时，为了避免大量的计算，加速梯度的计算速度，定义 了专门计算梯度的数据结构 t y p e d e fs t r u c td e r i v t y p e d o u b l ev a l ： d o u b l eg r a d p m a x ： ) d e r i v _ t y p e ； 其中v a l 存储梯度定义中函数的值，g r a d 数组存储了耵。实验证明利用 数据结构d e r i v t y p e 计算梯度并不比第一种方法的计算效率差。 2 5 曲面保形的优化模型的建立 平面和三维实体网格光滑化问题的优化模型通常是无约束的，但对于曲面网 7 浙江大学硕士学位论文第2 章特征保持的三角曲面网格光滑化算法 格光滑化，移动网格点时必须控制曲面形状改变在一定幅度内，因此其优化模型 通常是有约束的。本文建立的曲面网格光滑化问题的优化模型是： m i n ( - c i ( v ) ) s t 出+ 缈+ q + d = 0 公式( 2 2 ) 优化变量v ( x ，y ，z ) 是曲面自由点的坐标。目标函数矽( v ) 是包含v 的所有三角 形单元的质量指标： ( v ) 2 懋z ( v 1 其中掰为包含v 的单元总数，z ( v ) 为包含v 的第i 个单元的质量。本文算法 中，z ( v ) 取单元最小角的正弦值。约束条件血+ 砂+ c z + d = 0 定义的是v 点的 切平面，切平面的法向量根据公式( 2 1 ) 计算得到。 2 6 优化模型求解 2 6 1 求解流程 针对公式( 2 2 ) 定义的优化模型的求解，本文改进了常规的用于无约束优化 模型的最速下降法n 们： 1 ) 处理约束条件。通过参数消去法消除约束条件，将公式( 2 2 ) 转换为无 约束优化模型； 2 ) 计算下降方向。z ( v ) 连续可微，但目标函数妒( v ) 是组合函数，某些点处 连续不可微( 如图2 2 ) ，不存在理论上的“最速 下降方向( 即梯度方向) ，2 6 3 节给出了下降方向的计算方法。 3 ) 定义初始步长设为邻接节点间的最大距离，随后通过一维搜索求得移动后 的节点位置1 ，。 4 ) 将1 ，7 投影到原始曲面上，判断移动后局部网格质量是否得到改善，如否， 步长减半。当步长小于一个给定的步长最小值时，停止计算，否则转到( 3 ) 8 浙江大学硕i 学位论文第2 章特保持的j 宿曲日格光滑化算法 图2 1 模型尖点示意图 x 图2 2 复合函数在一维情形示意嘲 2 6 2 约束条件处理 由于约束条件是线性等式，因此可以采用参数消去法。由于a 、b 和c 不可 能同时为0 ，为方便起见，假设a 不等于0 ，切平面方程改写成： x ：州y ，z ) ：- z y - c z 一- d 将上式代入，( v ) ，消除变量z ； ，( v ) = z ( x ，y z ) = f , w ( y ，z ) ，y ，：) = z ( y ，：) f , t v ) 的最速下降方向g ( 呷, , - - g 。, - - g ) 被限制在切平面内，其中g 。和g ：为已知 浙江大学硕士学位论文第2 章特征保持的三角曲面网格光滑化算法 量： 矿蒡，铲警 下面讨论g ，的求解。设v o ( x o ，y o ，z o ) 沿g 移动步长五后得到点v l ( _ ，y l ，z 1 ) ， 则有： 瓴+ 缈o + q o + d = o 公式( 2 3 ) 瓜l + 砂l + q l + d = 0 公式( 2 4 ) 将公式( 2 4 ) 一公式( 2 3 ) 可得： 一b g 。一c g2 g z2 r 2 6 3 下降方向计算 在模型建立的过程中，可以看到组合函数妒( v ) 是单值函数，即在每一个确定 的位置可以取得一个确定的值。但是在实际的计算过程中，如果仅仅计算这个函 数单元的最速下降方向，而不考虑其它质量接近最差值的函数单元，将在很大程 度上降低计算步长步骤的有效性。因此，必须设定一个较小的范围，把质量落在 该范围的函数单元作为最差函数单元的集合，计算集合里每个函数单元的最速下 降方向，从而综合得到一个真正可以提高网格质量的节点移动方向。 如果记最差函数单元集合里的最速下降方向为g ，( v ) ，1 f m ，首先要判断 是否存在可行的搜索方向。所谓可行指的是当网格点沿着该方向移动时，最差函 数单元集合里的函数值全部都变小。这相当于判断是否存在搜索方向使得跟最差 函数单元集合中的各个最速下降方向的夹角都小于9 0 度，也相当于判断是否存 在一个半平面包含最差函数单元集合中的所有最速下降方向( 由2 6 1 知道所有 的最速下降方向共面) 。 如果不存在可行的搜索方向，说明网格点当前位置已经是最优位置，不必对 该网格点继续优化，否则搜索方向为最速下降方向集合的一个最优凸组合，即： 一r m i n gg 1 0 浙江大学硕士学位论文第2 章特征保持的三角曲面网格光滑化算法 其中 s t 屈= 1 ，屈0 g = 屈g 。( v ) l g 上述优化问题可通过二次规划法求解。 2 7 数值实验 图2 3 给出了一个水泵模型，图2 3 ( a ) 和( c ) 是优化前后的曲面网格，图 2 3 ( b ) 是识别出来的曲面特征。图2 4 ( a ) 和( b ) 是r o c k e r 2 5 优化前后的曲面网格。 图2 5 ( a ) 和( b ) 是马模型优化前后的曲面网格。表2 1 则给出了5 个曲面网格实 例优化前后的质量数据，包括全局最小角、全局最大角、最小角平均值、最大角 平均值和最小角分布数据。从表2 1 可以看出，本文算法是行之有效的。每个例 子都得到了明显的优化，各个质量指标都得到明显的改进，特别是3 0 度以下的 角度的比例明显降低。 表2 1 优化前后网格质量对比 浙江 学 t 论文第2 章特保持的j 角曲面m 格光* 化算法 鲁枣鲁 蚕霸 浙江大学硕学位论文第2 章特征保持的三角自i 月格光滑化算法 露黯 ( a ) 优化前的曲面阿格( b ) 优化后的曲面阿格 图2 5 马模型( 局部1 2 8 本章小结 本章在平面三角网格光滑化算法基础上将其拓展到曲面三角网格，解决了出 此产生的曲面特征识别和曲面保形问题。将数学优化原理应用于曲面网格光滑化 问题上，把曲面网格光滑化问题转变成为最优化问题，提出了一种特征保持的基 于优化原理的曲面网格光滑化方法。相比较于基于平均值的优化方法，具有优化 效果好并自动保证了网格有教性的优点。实验结果证明了本方法的有效性。根 据实际应用背景不同，可以仅仅通过改变质量函数束达到不同的优化目的。 浙江大学硕士学位论文第3 章结合几何方法与基本拓扑操作的四面体网格质量增强算法 第3 章结合几何方法与基本拓扑操作的四面体网格质 量增强算法 3 1 前言 由绪论中的论述可以知道，四面体网格质量增强算法中有两大类方法：几何 光滑化和拓扑变换。几何光滑化通过移动网格点的位置但不改变网格拓扑来得到 网格质量的提升，相对的拓扑变换通过改变网格的拓扑结构来达到提升网格质量 的目的。 目前人们对几何光滑化和基本拓扑变换的研究已经比较多，但在四面体网格 质量增强领域还存在的主要问题如下： 1 ) 采取怎样的结合顺序以达到时间性能与优化效果综合最优，目前并没有 统一的结论。 2 ) 优化效率和优化效果还可进一步增强。 本章主要研究内容有： 1 ) 通过有效的数据结构设计保证网格拓扑关系的快速查询，提高算法的时 间效率。 2 ) 研究几何光滑化与基本拓扑操作的结合方式，提出了一个综合考虑时间 效率和优化效果的四面体网格质量增强算法流程。 本章结构如下：3 2 节介绍分层四面体网格数据结构设计；3 3 节介绍常用的 四面体网格质量指标；3 4 节和3 5 介绍已有的基本拓扑变换和几何光滑化；3 6 节提出了一个结合几何光滑化和基本拓扑变换的四面体网格质量增强算法流程； 3 7 节和3 8 节为数值实验和本章小结。 3 2 分层的四面体网格数据结构设计 本章中采用以面为核心的数据结构体系，点数据结构中存储网格点的几何位 置，通过点面、面体数据结构的联系存储网格拓扑信息，网格边信息隐含在面数 1 4 浙江大学硕士学位论文 第3 章结合几何方法与基本拓扑操作的四面体网格质量增强算法 据结构中，没有专门的边数据结构。 下面首先给出数据结构的继承关系图( 如图3 1 ) ，再给出各个数据结构的具 体内容以及之间的关联。 图3 1 数据结构继承关系图 其中v e r t 、f a c e 、c e l l s k e l 、c e l l 类的结构如下( 只列出相关的主要数据成员) ： c l a s sv e r t ：p u b l i ce n t i t y d o u b l ea d l o c 3 ； f a c e 宰p f h i n t ； u n s i g n e di n tu i d i m ：2 ，u i t y p e ：4 ，u i u s e r ：10 ； b o o lq d e l ：1 ，q d e l r e q ：1 ，q a c t ：1 ，q s u r f s t r u c t ：1 ，q s t r u c t ：1 ，q s h a p e o k ：1 ； ) c l a s sf a c e ：p u b l i ce n t i t y c e l l 宰p c l ； c e l l 木p c r ； v e r t 木a p v v e r t s 4 ； u n s i g n e di n tu i l o c ：4 ； u n s i g n e di n tu i u s e r ：10 ； b o o lq s w a p c h e c k ：1 ，q s i z e o k ：1 ，q s t r u c t ：1 ，q s a m e s h a p e ：1 ，q d e l ：l ； ) 1 5 浙江大学硕士学位论文 第3 章结合几何方法与基本拓扑操作的四面体网格质量增强算法 c l a s sc e l l s k e l ：p u b l i ce n t i t y u n s i g n e di n tu i u s e r ：lo ，u i s h a p e c l a s s ：6 ，u i r e g i o n ：i r e g i o n b i t s ，u i t y p e ：4 ； b o o lq s i z e o k ：1 ，q l s d e l e t e d ：1 ，q l s s t r u c t u r e d ：1 ； ) c l a s sc e l l ：p u b l i cc e l l s k e l f a c e 木木p p f f a c e s ； ) 从上面的数据结构可知，网格点和网格面通过f a c e 中的数据成员v e r t 木 a p v v e r t s 4 以及v e r t 中的数据成员f a c e * p f h i n t 关联，网格面和网格单元通过 f a c e 中的数据成员c e l l 木p c l 、c e l l 木p c r 以及c e l l 中的数据成员f a c e * * p p f f a c e s 关联，网格点和网格单元不直接关联，但可以通过网格面为中间结构相关联。 3 3 四面体网格质量指标 四面体网格的应用范围非常广泛，因此不可能存在一种质量指标可以很好的 适用于所有的实际情形。然而网格质量增强程序却被要求在所有的情况下都要工 作的很好。因此网格质量增强程序把四面体单元的质量指标设计为目标函数，对 于不同的例子用户可以从程序提供的质量指标中选择最合适的作为目标函数。由 于程序提供每种的质量指标都有可能作为网格优化的目标函数，就要求质量指标 不仅要能反映四面体单元的质量，并且要容易计算梯度，优化后能明显的提高网 格的质量。下面列出四种研究比较多且已经被证明比较有效的质量指标随3 。 1 ) 第一种为四面体二面角的s i n 值。因为0 度和1 8 0 度的s i n 值都为0 ，因 此这个指标可以同时有效的消除d , - 面角和大二面角。当四面体单元为正四面体 时该指标取得最优值，为a r c s i n ( 2 , 互3 ) ，约等于7 0 5 2 8 7 7 9 度。在f r e i t a g 和 0 1 1 i v i e r g o o c h 的研究中，他们认为四面体二面角的s i n 值是最有效的指标。但 同时该指标也存在一些缺点，比如每个四面体都有6 个二面角，相应的要计算这 6 个二面角s i n 值的梯度，可能会影响程序的运行速度；还有仅对于一个四面体 单元而言，该指标是连续但是在某些点处不可微的；最后这个质量指标不能处理 1 6 浙江大学硕士学位论文第3 章结合几何方法与基本拓扑操作的四面体网格质量增强算法 一类尖顶四面体单元( s p i r e ) ( 如图3 2 ) ，这类四面体单元的二面角很好但是尖 顶处的固体角很小，可能对于应用过程是有害的。 图3 2s p 单元 2 ) 第二种指标为修正的二面角s i n 值。在实际的工程应用中，大角度的二 面角相对于小角度的二面角而言的危害更大，因为会影响有限元计算的精度，由 此提出了修正的二面角s i n 值指标。该指标的计算方法与第一种稍有不同，当二 面角为锐角时，二面角的s i n 值不变；当二面角为钝角时，将二面角的s i n 值乘 以o 7 。现有的研究实践表明，该质量指标在不太影响小角度二面角消除的情况 下，可以明显的消除更多的大角度二面角。 3 ) 第三种指标为体积边长比。该指标由p a r t h a s a r a t h y 、g r a i c h e n 、h a t h a w a y 啪3 提出，计算方法为 6 , 5 善， l 朋 其中 k = 吉( 匕+ 匕+ 匕+ ，三+ 坛+ ，三) ， y 为四面体体积，乙等为四面体6 条边的边长。包含大角度或者小角度二面角的 四面体单元的体积相对于边长来讲都比较小，在以体积边长比为指标时可以得到 有效的消除。为了归一化，将指标的范围调整为0 、1 之间，在前面乘以系数6 2 。 由此，正四面体的体积边长比将为1 。体积边长比是一个很有吸引力的质量指标。 首先，一个四面体只有一个体积边长比，容易计算。其次，对于一个四面体单元 而言该指标处处连续可微，梯度易于计算。最后，相对于二面角s i n 值该质量指 标能更有效消除的尖顶四面体单元。 4 ) 第四种指标为半径比，由c a v e n d i s h 、f i e l d 、f r e y 口提出，计算方法为 浙江大学硕士学位论文第3 章结合几何方法与基本拓扑操作的四面体网格质量增强算法 3 ，尺，其中，为四面体内切圆半径，r 为外接圆半径。同样的为了归一化，将指 标的范围调整为0 、1 之间，在前面乘以系数3 。由此，正四面体的半径比将为1 。 该质量指标并不常用，有如下几个缺点：计算耗时，尤其计算梯度时；虽然对于 每个四面体单元该指标处处连续可微，但对于退化的四面体单元，梯度为0 ，不 利于网格质量的增强：实践表明以体积边长比为目标函数的优化结果在半径比上 超过了以半径比为目标函数的优化结果。因此该指标可以被体积边长比取代。 由于尖顶四面体单元的存在，如果想有效地消除尖项单元，可以选择体积边 长比为目标函数，或考虑二面角的s i n 值和及其修正值。研究表明，体积边长比 和修正的二面角s i n 值在消除大角度二面角方面是差不多的，因此如果想优先消 除大角度二面角可以优先考虑这两个指标。如果想优先消除小角度二面角可以优 先考虑二面角s i n 值。从整体性能上来讲，体积边长比是第一选择。 3 4 基本拓扑变换 拓扑方法指的是在同一个三维形体空间( 多面体) 中以一组四面体来代替另 一组四面体来得到网格质量提升。拓扑操作是局部性的，每次的变换只会影响多 面体内的四面体单元的变化、消除或产生。现有的基本拓扑操作主要可以分为三 类：面变换、边变换和边退化。 面变换重新划分通过一个内部面分隔的由五个网格点组成的两个四面体单 元。由内部面分隔的五个网格点组成的两个四面体单元的不重复重划分方式有很 多种，但是只有两种是