（岩土工程专业论文）三维delaunay四面体网格生成加密技术与应用.pdf

e 镕d e l a u n a ) ，体月格成密$ 目应月 摘登 三维d ela u n a y 四面体网格生成加密技术与应用 摘要 f 在运蠲有限单元法求解力学问题时，事先需要对研究的对象进行单 、 元划分，即嬲拯救生成。网格一旦生成廷，单元的形状秘疏密程度将直 接影响到有限元计算结果的精度。为了减小计算误差，一方面需要保证 生成的网格单元形状较好，另一方面需要对己有的丽格进行加密来控制 网格的疏密理度。网格的生成和加密工作可以幽人工实现，但是当数据 准备工作量较大时既麻烦又容易出错，而且因计算者对计算对象的不同 理解和经验差异所配置的两格不蔺雨使计算结果茵入而异。随着计算枧 技术的发嶷，通过程序来实现网格的生成弱加密成为了磺究的热点。与 人工生成网格的方法相比，用计算机程序来生成和加密网格要可靠、方 便得多。另外，阏格加密的程序还可以和常援有限元程序以及误差估计 算法结合起来，从焉实现网格的自适应加密。自适应阚格能够根据工程 计算的精度来自动控制网格的疏密，以获得最优化的网格和计算结果。， 在二维平面洒题中，潮格生成和加密算法已经褶当完善，健在三维 空阅阉题中，上述工 乍还处在探讨阶段。本文以实现三维空闽的网格生 、2 善， 成及加密算法为目的，主要恻j 下几个方面的工作： 一、d e l a u n a y 谣面体溺格的生成算法及程序实现 上海交通太学磺士擎拄论定 i md c l a u n a , 口月格成蜜技术目应月摘要 ( 1 通过程序实现了网格点的生成及插入算法。生成的网格点分布 均匀，为生成形状较好的网格打好了基础。 2 实现了d e l a u n a y 四面体网格的生成算法，该算法是对二维 d e l a u n a y 三角化算法的推广。通过对可视性检验法的改善避免了空间单 元的重叠。 3 设计了如何判断一个点是否在封闭区域内部还是外部的算法， 解决了d e l a u n a y 网格生成算法不能处理凹形物体的问题，从而实现了任 意复杂形状三维物体的网格生成算法。 4 设计了一套有效的数据结构来实现对三维空间内点、面和单元 的管理，为程序的编制和改进提供了基础。，j 一一、 二、 四面体网格加密算法及程序实现 1 推广了最长边加密算法，实现了对加密单元的相邻单元的直 仂调加密算法。该算法能够改善初始网格单元的形状。 2 实现了网格的局部加密算法，能够对任意指定区域内部的网格 进行加密。程序编制了球区域、圆柱体区域以及立方体区域这三种常见 的指定区域的判断准则。 3 对于具有曲面边界的网格，提出了在加密过程中实现曲面边界 逼近的算法。程序实现了二次曲面边界的加密逼近功能。 三、自适应网格的有限元接口 上海交通大学硕士学位论文l l = m d e l a u n a ) 口口月# l 成密术目月 摘要 ，1 给网格加入了材料、约束和荷载三种物理信息，以便与常规有 限元计算程序接口。 2 实现了分布荷载的结点化算法，程序对直线分布荷载、曲线分 布荷载、平面分布荷载以及曲面分布荷载这几种情况分别进行了处理。 3 实现了网格加密过程中物理信息的继承，提出了加密过程中荷 载重分配的简便算法。 4 加入了对指定单元进行加密的功能，实现了与误差估计程序的 接口。 算例结果表明，本文所述的网格生成加密算法和程序能够实现复杂 形状的三维物体的网格生成和加密，生成的网格单元具有较好的形状。 由于实现了与常规有限元计算程序以及误差估计程序的接口，本文所述 程序可以作为自适应网格计算程序的一部分。 如何处理多材料物体，实现具有约束面的d e l a u n a y 网格生成算法是 今后的主要研究方向。 关键词：有限单元法，网格生成，网格加密，四面体，边界逼近，自适 q 一 “ 、。 应 上海交通大学硕士学位论文1 i i = 镕d e l a u n a ) 日i m 月镕l 成$ $ 目月 摘要 t e c h n o l o g ya n da p p l i c a t l 0 no fm e s h g e n e r a t i o na n dm 匠s hr e f i n e 匝n t a b s t r a c t w h e nu s i n gf n i t ee l e m e n tm e t h o dt os o l v et h em e c h a n i c sp r o b l e m ，i t1 s r e q u i r e dt h a tt h er e s e a r c h i n go b j e c tm u s tb es p l i ti n t oe l e m e n t sf i r s t ，w h i c hi s c a l l e dm e s hg e n e r a t i o n w h e nt h em e s hi sg e n e r a t e d ，t h en u m b e ro ft h e e l e m e n t sw i l ld i r e c t l ya f f e c tt h ea c c u r a c yo ft h ef i n a lc o m p u t er e s u l t i no r d e r t om i n i m i z et h ec o m p u t ee r r o r ，t w om e t h o d sc a nb ea c c e p t e d o n ei st o g u a r a n t e et h a t e v e r ye l e m e n to ft h eg e n e r a t e dm e s hh a sag o o ds h a p e ，t h e o t h e ri st or e f i n et h em e s hw h e r et h en u m b e ro ft h ee l e m e n t si sn o ts u f f i c i e n t a l lo ft h ew o r kc o u l db ed o n ea r t i f i c i a l l y , b u ti ft h e r ea r eal o to fr e q u i r e dd a t a t h a tm u s tb ep r e p a r e d ，t h ew o r kw i l lb e v e r yh a r da n dc o m p l i c a t e d i n a d d i t i o n t h ef i n a l c o m p u t er e s u l tw i l lb ed i f f e r e n ta c c o r d i n gt od i f f e r e n t p e r s o nw i t hd i f f e r e n te x p e r i e n c e w i t ht h ed e v e l o p m e n to fc o m p m e u s i n g p r o g r a mt og e n e r a t em e s ha n dr e f i n ei t h a sb e c o m eap o p u l a rr e s e a r c h i n g p r o j e c t c o m p a r ew i t ht h ea r t i f i c i a lw a y , t h en e wm e t h o di sm o r ec o n v e n i e n t a n dm o r ec r e d i b l e w h e nt h em e s hr e f i n e m e n tp r o g r a mi sa s s o c i a t e dw i t ht h e c o n v e n t i o n a lf i n i t ee l e m e n tp r o g r a ma n dt h ee r r o re s t i m a t e a l g o r i t h m ，a n a d a p t i v e f i n i t ee l e m e n t p r o g r a mw i l l b e g e n e r a t e d t h ea d a p t i v e f i n i t e e l e m e n tp r o g r a mc a na u t o - r e f i n et h em e s h a c c o r d i n g t ot h e e x p e c t e d a c c u r a c y i nt h e2 df i e l d ，t h ea l g o r i t h mr e s e a r c hw o r ko fm e s hg e n e r a t i o na n d m e s hr e f i n e m e n th a sg o tg r e a ta c h i e v e m e n t s b u ti nt h e3 df i e l d ，t h ew o r ki s s t i l lu n d e rd i s c u s s i n gb e c a u s et h ep r o b l e mi sm u c hm o r ed i f f i c u l t i no r d e rt of u l f i l lt h ea l g o r i t h mo fm e s hg e n e r a t i o na n dm e s hr e f i n e m e n t = 镕d d a u n a y 日口月格生成g & 术自月 摘要 i n3 df i e l d ，i nt h i sp a p e r , f o l l o w i n gw o r kh a sb e e ns t u d i e d 1 a l g o r i t h mo ft h ed e l a u n a yt e t r a h e d r o nm e s hg e n e r a t i o n 1 ) f u l f i l l i n gt h ea l g o r i t h mo fg e n e r a t i n gt h en o d e s i no r d e rt oo p t i m i z e t h ee l e m e n t st h a tw i l lb eg e n e r a t e d ，t h es p a c eb e t w e e ne a c hn o d ei su n i f o r m 2 ) f u l f i l l i n gt h ea l g o r i t h mo fg e n e r a t i n gd e l a u n a yt e t r a h e d r o nm e s h t h i sa l g o r i t h mi st h ee x t e n s i o no f2 dd e l a u n a yt r i a n g l em e s hg e n e r a t i o n v i s i b i l i t yc h e c km e t h o di su s e dt oa v o i dt h eo v e r l a p i n go fe l e m e n t s 3 ) f u l f i l l i n gt h ea l g o r i t h mo fh o wt oj u d g ew h e t h e ran o d ei si nt h e o b j e c to rn o t a s s o c i a t e dw i t ht h ea l g o r i t h m ，d e l a u n a ym e t h o dc a r lb eu s e dt o d e a lw i t ht h ec o n c a v eo b j e c t 4 ) d e s i g n i n gt h ed a t as t r u c t u r et om a n a g et h en o d e s ，f a c e sa n de l e m e n t s 2 a l g o r i t h mo f t h et e t r a h e d r o nm e s hr e f i n e m e n t 1 ) f u l f i l l i n gt h ea l g o r i t h mo fa l w a y sc o n f o r m i n gt h en e i g h b o re l e m e n t s f r o mt h i sw a yt h eo r i g i n a le l e m e n t s s h a p e sc a nb ei m p r o v e d 2 ) f u l f i l l i n gt h ea l g o r i t h mo fr e f i n i n gt h el o c a la r e ao ft h eo r i g i n a lm e s h t h ep r o g r a mc a nr e f i n et h ee l e m e n t si na n yd e f i n e dl o c a la r e a t h ed e f i n e d l o c a la r e ai sd i v i d e di n t ot h r e ef o r m s ：b a l la r e a ，c y l i n d e ra r e aa n dc u b ea r e a 3 ) f u l f i l l i n gt h ea l g o r i t h mo f a p p r o a c h i n gt ot h ec u r v i - f a c ew h e nr e f i n i n g t h ep r o g r a mh a st h ef u n c t i o no fa p p r o a c h i n gt ot h ec o n i c o i d 3 p r o g r a mi n t e r f a c ew i t ha d a p t i v ef e mp r o g r a m 1 ) a d d i n g t h ep h y s i c a li n f o r m a t i o ns u c ha sm a t e r i a l ，r e s t r a i na n dl o a dt o t h em e s h ，w h i c hm a k e st h ep r o g r a mc a nb ea s s o c i a t e dw i t hc o n v e n t i o n a lf e m p r o g r a m 2 ) f u l f i l l i n gt h ea l g o r i t h mo ft r a n s f o r m i n gt h ed i s t r i b u t i n gl o a d st ot h e n o d e s t h ep r o g r a mc a r ld e a lw i t hf o u rk i n d so fd i s t r i b u t i n gl o a d ss u c ha s l i n e l o a d ，c u r v e - l o a d ，p l a n e l o a da n dc u r v i f a c e 1 0 a d 3 ) f u l f i l l i n gt h ea l g o r i t h mo fi n h e r i t i n gt h el o a d sw h e nr e f i n i n g d e s i g n i n gas i m p l ep r o g r a m t of u l f i l li t 4 ) a d d i n gt h ef u n c t i o no fr e f i n i n gt h ed e f i n e de l e m e n t s ，w h i c hm a k e st h e p r o g r a mc a n b ea s s o c i a t e dw i t ht h ee r r o re s t i m a t ea l g o r i t h m r e s u l t so ft h ee x a m p l e ss h o wt h a tt h ea l g o r i t h ma n dt h ep r o g r a ma r e 上海交通大学硕士学位论文 v = 摊d e l a u n a 自格 成$ 水与应_ 幂摘要 e f f i c i e n tt og e n e r a t ea n dr e f i n e t h et e t r a h e d r o nm e s hf o r t h eo b j e c t sw i t h c o m p l i c a t es h a p e s 。a n dt h ep r o g r a mc a na l s ob eap a r to ft h ea d a p t i v ef e m p r o g r a m 。 h o vt od e a lw i t ht h eo b j e c tw i t hm u l t i m a t e r i a la n dh o wt of u l f i l lt h e a l g o r i t h mo fg e n e r a t i n gt h et e t r a h e d r o nd e l a u n a ym e s hf o rt h eo b j e c tw i t h r e s t r a i n e df a c e sa r et h ee m p h a s e so f t h ef u t u r er e s e a r c h i n gw o r k 。 k e yw o r d s ：f i n i t e e l e m e n tm e t h o d ，m e s hg e n e r a t i o n ，m e s h r e f i n e m e n t ， t e t r a h e d r o n ，a p p r o a c h i n g ，a d a p t i v e 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的裁定， 同意学校保翳并向豳家有关部门或机构送交论文的复印件和电子 版，兔许论文被查阕和借阕。本人授权上海交逶大学可以将本学位 论文的全都或部分内容编入有关数据库进行检索，可以采焉影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密霭，在l 年勰密廷逶用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框肉打“” 学位论文作者签名：纷琏妫 日期：d a 年p 月j d 曰 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：纷缝够 日期：d 彻o j 年。) 月一2 日 i m o e i a u n a y 月 备趣成密技$ s s 第一章缝论 第一睾绪论 随着计薄机的发展，有限元法在众多领域得到了广泛的应用，特剐是在土木工程 领域，有限元法已经成为工程结构力学性能数值分析的主要工具。在应用有限元方法 分析工程结构时，一个重要的步骤是根据研究对象的物理及几何边界划分出所需要的 网格，这部分工作称为网格的生成。在实际工程计算中，存在大量的应力集中区，要 提高这类区域的计冀精度，势必要在该区域对原有网格进行局部细分，这部分工作称 为网格的加密。 通过生成和加密所形成的网格只具有几何上的意义，是不能直接用于有限元计算 的。如柴给网格赋以物理信息，如材料、约束和荷载等信息，设计好网格与有限元程 序的接口部分，便可将艇生成的网格运用到有限元计算当中。进一步地，如果能够与 误差估计算法结合起来，便能够实现网格的自适应加密功能。 1 1 网格生成算法械述 网格生成技术发展到现在，已经出现了大量的不同实现方法。按照网格所生成的 单元类型可以分为生成结构化( c o n s t r u c i o n ) 网格的方法和生成非结构化 ( n o n c o n s tr l l c t i o n ) 网格的方法。结构化网格采用的单元是四边形( 二维) 或六面 体( 三维) 。其特点是每一结点与其相邻结点之间的连接关系嘲定不变，因此结点的 邻接关系是可以依据网播编号的规律自动得出的，不必专门储存这一僚息，这是结构 化网格的一大优点。但是当计算区域比较复杂时，难以处理所求解的不规则区域。生 戏结构化网格的方法是映射法，通常嚣要人工来完成，因而自动化程度低。不造合自 动阚揍的生戏。本文着莛介绍生成非结构化网格的方法，这类方法可以采用三危形( 二 维) 或四露体( 三维) 作为网揍单元，能够较好地逼近区域边爨，面且一般都可实现 不周程度的塞动化。琏藿计算枫的普及应髑，j # 结构化嘲格的生成方法缮到了迅速灼 发提。棼缝构化网播鲮单元邻接关系可以不一致，如四边形单元，每一边上既可以有 一个邻接孳元，也可以有嚣个邻接单元。本文只讨论三角形网摄( 二缍蠖况) 釉四蠢 体瓣穰( 三维情况) 。 一个好的躅格生成算法必需保证其有好匏网撂单元形状。繇淫好的嘲撂单元形 获，篱擎丽言就是单元豹形状不链太尖或密太赢，即摹元熟最小焦不小于禁个毽( 如 2 0 度) ，苇元静最大角不大予菜个僮( 妇t 6 0 菠) 。好的鼙元形状怼予数毽分板是龚 i 擅d e ia u n a y 日月格成力口密& 术目n 月 第一章绪论 常重要的，形状差的单元会大大降低计算的收敛速度，对于非线性问题甚至使计算无 法收敛。因此，网格生成算法总是以生成形状较好的单元为目的。但是，当实际几何 模型本身形状就很差时( 具有很小角度的边或面) ，生成形状差的单元在所难免。下 面介绍一下几种具有代表性的网格生成方法：d e l a u n a y 三角化法、前沿推进法和八叉 树法。 1 1 1d e l a u n a y 三鹧化法 d e l a u n a y 三角化法源于1 9 3 4 年b d e l a u n a y 提出的d e l a t m a y 准则。它本身并不 是一种网格生成算法，它仅仅提供如何对已知的一群散点进行连接的准则。尽管该准 则已提出了多年，但是直到近二十年才被运用到网格生成算法中。在二维情况下， d e l a u n a y 三角化法所生成的三角形网格具有以下特点： ( 1 ) 所形成的三角形互不重叠； ( 2 ) 所形成的三角形可以覆盖整个平面； ( 3 ) 每一个点均不位于不包含该点的三角形的外接圆内。 ( a )( b )( c ) 图1 - 1 不同的连接方法对三角形最小角的影响 f i g1 1d i f f e r e n ti n f e c t i o nb yd i f f e r e n tc o n n e c tm e t h o dt ot h em i n i m u ma n g l eo f t r i a n g l e 对于一组给定的点，用d e l a u n a y 三角化法所形成的网格中的各三角形的最小角 是各种连接方案中的最大者。如图1 1 所示，对于给定点a 、b 、c 、d 、e ，采用三 种不同的连接方案来组成三角形网格。( a ) 所示连接方案中的虚线圆是c i ) e 的外接 圆，( b ) 所示连接方案中的虚线圆是a c d 的外接圆。显然，( c ) 所示连接方案中的 三个三角形的最小角最大，因而边长的均匀性也最好。从几何上分析，这是因为( c ) 所示连接方案中的每一个三角形的外接圆都不包括除了该三角形三个顶点以外的点， 而( a ) 和( b ) 所示方案则不是如此。这就意味着，用d e l a u n a y 三角化法形成的三 角形的边长的均匀性是最好的。显然，这一点对于网格生成是非常具有吸引力的，因 - i t l ld ea u n a y 日月# l 戚密# $ 目月 第一章绪论 而d e l a u n a y 三角化法得到了迅速的发展，出现了大量的不同算法。一般来说d e l a u n a y 三角化法可以分为以下三大类 2 】：以b o w y e r 3 】和g r e e n 、s i b s o n s 为代表的计算v o r o n o i 图方法：以w a s t o n 4 1 为代表的空间外接圆法和以l a w s o n l 5 1 为代表的交换对角线算法。 其中，计算v o r o n o i 图方法复杂且效率低，现在已经很少采用。交换对角线算法适用 于二维领域，但在三维情况下，基于最大一最小角判据的对角线交换规则不再适用， 因此不容易推广到三维领域。目前应用最广的就是空间外接圆法，但在三维情况下， 空问外接圆法一般也不再能保证生成的网格质量，而且在三维情况下，点、边、面的 管理及单元之间的相邻关系更加复杂，单元重叠的可能性也更大，给研究工作带来了 较大的难度。此外，d e l a u n a y 三角化法的局限在于它只适用于凸形( c o n v e x ) 物体， 对于凹形( c o n c a v e ) 物体，它只能根据给定的空间散点生成一个由多个网格单元所 构成的凸包( c o n v e xh u l l ) ，因此不能直接用d e l a u n a y 三角化法来生成凹形物体的网 格。以上种种困难，使得三维d e l a u n a y 网格生成算法仍处于发展中。 1 12 前沿推进法( a d v a n c n gf r o n tm e t h o d ) 前沿推进法是在1 9 8 5 年由l 0 1 6 1 提出的，用于平面区域三角形网格的自动生成。 该方法将边界进行剖分并作为最初的推进边线( 前沿) ，在网格生成过程中，将当前 的边线逐渐向区域内部推进形成新的边线，并连接成单元。如此不断向区域内部推进， 直到前沿的行列为空，整个区域被所生成的网格覆盖为止。在二维问题中向前推进的 是线，在三维问题中向前推进的是面。前沿推进法包括边界前沿的形成、区域内部点 的形成、连接点形成三角形以及网格的光顺滑四个部分。p e r a i r e 等引入了背景网格来 控制网格特性参数以确定内点的生成位置，推广了前沿推进法在二维领域中的应用。 后来l o h n e r 7 1 将前沿推进法推广到了三维领域，用以生成三维四面体网格。 图卜2 前沿推进法生成网格 f i g 1 - 2 e x a m p l eo f m e s hg e n e r a t e db y a d v a n c i n g f r o n t m e t h o d 图j 一2 所示的是用前沿推进法生成网格的例子。对于具有复杂形状的二维域或三 维域的网格生成，前沿推进法比d e l a u n a y 三角化法具有更大的灵活性及可靠性。但 上海交通大学硕士学位论文j i m d e la u n a y 日_ 网# 成密n 术与应j h 第一章绪论 是这种方法的最大缺点是效率相对较低，需要不断花时间来寻找下一个网格点。而且 为了保证形成的网格的质量，必需依赖背景网格来确定点的位置，这样也增加了三维 情况下的应用难度。近年来，出现了些将d e l a u n a y 三角化和前沿推进法相结合的 新算法，拓宽了前沿推进法的应用。 1 13 八叉树法( o c tr e em e t h o d ) 八叉树法最早是由y e i t y 和s h e p h a r d 8 j 提出来的，它又叫做四( 八) 叉树空间分 解方法，对于二维问题一般用四叉树，对于三维问题一般用八叉树。该方法首先将目 标区域用一个尽可能小的方盒( 正方形或立方体) 圈定，然后将这个方盒分解成四( 八) 个子区域，对每一个子域测试其是否完全在目标区域外面和是否满足密度控制的要 求。若满足所给定的条件则停止对此子域的细分，否则将之细分，该过程迭代执行下 去直到达到预定的离散要求为止。图1 3 所示为八叉树法生成网格的过程。在细分的 过程中，相邻的子域最多只能相差一级的分划水平，这样目标区域就被一些相互不重 叠的各种大小的方形子域拼成的图形所逼近。用八叉树法形成的内部网格单元形状较 好，但边界网格单元形状较差，而且当目标区域的边界很复杂时，某些子域不得不分 成许多个网格单元，因此网格数量较大，程序实现也太复杂。基于以上原因，目前该 方法研究的人不多。 图1 3 八叉树法生成网格举例 f i g j - 3e x a m p l eo f t h ep r o c e s so f m e s hg e n e r a t i o nb yo c t r e em e t h o d 1 2 网格加密算法概述 网格加密的用途有两个，一是逼近不规则边界，一是提高计算精度。通常不必 对全部的网格都进行加密，而只需加密局部网格。对于结构化网格，由于单元邻接关 系的一致性，难以实现网格的局部加密功能，所以网格加密算法一般用于非结构化网 格。网格的加密也意味着新网格的诞生，所以通常也可把这部分工作划归到网格生成 上海交通大举硕士学位论文4 - ! 1 l td ea u n a y 口t 月# 生m 密技$ 目e 月 第一章绪论 中，统称为网格生成算法。但是网格加密算法与网格生成算法所考虑的主要问题不同， 特别是下面要介绍的最长边加密算法，完全是在初始网格已经具备的前提下进行的， 因此本文将网格加密算法单独列出来讨论。对于三角形网格或四面体网格，常用的加 密算法有三种：剖分边法、插入点法和模板法。 1 2 1 剖分边法( e d g eb i s e c t i o n ) 边剖分法是将需加密单元的一条边分成两半，那么该单元便一分为二，从而达到 了加密的目的。同时，所有包含有这条边的单元都要相应地分为二，如图1 - 4 所示。 图1 4 四面体单元的边剖分a b 边被c 点剖分，包含a b 的所有单元也被剖分为二 f i g 】一4e d g ei n s e c t i o ni nat e t r a h e d r a lm e s h e d g ea - bi ss p l i ta tp o i n tc ，a l s os p l i t t i n gi t s s u r r o u n d i n gt e t r a h e d r o n s r i v a r a 9 1 提出了最长边加密算法，即应该对需要加密单元中最长的边进行剖分。 由图1 5 可以看出，采用最长边加密算法的( c ) 方案所生成的新单元的形状是最好 的。对于最长边加密算法，r i v a r a 提出了分子表数据结构，利用该方法可以将网格加 密与有限元计算统一管理起来，具有较高的效率。在国内。王建华等1 0 】在此基础上实 现了平面任意区域网格加密算法，陈振建【1 1 】对最长边加密算法在三维空间内的应用进 行了探讨。 图1 _ 5 不同边剖分后对单元形状的影响 f i g 1 5d i f f e r e n ti n f e c t i o n st ot h es h a p e so f e l e m e n t sb yb i s e c t i n gd i f f e r e n ts i d e s = 自l d e ia u n a y 口体罔格l 成加蔷术与应月 第一章绪论 122 插入点法( p o i n ti n s e r t i o n ) 最简单的插入点法是在需要加密的单元的内部插入一个新点，然后将该点与单元 的其他顶点相连。对于三角形单元，原单元一分为三；对于四面体单元，原单元一分 为四。但是经过这样加密后生成的新单元形状不好，为此可沿用d e l a u n a y 三角化算 法，将插入点插入到原网格中。所以这种加密算法实际上也就是网格生成算法的延续， 如图1 6 所示。 图1 7 采用模板法来加密单元a 和b f i g 1 7e x a m p l eo f l o c a lt r i a n g l er e f i n e m e n tu s i n gat e m p l a t ew h e r ee l e m e n t sa taa n db a r er e f i n e d 对于三角形单元，原单元被一分为四；对于四面体单元，原单元的每个面被分 为四，整个单元被一分为八。s t a t e n l l 2 1 对此方法作了详细的叙述。与剖分边法相比， 在初始网格单元形状较好的情况下，需加密部分生成的新单元的形状较好，但对于加 密单元的相邻单元，则被分解为形状较差的单元。 上海交通大学硕士学位论文 - - = i n l d e la u n a y 日_ 网# l 成密n $ 目_ 甩 第一章绪论 1 3 自适应网格介绍 自适应网格技术起源于将自动控制理论引入到数值分析方法中这一思想。在自动 控制理论中信息反馈是关键问题，根据信息反馈可以更准确地实施控制并达到预期目 标。在自适应网格技术中，误差估计充当了信息反馈这一角色，通过误差估计算法， 可以实现网格的自动加密，以达到所需的计算精度。 白1 9 7 8 年美国马里兰大学b a b u s k a ”】提出有限元后验误差估计算法以来，自适 应网格技术得到迅速的发展。其研究工作主要集中在两个方面：后验误差估计方法的 研究；网格生成器与有限元计算程序的接口设计。 131 后验误差估计方法的简介 自适应网格的加密分为h 加密、p 加密和h p 加密几种形式。h 加密指保持单元 形函数的阶数不变，通过逐步加密网格使结果向精确解逼近：p 加密是指保持单元的 几何尺寸不变，通过增加单元形函数的阶数来逼近精确解。通常p 加密的速度比h 加密快，而将h 加密和p 加密结合起来即h - p 加密的加密效果最好。根据加密方法的 不同，后验误差估计的方法也有所区别。由于实际工程中用的最多的加密方法是h 加密，即1 2 节所介绍的加密方法，因此本文只对在h 加密下的后验误差估计的方法 作简要介绍，关于p 加密和h - p 加密下的后验误差估计方法可参考文献f 1 4 】和i ”】。 基于h 加密的后验误差估计方法可以分为两类：基于平衡方程的残值法和基于有 限元解的后处理法。残值法即通过计算局部区域残值而得出的误差估计方法，由 b a b u s k a 和r h e i n b o l t 1 3 , 1 4 在1 9 7 8 年提出。该方法具有较好的数学理论基础，但是由于 形式复杂而没有在工程中得到广泛的应用。1 9 8 7 年0 c z i e n k i e w i c z 和j z z h u t l 6 】提出 了一种与残值法有着根本区别的后处理法( 简称z z 方法) ，该方法计算简单、易于 理解，而且和有限元应用程序接口方便，因而得到了工程界的广泛应用。经过众多学 者的努力，后处理法得以不断地改进，成为误差估计的主要方法。 132 网格生成器与有限元计算程序的接口设计 一个具有网格生成和网格加密功能的程序称之为网格生成器，但是若要将该程序 与现有的有限元计算程序结合起来用于工程计算，就必需实现网格生成器与有限元计 算程序的接口。该部分工作主要包含两个方面：赋予单元物理信息( 材料、约束、荷 载等) 和在网格加密过程对以上物理信息进行处理。其中后一部分工作是重点，主要 表现在以下两个方面： = - - - t l t d e ia u n a y 日_ 网# 成加密$ 目t 月 第一章绪论 1 ) 加密过程中材料信息的继承。老单元经过加密后不再存在于网格中，新单元的材 料与老单元一致。对于均质材料问题，以上功能很容易实现；对于非均质材料问题， 情况就要复杂得多。因为在材料的交界处，不允许出现含有一种以上材质的单元，这 在实际工程计算中是没有意义的。在岩土工程领域的实际计算中，土体的材质是非常 复杂的，在任意方向都有可能出现材料的交界面，而材料的交界处又是应力分析的重 点，因而如何实现多材质对象的网格加密也就成为了研究的热点。 2 ) 加密过程中荷载的的重分布。在实际工程计算中，纯粹的集中点荷载是不存在的， 研究分析的荷载一般都是分布荷载。在有限元计算中，物体所受的分布荷载需要转换 成结点荷载，称为荷载的结点化。分布荷载结点化的转换公式是由荷载的分布区域以 及该区域内单元的数目所决定的。在加密过程中，若荷载分布区域内的单元数目发生 了变化，则该区域内的单元的结点荷载要进行重分布。 实现了网格生成器与常规有限元计算程序的接口后，可以进一步地实现网格生成 器与误差估计程序的接口，三者结合起来，形成自适应网格计算程序。 1 4 本文的研究内容 本文的研究内容分为网格生成、网格加密和有限元程序接口设计三部分。 在网格生成部分，本文采用了d e l a u n a y 三角化算法。基于外接圆判据的d e l a u n a y 准则是应用于二维领域的，本文运用的是基于外接球判据的d e l a u n a y 算法，它是二 维d e l a u n a y 三角化算法在三维空间内的推广，网格所用的单元由二维情况下的三角 形变为三维情况下的四面体。 为了较好的管理三维空间内的点、面和单元，本文设计了一套数据结构，具体将 在第二、三、四章中介绍。h b o r o u c h a i 和s h l o 在文献【】7 中提出了可视性检验法 ( v i s i b i l i t yc h e c k ) ，对避免单元重叠( o v e r l a p ) 的方法作出了探讨。本文对该方法进 行了修正，有效地避免了四面体单元的重叠。针对d e l a u n a y 三角化方法只能生成凸 形物体的网格这一问题，本文给出了如何判断一个点是在任意区域内还是在区域外的 算法，由此可以在d e l a u n a y 三角化完成以后将生成的凸包中不在研究区域内部的单 元删去，从而达到生成凹形物体网格的目的。在程序中通过引入背景网格加快了这部 分算法的实现速度。有关网格生成的算法描述详见第三章。 在网格加密部分，本文采用了最长边加密算法。对于平面问题，最长边加密算法 可在有限步达到网格局部加密效果，这一点已被严格证明【1 8 】；对于空间问题，最长边 加密算法同样可在有限步达到网格局部加密效果【l l 】。 【定义】最长边加密法：最长边指的是单元( 三角形单元或四面体单元) 中最长 = md e ia u n a y 口月# l 成力a 密$ 自月第一苹绪论 的那条边。对于需要加密的单元，取该边的中点为网格新增点，将单元中不在此边上 的其他点与新增点相连，原单元一分为二。对于该边所参与的其他单元，新增点为不 协调点( n o n c o n f o r m i n gn o d e ) ，需要进行协调加密。 最长边加密算法可以有效地改善单元的性态，其关键问题在于如何处理好加密单 元和周围需要协调的单元之间的关系，保证网格内不存在不协调点。文献j 采用的直 接协调加密算法简单、速度较快，在网格本身较均匀、初始性态较好的前提下能够取 得较好的加密效果，但对于初始性态较差且不均匀的网格则加密效果欠佳。本文采用 一直协调加密算法，对于初始性态较差的网格也能取得较好的加密效果。同时，对于 具有曲面边界的物体，通过挪动加密点的方法实现了四面体单元网格在加密过程中的 曲面边界逼近功能。有关网格加密的算法描述详见第四章。 在与有限元计算程序的接口设计部分，本文给网格赋予了材料、约束和荷载这三 种物理信息。在网格生成以后，对于分布荷载实现了荷载的结点化；在网格加密过程 中，实现了单元物理信息的继承以及分布荷载的重分配。为了进一步与误差估计算法 结合起来，加入了按指定网格单元进行加密的功能，通过误差估计算法的信息反馈， 能够实现网格的自适应加密。有关这部分的具体内容详见第五章。 三垒堕! ! ! ! 型里曼堡婴堑兰苎塑兰苎查皇皇里 蔓三童墼塑箜塑堡生 第二章数据结构设计 第一章中谈到，在三维情况下，单元之间的相邻关系比较复杂，点、边、面的管 理有定的难度，因此设计套有效的数据结构就成了程序实现的关键。在网格生成 部分，g u i b a s 和s t o l f i i ”】提出的q u a d e d g e 数据结构被广泛地应用于二维网格生成算 法中。该结构以边为基本单位来表达图形元素，能够快速地对图形各部分进行各种变 换操作。d o b k i n 和l a s z l o 2 0 1 将q u a d 。e d g e 数据结构推广到了三维领域，提出了以边 环和面环为基本单位的e d g e f a c e 结构。m u c k e l 2 1 1 将e d g e f a c e 结构进行了简化，提 出了以三角形为基本单元的t r i a n g l e e g d e 结构。s h e w c h u k 2 2 1 进一步提出了以四面体 为基本单位的四面体数据结构，非常适合于生成d e l a t m a y 四面体网格。在网格加密 部分，r i v a r a 提出了适用于二维网格加密算法的分子表数据结构【9 】。该结构将每一个 结点的相邻点记录为该结点