（机械设计及理论专业论文）基于分层发散思想的四边形网格生成算法研究与实现.pdf

浙江大学硕士学位论文 摘要 摘要 近十几年来，随着计算机技术的飞速发展，数值模拟技术在理论和应用上都取得了 巨大的成功。数值模拟技术作为工程领域复杂问题求解不可或缺强有力手段，己得到工 程人员足够高重视，成为推动工程技术发展重要工具。网格划分是数值模拟技术关键技 术之一，在c a e 分析之前，网格划分需要花费大量时间。同时，数值模拟技术准确性和 分析速度都直接受到网格质量影响。所以研究快速生成高质量网格，对数值模拟技术而 言，具有不可替代的意义。 铺路法作为四边形网格经典算法之一，已得到广泛应用。但是由于铺路法存在网格 生成过程操作复杂而且生成的网格均匀性较低的缺陷，本文提出了分层发散网格划分 法。为有效保证所生成的四边形网格的质量，在三角不等式的基础上，推导出一种新的 网格质量评价因子。在对网格平滑过程中，结合被搜索节点周围网格形成区域的凹凸性， 对等参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 平滑法的基础上，结合被搜索 节点邻近的网格的凹凸性，对等参l a p l a c i a n 平滑法进行了修正。 对分层发散的四边形网格划分方法在空间曲面上进行推广，讨论了空间曲面的连续 区域和非连续区域布点，空间曲面网格生成等内容。 关键词：网格划分，四边形，分层发散，网格平滑，网格质量判断，数值模拟 浙江大学硕士学位论文摘要 a b s t r a c t i nt h e p a s t f e wy e a r s ，w i t ht h ed e v e l o p m e n to f c o m p u t e rt e c h n o l o g y ，t h e m e t h o do f t h en u m e r i c a ls i m u l a t i o nh a sr e c e i v e dg r e a ts u c c e s sb o t hi n t h e o r y a n di np r a c t i c e i th a sp o w e r f u lm e a n st oc o m p l i c a t e dp r o b l e m si n e n g i n e e r i n g c o m m u n i t y t h em e s hg e n e r a t i o n ，w h i c hi sa k e yt e c h n o l o g yf o rn u m e r i c a l s j m u a t i o n ，j sv e r yc o m p l i c a t e da n de a s i l yb em i s t a k e n i tt a k e su p am a j o rd a r t o ft h et o t a lt i m eo ft h en u m e r i c a l s i m u l a t i o n a tt h es a m et i m e ，t h eq u a l i t v o fam e s hd i r e c t l ya f f e c t sb o t ht h er e l i a b i l i t yo ff i n i t ee l e m e n ta n dt h et i m e t h a tt h ea n a l y s i sp r o c e s sc o s t a sa r e s u l t ，h o wt og e n e r a t eh i g hq u a l i t ym e s h r a p i d l yi se x t r e m e l yv a l u a b l ef o rt h en u m e r i c a ls i m u l a t i o n p a v i n g m e t h o dh a sr e c e i v e dw i d e a c c e p t a n c e ， w h i c h g e n e r a t e s a 1 1 一q u a d r i l a t e r a l m e s h e si na na r b i t r a r y2 dr e g i o n h o w e v e r i th a s s e v e r a l d e f e c t s ，s u c ha st h ec o m p l e x i t yo fm a k i n gp r o g r a ma n di r r e g u l a rm e s h i no r d e r t oa v o i dt h o s ed e f e c t so f t h ep a v i n g ，an e wa l g o r i t h m ，n a m e d d e l a m i n a t i o n d i v e r g e n c ea l g o r i t h m ，h a sb e e nb r o u g h tf o r w a r d b a s eo nt h et r i a n g l ei n e q u a l i t y ， an e wj u d g m e n tp a r a m e t e rf o rm e s hq u a lit yh a sb e e na d v a n c e dt o g u a r a n t e et h e m e s hq u a l i t y b a s e do nt h ei r r e g u l a rm e s ha r o u n da n o d e ，am o d i f i c a t i o ni sm a d e t ot h ei s o l a p l a c i a ns m o o t hm e t h o di nt h em e s h s m o o t h i n g i nt h i sd i s s e r t a t i o n ，r e s e a r c hw o r kr e l a t e dt ot h ec o n t e n tt h a t d i s c u s s e s a b o v eh a sb e e nin t r o d u c e d f i r s t l y ，t h e d is s e r t a t i o ne x p a t i a t e st h es t a t u sa b o u tm e s hg e n e r a t i o n r e s e a r c h a f t e ra n a l y s et h es i g n i f i c a n o e so fr e s e a r c h i n gq u a d r i l a t e r a lm e s h e s ， t h es t r u c t u r eo ft h ed i s s e r t a t i o nd e t a i l si sp r e s e n t e d s e c o n d l y ，b a s e d o nt h e t h o u g h t o ft h e d e l a m i n a t i o n d i v e r g e n c e ，t h e d is s e r t a t i o ne x p a t i a t e st h ep r e d i s p o s eo ft h ef e mm e t h o d ，i t i n t r o d u c e sh o w t op r e p a r ef o rt h ep r e c o n d i t i o no fm e s hg e n e r a t i o na n dh o wt o d i s t r i b u t ea n d s t o r et h ep o i n t sb yw h i c ht h em e s hi s g e n e r a t e d t h i r d l y ，t h ed i s s e r t a t i o ni n t r o d u c e st h ed e t a i l so fh o wt o g e n e r a t et h e m e s h b a s e do nt h et h o u g h to ft h ed e l a m i n a t i o n d i v e r g e n c e f r e e d r a ws o f t w a r e w h i c hg e n e r a t e s q u a d r il a t e r a lm e s h e s b a s e do nt h e d e l a m i n a t i o n d i v e r g e n c e m e s h g e n e r a t i o na l g o r i t h m ，h a sb e e n d e v e l o p e d f o u r t h l y ，b a s eo nt h et r i a n g l ei n e q u a l i t y ，an e wj u d g m e n tp a r a m e t e ro f m e s h 2 浙江大学硕士学位论文摘要 q u a l i t yh a sb e e na d v a n c e dt op r o t e c tt h em e s hq u a l i t y b a s e do nt h ei r r e g u l a r m e s h a r o u n dan o d e ，am o d i f i c a t i o nt ot h e i s o l a p l a c j a ns m o o t h m e t h o di s p r e s e n t e d ， f i f t h l y ，t h ed e l a m i n a t i o n d i v e r g e n c em e s hg e n e r a t i o na l g o r i t h me x t e n d s t ot h es p a c ef a c e t i te x p a t i a t e sh o wt og e n e r a t e n o d ei ns p a c ef a c e ta n dh o w t om e s h s p a c ef a c e t k e yw o r d s ：m e s hg e n e r a t i o n ，q u a d r a n g l e ，d e t a m i n a t i o n & d i v e r g e n c e m e s h s m o o t h ，m e s hq u a l i t yj u d g m e n t ，n u m e r i c a ls i m u l a t i o n 浙江大学硕士学位论文 第一章绪论 1 1 引言 第一章绪论 网格划分广泛应用于工程计算、计算机图形学、科学计算及可视化、地理信息系统、 生物医学工程、物理学等领域。网格划分的目的是为了对几何域迸行离散，获得简单形 状，以便于几何域在工程中的应用 随着市场的发展，竞争日趋激烈，商家们总期望在最短的时间内以最少的投入，获 得更好的产品。计算机辅助设计( c a d 技术) 在此过程中，决定着产品的设计质量， 计算机辅助制造( c a m 技术) 决定着产品的制造精度和加工效率，而计算机辅助工程 ( c a e ) 在这过程中，也扮演着一个重要的角色。它通过分析、仿真等手段对产品品 质进行预检验。而作为计算机辅助工程( c a e ) 关键技术之一的网格划分技术，决定着 c a e 计算的规模、速度、精确度等，从而日趋得到人们重视 2 - 3 】。 1 2 网格划分基本原则 网格划分是建立有限元模型的一个重要环节，网格划分的合理与否，影响到有限元 分析结果的准确性和精度以及分析计算的效率。因此，在网格划分时需要考虑网格数量、 网格疏密度、单元阶次、网格质量、网格分界面和分界点、单元的位移协调性、网格的 布局等问题”。1 。 1 网格的数量 网格数量指被分析对象所划分成的网格的总个数。网格数量的多少直接影响着有限 元分析的计算规模和计算精度。一般而言，较少网格时，增加网格可以使计算精度明显 提高，与此同时计算时间的增加却不十分显著。当网格增加到定的程度后，如果继续 增加网格数量，分析精度提高甚少，而计算时间增加甚多。根据前人的经验，对于结构 的小变形分析计算，可以使用较少的网格：而计算结构的大变形以及计算结构的应力时， 则必须增加网格的数量。 2 网格的疏密 网格疏密度指单位面积( 体积) 内网格的数量。在进行网格划分时，结构的不同部 位网格的疏密程度不同。一般而言，在计算数据变化梯度较大的部分，为较好的分析数 据变化规律，需采用比较密集的网格；反之在计算数据变化梯度较小的部分，可采用较 浙江大学硕士学位论文第一章绪论 稀疏的网格。根据被分析对象的特点合理地划分网格疏密度，可以有效地减少结构有限 元计算的时间，提高分析效率。 3 单元阶次 许多单元都具有线性、二次、三次形式，其中二次和三次形式的单元称为高次单元。 选用高次单元可以对结构的曲线和曲面边界更好地逼近，而且高次插值函数能更高精度 地逼近复杂场函数。所以，对于不规则结构或应力应变复杂时，可采用高次单元。在同 等网格数量时，具有较多高次单元的网格的计算规模较大。 4 网格质量 网格质量是指网格形状的几何合理性。网格质量的好坏将影响计算精度。直观上， 如果一个网格的各边或各个内角相差不大、网格面不过分扭曲、边节点位于边界等分点 附近，则认为该网格的质量较好。网格划分时一般要求网格质量能达到某些指标要求。 通常，对于被分析对象上重点研究的关键部位，应保持每一网格的高质量；对于次要部 位，可以降低对其结构网格的质量要求。 5 网格分界面和分界点 结构中的一些特殊界面和特殊点应划分为网格的界面或节点，以便定义材料特性、 物理特性、载荷及位移约束条件。即应使网格的划分满足边界条件特点，而不是让边界 条件来适应已有的网格。常见的特殊晃面和特殊点有材料分界面、几何尺寸突变面、分 布载荷分界线( 点) 、集中载荷作用点和位移约束作用点等。 6 位移协调性 位移协调性是指单元上的力和力矩能够通过节点传递给相邻的单元。为保证位移协 调性，要求每一单元节点必须同时是相邻单元节点，而不应是内点或边界点。相邻单元 的共有节点具有相同的自由度。 7 网格布局 当结构形状对称时，其网格也应当对称分布，阱减小布局不对称时引起的分析误差。 因此，在网格布局中，对于具有对称性质的被分析对象，需要使计算模型表现出对称特 征，以便于计算。 浙江大学顿士学位论文第一章绪论 1 3 国内外研究状况 1 3 1 网格划分算法发展现状 有限元网格从复杂性来说，可分为二维网格、曲面网格、三维网格。从单元形状来 分有：二维有三角形网格、四边形网格，三维有四面体网格、六面体网格等。从拓扑结 构来分，有限元网格具有两大类：结构化网格、非结构化网格。按自动化程度来分有半 自动化算法和全自动化算法。 下面我们讨论几种典型的网格划分方法。它们分别是：映射法、四叉树法、波前 法、劈分法、d e l a u n a y 三角音0 分法、铺路法等。 1 映射法 映射法是一种传统的有限元网格划分方法。映射法的主要目的是将具有一定拓扑关 系的区域通过参数变换转换为规则区域，在规则区域中，通过插值法进行网格划分，然 后再通过参数逆交换回到相对应的区域，获得所需要的网格。如图1 1 所示。 a ) 求转授箭的堪域b ) 转穗菥的区城 图1 1 映射法转化原理图 映射法在划分网格过程中，划分区域内部的各节点都比较规则。网格的划分速度比 较快。但是，由于参数变换过程中具有很大的不确定性，对于具有不同特征的几何域， 所获得的映射网格品质相差甚远。因此，所获网格并非都达到预期效果。 z i l e n k i e w i c z 和p h i l i p s 于1 9 7 1 年提出了等参映射法“”。o o r d e n 与h a l l 于1 9 7 3 年提出了超映射法“。 扫描法“”，是一种介于二维和三维之间的网格划分方法，是一种典型的映射法， 用于六面体网格生成。当四边形网格沿空问中一条曲线在空中扫描时，几何体内每隔一 定的间距就生成一层与四边形网格拓扑结构相同的网格。这种方法通常用于划分某种定 义了源表面和目标表面的几何体。 浙江大学硕士学位论文 第一章绪论 2 四叉树法 四叉树法是由y e e r y 和s h e p h a r d 等”提出来的。后来，k e l a ，y e e r y 等”人对其进 行了完善和发展，使之成为目前最经典的网格生成算法之一。 在四叉树法网格分解中，预先采用一个尽量可能小的正方形将域包围，然后将正方 形分为四个子域，测试各个子域是否满足要求，若满足就停止划分。否则采用此种思想 继续划分到满足要求为止。在相邻的网格中，只能细分一次。如图1 2 所示。 该方法适合于任意的复杂的二维问题，网格的生成易于实现密度控制，易于进行自 适应划分。但是，四叉树法在单元密集的地方质量欠佳，对边界的模拟精确性不够。而 且，程序实现复杂，所需内存较大，不利于实现并行处理。 b e r n 和e p p e t e i n 对该方法作了改进。”，使其单元形状和密度都可控，而且对有孔 的多连通域，能够保证所有网格内角大于2 0 度。国内大连理工大学的杨名生等”2 8 对四 叉树法也进行了研究。 _ 7 、 吆 ， ；pl 1 、 、 牛 k 半峨 一 毒 zl 一 ll_ lll_ r h 一i j - i r_ i 图1 2 四叉树法原理图 3 波前法 波前法是一种全自动网格生成方法，这一思想最初是由l o h n e r 和l o 提出的【2 9 0 2 ， 此后许多人都对该方法进行了改进 3 3 - 3 5 1 。这种方法特点主要如下：首先从物体的边界 开始，定义一个“前沿”，在“前沿”上满足一定条件的地方生成一个单元、同时更新 “前沿”，如此不断地重复。做到前沿变为主空，网格生成结束。在生成过程中，前沿 就象波浪一样往前推进，直到消失。如图1 3 所示。 先把物体的边界离散，形成一个节点组成的环。并把它定义为初始前沿。物体边界 上节点的密度和分布对最终网格的质量和尺寸分布影响很大。特别是在生成四边形网格 时，边界上节点的个数必须为偶数。这是由四边形网格的拓扑关系决定的。 浙江大学硕士学位论文 第一章绪论 在初始前沿定义后，进行以下三步进行网格生成： 检查前沿上每个节点的内角，确定新生成单元的位置： 在满足条件的节点处创建一个或几个单元； 更新前沿，即把新生成的边界加入环中，删除旧的边界。 图1 3 波前法原理图 4 劈分法 劈分法是将一个三角形单元分裂为三个四边形单元，如图1 ，4 所示。三角形单元每 条边上增加一个点，通常选其为中点。三角形内增加的点通常为三角形的重心。这样生 成的网格就可以保证为四边形。这是一种四边形网格生成的可行方法，但是由于三角形 生成的非稳定性和不均匀性，该方法生成的网格质量较差。 s h l o 对该算法进行了改进，生成了包含着最少三角形的四边形占优的网格，浚 算法就三角形组合的顺序给出了几个步骤。j o n s t o n 3 7 1 提出了局部单元细分与交换策略， 可以提高四边形数量和品质。l e e l 3 9 l 等通过包含三角形的切分优化了l o 的策略，并将波 前法用于产生初始三角形网格。 堑垩查堂堡圭兰焦堕皇 一兰二兰生兰一 图1 4 劈分法生成四边形网格 5 o e l a u n a y 法 d e l a u n a y 三角剖分法是一种利用离散点集生成网格的方法。这些离散的点由v o r o n o i 图产生。 二维v o r o n o i 图是由一些凸多边形组成，且具有以下性质： n 点集中的任一节点与凸多边形一一对应： 2 ) 凸多边形内部任意点均以该节点为“最近邻”； 3 ) 三个或更多的凸多边形可交于一点，这些点称为v o r o n o i 顶点； 4 ) 外部的v o r o n o i 多边形为开的、而内部的多边形均为闭式的。 如果两个节点相邻。s t j z f t 的v o r o n o i 多边形必然相邻连接所有v o r o n o i 多边形 中的节点，即为d e l a u n a y 三角剖分。如图1 5 所示。 图1 5 点集的v o r o n o i 图( 虚线】及其d e l a u n a y 三熊骞分( 实线) 使用d e l a u n a y 生成三角形或四面体网格算法很流行。d e l a u n a y 准则在1 9 3 4 年就已 浙江大学硕士学位论文第一章绪论 提出，后来l a w s o n 3 9 1 和w a t s o n 4 0 1 利用它给出7 - - 响化一个点集的算法，而b a k e r 【4 i i 、 w e a t h e r i l l 和h a s s m l 4 2 1 利用它分别给出了网格生成算法。d e l a u n a y 划分方法有无约束节 点插入法4 2 4 4 1 和约束边界d e l a u n a y 划分法 4 5 两种。 6 铺路法 铺路法1 4 6 】采用由外向内逐步铺砌的方法对域进行剖分。如图1 6 - 1 7 所示。铺砌层 由外向内层层铺砌，直至填满整个剖分域。 销路算法始于定义区域边界的有序封闭点环。这些点环构成区域的原始边界，成为 永虞 力界肃反j 力界 的占量占，问的 车辖羊磊乃苴柿罾在救小生晰讨 晕由屋不亦的 在网格生成过程中，节点被分为定点( 永久边界上的节点) 、浮点( 铺路边界上的 非定节点) 、铺砌节点( 铺路边界上的节点，包括定点和浮点两种) 。每个铺砌节点都有 一个内角( 该节点与前后节点连线所形成的角) 。每个铺砌边界上各节点数必须保持偶 数。节点之间的距离决定着网格大小。整个网格生成过程中，网格单元间距基本保持不 变。要改变网格单元的大小，必须由边界网格上的节点数来控制。 王世军1 4 7 1 对铺路法进行了发展，提出了堆砌法。但文蛟1 4 8 1 提出了分层发散法。 图i 6 铺路法原理图 肉睡岗边界 可劲带矗 铺翻国弄 节点，内角 舟圜麾逑器 图1 6 铺路法原理图 l j 始，q 圈 舟围麾遗器 浙江大学硕士学位论文第一章绪论 口口 口口田 图1 7 铺路法单元的生成过程 铺路法实现的基本步骤如下： 1 ) 以现行的边界为波前，沿区域当前边界按铺路规则铺砌一层单元，然后进行单 元调整，以便达到接近于矩形的的四边形单元。然后进行封闭判断，若封闭， 则进入步骤4 ) 。 2 ) 如果本层单元无重叠现象发生，则推进波前，继续步骤1 ) ，否则，转入步骤3 ) 。 3 ) 进行波前的交叉处理，得到更新的区域边界，然后执行步骤1 ) 。 4 ) 进行封闭处理。 铺路法生成的单元接近于矩形，单元质量比较好，且生成的自动化程度比较高。但 是在铺路法生成过程中，具有大量的交叉判断计算，因此单元生成的效率比较低。而且 对于复杂边界处，容易产生单元畸变。 1 3 2 网格划分发展趋势 有限元网格全自动生成系统的研制是近年来的一个研究热点，在众多的研究者的辛 勤劳作之下，已有大量的各具特色的网格划分算法问世，而且其中的些算法已为多种 流行的商用软件所采用，并且通过实践证明了其实用性和有效性。但是，网格划分算法 也是各具不足，这些不足决定着有限元网格划分技术未来发展的趋势： 1 ) 综合几何及力学特性的自适应性网格划分技术的进一步完善。随着对有限元高精度 计算的要求，有限元网格划分技术必将是尽量减少经验和人为地判断，而采用综合物 体在工程应用过程中的几何及力学特性，通过几何及力学特征知识库，进行自适应性 网格划分。 浙江大学硕士学位论文 第一章绪论 2 ) 多种网格划分方法综合的通用性强的综合算法的研究是未来应用中的热点。每一个 网格划分算法都具有自己的缺陷，而多个划分算法的综合应用可以相互补充。 3 ) 智能化网格生成以及专家系统的有限元模型的自动生成是一个同时体现知识化和智 能化的综合应用。它既实现了工程人员的划分理想的网格意向，同时采用知识和智能 技术引导产生理想的网格。 1 4 论文研究主要内容 1 4 1 论文研究背景及意义 由于网格划分技术在c a e 技术中的重要作用，因此许多现行的软件都将网格划分 作为其重要的部分之一。例如，c a d 软件中，p r o e 、u g 、c a t i a 中都带有网格划分功 能。而在c a e 软件中，例如h y p e r w o r k 、a n a s y s 、n a s t r a n 、m s c 系列等都具 有强大的前处理功能。但是由于计算机分析速度远低于计算机辅助设计速度，使得产品 的- 丌发会产生严重的滞后。同时，c a e 在建模过程中，需要的专业知识太强，超过了设 计人员所具有的知识范围，从而降低了产品分析速度。因此，网格划分方法通用性、快 速性的提高是一个迫在眉睫的问题。 采用何种网格曾一度是研究者们所讨论的一个热门话题。但是在工程实际分析过程 中，分析人员更愿意采用四边形网格和六面体网格。究其原因，主要有以下几点： 1 ) 四边形网格和六面体网格比三角形网格和四面体网格更能体现分析模型的特 征，所获得的解更精确。 2 ) 线性六面体网格进行分析所达到的精度，如果采用四面体来分析，单元的数目 以及单元的次数都要增加“1 。同时人们意识到，要进行六面体网格的划分，首 先要在划分域的表面产生四边形网格”。 因此，四边形网格划分技术的研究具有重要的工程意义。 1 4 2 论文研究主要内容 现有四边形网格生成算法各具特色，但也各具缺点。论文在铺路法的思想基础上， 针对铺路法网格生成操作复杂以及生成的网格均匀性低的缺陷，提出了一种基于分层发 散思想的有限元网格生成方法。为了有效的保证所生成的四边形网格的质量，在三角不 等式的基础上，提出一种网格质量评价因子。在对网格平滑过程中，对等参l a p l a c i a n 网格平滑法进行了修正。 浙江大学硕士学位论文 第一章绪论 论文主要分为六章，其具体内容组织如下： 第一章，介绍了网格生成的国内外研究状况，在四边形网格生成的背景以及研究意 义的基础上，提出了论文研究的主要内容。 第二章，在铺路法的思想基础上，提出了一种基于分层发散思想的有限元网格生成 方法。详细地介绍了这种分层发散网格生成过程中的初始条件确定、布点、点的存贮等 网格划分预处理的关键内容，最后给出了布点生成实例。 第三章，在分层发散网格划分法产生的节点基础上进行网格生成，研制并实现了基 于分层发散网格生成法的四边形网格生成器，给出了网格生成流程图和大量网格生成实 例，最后对分层发散网格生成算法进行了分析。 第四章，网格质量判断因子，n 评价因子、b 评价因子、入评价因子、y 评价因子 等进行了讨论。在三角不等式的基础上，推导了一种四边形网格质量判断因子，并通过 实例对其进行了验证。然后在经典l a i ) l a c i a n 平滑法和等参l a p l a c i a n 平滑法的基础上， 结合被搜索节点邻近的网格的凹凸性，对等参l a p l a c i a n 平滑法进行了修正，并通过例 题对此作了验证。 第五章，对分层发散的四边形网格划分方法在空间曲面上的进行推广，讨论了空间 曲面的连续区域和非连续区域布点，空间曲面网格生成等主要内容，最后给出了网格划 分实例。 第六章，对论文进行总结和展望。 浙江大学硕士学位论文 第二章四边形网格划分预处理 第二章四边形网格划分预处理 摘要：在铺路法的思想基础上，提出了一种基于分层发散思想的有限元网格生成方法。 详细地介绍了这种分层发散网格生成过程中的初始条件确定、布点、点存贮等网格划分 预处理的关键内容，最后给出了布点生成实例。 2 1 引言 有限元方法是一种在工程上非常重要的数值分析方法，在许多领域得以广泛应用。 随着计算机技术的发展，传统的人工进行网格划分己不能满足需要，因此研究自适应的 网格划分方法变得尤为重要。怎样快速地划分高质量的有限元网格是其中一个重要的研 究课题，研究人员已提出了许多网格自动生成的算法。在众多的网格生成算法中，三角 形网格的自动生成算法最为成熟，但三角形网格计算精度低，为了满足高精度计算的需 要，需要设计能直接生成四边形单元网格的算法。本文在铺路法的思想基础上，提出一 种新的算法一一分层发散法【4 8 】。 所谓分层发散；分层，是指单元划分及其点的布置是从中心初始点开始，一层一层 生成的；发教，是指下一层的单元和节点是在上一层的单元和点基础上，沿四边的方向 扩散生成。如图2 1 。 铺路法是单元一层一层从边界铺到区域内部。当外层边界变化时，两者在区域内部 的单元都要进行缝合、湮灭、光顺，使得区域内部的过渡单元并不均匀。而板料成形过 程中，产生变形的关键部分的单元的合理性、均匀性尤为重要。因此，我们提出了一种 分层发散布点的方法，以解决各层边界变化时过渡单元的均匀性问题。 为了明确构造算法的真实目的，因此有必要了解清楚铺路法的优缺点。然后在继承 它的优点的基础上，针对这些缺点进行改进。 铺路法的优点： 1 ) 具有很好的边界逼近性能。 2 ) 几何模型的几何变换不影响网格的拓扑结构。 3 ) 不规则节点少。 浙江大学硕士学位论文 第二章四边形网格划分预处理 铺路法的缺陷： 1 ) 每次单元形成过程中，求交操作极大影响了单元生成速度。 2 ) 求交所获得单元可能大小各异，导致网格分布不均匀。 针对铺路法的这些不足之处，分层发散法作了以下的改进： 1 ) 为了加快单元生成速度，分层发散法区域内部的单元采用统一模型，按一定的 规律发散形成。而将求交工作集中在内部单元和内缩边界交界区的部分单元， 可以大大减少求交次数，加速网格生成。 2 ) 由于区域内部的单元采用统一模型，因此网格分布比较均匀。而过渡区域通过 特定的边界处理方法进行网格生成控制，因此可以得到比较合理的网格。 图2 1分层发散法生成网格原理图 分层发散法在实现过程中，主要有三大步骤： 1 ) 初始条件的确定； 2 ) 区域的布点： 3 ) 网格生成。 本章主要对1 ) 、2 ) 两个部分( 网格生成的预处理) 进行讨论。 浙江大学硕士学位论文第二章四边形网格划分预处理 2 2 网格划分域初始条件确定 2 2 1 边界分类 在网格划分之前，我们首先要明确网格划分区域的边界，这是实现分层发散算法的 首要条件。 在这里，我们按照边界在划分区域所处的物理位置不同，可以将其划分为：内边界 和外边界。分别采用v 0 0 和v 1 0 表示。前者为外边界，后者为内边界。 其中，内外边界的判断标准如下： v o0 判断准则：假设有一质点沿边界逆时针方向运动，若网格划分区域在其左边， 则为外边界，记为v 0 ( i ) ，其中i 表示第i 外边界。 v i ( ) 判断准则：假设有一质点沿边界逆时针方向运动，若瞬格划分区域在其右边， 则为内边界，记为v i ( j ) ，其中j 表示第j 内边界。 2 2 2 外边界凸处理 在进行网格划分之前，为了求取合理的初始点，我们有必要对图形外边界进行凸处 理。其主要处理方法如下： 凹多边形的凸化准则1 ( 边为直线) ：如果有一多边形，连接其顶点i 和i + 2 ，若由 顶点i 、i + l 和i + 2 组成的区域位于该多边形的外部，则该多边形为凹多边形。由顶点 i 和i + 2 的连线替代i 、i + l 和i + l 、i + 2 的连线，并称顶点i 和i + 2 的连线为凸化边。 然后依次进行判断直到图形完全凸化为止。如图2 2 ( 1 ) 所示。 凹多边形的凸化准则2 ( 边为曲线) ：如果有一多边形，若连接某一边s 的两端点 ( 或拐点) 得一直线l 】，若l l 与s 。组成的区域位于该多边形的外部，则该多边形为凹 多边形。由l 。替代s 。，并称该直线为凸化边。然后依次继续判断直到图形完全凸化为止。 如图2 2 ( 2 ) 所示。 凹多边形的凸化准则3 ( 边为曲线) ：如果有一多边形，若连接某两相邻边s ，、s 。 的两端点( 或拐点) 分别得一直线l 、l ：，若l 1 与l ：组成的区域位于该多边形的外部， 则该多边形为凹多边形e 由l i 与l 两不相邻端点的连线l 。替代s ，与s ，并称l 。为凸化 边。然后依次继续判断直到图形完全凸化为止。如图2 2 ( 3 ) 所示。 对于直线和曲线混合的凸化多边形，则由上述三种方法综合解决。 浙江大学硕士学位论文第二章阻边形网格划分预处理 虚线为凸化边 i1 ) 2 2 3 初始点确定 虚线为凸化边 c2 ) 图2 。2 图形外边界凸化处理 点划线为替代边 虚线为凸化边 ( 3 ) 当多边形外边界进行完凸化之后，我们就可以进行网格划分初始点的确定。 所谓网格划分初始点就是：在网格划分之前，为了保证网格能够有规律快速的生成， 在己凸化的多边形的顶点的基础上，通过算术平均值所求取得的某一点。 其符合以下的准则： 初始点的确定准则1 ：设凸化多边形由直线组成，则平面布点初始点o ( x 。，y 。) 可表 示为，l = 去喜t ，y 。= i i 善n y ，( x l , y i ) 为边界顶点坐标( i = 1 n ，n 为凸化多边 形顶点) 。 初始点的确定准则2 ：设凸化多边形由某一条连续曲线组成，则设f ( x ，y ) = o 为平面 边界方程，并设f ( x ，y ) - - o 在定义域内连续可导。则平面边界周长l 为； l = i 再i d ) c 如果沿边界均匀布n 个点，则每相邻两点的弧长为l ，l = l n 。即l 为 上= 去眵= 了丽= j 丽c t = ，n 一， 浙江大学硕士学位论文 第二章四边形嘲格划分预处理 设平面布点初始点为o ( x 。，y 。) ，则x o y 。分别为： _ = 去霎一，儿= 去蒸m ( 碲y ) 为边界均布点坐标( i = 1 n ) 对于直线和曲线混合的凸化多边形，则由上述两种方法综合解决。 2 2 4 长短轴及单元距确定 设平面边界均匀点距离o 点距禹为d i ，则： d ，= 瓜i 了i 而( i = 1 n ) d 。= m a x ( d 1 ，d 2 ，q ) ，称之为长轴 d m = m i n ( d 1 ，d 2 ，见) ，称之为短轴 设平面布点最大层数为n ，采用长轴和短轴可求出单元距h 和最小层数m ，即 h ：生 m = 吲 2 2 5 边界内缩 如果直接按分层发散法划分网格，当网格划分到边界时，边界的网格会比较差，为 了解决这一问题，将图形边界内缩若干个单元距，使得边界单元网格有足够的空间进行 调整。这样就可以较好的解决边界单元不均匀的问题。 在这里采用的边界内缩是近似内缩，其描述如下i 见图2 3 。 s t e p l ：求取划分区域边界上的顶点( 拐点) a i ( x i ，y i ) 在相邻两曲线的法向n l ，并定义其 指向区域内部的方向为正向。 s t e p 2 ：若将该部分边界曲线方程f ( x ，y ) = o ，在两顶点( 或拐点) 之间平移一个单元距。 s t e p 3 ：外部边界内缩后，内缩边界之间进行求交，将交点a ，。( x i ，y i ) 作为内缩边界的顶 点。内部边界内缩后，要将内缩边界延长后再进行求交，将交点a 。( x 。y ) 作为 浙江大学硕士学位论文第二章四边形强格划分预处理 内缩边界的顶点。内部内缩边界记为v r l 0 ，外部内缩边界记为v r o ( ) 。 重复以上三个步骤，直到完成所有的边界内缩。 ( 1 ) 韧始边界 2 3 网格划分区域布点 图2 3 边界内缩原理图 t 乏边界内缡 对于四边形网格，布点与其生成的均匀性、合理性紧密相关。 2 3 1 点分层和生成方法 平面布点从布点起始点o ( 即第零层) 开始生成八个方向，第一层按8 个均匀方向 生成相应的点。然后，在第一层生成的点的基础上，进行第二层点的生成；在两个对角 线的四个方向。各要新增两个新点。依次可得第三层，直至第n 层。每层的点数为8 + i 个( i 表示第i 层，i 从0 到n ) 。如图2 4 所示( 小黑点表示所布之点) 。而图2 , 3 表示 为分层点的逻辑关系图( 前三层) 。 孓，江 、。 。 裂j i些 莉愫 第零层第一层 第= 层 图2 4 分层发散网格布点原理图 浙江大学硕士学位论文 第二章四边形阐格划分预处理 第 图2 5 分层布点的逻辑关系图 由图2 5 表示的分层点的逻辑关系图可以得出点在生成过程中所获得的位置关系循 环系数。如表2 卜2 4 所示( 前三层) 。图2 5 中的点数和表2 1 - 2 4 中的系数存在如下 关系： 设i 为层数、k 为每层所布的某点。每层点分四个部分生成，每2 i 作为一个部分。 塑坚查兰堡主兰垡堡苎兰三兰婴望丝堕塑型坌堡竺垄一 0 2 i 1 ： 2 + i 4 0 i 1 ： 4 i 6 i 一1 ： 6 + i 8 + i 一1 ： 点的位置关系循环系数为，x = i ，y = ( k ( 2 + i ) ) 一i ； 点的位置关系循环系数为，x = i - ( k ( 2 + i ) ) ，y = i ； 点的位置关系循环系数为，x ；一i ，y = i 一( k ( 2 8 i ) ) 点的位置关系循环系数为，x = ( k ( 2 + i ) ) 一i ，) r = 一- i 表2 1 第零层点的位置关系循环系数 点值 0 x 值 0 y 值 o 表2 2 第一层点的位置关系循环系数 点值 oi23 4567 x 值 1llo lll0 y 值 - 1o11 10一l一1 表2 3 第二层点的位置关系循环系数 点 0l234567891 0 1 l1 21 31 41 5 值 x222221ol- 2- 2 - 222- 10l 值 y 一210l222221 0一l- 2- 2- 22 值 浙江大学硕士学位论文第二章四边形网格划分预处理 表2 4 第三层点的位置关系循环系数 点 o1234567891 01 11 21 31 41 5 值 x3333 33 32lol一23- 333 值 y 一321o1233333 3321o 值 点 1 61 71 81 92 02 1 2 22 3 值 x- 3- 332101 2 值 y 一1- 2 3- 3- 3- 3- 3 3 值 2 3 2 点与平面内外边界位置判断 当平面布点层数达到内缩边界时，要判断点与内缩边界的位置关系。 点与内缩外部边界的位置判断准则： 如图2 6 所示，设被判断点为c i ，其上一层的相应点为c o ，其下一层的相应点为 c 2 ，平面内缩边界方程为f l ( x ，y ) = 0 。连接c o c l 、c l c 2 ，如果c o c 】与f i ( x ，y ) = o 相交点k 2 位于c 。、c i 之闻，则c i 位于平面内缩边界之外，则要将c i 点内移到c o 点。如果c i c 2 浙江大学硕士学位论文第二章四边形网格划分预处理 与f l ( x ，y ) = o 相交点k l 位于c l 、c 2 之f b j ，则c l 位于平面内缩边界之内，则不必将c3 点 内移。 k l 为莲战c o l z l 与1 缸，y ) 的交点 蛇为连战c l c 2 与f l ，y ) 的交点 ) = 0 图2 6 平面布点与内缩边界位置关系判断原理图 其数学表达形式为：设有c o ( x 0 ，y 0 ) 、c 1 ( x l ，y 1 ) 、c 2 ( x 2 ，y 2 ) 三点分别位于所不同的三 层。c 1 为c 0 所布之点，c 2 为c 1 所布之点。其中c o 、c 1 点为已布置点。 _ 若f i ( x 2 ，y 2 ) + f l ( x l ，y 1 ) 大于零，则c 2 、c l 点位于曲线f l ( x ，y ) = o 同侧，c 2 点可以布 置。 若f i ( x 2 。y 2 ) 4f i ( x l ，y 1 ) 小于零，则c 2 、c 1 点位于曲线f i ( x ，y ) = o 两侧，c 2 点为不可 布置点。 - 若f i ( x 2 ，y 2 ) + f i ( x l ，y 1 ) 等于零，f i ( x 0 ，y o ) + f f f x l ，y 1 ) 等于零，则c 1 点位于曲线f i ( x ，y ) = 0 上，c 2 点为不可布置点。 点与内缩内部边界的位置判断准则： 设有c 0 ( x 0 ，y 0 ) 、c 1 ( x l ，y 1 ) 、c 2 ( x 2 ，y 2 ) 三点分别位于所不同的三层。c 1 为c 0 所 布之点，c 2 为c l 所布之点。其中c 2 、c l 点为已布置点。 - 若f i ( x 0 ，y 0 ) + f i ( x l