（计算数学专业论文）基于特征的四边形网格生成.pdfVIP

大连理工大学硕士学位论文 摘要 近年来，随着计算机技术的飞速发展，有限元方法已经成为复杂工程问题求 解中最强大的数值分析方法之一。而使用该方法的第一步，也是关键技术之一就 是对给定目标区域的离散，即网格的生成数值模拟结果的准确性和分析速度都 直接受到网格质量的影响，所以研究高质量网格的快速生成，对数值模拟技术而 言，具有非常重要的意义 有限元中常用的两种平面或三维曲面网格是三角形网格和四边形网格，其中 四边形网格无论是在计算精度上还是在收敛速度上，都要优于三角网格因此从 上个世纪八十年代四边形网格生成开始受到人们的重视通过很多工程技术人员 和学者的不懈努力，涌现除了大量有关四边形网格生成的方法根据网格的生成 过程这些方法大致可以分为两大类：即直接方法和间接方法 本文首先从这两个方面对四边形网格的发展现状做了一个简单的综述，同时 介绍了几种比较典型的四边形网格生成方法随后对三角网格上特征的应用，定 义进行简单介绍，并介绍了几种特征的提取方法 据此，本文提出了基于特征的四边形网格生成方法对于一个给定的三角网 格，首先提取出其特征边和特征点然后用p a v i n g 方法在特征附近生成一圈四边 形网格。从而不但可以使得它们在四边形网格的生成过程中不会被删除，而且可 以保证它们周围的四边形网格的质量最后利用q 州o r p h 方法将得到的混合网格 转化为全四边形网格，并用已有的优化方法对得到的网格进行带约束的网格优 化在文章最后给出网格生成的数值实例，结果表明这不但可以很好地保留一些 重要特征，而且提高了特征处的四边形网格质量 关键词：特征；四边形网格；高斯面积；q 叫o r p h 方法 大连理工大学硕士学位论文 q u a d r i l a t e r a lm e s hg e n e r a t i o nb a s e do nf e a _ t u r e s a b s t r a c t i nr e c e n ty e a r s ，砌t h ef h s td e v e l o p m e mo fc o m p u t e rt e c l l n o l o g y ，t h ef i i l i t e e 1 e m e i l tm e t l l o d ( f e m ) h a sb e c o m eo n eo ft l l em o s tp 明，曲la n a l y s i st o o l sa v a i l a b l e i i ls 0 1 v i n gc o m p l e xe n g i i l e e r i n gp r o b l e m s a st 1 1 ef i r s t 鼬印，w b j c hi sa l s oo n eo ft l l e c r i t i c a lt e c h n i q u e s ，i s 也ed i s c r e d z a t i o no f 血eo b j e c tr e 百o n ，i e n l eg e n e r a t i o no fn l e m e s l l t h er e s u no fm ei m 皿旧r i c a ls i m l l l a d o na n d 也es p e e do ft l l ea n a l y s i sa r es t r o n g l y r e l 删t ot l l eq u a l i 够o ft l l ei r l c s h t h e ni ti sv e r yi m p o r 咖tt 0s m d y 也e 伍s tg e n e r a t i o n o fh i 曲- q l l a i 毋m e s hi nt h en 岫耐c a ls i 舢l a t i o n 矗e l d a t r i 缸g 址盯m e 出a l l daq u 枷l a 蛔mm e s ha r ec o m m o l l l yi l s e df o r2 dp l a i l ea n d o v e r3 dc u r v e ds u r f a c ei n 吐1 ef e m q u a d r 主i a t 唧im e s hi i lg e n e r a l 王l a sb e 讹rp r e c i s i o n 蛆dc o n v e 瞎e sf 跚e rt h a l lt h et r i 锄g l l l 8 rm e s h f o rt h a tr e 鹤o n ，l o t so fe n g i n e e r sa n d s c h o l a r sh a v ea t t a c h e d 毋j e a ti i n p d r t a n o nt h eq u a d r i l a t e r a lm e s hg e n e r 8 ：t i o ns i n c e 吐忙 1 9 8 0 s al a r g en 啪b e ro fa p p r o a c h e sh a v eb e e np r o p o s e di nt l l i sf i e l d t h e yc a nb e b r o a d l yc l 船s m e di n t ot w om 洳c a t e g o r i e s ：d i r 鲥趾d 抽d i r e c ta p p m a c h e s i nt h i sp a p e r ，as i m p l e s u r v e yo ft h ed e v d o p m e n to f 也eq u a d r i l a t e r a lm e s h g e n 训o n 谢1 1b eg i v e n 丘d mt h ea ：b o v et 、 ，o 鲢p e c t sf i r s t l y a n dt l l e ns e v e 嘣帅i c a l q 啦m l a 士c r a lm e s hg e n e r a t i o n 叩p r o a e h e sw i l lb ep r e s e m e d a f t e rf h a t ，1 h ea p p l i c a ：c i o n a i l d 也ed e f i i l i t i o no f 也ef e a l ：山e so nt h et r i a n 刚a r 玲s hw i l lb ei 圳b r o d u c e d ，s ob es o m e f b a t i 】r ee x 椭c t i o n 印p r o a c h c s b a s 酣o n “s ，af b a n l r ep r e s e n ，e dq l l a d r i l 8 t e l m 删：s hg e n 删o na l g o i s p r 叩o s e d f i r s n y ，f b a 乜鹏e d g e s 觚df e a m r ep o i m sa r ee x 蚴e d 劬mm eg i v c n 仃i a n g l l l a rm e s h t h c nq u a d d l a t e r a lm e s h e s 硼lb eg e n e r a t e da r o u n dt l l e mu s i n gp a _ v i n g m e t l l o d st o 毋瑚n a n t e et h eq l l a l i 哆o f t h em e s h e sa r o u n dn l e m ，觚dt h e y 、v o n tb ed e l e t e d m 丽n g 也eg e n e m t i o no f 也eq u a d r i l a t e r a lm e s h w e l l a r e r 血瓯t h em 权e dm e s hw i l l b ec o n v e r t e dt 0f l n l y 则枷l a l e r a lm e s hb yq m o 讪m e t h o da n do 砸芏i l i z e dv i ae x i s 吨 o p t i m 幽gm e t h o d sw i m c o 班暗a i n ：t s a tl a s t ，m l m e d c a lt e s t sa r eg i v e n t h e ys h o w 也a t s o m ei n l p o r t 锄tf e a ：七i l r c sc a nb ew e l lp r e s e r v e da n di ti i l d e e di n l p r o v e st l l eq u a l 时o f m e m e s h e sa n ) l j n dt l l e 五巴a 】m s k e yw o r d s ：f e a t u r e ：0 u a d r ii a t e r a l s h ：g a u s sa r e a ：0 。m o r p hr 噼t h o d i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研 究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含 为获得大连理工大学或者其他单位的学位或证书所使用过的材料。与 我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明 并表示了谢意。 作者签名：勉 日期：6 竺堡 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版 权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等 复制手段保存和汇编学位论文。 作者签名：塑塾 翩躲 汪监 五生乏年。l 月2 生日 大连理工大学硕士学位论文 1 绪论 有限元方法是随着计算机技术的发展而在上个世纪七十年代兴起的求解复杂 工程问题的一种近似的数值分析方法，被广泛地应用于工程技术的各个领域：如 固体力学中物体的受力及稳定性分析；流体力学中流场的压力、温度、密度和流 速的分布；传热学中分析热传导速度与温度分布等 该方法的基本思想是将连续的求解区域离散为一组有限数目且按一定方式相 互联系在一起的组合体由于单元能按不同的联结方式进行组合，且单元本身又 可以有不同形状，因此可以模型化几何形状复杂的求解域随着单元数目的增加， 也即单元尺寸的缩小，或者随着单元自由度的增加及插值函数精度的提高，解的 近似程度将不断改进如果单元是满足收敛要求的，近似解最终将收敛于精确解 在进行有限元分析之前，必须对将要分析的几何模型进行网格离散为了保 证计算的准确性，生成的网格的数目、拓扑形状和几何尺寸应该满足原来的模型 以及有限元分析方法的要求，所以有限元网格的合理划分在有限元法中占据着重 要的位置 1 1 网格划分的基本原则“1 划分网格是建立有限元模型的一个中心环节，它需要的工作量很大，要求考虑 的问题也比较多所划分的网格形式对计算精度和计算规模将产生直接影响为 建立正确、合理的有限元模型，这里简要介绍划分网格时应考虑的一些基本原则： 1 1 1 网格数量 网格数量直接影响计算结果的精度和计算规模的大小，因此它应该是首先考 虑的因素一般来说，由于有限元是用离散的网格来近似逼近目标区域，因此提 高网格数量，计算精度也会有所提高但同时增加的还有计算量，所以在确定网 格数量时应综合考虑这两个因素 通常，当网格比较少时，增加网格的数量可以使计算精度有明显的提高，而 计算量增加则不是很明显；当网格数量到达一定程度时，增加网格的数量对计算 精度的提高就变得非常微小，而计算量却大幅增加因此可以通过比较两次计算 结果的误差来决定是否有必要增加网格的数量 分析数据的类型也会对网格的数量产生影响：比如对于仅仅计算结构变形的 静力分析可以使用较少的网格；而在计算应力时，则在同精度下要用比较多的网 基于特征的四边形网格生成 格在计算结构固有动力特性时，如果仅仅计算少数低阶模态，可以选择较少的网 格；而如果计算的模态阶次较高，则应选择较多的网格 1 1 2 网格的琉密 网格的疏密是指在目标区域的不同部分采用大小不同的网格，这主要是为了 适应计算数据的分布特点在计算数据变化梯度较大的部位( 如应力集中处) ，为 了较好地反映数据变化规律，同时也保证计算结果的精确度，需要采用比较密集 的网格；而在计算数据变化梯度较小的部位，为减小计算量，则应该使用相对稀 疏的网格这样，整个结构便表现出疏密不同的网格划分形式采用疏密不同的 网格划分，既可以保持一定的计算精度，又可以尽量减小网格数量因此，应该 在关键部位增加网格数量，在次要部位增加网格不但不必要，而且不经济 疏密不均的网格主要用于应力分析( 包括静应力和动应力) ，而计算固有特性 时则一般采用较均匀的网格这是因为固有频率和振型主要取决于结构质量分布 和刚度分布，不存在类似应力集中的现象，采用均匀网格可使结构刚度矩阵和质量 矩阵的元素不致相差太大，从而可以减小数值计算误差 1 1 3 单元的阶次 许多单元都具有线性、二次和三次等形式，其中二次和三次形式的单元称为 高阶单元选用高阶单元可提高计算精度：因为商阶单元的边界能够更好地逼近 结构的边界，且高次插值函数可更高精度地逼近复杂场函数，所以当结构形状不规 则、应力分布不均或变形很复杂时可以选用高阶单元但高阶单元的节点数较多， 在网格数量相同的情况下由高阶单元组成的模型规模要大得多，因此在使用时应 综合考虑计算时间和精度，而不能一味的追求高阶元 从上述我们知道：增加网格数量和提高单元阶次都可以提高计算精度因此在 精度一定的情况下，用高阶单元离散结构时可以选择相对较少的网格数量，太多 的网格提高的计算精度与增大的计算量相比是微不足道的当然，同一结构也可 以采用不同阶次的单元，即精度要求高的部位用高阶单元，而精度要求低的部位用 低阶单元不同阶次单元之间或采用特殊的过渡单元连接，或采用多点约束等式连 接，不过这样又增加了问题的复杂度 除了上述讨论的因素以外，网格划分还要考虑网格质量、网格分界面和分界 点、位移协调性、网格布局、节点和单元编号等 1 大连理工大学硕士学位论文 1 2 网格的类型 在工程应用中，有限元网格主要有两种：一种是结构化网格( s t r u c t u r e d m e s h ) ，另一种是非结构化网格( u n s t r u c t u r e dm e s h ) 从严格意义上讲，在结构化网格中，所有内部节点都有相同数量的邻近节点 和相同数量的邻近单元，即所有的内部节点都具有相同的度在平面和空间曲面 网格生成中，有代表性的结构化有限元网格是由四边形单元构成的网格；在三维 实体网格生成中，有代表性的结构化网格是由六面体单元构成的网格在结构化 有限元网格生成方法中，映射法是典型和通用的方法，它既可以被用来生成结构 化的四边形单元网格，也可以被用来生成结构化的六面体单元网格 结构化网格的优点是：它可以很容易地实现区域的边界拟合：网格生成的速 度快，质量好；数据结构简单它的最大的缺点是适用的范围比较窄，对于比较 复杂的区域或者物体表面很难生成高质量的计算网格目前高效的全自动结构化 网格生成方法还正在研究当中 在非结构化网格中，对节点放松了要求，允许任意数量的单元在一个节点处 交汇，即所有内部节点的度都可能不同在平面和空间曲面的有限元网格生成中， 非结构化有限元网格的典型代表是三角形网格；在三维实体有限网格生成中，非 结构化有限元网格的典型代表是四面体网格 非结构化网格生成方法的一个突出的优点是它可以适应任意复杂的几何形 体，与几何形体的形状关系不大结合一定的控制方法，可以生成质量很高的单 元，而且利用非结构化网格生成算法可以实现区域网格生成的自动化 值得一提的是，三角形单元和四面体单元并不是非结构化有限元网格的唯一 选择，由四边形单元或六面体单元构成的有限元网格只要节点的度有所不同，此 时的有限元网格仍然是非结构化网格 我们更关注的是非结构化网格的生成，而且后厩如无特别说明，网格仅指二 维平面或者三维曲面上的三角形网格或者四边形网格，我们不讨论三维网格 1 3 四边形网格的质量评价准则 网格质量是指网格几何形状的合理性，它的好坏将影响计算精度，质量太差 的网格甚至会中止计算直观上看，网格各边或各个内角相差不大、网格面不过分 扭曲、边节点位于边界等分点附近的网格质量较好网格质量可用细长比、锥度 比、内角、翘曲量、拉伸值、边节点位置偏差等指标度量 1 上述规则既适用于 基于特征的四边形网格生成 三角形网格，也适用于四边形网格不过我们更感兴趣的还是四边形网格因此 下面我们仅对四边形网格的质量评价准则加以简单介绍： 1 ，3 1 拓扑准则 拓扑准则可以用下面的度量来表示 2 ： ，= 寺i 地) 一d ( 1 1 ) 其中d ( 叶) 表示节点的度( 相邻节点的数目) ，表示网格节点的总数如果v 为 内部节点，则d = 4 ：若v j 为边界节点，则d = 3 如果一个网格其拓扑结构比较 规则，则度量值接近于o 然而那只是理想的情况，实际应用中它般为一个正值， 表示实际网格拓扑结构和理想拓扑结构之间的差距很显然，在网格节点数一定 时，该值越小，则表明网格越规则 1 3 2 几何准则 1 三角形的口因子0 3 三角形彳曰c 的a 因子定义如下： 斫脚冲压高赫 z ， 其中竹是这个三角形的单位法向量，系数2 3 是为了使正三角形的口值取最大 值1 a 因子的直观意义就是三角形面积与边长平方和之比，0 a 1 a 越大， 表明三角形的质量越好一些典型的三角形的a 值如图1 1 ： 笪 图1 1 一些典型三角形的口值 2 四边形网格的口因子。3 四边形单元的形状质量评价准则通常使用卢系数，如图1 2 ，四边形a b c d 的两 条对角线将其分割成四个三角形4 肋，鲋b c ，c d 四和c d 且，令 大连理工大学硕士学位论文 ( a l ，a 2 ，口3 ，口4 ) = a ( 4 b d ) ，a ( 一b c ) ，a ( c d 口) ，a ( c 列) ，假设有a 1 a2 a 3 4 则四边形a 丑c d 的口系数定义为： 图1 2 ( 1 3 ) 其中，凸四边形的卢值在0 和1 之间，矩形的卢值有最大值1 当四边形退化为 三角形时，卢值为0 凹四边形的卢值小于o 一些四边形的卢值如图1 3 ： 圈豳 尹= l，_ o t c o，_ o - 拍，_ 札t声霉0 s 釉 图1 3 一些典型四边形的卢值 3 网格的评价标准d 1 基于三角形的口因子和四边形的口因子， 网格的质量评价因子i 和口： n t l 瓦= ( n a ，) 舸 i _ 1 m l 万= ( n p ，) 叼 l e e 和l o 给出了三角形网格和四边形 ( 1 i4 ) ( 1 i5 ) 基于特征的四边形网格生成 其中r 和 伫分别为三角形和四边形单元的数量l e e 和l o 基于四边形网格 万因子的质量评价表如下： 表1 _ 1 四边形万因子的质量评价表 3 j b 值描述 口 o 3 6无法接受的 o - 3 6 口 o 5 4可以接受的 o 5 4 s 口 0 7 2好的 口o 7 2优秀的 1 4 本文的主要工作综述 本论文的主要研究工作集中在下述几个方面： ( 1 ) 国内外四边形网格剖分的研究现状 本论文首先分析了国内外四边形网格剖分的研究现状，对目前几种主要的方 法进行了简要的介绍和总结，分析了各种算法的优缺点 ( 2 ) 对三角网格模型上特征的应用，定义以及提取进行了综述，并介绍了几 种特征提取的典型方法 ( 3 ) 提出了一种基于特征保持的四边形网格生成方法 对于给定的三角网格曲面，提出了一种基于特征保持的四边形网格生成算 法该算法首先提取网格上的特征边和特征点，然后使用p a v i n g “1 方法在它们周 围生成一圈四边形网格这不但可以使得它们在四边形网格的生成过程中不会被 删除，而且可以保证它们周围的四边形网格的质量最后，利用q m o r p h 方法将 得到的混合网格转化为全四边形网格，并利用已有的优化方法对生成的四边形网 格进行带约束的优化在文章结尾还给出了一些数值实例，通过实例对本文提出 的算法进行了分析，指出了该算法的优缺点以及今后努力的方向 大连理工大学硕士学位论文 2 四边形网格剖分方法介绍 2 1 四边形网格生成方法综述 前面我们已经提到，网格生成是有限元前处理阶段的关键一步，网格生成的 质量直接影响有限元分析结果的精度而三角形网格无论是在计算精度上还是在 收敛性上都要稍逊于四边形网格，因此四边形网格的生成从上个世纪八十年代以 后逐渐成为人们研究的热点经过国内外无数学者和工程技术人员的共同努力， 涌现出了很多算法按照生成原理大致可以分为直接方法和间接方法下面我们 就从这两方面对国内外四边形网格生成的研究进展进行简单的综述 2 1 1 直接方法 直接方法就是在给定的几何区域上直接生成四边形网格，直接方法按照网格 的生成过程大致可以分成两大类： 第一类方法是几何分解法，即把一个区域分解成一些简单的凸子区域或者是 可映射的子区域，然后在这些子区域上生成四边形网格b a e h l n a n n 等人首先把四 叉树方法应用于区域分解：在经过初始分解后，根据区域局部的情况将二维空间 分解成一棵四叉树四边形网格在各叶子节点生成，调整节点位置使其可以更好 地拟和边界t a l b e r t 和p a r k i n s o n 6 等人随后又引入了另外一种分解技术：将 区域递归地分解为简单的多边形区域，当这些多边形满足一定的模板时，就可以 通过剖分这些模板来实现整个区域的四边形网格生成，即l o o p i n g ”1 方法国内刘 阳在 7 中借用p a v i n g 算法的边界拟和好的优点在边界处生成一圈单元来改善 l 0 0 p i n g 方法生成网格在边界处的质量郭晓霞等人 8 ， 9 对该方法生成四边形 网格中的边界偏移、最优分割线确定等关键技术作了改进t 锄等人则引入了中轴 ( m e d i a la x i s ) 技术这类方法可以生成全四边形网格，网格质量也比较高，但是 需要较多的人工干预，自动化程度不高 第二类方法是利用推进前沿技术( a d v a n c i n gf r o n tt e c h n i q u e ) ，即从边界开 始向内部逐个或逐层生成四边形网格z h u 1 0 等人是最先把该技术应用到四边形 网格生成的学者之一该方法首先在边界上布点，然后利用边界向内部投影的方 法生成三角形网格，每生成两个三角形网格就将其合并，从而得到一个四边形网 格但是该方法得到的四边形质量缺乏保证，因为两个高质量三角形单元合并以 后得到的四边形单元质量并不一定好 1 1 该方法中最著名的要数b l a c k e r 等人的 p a v i n g 方法即从区域边界向内部逐个生成四边形单元，在网格生成过程中要不 基于特征的四边形网格生成 断进行冲突检测，交叉和特殊情况的处理真至生成全四边形网格该方法生成的 网格具有边界敏感性和方位不敏感性的优点，并且能极大地减少网格中的不规则 点但是当目标区域边界非常复杂时，很容易出现大量交叉，而交叉判断和处理 既复杂又耗时，处理不好还会造成算法的不稳定c a s s 和b e n z l e y 则将p a v i n g 方法 推广到3 d 曲面的情形随后w h i t e 和k i n n e y 又通过每次生成一行单元而非逐个单元 生成，以提高算法的稳定性p a v i n g 方法目前已经被应用在一些商用软件中，如 m s cp a t r a n ，f l u e n t sg a m b i t 1 2 等 2 1 2 间接方法 间接方法就是首先在给定的几何区域上生成三角网格，这可以利用任何一种 已经很成熟的三角形网格生成方法，如d e l a u n a yt r i a n g u l a t i o n ，a d v a n c i n gf r o n t t e c h n i q u e 等，然后再将该三角网格转化为四边形网格此类方法主要有简单拆分 方法和合并法 拆分方法如图2 1 ，就是取每个三角形的重心和三边中点的连线把每个三角形 分成三个四边形该方法虽然实现了全四边形网格的自动生成，但是由于产生了 大量度为三的不规则节点，因此最终得到的网格质量很差。 瓜圆 图2 1 简单拆分法 另一种方法就是合并法如图2 2 ，即将两个或多个相邻的三角形合并成一个四 边形l o 1 3 首先给出了一个简单的合并方法，得到了个既有三角形网格又有 四边形网格的混合网格j o h n s o n 1 4 等人通过引入局部网格的拆分( s p l i t t i n g ) 和交换( s w a p p i n g ) 策略来进一步提高四边形的数量和质量l o 和l e e 3 则通过引 入系统合并技术( s y s t e 腑t i c a lm e r g i n gt e c h n i q u e ，s 岍) 来生成全四边形网格结 合s 舯和p a v i n g 方法，0 w e n 等人提出了全四边形网格自动生成的q _ m o r p h 方法， 该方法是目前间接方法中最好的一个，并被应用在商用软件中，如f e a 5 等l e e y k 和l e ec k 1 5 ， 1 6 给出了各向异性四边形网格的生成国内闵卫东 1 7 等人 计算每条非边界边被删除后所形成的四边形的口值，将其作为该边的权值然后 每次删除权值最大的边，这样得到了一个收敛速度为线形的分级合并算法然而 最后得到的网格是四边形与三角形的混合网格顾元宪 1 1 等人通过改进网格生 大连理工大学硕士学位论文 成的布点方法，首先生成三角形网格，然后再将其转化为四边形网格由于在生 成三角形网格时就考虑到了将来得到的四边形的质量，因此可以提高生成四边形 网格的质量，但网格质量仍然有待提高赵熠 1 8 等人针对传统前沿方法的缺点 提出了泛前沿“”的概念，即对前沿概念的更高层次上的抽象，不但避免了前沿拆 分和合并带来的不稳定，而且使得前沿操作起来更简单有效但是最后仍然有一 些残余三角形，需要通过移动和拆分来处理不但增加了算法的复杂性，而且也 影响了网格的质量胡向红 1 9 等人则提出了区域增长算法“ 函瓜 图2 2 合并法 间接方法由于所有操作都是局部的，不像有些直接方法那样需要进行全局交 叉检测，因此网格生成速度很快结合了比较成熟的三角网格生成方法，可以实 现对任意复杂区域的四边形网格生成缺点是有很多不规则节点产生，而且即使 不规则节点很少时也不能保证具有很好的边界拟和性，而这在有些应用中是很重 要的因此网格的质量不如直接方法好，需要通过一些额外的优化方法来提高其 质量 总之，通过上述简单的综述我们可以看出：直接方法和间接方法各有优缺点， 因此四边形网格生成方法与比较成熟的三角形网格生成方法相比，还有很长的路 要走这需要无数工程技术人员和学者的不懈努力 2 2 主要方法介绍 下面我们对四边形网格生成中的一些典型算法进行简单介绍 2 2 1m a p p i n g 方法 映射法又称为参数变换法，是研究最早也是比较成熟的一种网格生成方法它 的主要思想是将具有一定拓扑关系的区域变换为规则区域，在规则区域中利用线 性或二次插值划分网格，再把规则区域的节点通过逆变换生成对应的空间节点， 同时保留节点间的拓扑关系，如图2 3 该方法的关键技术就是映射函数的选择 映射法又分为映射单元法啪1 ( p p e de 1 e m e n ta p p r o a c h ) 和保角映射法 基于特征的四边形网格生成 ( c o n f o n n a l l a p p i n ga p p r o a c h ) 早期的映射单元法要求将目标区域手工分成许 多有利于映射操作的简单子域现通常用所谓超映射技术来获得过渡比较光滑的 网格保角映射法能直接处理单连通问题，但是因为该法难于控制单元形状和单 元密度，所以很少采用 图2 3m a p p i n g 方法生成网格示意图 m a p p i n g 方法的优点在于在每一子域内网格生成可以得到相当好地控制，能 够用以进行曲面网格的生成，得到的网格质量也比较高但其最大的弊端在于要 求事先根据所要产生的网格类型将目标域分割成一系列可映射的子区域而这一 工作通常需人工来完成，因而自动化程度低，不适合四边形网格的自动生成 2 2 2 基于栅格方法o ” 基于栅格法( g r i d _ b a s e da p p r o a c h ) ，又称反p a v i n g 方法，该方法曹先将一 完全包含目标区域的正则栅格( 一般为矩形) 放置在目标区域上面，除去落在目标 区域之外的栅格单元，并对与物体边界相交的栅格单元进行调整或剪裁以便更准 确地逼近目标区域再将这些栅格单元按一定的样式分成一定数量的网格单元， 之后通过光滑技术处理即得到最后的网格该方法分为以下几步： 1 - 用均匀矩形网格覆盖图形，如图2 4 ( a ) 图2 4 大连理工大学硕士学位论文 2 只保留在图形内部的栅格，而将在图形之外的及与图形相交的栅格删除， 如图2 4 ( b ) 3 对外部边界和内部栅格边界之间的缝隙进行d e l a u n a yt r i a n g u l a t i o n 如 图2 4 ( c ) 然后对一些三角形网格进行合并，如图2 5 ( a ) 最后将每个残 余的三角形拆分成三个小四边形，为了保持网格的相容性，需要对一些相 邻的四边形进行处理，如图2 5 ( b ) ilj i |， ii ， 蚪 v 扩 r r r ；j j， l l 1 i k 彤li ； i i 蝌l l i li 爿 l ij li、- j i 1计 l 、r ，州 li 对 霸麓 图2 5 4 对需要网格密集的区域进行加密处理，如图2 5 ( c ) 5 局部光滑处理，如图2 5 ( d ) 该方法生成的栅格越密，所得网格质量将越好对于生成大量网格，其效率 一般也要高于其他方法，如p a v i n g 方法等其不足之处就是所生成的网格与所选 择的初始栅格及其取向有关，网格边界单元质量差这种方法在原理上相当简单， 也易于扩充到三维，对于相对规则的问题区域不失为一种简单有效的方法 2 2 3l o o p i n g 方法“ l o o p i n g 方法属于几何分解方法，该方法通过一定的规则逐步分解所要剖分的 区域，直至子区域均已分解成为简单区域，然后根据简单区域的类型采取合适的 剖分方式，最终实现区域的全四边形剖分下面我们对该方法的一些关键步骤进 行介绍： 1 最优分割线的确定 分割线是连接区域或予区域边界上两点的线段，该线段可把区域一分为二 该方法的关键技术就是分割线的确定实际上，边界上任两个点的连线并不一定 基于特征的四边形网格生成 都可以把区域一分为二另外分割线的选择还会影响最终生成的四边形网格的质 量，因此在选择分割线时要特别慎重，下面是确定最优分割线的一些规则 2 ： ( 1 ) 用最短的边分割出最大的面积，其度量函数可用式( 2 1 ) 来表示， ，( e ) = ，2 爿 ( 2 1 ) 其中4 = 酊e 口( q 。) ，彳= i n j i l ( 4 ，4 ) 一：yfk y 1 ，魁铲j 如 图2 6 最短的边分割出最大的面积 ( 2 ) 用最短的边分割出最大边长，其度量函数可用式2 2 表示 ， ，( e ) = 去 ( 2 2 ) l 其中c ；为q ，的周长，c = m i n ( c l ，c ：) ( 3 ) 添加分割线e 后新生成的角应尽量接近于要或万我们用甲来表示这个 上 度量，使其满足当e 垂直于边界或仍远远大于时，甲取得最小值 接下来采用加权组合的方式来定义分解规则由于上述度量值的实际大小范 围较大，在此先定义两个缩放变换： 9 1 ( x ) = a r c l c 趾( x ) ，9 2 ( x ) = 1 一e 印( 吖2 ) ( 2 3 ) 则得到如下的优化问题的目标函数： ，2， 厂( e ) 2 口1 轧( j ) + 口：g b 畴) + a 3 9 n ( 甲慨，妒2 ) ) ( 2 4 ) 其中，盘。r ， l ，2 ) a ，为用户给定的参数，默认情况下，a ，= 1 ，= 1 即， ，2， ，( e ) = 8 删越呼) + 删叫寺) + 蜘一 t ，9 2 ) ) ( 2 - 5 ) 选择剖分线的过程就是在几何区域上求解该目标函数的离散化最优问题 奎壅垄王莶堂堡主堂堡堡銮一 一 2 剖分线上新节点的布置 7 在剖分线上合理地布置新节点，是网格生成算法中关键的一步这是因为，新 节点的位置和间距反应了单元尺寸信息在剖分区域上的分布，直接影响最后形成 网格的疏密分布和质量剖分线上新节点的布置，必须满足以下两个条件 7 ： ( 1 ) 在剖分线上布置节点的个数，应该保证形成的两个子区域的边界节点个数 为偶数 ( 2 ) 新节点在剖分线上的间隔值必须均匀分布，以保证单元尺寸渐变过渡 首先，按照剖分线两端的单元尺寸，计算剖分线上所需布置新节点的数目假 设剖分线两端的单元尺寸为以，丸，不妨假设九s 如剖分线长度为，则定义剖 分线上的节点间隔值d ( x ) 为线性函数 d ( x ) = d + ( d 口一d ) x ， o x 1( 2 6 ) d ( 工1 是分段线性连续函数，则所需布置的节点数目为 7 ： ：f 鱼： d 0 ) 去m 白 d b d 、d 。 ， 以 取，使得一1 ，则即为分割线上所需的节点数记= o ，h = ， 然后在 o ，f 中插入一1 个内节点x 。，x ：，x 。，于是，x 0 和h 的间隔度为 y 。= ，如果节点在剖分线上的分布是渐变的，那么 o ， 中相邻节点都应该取 相同的间隔度y = ，所以，节点x 。的坐标应该满足 7 ： f 焘刮邶 f o ， ( o f ) ( 2 9 ) l i 吖，卢= o ， 如果计算得到节点数目为奇数，最简单的做法是令= + 1 以满足奇偶性 要求 3 六节点子区域的处理 在最后剩下六节点区域时，如果对其仍旧用区域递归分解算法进行剖分，则 最后生成的单元质量较差，需要进行复杂的网格优化才能得到质量较好的网格而 7 q 如 如 = “ 九 基于特征的四边形网格生成 对六节点子区域进行分类，对每一种情况给出剖分方法，则可以避免这种情况的 发生下面是一些六节点子区域的剖分模板 8 ： ( 1 ) 当六节点子区域的节点处的内角没有一个接近万时，如图2 7 ( a ) ，( b ) ，可 以分为两个或者3 个四边形；如果有一个节点内角接近露时，可以使用2 7 ( c ) 所 示的方法剖分 p 圆仓q 图2 7 六节点子区域剖分模板1 ( 2 ) 当六节点子区域上的节点的内角有两个接近，r 时，可以根据节点的位置使 用下面的方法剖分如图2 8 ( a ) ，( b ) ，( c ) a i 图2 8 六节点子区域剖分模板2 ( 3 ) 当六节点子区域上的节点的内角有三个接近筇时，根据情况可以按下面的 方法剖分成四边形，如图2 9 ( a ) ，( b ) ，( c ) 睑 a b c 图2 9 六节点子区域剖分模板3 2 2 4p a v i n g 方法 p a v i n g 方法是种直接的全四边形网格生成方法，该方法的输入是区域边界 离散所形成的边界环它们被称为永久边界，即在内部网格生成的过程中，它们 不许变动永久边界又分为内边界和外边界：一般外边界仅有一个，它包含了生 成网格的区域( 对于连通区域) ；而内部边界则定义了区域内部的洞外部边界节 盔垄坚盔堂堡主堂堡笙壅 一一 点按逆时针顺序排列，内部边界节点按顺时针顺序排列内部的节点和单元会随 着四边形网格的生成而动态的计算出来p a v i n g 方法生成的网格质量高，边界灵 敏性好，内部不规则网格节点数较少，但是在网格生成过程中要进行大量的交叉 判断和处理，因此计算量很大特别当目标区域比较复杂时，极容易产生大面积 的网格交叉，对其进行处理需要大量的计算，处理不好还会造成算法不稳定 如图2 1 0 所示，处于永久边界上的点称为固定节点( f i x e dn o d e ) ，不在水久 边界上的点都称为浮动节点( f l o a t i n gn o d e ) 当前边界上的节点内角a 定义为： 该节点与前一节点之间的线段与该节点与下一节点之间的线段之间的夹角- 一 一 0 角瓞 一 一 。矿点内角x 乏z r 弋 3 一 图2 1 0p a v i n g 方法示意图 p a v i n g 方法的一些主要步骤如下 4 ： 1 层的选择( r o wc h o i c e ) 寻找产生下一层单元的第一个和最后一个节点，这有助于减少不规则节点的 数量为此将节点按照该点的内角a 的大小进行分类： a 2 ，r 3 ，则称该节点为终止节点( r o we n d ) 2 石3 a 4 石3 ，则称该节点为边节点( r o ws i d e ) 4 盯3 1 l 玎6 ，则称该节点为转节点( r 0 wr e v e r s a l ) 不同类型的节点，网格的生成方法也不一样 2 结束检查( c l o s u r ec h e c k ) 如果最后边界上的浮动节点数为零时，贝q 结束操作当为2 时，则进行缝合 ( s e a m ) 操作( 见后面) ；如果为4 ，则最后形成一个四边形并结束；如果最后剩下6 个节点，则进行以下闭合操作如图2 1 1 3 内部单元的生成( r o wg e n e r a t i o n ) 根据不同的节点类型，生成新节点及单元的方式也不同下面是具体的生成 算法： 基于特征的四边形网格生成 3 1 以边节点和终止节点为基点的新单元生成 如图2 1 2 ( a ) ，由m f ，+ ，三点生成一个新节点一，连接新旧节点组 成一个新单元，y 与向量f 高。的夹角为詈，令d 。= 4 或一，吐= 0 m 砘+ 。肛则 有： 怍缫 ( 2 - l o ) s i n ( a 2 ) r e c t r 黼l e t r 工 辩g l 丑s e 瓶i c 工r c l e 图2 1 1 六节点边界的闭合处理 ( a ) ( b ) 图2 1 2 新节点的生成 3 2 以角节点为基点的新单元生成 如图2 1 2 ( b ) 所示，此时由j _ l f ，j + 三点生成三个新节点，以，m ， 连接新旧节点，组成两个新单元，_ ，k ，巧与i 裔。的夹角分别为詈，詈，等， 则有： 1 6 大连理工大学硕士学位论文 阱等喾，阱吨j ( 21 1 ) 3 3 以转节点为基点的新单元生成 如图2 1 3 所示，此时由h ，f ，。三点生成五个新节点m ，m ， 。，连接新旧节点，组成三个新单元，k ，k ，吒，_ 与，赢。的夹角分别为 詈，詈，詈，兰，詈，等，则有： 阱等等，阱压阶州味 n k l = l _ 1 ， _ l = l i ( 2 1 2 ) 图2 1 3 新节点的生成图2 1 4 长度光滑 4 网格光滑 在网格生成的过程中，由于一些局部操作，如缝合处理，交叉处理等，很容易 使生成的网格和p a v i n g 边界变形，从而影响网格的质量，因此需要对其进行光滑 操作b l a c k e r 等人在 4 中给出了先进行边界光滑，然后进行内部节点光滑，最 后再进行边界光滑的光滑方法下面首先看边界光滑， 4 1 边界光滑 边界光滑就是对除了永久边界以外的当前p a v i n g 边界上的点进行光滑处 理记巧为从原点指向需要光滑处理的节点m 的向量吒，和，分别为始于 原点而指向第埘个四边形单元的另外三个节点，。和f ( 这些节点按顺时针或 逆时针排列) 的向量则向量矿。计算如下： k = 亡( + ，一) ， ( 2 1 3 ) 基于特征的四边形网格生成 记。= 巧一_ ( 如图2 1 4 ) 下面首先考虑长度光滑，如图2 1 4 ，k ，分别为原点指向节点f ，的向 量，记f d = 0 ，f 。为，到新向量k 终点的距离则得： 8 = 一k + ( 4 + 一) 等 ( 2 1 4 下面再看角度光滑( a n g u l a rs m o o t h n e s s ) ，如图2 1 5 ，记m l ，m + 1 分别为 当前需要光滑的浮动边界上的节点l 的前一个节点和下一个节点记只- 1 ，只和 只+ ，分别为以，为起点，以。，；和。为终点的向量令向量岛，平分向量p 。 和只+ ，之间的夹角向量b ：为以，为起点平分向