《一种改进的全四边形网格生成方法及优化.doc》由会员分享，可在线阅读，更多相关《一种改进的全四边形网格生成方法及优化.doc（5页珍藏版）》请在三一文库上搜索。
1、一种改进的全四边形网格生成方法及优化李晓辉 , 李昌华(西安建筑科技大学 信息与控制工程学院 , 陕西 西安 710055)摘 要 :在任意二维区域的全四边形网格生成方法中 ,铺砌法是目前较好的一种方法 。但是当边界出现不规则区域时 ,网格生成完毕后内部会产生一些质量较差的单元 ,且判断网格交叉现象是否发生和解决网格交叉问题比较困难 。为了提高 该方法的适应性和可靠性 ,提出一种新的改进算法 ,它对边界不规则区域网格生成和解决网格交叉问题等关键技术进行改 进 ,并加入四边形网格优化方法 ,将改进后的铺砌法应用于船舶有限元网格划分中 ,取得了较好的应用效果 ,最后给出算例 进行了验证 。关键词
2、:网格生成 ; 四边形单元 ; 网格优化 ; 铺砌法中图分类号 : T P391 . 7文献标识码 : A文章编号 :10042373 X (2010) 0820119204Modif ied Method and Optimization of Generating All2qua drilateral MeshL I Xiao2hui , L I Chang2hua( Info rmatio n and Co nt rol Enginee ring School , Xian U nive r sit y of A rchitect ure and Technolo gy , Xian 7
3、10055 , China)Ab stract : The paving met ho d a mo ng t he quadrilat eral me sh generatio n met ho ds in t he ar bit ra r y t wo2dimensio nal i s bet ter . Ho wever , when ir regula r area i s appea red at t he bo r der , so me poo r me shes a re generated in t he inter nal a rea af ter me sh gen2 e
4、ratio n , a nd it i s difficult to deter mi ne cro ss2bo r der p heno meno n in ir regula r regio n and resolve t he cro ss2cut ting i ssue s. A mo dified al go rit hm i s p ropo sed to enha nce t he adap tabilit y and reliabilit y of t he met ho d. It imp ro ve s t he key technolo gie s of generati
5、ng me shes in ir regula r regio n a nd re solving t he cro ss2bo r der p ro blem. In co mbinatio n wit h t he quadrilateral mesh op ti2 mizatio n algo rit hm , t he i mp ro ved p aving met ho d wa s applied i n t he finite element meshing fo r a ship and a goo d eff ect wa s o b2 t ained. A n exa mp
6、le i s given fo r verif ying t he efficiency of t he p ropo sed met ho d.Ke ywords : me sh generatio n ; quadrilateral element ; mesh op ti mizatio n ; paving met ho d里在该方法的基础上进行了一些改进 ,即在每个新单元的生成过程中 ,随时判断有无交叉 ,现象发生 ,若出现交 叉则进行相交和缝合处理 ,而不是等待层生成完毕再处理 ,这样相交判断和处理就得到了很大的简化。同时对小角度缝合处理做了改进 ,增强了边界适应性。最后加 入网格
7、优化模块 ,进一步提高了区域内部的网格质量 。0引言随着计算机科学技术的快速发展 ,以有限元技术为代表的数值方法得到了广泛应用 。然而 ,制约其进一步 发展的主要因素之一是网格划分技术和优化技术 ,特别 是在船舶板架的有限元网格划分中 ,由于精度和质量上 的考虑 ,要求网格单元尽量是四边形。目前 ,网格生成 方法 1 主要有 Dela una y 三角化方法、铺砌法 ( Pa vi ng) 、四 (八) 叉树法、行波法等 2 。其中 , 铺砌法是由 T. D . Blacke r 和 M . B . St ep he n so n 提出的 3 ,该算法重复地 在区域边界内部放一层或者铺一层单元
8、 ,从区域边界开 始向内部形成四边形单元。Whit e 4 重新设计了铺砌 算法 ,单元不是生成一排 ,而是一个接一个的生成 ,它生 成的网格质量和灵活性要优于其他算法 ,尤其是边界单 元 (接近正方形) 5 。方兴、张武等 6 在 Whit e 的基础上 对铺砌法做了改进 ,主要是提出一种节点计算方法 ,但 是在复杂区域的相交和缝合处理等方面仍有不足 。这1铺砌法网格生成算法铺砌法是一种全自动的网格生成方法 ,它不要求预先配置好内部节点 ,单元和节点都在网格划分的过程中 自动生成。1 . 1输入初始条件与起始点的选择为了保证在区域内生成的单元全部为四边形单元 , 要求初始边界上的节点数目为偶
9、数个 。在铺砌过程中 , 首先要在边界上选择网格生成的起始点 ,为了方便生成 网格节点 , 本文取铺砌边界上内角最小的节点为起 始点。1 . 2网格单元的生成 新节点一般是以边界上相邻的三点为基础的 ,并以一定的角度和方向向区域内部投射而生成。如 :新节点119收稿日期 :2009211226基金项目 :国家自然科学基金资助项目( 50878176)的生成是以当前边界上 N i - 1 , N i , N i +1 这 3 个节点为基础的 , 假设节点 N i 的内角为; 节点 N i - 1 到节点 N i 的距 离为 d1 ; 节点 N i 到 N i +1 的距离为 d2 , 则根据节点
10、夹角的不同可分为四种类型 , 即 :终止节点 : 120+; 边界节点 :120+ 240+; 角节点 :240+ 300+。其中 , 取 5 10。界上 N i 的前一节点和后一节点。如果 N i - 1 也为终止节点 , 则 N j , N i - 1 , N i , N i +1 就构成一个单元 。以边节点为基点的生成方法1 . 2 . 1如图 1 (a) 所示 , 由节点 N i - 1 , N i , N i +1 组成当前铺砌边界 , 生成新节点 N j , 同时这四个节点形成了一个新 单元。设新节点是由矢量 V 所决定的 ,V 平分内角, 长 度由下式定义 :图 2 角节点生成法
11、图 3 转角节点生成法d1 + d2( 1)| V | =2 si n (/ 2)对于两节点皆为边节点的特殊情况下新节点的生成如图 1 ( b) 所示。按照边节点的生成算法 ,由节点 N i 生成新节点 N j , 由节点 N i +1 生成新节点 N k , 同时这 四个节点形成一个新单元。图 4 终止节点生成法2相交处理在网格生成过程中 ,本文对边界相交处理顺序进行了调整。在新单元的生成过程中 ,随时判断有无交叉现 象的发生 ,若出现交叉则立即进行相交处理 ,这样只是 局部个别网格的交叉和重叠 ,简化了对交叉重叠问题的 处理 ,也使算法更加稳定可靠 。2 . 1 相交判断在铺砌过程中 ,当
12、铺砌边界与自己或其他铺砌边界 相交时 ,则至少存在一对边相交如图 5 ( a ) 所示。通过 判断线段是否相交即可确定铺砌边界是否相交 , 假设 A B 与 CD 为两条相交线段 , A 表示为从原点到 A 点的矢量; B 表示为从 A 点到 B 点的矢量; C表示为从原点到 C 点的矢量; D 表示为从 C 点到 D 点的矢量 , 则线段 A B 上 P 点的位置矢量和线段 CD 上 Q 点的位置矢量分别 表示为 :图 1 边界点生成法1 . 2 . 2以角节点为基点的生成方法如图 2 所示 ,由 N i - 1 , N i , N i +1 生成三个新节点 N j , N k , N i
13、, 同时形成了两个新单元。三个节点分别由矢量V j ,V k ,V l 决定 。矢量 V j ,V k ,V l 与 N i - 1 N i 的夹角分别为/ 3 ,/ 2 , 2/ 3 , 长度由下式定义 :d1 + d22 | V j | , | V l | V j |= 2 si n (/ 3) , | V k |= | V j |= A + uB , u 0 , 1 = C + w D , w 0 , 1 ( 2)P ( u)Q ( u)( 4)1 . 2 . 3以转角节点为基点的生成方法如图 3 所示 ,由 N i - 1 , N i , N i +1 三点生成五个新节 点 N j ,
14、 N k , N l , N m , N n 同时形成了三个单元。五个新节点分别由矢量 V j ,V k ,V l ,V m ,V n 决定。矢量 V j ,V k ,V l ,V m ,V n 与 N i - 1 N i 的夹角分别为/ 4 , 3/ 8 ,/ 2 , 5/ 8 ,3/ 4 , 长度由下式定义 :当线段 A B 和 CD 相交时 ,则在交点处有 :P ( u) = Q ( u)或A + uB = C + w D由式 (5) 转化为线性方程组 ,可得 :Ax + uB x = Cx + w D x( 5)d1 + d22 | V j | ,( 6)| V j |= 2 si n
15、 (/ 4) , | V k |=Ay + uB y =Cy + w D y( 3)| V l | = | V j | , | V m | = | V k | , | V n |1 . 2 . 4以终止节点为基点的生成方法= | V j |令 :B xBy- D x- Dy( 7)H =如图 4 所示 ,在网格生成过程中 ,遇到终止节点时线段相交 ,相交的相对位置由式 ( 7 ) 解得的 u , w 值而定。有了这些信息 ,就可以计算出适当的方式进行相交 处理。上生成的网格将会产生畸变。此时可以通过嵌入单元 ,改变节点连接来处理。如图 7 所示 ,如果两相邻边的长 短比值大于设定值 ( 本文取
16、 2) 时 , 则应该在长边插入 一个楔形单元来改善相邻边的过渡。在长边中点增加 一节点 d , 且节点 d 在 2/ 3 位置处 。图 5 相交判断图示2 . 2相交处理在生成新单元的过程中 ,一旦判断到相交情况的发 生 ,就立即转入相交处理模块进行相交的处理。根据最 近原则重新连接 ,形成新的铺砌边界 。如果当前边界与 自己发生相交 ,则边界分割后形成两个新的铺砌边界 ; 如果是与其他边界相交 ,则两条边界连接后合并为一条 铺砌边界 ,如图 5 ( b) 所示。但前提是保证新生成的铺 砌边界上的节点数为偶数 ,若为奇数 ,则通过调整相应 的参数 u 和 w 来调整分割或连接的位置 。相交处
17、理完 之后要进行缝合和光顺处理。图 7 过渡缝合处理4网格质量优化一般情况下 , 用上述算法生成的网格并不是最优的 ,其中包含有一些质量较差的单元 ,要对其进行网格 优化 ,以便尽量减少不规则单元的数目。网格优化技术 大致可分为两类 :拓扑优化和几何优化 8 。几何优化是 调整网格中的节点位置 ,提高单元的几何质量 ,而节点之间连接关系保持不变 。与此相对 ,改变节点之间的连 接关系的网格优化技术则称为拓扑优化。4 . 1 网格拓扑优化拓扑关系是指网格节点的连接关系 ,拓扑关系的调 整是指改变节点之间的连接关系 ,也包含通过增加或删3缝合处理网格生成的过程中 ,可能会出现内角较小的节点 ,这时
18、可以通过小角度缝合处理来消除此夹角 ,有时也可 能会出现相邻边长短悬殊较大的情况 ,此时可通过过渡缝合处理的办法使过渡更加均匀化 7 。3 . 1小角度缝合处理 当浮动边界上节点的内角小于某一给定的阈值时 ,将会在网格中形成一道细缝 ,此时应该进行小角度缝合 处理 , 以便于后续网格的生成和提高网格的质量 , 如 图 6所示。 9 除网格中的节点。对四边形网格而言 ,四边形单元的最佳形状是正方 形 ,其内角为 90,因而 ,其内部节点的相邻单元个数 N e (节点周围的单元数目) 最好为 4 ,这样可以使这一结点 的周围单元在此点的平均内角为 90。当某一个内部 节点的 N e 比 4 大或小
19、很多时 ,环绕该节点的单元就会 产生很大的畸变 ,此时 ,就应该对其调整 ,主要的调整方 法有单元删除和单元交换 。4 . 1 . 1单元删除 通过删除某些单元可以改变局部的网格质量 ,单元删除涉及到三个检测 :节点检测 、边检测和单元检测。 (1) 节点检测 。如果某一节点周围只有两个单元 , 并且该节点不在约束边界上 ,则该节点删除 ,以该节点 为端点的两条边也同时删除 , 两个单元合并为一个单 元 ,如图 8 (a) 所示。通过删除这些节点 ,可以很好地删除对网格质量有重要影响的凹四边形 。(2) 边检测。如果某一边的两个端点周围都是图 6 小角度缝合处理图 6 中 : N e 为节点内
20、角顶点处与节点相连的边数 ; 为 节点内角; N n 为缝合后与缝合节点相连的边数 , 其 选取准则是根据节点内角大小和 N e 决定 ,即 : 15, N e 5 30, 其他 分别采取图 5 (a) , ( b) 的方法。3 . 2过渡缝合处理当网格生成单元的相邻边长比例过大时 ,在此基础三个单元 , 如图 8 ( b) 所示 , 删除该边和两个单元E1 ,E2 。新四边形有两种选择 , 取 N e 值最小的为最终边。121(3) 单元检测。如果某一四边形单元 E1 的对角线上两端的节点 N 1 , N 2 周围都是三个单元 , 则应该删除 四边形单元 E1 应该删除 , 同时 N 1 和
21、 N 2 合并为一个节点 ,如图 8 (c) 所示。N i1= X jX iNi j = 1( 8)N i 1 =Y jY iNi j = 1式中 : N i 是与节点 i 相邻的节点总数 ; j 是与 i 相连的节点 ; X j 和 Y j 是节点 j 的坐标值。使用这种方法简单可 靠 ,计算效率高 ,对网格质量的提高起到了非常重要的作用。但是 L ap lace 修匀同样也具有准则法所固有的 不足 ,最根本的问题在于不能确定修匀后的网格是否为 最优网格。图 10 给出网格优化前后的比较 。由于铺砌 法由于是从边界向区域内部生成单元 ,所以内部单元的 质量比较差 。图中经 L ap lace
22、 修匀后 ,中心的网格质量得到提高。图 8 节点删除 、边删除和单元删除4 . 1 . 2单元交换 依次对所有由内部节点连接的单元边进行检验 ,如图 9 (a) 所示 ,若满足 N e ( A ) + N e ( B ) 9 , 公共边 A B将被调换成 CD 或者 E F , 单元边满足以下关系 :N e ( A ) + N e ( B ) ; N 2N 3 = N e ( E)N e ( C) + N e ( D) ;N 1=+ N e ( F)图 10 网格修匀(1) N 1 N 2 + 3 且 N 3CD , 如图 9 ( b) 所示。( 2) N 1 N 3 + 3 且 N 2E F
23、 , 如图 9 (c) 所示。 N 2 公共边 A B 调换成5网格生成实例 N 3 公共边 A B 调换成图 11 给出用上述铺砌法生成的网格图 。由图中可以看出 ,区域边界几何形状复杂 ,截面变化较大 ,属于复 杂边界情况 。但从生成的网格来看 , 不仅边界拟合良 好 ,而且网格质量较高。图 9 单元交换4 . 2 网格几何优化网格的几何优化处理指网格生成后进行的网格调 整 ,在保证单元尺寸、单元节点的拓扑关系的基础上 ,进行单元节点的重新布置。大部分的几何优化算法都是以某种顺序遍历网格中的节点 ,逐个调整节点位置 ,提 高单元质量。在网格几何优化过程中 ,普遍采用的技术 是拉普拉斯光顺处
24、理 (L ap lacia n Smoo t hi ng) 。目前为止拉普拉斯光顺处理应用得最广泛 、最有 效 ,同时也是最成熟的网格优化方法 10 。拉普拉斯光 顺算法的基本原理是保持网格拓朴关系不变 ,将整个内 部节点的位置移动到由其相邻节点组成的多边形形心 位置 ,从而优化每个单元的形状。将这个移动过程遍历所有内部节点若干次 ,可较大地提高网格质量。拉普拉图 11 网格生成实例6结语通过对铺砌法进行了的改进 ,实现了对任意复杂区域全四边形网格的自动划分。与原算法相比 ,本算法的 优越性主要体现在 :在网格生成之前对初始边界进行先处理 ,增强了程序的适应性 ; 原算法中待一层单元生成 完毕
25、后再进行相交处理 ,本文采用边生成边进行相交判 断 ,一旦发现相交情况 ,立即转入相交处理模块 ,使相交 处理极为方便 ;缝合处理时 ,对不同小角度进行分组缝 合处理 ,提高了网格单元的质量 ; 最后通过几何优化和此 ,本文将截集 FCM ( SFCM ) 聚类算法和特征加权FCM ( W FCM) 聚类算法相结合 ,提出了截集型特征加 权模糊 C2均值 ( SW FCM ) 聚类算法 。实验结果表明 , SW FCM不仅具有良好的特征选择能力和很强的抗噪 声性能 ,而且具有较高的收敛速度 ,是一种经济有效、可 供选择的聚类算法。to t yp es and at t ribute weigh
26、t s J . Pat ter n Reco gnitio n ,2004 , 37 (3) : 5672581 . 5 李洁 , 高新波 , 焦李成. 基于特征加权的模糊聚类新算法J . 电子学报 , 2006 , 34 (1) : 89292 . 6 H U N G W L , YA N G M S , C H EN D H . Boo t st rapping ap2 p roach to f eat ure2weight selectio n in f uzzy C2mea ns algo2 rit hms wit h a n applicatio n i n colo r i mag
27、e segmentatio n J . Pat ter n Reco gnitio n L et ter s , 2008 , 29 (9) : 131721325 . 7 陈新泉. 特征加权的模糊 C 聚类算法J . 计算机工程与设计 , 2007 , 28 (22) : 532925333 . 8 裴继红 , 范九伦 , 谢维信. 一种新的高效软聚类算法 : 截集 模糊 C2均值聚类算法J . 电子学报 ,1998 , 26 (2) : 83286 . 9 YA N G Miin2shen , WU Kuo2l ung. Alp ha2cut implement ed f uzzy cl
28、ustering algo rit hms and switching regre ssio ns J . IE E E Tra ns. o n Systems , Ma n a nd Cyber netic s , Part B ,2008 , 38 (3) : 5882603 . 10 L I Y H , DON G M , H U A J . Localized f eat ure selectio n fo r cl ustering J . Pat t er n Reco gnitio n L et ter s , 2008 , 29 (1) : 10218 . 11 BL A KE
29、 C L , M ERZ C J . U CI repo sito r y of machine lea r ning Databa ses EB/ OL . 1998207220 . ht tp : / / a r2chive . ic s. uci . edu/ ml/ .参 考 文 献 1 C H IE H YU A N Tsai , C H IU Chua ng2cheng. Developing a f eat ure weight self2adj ust ment mecha ni sm fo r a K2mea ns cl ustering algo rit hmJ . Co
30、mp utatio nal Stati stic s a nd Data A nalysi s ,2008 , 52 (10) : 465824672 . 2 J IN G L , N G M K , H U A N G J Z. A n Ent rop y Weighting K2Means Algo rit hm fo r Subspace Cl ustering of High2dimen2 sio nal Spa r se Dat a J . IE E E Tra ns. o n Kno wledge and Da2 t a Engineering , 2007 , 19 (8) :
31、102621041 . 3 WA N G X Z , WA N G Y D , WA N G L J . Imp ro ving f uzzy f eat ure C2means cl ustering ba sed o n f eat ure2weight lea r ning J . Pat ter n Reco gnitio n L et ter s , 2004 , 25 ( 10 ) :112321132 . 4 FR I GU I H , N A SRAO U I O . U nsup ervi sed lea r ning of p ro2作者简介 : 支晓斌 男 ,1976 年
32、出生 ,内蒙古巴彦淖尔人 ,在职博士研究生 , 讲师 。研究方向为模式识别 、模糊集理论及其应用 。范九伦 男 ,1964 年出生 ,陕西西安人 ,教授 ,博士生导师 。研究方向为模糊集理论、模式识别与图像处理、智能信息 处理 。element meshing C / / Proce ssi ngs of 6t h Inter natio nal Me s2hing Ro undta ble S. l : s. n. , 1997 : 3232335 . 5 龚光彩 , 张文宏 , 孙培雷 , 等. 网格自动生成技术进展综论J . 建筑热能通风空调 , 2006 , 25 (1) :26231
33、 . 6 方兴 , 张武 , 唐锦春 , 等. 一种改进的生成有限元全四边形 网格 的 铺 砌 法 J . 浙 江 理 工 大 学 学 报 , 2005 , 22 ( 1 ) :70273 . 7 贾虹 , 卢炎麟 , 高发兴 , 等. 高品质全四边形有限元网格生 成的 铺 砌 法 J . 浙 江 工 业 大 学 学 报 , 2000 , 28 ( 4 ) :3532357 . 8 朱宝利 , 吴丽娟. 四边形网格优化处理研究 J . 沈阳师范 大学学报 , 2007 , 25 (1) : 42245 . 9 陈立岗 , 郑耀 , 陈建军 , 等. 全四边形有限元网格的拓扑优 化策略J . 计
34、算机辅助设计与图形学学报 , 2007 , 19 ( 1) :78283 . 10 L E E K Y , KIM I I , C HO D Y , et al . A n algo rit hm fo r a uto matic 2D quadrilateral me sh generatio n wit h line co ns2 t raint s J . Co mp ut er Aided De sign , 2003 , 35 ( 12 ) :105521068 .(上接第 122 页)这种方法与自适应分析技术相结合 ,将是一种很有 前途的有限单元自动生成方法 ,对船舶板架结构有限元
35、 网格划分起到积极重要的作用 。参 考 文 献 1 关振群 , 宋超 , 顾元宪 , 等. 有限元网格生成方法研究的新进展 J . 计算机辅助设计与图形学学报 , 2003 , 15 ( 1 ) :1214 . 2 李毅 , 鲍劲松 , 金烨 , 等. 二维域多约束四边形有限元网格 生成算法 J . 计算机辅助设计与图形学学报 , 2008 , 20 (4) : 4882493 . 3 BL A C KER T D , S T EP H EN SON M B . Paving : a new ap2 p roach to auto mated quadrilateral me sh gener
36、atio n J . In2 t er natio nal J o ur nal fo r N umerical Met ho ds in Engineering ,1991 , 32 (4) :8112847 . 4 W H I T E D R , KIN N E Y P. Redesign of t he p aving algo2rit hm : ro bust ne ss enha ncement s t hro ugh element by作者简介 : 李晓辉 男 ,1982 年出生 ,陕西渭南人 ,硕士研究生 。主要研究方向为有限元分析 、计算几何 。李昌华 男 ,1963 年出生 ,教授 ,博士生导师 。主要研究方向为计算机图形学 、建筑智能信息处理 。126