四叉树法非结构网格剖分技术研究

中国机械工程第17卷增刊2006年10月

四叉树法非结构网格剖分技术研究

许 鹏

梁国柱

北京航空航天大学, 北京, 100083

摘要:针对有限元前置处理中二维复杂域四边形网格自动剖分问题, 对四叉树网格剖分算法进行了研究。描述了四叉树网格的数据结构及其递归生成过程; 提出基于计算机图形学的网格黑白性判断算法; 给出两种边界网格处理的修正方法, 并对这两种修正方法进行了比较; 利用四叉树数据结构的特点实现对网格遍历、查找、插入等操作, 并根据最近共同祖先法完成四叉树网格邻域的查询。结果表明:采用该方法可以实现有限元网格全自动剖分, 网格生成只依赖于二维域的几何特征, 对复杂边界的适应性强, 生成的网格域内全部为四边形, 只在域边界处出现少量三角形网格, 具有较高的质量; 网格生成、遍历、查找等数据操作效率高、时间短。

关键词:非结构网格; 四边形网格; 网格生成; 四叉树

中图分类号:T P391. 72 文章编号:1004 132X(2006) S2 0312 03

Study on Unstructured Mesh Generation Technique Base on Quad -tree Method

Xu Peng Liang Guozhu

Beihang University, Beijing, 100083

Abstract :The arithm etic o f quadtree mesh g eneratio n w as studied in order to so lve the problem of the finite element auto matic quadrilater al mesh g eneration for a tw o dim ensional complex r eg io n. The data structure and recursion g ener ation of quadtree mesh w as described, and the method of black-w hite property judgm ent of mesh based on computer graphics w as presented. Tw o mo dified methods of boundary -m esh w ere given and co mpared. The operation o f mesh such as ordering, finding and in serting w as car ried out accor ding to the character o f quadtree data structure and the neighbor-finding of mesh w as realized by using the alg orithm s of the last co mmo n ancesto r. T he results show that the method based on the quadtree w as very useful fo r the finite element automatic quadrilater al mesh gen eration in tw o dim ensional regions, w hich only depends on the geometrical character o f the region and has g reat flexibility fo r complex boundary. The meshes generated in planar w ere all quadrangular and only a few triang ular near the boundary. In addition, the operation of m eshes such as g enerating, or der ing and finding w as efficient and timesav ing.

Key word :unstructured mesh; quadrilater al mesh; m esh g ener ation; quadtree

0 引言

非结构化网格生成具有数据准备工作量小、自动化程度高、对不规则区域适应性强等优点, 自20世纪80年代以来得到了迅速的发展。在这种网格中, 单元与节点编号无固定规则可遵循, 因而除了每一单元及节点的几何信息必须存储外, 与该单元相邻的那些单元的编号等也必须作为连接关系的信息存储起来, 致使非结构网格的存储信息量较大[1]。

二维域非结构网格生成的方法有很多种, 最主要是Delaunay 法、阵面推进法(adv ancing front method) 和有限四叉树(finite quad-tree meth o d) 。将四叉树空间分解方法用于网格生成之中进而发展而成的有限四叉树方法已成为目前最成

收稿日期:2006 07 17

功有效的网格生成方法之一, 它适用于任何复杂的二维区域问题, 而且其算法效率几乎与单元节点数呈线性增长, 其网格生成易于实现密度控制,

易于进行自适应分析, 也易于同实体造型系统相结合。但其缺点也是明显的, 网格生成计算时间长, 所需内存较大, 不利于实现并行处理等[2]。本文对基于有限四叉树法的四边形网格自动生成方法进行了研究。

1四叉树法网格剖分数据结构及算法

设计

1. 1 四叉树法网格剖分算法设计

规则1 四边形网格的长和宽为名义长和宽, 其大小为包容盒的长与宽。

规则2 四边形网格的参考值为其长和宽的最大值。

四叉树法非结构网格剖分技术研究 许 鹏梁国柱

四叉树网格剖分的过程是一个四叉树递归生成的过程

[3]

黑白性判断的第一步是确定网格各边界与二维分析域的交点个数, 如果交点个数大于2则网格为灰节点; 如果交点个数小于2且网格中心在二维域内则为黑节点, 否则为白节点。

对于灰节点, 一般有两种处理方法。第一种方法是判断网格各边顶点中点与二维域的位置关系, 再使用在二维分析域内的顶点和中点来重新组合生成新的网格, 详细方法见文献[4]; 第二种方法是用二维分析域的边界分割网格产生新的网格。第二种方法可以分为如下三种情况:

(1) 边界网格中有一个顶点在二维域外, 其处理方法为连接边界曲线与网格两边交点, 再连接它们的中点和域外顶点相对的顶点, 则生成两个新的四边形网格, 如图2a 所示。

(2) 边界网格中有两个顶点在二维域外的情况有两种, 即域内两点相邻和域内两点相对的情况。域内两点相邻时的处理方法是, 连接边界曲线与网格两边交点, 生成新的四边形网格, 如图2b 所示; 域内两点相对的处理方法是, 分别连接边界曲线与网格两边交点, 再连接域内两个顶点, 生成两个新的四边形网格, 如图2c 所示。

(3) 边界网格中有三个顶点在二维域外, 处理方法是, 先分别得到边界曲线与网格两边交点以及与过域内顶点的四边形网格对角线的交点, 再依次连接这三个交点和域内顶点, 生成新的四边形网格, 如图2d

所示。

, 由目标分析域的包容盒作为根节点

进一步生成四叉树, 从而实现对整个二维分析域进行剖分, 具体步骤如下:①找到一个能够完全包含二维域的包容盒作为初始目标矩形; ②将目标矩形离散为4个子矩形, 并按照顺序依次对子矩形进行判断; ③判断子矩形是否完全在分析域外; ④若子矩形不完全在分析域外则再判断子矩形的参考值是否满足终止条件; ⑤若不满足终止条件则将该子矩形作为目标矩形重复②至所需精度; ⑥将不完全在分析域外且参考值小于终止条件的子矩形作为网格, 并存储在链表中。

1. 2 四叉树法网格剖分数据结构设计

规则3 度数表示节点在兄弟节点中的位置, 其大小由节点所处位置决定, 从左下角的节点开始按照逆时针方向分配各节点度数, 范围为0~3。

规则4 节点的黑白性标识即网格与分析域的关系分为三类:第一类为黑节点(1) , 表示此节点代表的子矩形完全包含在二维分析域内; 第二类为白节点(-1) , 表示此节点代表的子矩形全部在二维分析域外; 第三类为灰节点(0) , 表示此节点代表的子矩形部分包含于二维分析域内。为实现四叉树网格自动剖分以及存取, 四叉树网格节点的数据结构应该包含基本信息、几何信息和连接关系信息三部分信息。基本信息包括网格的编号、黑白性标识和度数; 几何信息包括网格4个顶点坐标、中心坐标以及长和宽; 连接关系信息包括了父节点指针、4个子节点指针、邻居的网格编号。1. 3

边界网格单元的判断与处理

网格节点黑白性的判断是网格自动生成过程

(a) (

b)

中最为重要的一环, 本文采用的算法完全基于计算机图形学, 并且只依赖于网格和二维分析域的几何特征, 可以实现完全自动化网格黑白性判断。该算法的流程如图1

所示。

(c)

图2 各种边界网格的处理方法

(d)

处理灰节点的两种方法各有优缺点, 第一种方法生成的边界网格较为规则, 但新网格对边界的拟合不够好, 第二种方法对边界拟合较好, 但容易出现不规则网格。在使用时应从具体的问题出发进行选择。

图1

网格黑白性判断流程图

2网格节点的操作

先节点使AD J OI N (I , O) 为真, 就沿四叉树上升, 找层次更高的祖先节点, 当被考察的祖先节点使ADJ OI N (I , O) 为假时, 其父节点就是节点P 与节点Q 的最近公共祖先。

(2) 寻找邻节点 从节点P 和节点Q 的最近公共祖先开始, 沿四叉树向下移动, 其下降路径用REFL E CT 得出。下降路径与上升路径沿P 和Q 的公共边I 对称。

2. 2 四叉树网格的遍历与查找

规则7 如果两个网格节点的中心、长和宽均相同, 则认为这两个网格节点相等; 如果两个网格相比较, 参考值小的网格节点小。

四叉树网格的遍历是完成网格的存储插入等网格操作的重要过程, 该过程可以利用树的数据结构的特点方便实现[6]。

四叉树网格的查找是网格生成后处理的重要环节, 对于网格的加密、删除以及修改等网格操作都有十分重要的作用, 本文采用的网格查找算法体现了四叉树数据结构在网格划分过程中的特点, 使得网格查找更加快速更加有效。具体的查找过程如下:①从四叉树根节点作为初始的当前节点; ②通过目标网格节点与当前节点的位置关系

NW F F F T F F T T

2. 1 邻域查询

整个树的结构通过父节点与子节点之间的指针进行联系, 划分网格生成的四叉树是显式四叉树结构。在显式四叉树结构上进行邻域查询有许多不同的方法, 最近公共祖先方法最为常见[5]。该方法不考虑节点的位置和网格大小, 只需用到四叉树的结构即可实现对指定节点的邻域进行查询。

规则5 ADJ OI N (I , O) 的定义是, 当且仅当象限O 与其所在块的I 向边或顶点相邻时返回值为真, 如ADJ OI N (! W ∀, ! SW ∀) 为真, AD J OI N (! SW ∀, ! SW ∀) 也为真。

规则6 RE FL ECT (I , O) 的作用在于寻找一个象限, 该象限与象限O 共享O 的I 边或顶点, 且与O 的面积相等(该象限不一定与O 在同一个块) , 如REFL E CT (! N ∀, ! SW ∀) 为! NW ∀, REFL E CT (! N W ∀, ! SW ∀) 为! NE ∀

规则5和规则6的具体定义见表1和表2。

表1 A DJ OI N (I , O)

I (方向) SW S E NE NW S E N W

O(象限)

SW T F F F T F F T

SE F T F F T T F F

NE F F T F F T T F

判断当前节点中哪个子节点包含目标网格节点; ③判断目标节点和判断出的子节点是否相等, 如果相等则该子节点即为查找的目标节点, 否则以该子节点作为当前节点。

3 算例分析

基于上面对四叉树网格剖分算法的研究, 利用Microsoft VisualC ++6 0编写网格剖分程序, 程序实现了两种边界网格处理方法。图3所示为某二维域网格剖分结果, 边界网格使用第二种方法即灰节点处理方法进行处理。

表2 REF LECT (I , O)

I (方向) SW S E NE NW S E N W

O(象限)

SW NE NE NE NE NW SE NW SE

SE NW NW NW NW NE SW NE SW

NE S W S W S W S W SE NW SE NW

NW S E S E S E S E SW NE SW NE

图3 四叉树网格划分结果

4结论

(1) 实现了四边形网格地全自动剖分, 网格生

假定指定节点P, 寻找与节点P 的I 边大小相等的相邻节点Q 的步骤如下:

(1) 寻找最近公共祖先 如果节点P 的某祖成只依赖于二维分析域的几何特征, 对复杂边界

(下转第326页)

线圈采用特殊结构, 为方便定位, 椭圆管盖板放置在定位夹具上, 感应线圈与定位夹具之间的衬垫采用隔热材料, 线圈与工件之间保持一定的间隙。

(3) 三维微调机构 具有上下、左右、前后的手动微调功能, 调整范围为#10m m, 可满足感应器套入工件对中位置的调整。

(4) 定位夹具 夹具为组合结构, 设计成可拆卸形式, 便于实现不同大小工件的焊接。(5) 气压机构 由于采用双工位焊接, 采用两个加压气缸, 共用一套气路系统及控制装置, 可实现电极的抬起和压下, 也可以根据焊接工艺要求调节压力大小。

(6) 水冷系统 水冷系统分电源内部循环冷却回路和电极冷却系统两路。内部冷却系统是为中频电源、中频变压器和中频电缆、感应线圈的冷却设置的。电极冷却系统是为了防止焊接时电极过热而设置的。各冷却水路设有球阀, 可调节水的流量。冷却水由循环水水箱泵供水, 水箱内设有自动补水控制。

(7) 控制系统 主要实现系统各部分的程序控制, 采用可编程序控制器配以微电脑触摸屏, 大部分参数设定和控制集中在屏幕上, 并具有故障报警显示功能。

焊设备的研制[J], 焊接技术, 2004, 33(3) :41 42. [4] 李桂变, 王德虎, 王宏来, 等. 感应加热新技术的应

用及探讨[J].新技术新工艺, 2006(1) :105 107. [5] 俞勇祥. 感应加热技术的应用与发展[J].今日科技,

1999(9) :4 5.

[6] 沈庆通. 感应加热技术的近期发展[J]. 机械工人

(热加工) , 2005(6) :12 15.

[7] 段广平, 张淑敏, 韩文仕, 等. 一种钢制柱状散热器

焊接工艺方法:中国, 01120471[P], 2002 02 06.

(编辑 周本盛)

作者简介:罗 键, 男, 1971年生。武汉理工大学材料科学与工程学院教授、博士后研究人员, 华中科技大学塑性成形模拟及模具技术国家重点实验室客座研究员。主要研究方向为材料连接及其控制。发表论文30余篇。谢 冰, 女, 1968年生。武汉理工大学材料科学与工程学院讲师。李爱农, 男, 1958年生。武汉理工大学材料科学与工程学院副教授、博士。陈士民, 男, 1963年生。武汉理工大学材料科学与工程学院讲师。

(上接第314页)

的适应性强。

(2) 生成的网格在域内全部为四边形, 只有少量三角形网格出现在二维分析域的几何边界处, 具有较高的质量。

(3) 实现网格遍历、查找、邻域查询等操作, 算法效率高、时间短。

参考文献:[1]

胡恩球, 张新访, 向文, 等. 有限元网格生成方法发展综述[J]. 计算机辅助设计与图形学学报, 1997, 9(4) :378 382. [2]

魏红宁, 周本宽. 适于自适应网格加密的数据结构和算法[J].西南交通大学学报, 1996, 31(6) :652 658.

[3] M ar k A Y. A utomatic T hree -dimensional M esh

Generat ion by t he M odified-octr ee T echnique[J].Internatio nal Journal o f N umerical M ethod in Eng i neer ing, 1984, 20:1965 1990.

[4] 孔铁全, 任钧国. 四叉树法网格划分的数据结构及

算法设计[J]. 航空计算技术, 2003, 33(2) :82 84. [5]

张芩, 郭薇. 基于四叉树的邻域查询技术[J]. 系统仿真学报, 2001, 13(1) :48 50. [6]

Sartej S. 数据结构算法与应用 C++语言描述[M ].汪诗林, 译. 北京:机械工业出版社, 2000.

(编辑 郭 伟)

作者简介:许 鹏, 男, 1980年生。北京航空航天大学宇航学院博士研究生。研究方向为固体火箭发动机燃烧与流动仿真。梁国柱, 男, 1966年生。北京航空航天大学宇航学院教授。

4结论

(1) 散热管封头管-盖板使用不加钎料感应

压力焊接是完全可行的。试样外表面光滑, 内表面无毛刺, 焊缝无裂纹, 显微组织达到冶金熔合。

散热管耐腐蚀性较强, 焊接效率高, 成本低。

(2) 界面状态、感应加热工艺参数、压力工艺参数三者之间的相互作用明显影响散热管封头的最终质量。

(3) 焊缝粘滞的超塑性熔融金属沿界面摩擦、塑性剪切、流动与扩散过程的充分实现, 是界面完成自清洁作用、减少缺陷、获得优质接头的关键。

(4) 焊机的设计体现了散热管封头感应压力焊高效率、低成本、优质焊接接头的要求。

参考文献:

[1] Zhang X P , Shi Y W. White Speck F or ming -mechanism and Dim ple M o dels in the Interface Fr acto g raphy of Induct ion P ressur e Butt -welding [J].Jo ur nal of M aterials Pr ocessing T echnolog y, 1997, 65:237 244.

[2] 韩红彪, 段明德, 崔琦, 等. 散热器曲线焊缝五枪自

动焊工艺[J].焊接学报, 2005, 26(8) :77 80.

[3] 韩红彪, 林青松, 李济顺, 等. 散热器堵座双枪自动