tceic.com
学霸学习网 这下你爽了
相关文章
当前位置:首页 >> 自然科学 >>

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


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

四叉树法非结构网格剖分技术研究
许 鹏 梁国柱
北京航空航天大学, 北京, 100083
摘要: 针对有限元前置处理中二维复杂域四边形网格自动剖分问题, 对四叉树网格剖分算 法进行了研究。描述了四叉树网格的数据结构及其递归生成过程; 提出基于计算机图形学的 网格黑白性判断算法; 给出两种边界网格处理的修正方法, 并对这两种修正方法进行了比较; 利用四叉树数据结构的特点实现对网格遍历、 查找、 插入等操作, 并根据最近共同祖先法完成 四叉树网格邻域的查询。结果表明: 采用该方法可以实现有限元网格全自动剖分, 网格生成只 依赖于二维域的几何特征, 对复杂边界的适应性强, 生成的网格域内全部为四边形, 只在域边 界处出现少量三角形网格, 具有较高的质量; 网格生成、 遍历、 查找等数据操作效率高、 时间短。 关键词: 非结构网格; 四边形网格; 网格生成; 四叉树 中图分类号: T P391. 72 文章编号: 1004 ) 132X( 2006) S2 ) 0312 ) 03 Study on Unstruct ured Mesh Generat ion Technique Base on Quad- t ree Method Xu Peng Liang Guozhu Beihang Universit y, Beijing, 100083 Abstr act: The arithmet ic of quadtree mesh generation was st udied in order to solve t he problem of the finit e element automat ic quadrilat er al mesh generation for a two dimensional complex r egion. The dat a st ruct ure and recursion gener at ion of quadt ree mesh was described, and t he method of blackwhit e propert y judgment of mesh based on comput er graphics was presented. Two modified met hods of boundary- mesh were given and compared. The operat ion of mesh such as ordering, finding and in2 serting was car ried out accor ding t o t he character of quadt ree dat a st ruct ure and t he neighbor- finding of mesh was realized by using the algorit hms of t he last common ancestor. T he result s show t hat the method based on t he quadt ree was very useful for t he finit e element aut omat ic quadrilat er al mesh gen2 erat ion in t wo dimensional regions, which only depends on t he geomet rical character of t he region and has great flexibilit y for complex boundary. The meshes generat ed in planar were all quadrangular and only a few t riangular near the boundary. In addit ion, t he operat ion of meshes such as generating, or2 der ing and finding was efficient and timesaving. Key word: unst ruct ured mesh; quadrilat er al mesh; mesh gener at ion; quadt ree

0

引言
非结构化网格生成具有数据准备工作量小、

功有效的网格生成方法之一, 它适用于任何复杂 的二维区域问题, 而且其算法效率几乎与单元节 点数呈线性增长, 其网格生成易于实现密度控制, 易于进行自适应分析, 也易于同实体造型系统相 结合。但其缺点也是明显的, 网格生成计算时间 长, 所需内存较大, 不利于实现并行处理等[ 2] 。本 文对基于有限四叉树法的四边形网格自动生成方 法进行了研究。

自动化程度高、 对不规则区域适应性强等优点, 自 20 世纪 80 年代以来得到了迅速的发展。在这种 网格中, 单元与节点编号无固定规则可遵循, 因而 除了每一单元及节点的几何信息必须存储外, 与 该单元相邻的那些单元的编号等也必须作为连接 关系的信息存储起来, 致使非结构网格的存储信 息量较大[ 1] 。 二维域非结构网格生成的方法有很多种, 最 主要是 Delaunay 法、 阵面推进法( advancing front method) 和有 限四叉树( finite quad- t ree met h2 od) 。将四叉树空间分解方法用于网格生成之中 进而发展而成的有限四叉树方法已成为目前最成
收稿日期: 2006 ) 07 ) 17

1
1. 1

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

设计
规则 1 四边形 网格 的长 和宽 为 名义 长和 宽, 其大小为包容盒的长与宽。 规则 2 最大值。 四边形网格的参考值为其长和宽的

# 312 #

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



梁国柱

四叉树网格剖分的过程是一个四叉树递归生 成的过程
[ 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 网格黑白性判断流程图

# 313 #

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

2
2. 1

网格节点的操作
邻域查询 整个树的结构通过父节点与子节点之间的指

先节 点使 AD J OI N ( I , O) 为 真, 就沿 四叉 树上 升, 找层次更高的祖先节点, 当被考察的祖先节点 使 ADJ OI N ( I , O) 为假时, 其父节点就是节点 P 与节点 Q 的最近公共祖先。 ( 2) 寻找邻节点 从节点 P 和节点Q 的最近 公共祖先开始, 沿四叉树向下移动, 其下降路径用 REF LE CT 得出。 下降路径与上升路径沿 P 和 Q 的公共边 I 对称。 2. 2 四叉树网格的遍历与查找 规则 7 如果两个网格节点的中心、 长和宽 均相同, 则认为这两个网格节点相等; 如果两个网 格相比较, 参考值小的网格节点小。 四叉树网格的遍历是完成网格的存储插入等 网格操作的重要过程, 该过程可以利用树的数据 结构的特点方便实现 [ 6] 。 四叉树网格的查找是网格生成后处理的重要 环节, 对于网格的加密、 删除以及修改等网格操作 都有十分重要的作用, 本文采用的网格查找算法 体现了四叉树数据结 构在网格划分 过程中的特 点, 使得网格查找更加快速更加有效。 具体的查找 过程如下: ? 从四叉树根节点作为初始的当前节 点; ? 通过目标网格节点与当前节点的位置关系
NW F F F T F F T T

针进行联系, 划分网格生成的四叉树是显式四叉 树结构。在显式四叉树结构上进行邻域查询有许 多不同的方 法, 最近公 共祖先方 法最为 常见[ 5] 。 该方法不考虑节点的位置和网格大小, 只需用到 四叉树的结构即可实 现对指定节点 的邻域进行 查询。 规则 5 ADJ OI N ( I , O) 的 定义是, 当 且仅

当象限 O 与其所在块的 I 向边或顶点相邻时返回 值 为 真, 如 ADJ OI N ( - W. , - SW. ) 为 真, AD J OI N (- SW. , - SW. ) 也为真。 规则 6 RE F LECT ( I , O) 的 作用在于 寻找 一个象限, 该象限与象限 O 共享O 的 I 边或顶点, 且与 O 的面积相等( 该象限不一定与 O 在同一个 块 ) , 如 REF LE CT ( - N. , - SW. ) 为 - NW. , REF LE CT ( - N W. , - SW. ) 为- NE. 规则 5 和规则 6 的具体定义见表 1 和表 2。
表1
I ( 方向) SW SE NE NW S E N W

ADJ OI N ( I , O)
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+ + 61 0 编写网格剖分程序, 程序实现了两种边界网格处理方法。图 3 所示为 某二维域网格剖分结果, 边界网格使用第二种方 法即灰节点处理方法进行处理。

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

REF LECT ( I , O)
O( 象限)

SW NE NE NE NE NW SE NW SE

SE NW NW NW NW NE SW NE SW

NE SW SW SW SW SE NW SE NW

NW SE SE SE SE SW NE SW NE

图 3 四叉树网格划分 结果

4

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

假定指定节点 P , 寻找与节点 P 的 I 边大小 相等的相邻节点 Q 的步骤如下: ( 1) 寻找最近公共祖先 如果节点 P 的某祖 # 314 #

成只依赖于二维分析域的几何特征, 对复杂边界
( 下转第 326 页)

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

线圈采用特殊结构, 为方便定位, 椭圆管盖板放置 在定位夹具上, 感应线圈与定位夹具之间的衬垫 采用隔热材料, 线圈与工件之间保持一定的间隙。 ( 3) 三维微调机构 具有上下、 左右、 前后的 手动微调功能, 调整范围为 ? 10mm, 可满足感应 器套入工件对中位置的调整。 ( 4) 定位夹具 夹具为组合结构, 设计成可拆 卸形式, 便于实现不同大小工件的焊接。 ( 5) 气压机构 由于采用双工位焊接, 采用两 个加压气缸, 共用一套气路系统及控制装置, 可实 现电极的抬起和压下, 也可以根据焊接工艺要求 调节压力大小。 ( 6) 水冷系统 水冷系统分电源内部循环冷
[ 4] [ 5] [ 6] [ 7]

焊设备的研制[ J] , 焊接技术, 2004, 33( 3) : 41O 42. 李桂变, 王 德虎, 王 宏来, 等. 感应 加热 新技 术的 应 用及探讨[ J] . 新技术新工艺, 2006( 1) : 105O107. 俞勇祥. 感应加热技术的应用与发展[ J] . 今日科技, 1999( 9) : 4O5. 沈庆 通. 感应 加热 技 术的 近期 发 展[ J] . 机械 工 人 ( 热加工) , 2005( 6) : 12O15. 段广平, 张 淑敏, 韩 文仕, 等. 一种 钢制 柱状 散热 器 焊接工艺方法: 中国, 01120471[ P] , 2002 O06. O02 ( 编辑
作者简介: 罗

周本盛)

键, 男, 1971 年生。 武汉 理工 大学材 料科 学与 工

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

却回路和电极冷却系统两路。内部冷却系统是为 中频电源、 中频变压器和中频电缆、 感应线圈的冷 却设置的。电极冷却系统是为了防止焊接时电极 过热而设置的。各冷却水路设有球阀, 可调节水 的流量。冷却水由循环水水箱泵供水, 水箱内设 有自动补水控制。 ( 7) 控制系统 主要实现系统各部分的程序 控制, 采用可编程序控制器配以微电脑触摸屏, 大 部分参数设定和控制集中在屏幕上, 并具有故障 报警显示功能。

( 上接第 314 页)

的适应性强。 ( 2) 生成的网格在域内全部为四边形, 只有少 量三角形网格出现在二维分析域的几何边界处, 具有较高的质量。 ( 3) 实现网格遍历、 查找、 邻域查询等操作, 算 法效率高、 时间短。
参考文献: [ 1] 胡恩球 , 张 新访, 向 文, 等. 有限 元网 格生 成方 法 发 展综述[ J] . 计算机 辅助 设计与 图形 学学报, 1997, 9 ( 4) : 378 O382. [ 2] 魏红宁, 周本 宽. 适 于自 适应 网格 加密 的数 据结 构 和算法[ J] . 西 南 交 通大 学 学报, 1996, 31 ( 6) : 652O 658. [ 3] Mar k A Y. Automatic Three - dimensional Mesh Generat ion by t he Modified- octr ee Technique[ J] . International Journal of Numerical Method in Engi2 neer ing, 1984, 20: 1965 O1990. [ 4] [ 5] [ 6] 孔铁全, 任钧 国. 四 叉树 法网 格划 分的 数据 结构 及 算法设计[ J] . 航空计算技术, 2003, 33( 2) : 82O84. 张芩, 郭薇. 基于四叉树的邻域查询技术[ J] . 系统 仿 真学报, 2001, 13( 1) : 48O50. Sartej S. 数据 结构算 法与 应用 ) ) ) C+ + 语 言描 述 [ M] . 汪诗林, 译. 北京: 机械工业出版社, 2000. ( 编辑
作者简介: 许

4

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

压力焊接是完全可行的。试样外表面光滑, 内表 面无毛刺, 焊缝无裂纹, 显微组织达到冶金熔合。 散热管耐腐蚀性较强, 焊接效率高, 成本低。 ( 2) 界面状态、 感应加热工艺参数、 压力工艺 参数三者之间的相互作用明显影响散热管封头的 最终质量。 ( 3) 焊缝粘滞的超塑性熔融金属沿界面摩擦、 塑性剪切、 流动与扩散过程的充分实现, 是界面完 成自清洁作用、 减少缺陷、 获得优质接头的关键。 ( 4) 焊机的设计体现了散热管封头感应压力 焊高效率、 低成本、 优质焊接接头的要求。
参考文献: [ 1] Zhang X P , Shi Y W. White Speck F or ming mechanism and Dim ple Models in the Interface Fr actography of Induct ion P ressur e Butt - welding [ J] . Jour nal of Materials Pr ocessing Technology, 1997, 65: 237O244. [ 2] [ 3] 韩红彪, 段 明德, 崔 琦, 等. 散 热器 曲线 焊缝 五枪 自 动焊工艺[ J] . 焊接学报, 2005, 26( 8) : 77 O80. 韩红彪, 林 青松, 李 济顺, 等 . 散热 器堵 座双 枪自 动



伟)

鹏, 男, 1980 年生。 北京 航空 航天大 学宇 航学 院

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

# 326 #


推荐相关:

四叉树法非结构网格剖分技术研究_图文.pdf

中国机械工程第 17 卷增刊 2006 年 10 月 四叉树法非结构网格剖分技术研究许 鹏 梁国柱北京航空航天大学, 北京, 100083 摘要: 针对有限元前置处理中二维复杂域...

四叉树网格划分研究_图文.doc

主要研究内容及拟解决的关键技术 研究构想与思路 通过研究四叉树的数据结构特点...四叉树法非结构网格剖分... 4页 免费 4.简单的2D网格划分 7页 免费 喜欢...

四叉树法网格划分的数据结构及算法设计.pdf

2四叉树网格划分的算法设计 2.1树的生成 四叉树过程就是由根结点生成整个树结构从而 达到对分析域进行剖分的过程。其算法采用递归调 用,表示如下: 收稿日期...

有限元网格划分技术研究_黄志超.pdf

网格自动剖分一直是国内外有限元研究和应用的热点 ,...[ 12] 两个三角形可以组成一个四边形 , 一个...对于二维问题 , 一个方形区域用四叉树法分成 4 ...

有限元网格剖分方法概述.doc

有限元网格剖分方法概述在采用有限元法进行结构分析...有限元网格生成技术发展到现在, 已经出现了大量的不...2)从第一步产生的四叉树数据库中, 取出满足终止...

基于四叉树的图像分割技术.pdf

四叉树的图像分割法将场景空间按 X/Y 方向分割成 4 个子方格组成空间四叉树...若某一子 方块网格中所含的景物大于给定阈值,则对该子方 块网格做进一步剖分...

六面体网格剖分算法的研究现状.pdf

六面体网格剖分算法的研究现状 电脑应用技术 二零一...并且可以生成质量较高的结构化六面体网格,但其所适用...基于上面的理论基础,又有许多学者依次提出了四叉树...

任意平面区域的高质量有限元网格自动剖分.pdf

随后又出现了一些基于四叉树的三角形形状 优化算法 ...剖分就 以 PSL G 描述的任意平面区域作为研究对象...约束边组成的某 4 网格优化方法初始三角形网格形成...

基于GIS的高质量约束Delaunay三角网格剖分_图文.pdf

目前, 实现网格剖分的算法很多, 而且 不断有新的算法推出 , 其相关研究领域...生成二维非结构化网格的常用 方法[ 4] 有四叉树法 ( Quadtr ee) 、 Del ...

网格生成技术.doc

19 3.4 四叉树(2D)/八叉树(3D)方法 ......网格单元 现有的网格生成技术一般可以分为:结构网格,非...网格不能解决任意形状和任意连通区域的网格剖 分的...

平面四边形网格自动生成方法研究_图文.ppt

网格的比较 五、 Delaunay三角剖分逐点插入法 六、栅格法(新) 七、四叉树 ...非结构网格生成技术从生成网格的方法来区分 主要有Delaunay准则和前波发以及...

65-筏板基础有限元网格划分方法研究-朱春明_图文.pdf

筏板等基础结构物所对应的点线约束条件进行二维平面区域网格剖分,生成以四边形为...2.3 四叉树法 [4] 在四叉树法网格划分中,首先用一个尽可能小的正方形...

四叉树有限元网格的数据结构在面向对象中的实现.pdf

四叉树有限元网格的数据结构在面向对象中的实现 - 第27卷 第 2 期 2 0

基于改进四叉树的LiDAR点云数据组织研究.pdf

4 四叉树的优化改进方法研究 4.1 优化四叉树点云...其基 本思想是将数据区域划分为大小相等的网格。 当...分块索引结构。 (例如航飞中由于存在点云打到水面...

03-第三章 GAMBIT 网格划分基础.pdf

网格可分为两大类:结构网格和非结构网格。 3.2.1 结构网格生成技术 过去普遍...原理(二维) ,最为常用的是以 下三种: 1、四叉树(二维)/八叉树(三维)方法...

基于四叉树的LOD算法实现_图文.ppt

进行重组, 得到一种更加便于实时绘制使用的数据结构...隔层四叉树是指在地形网格由粗往细的剖分过程中 ...18 由于采用了地形分块技术,除了考虑同一块地形内部...

2.第二章空间数据结构(6学时)(四叉树编码)_图文.ppt

2.第二章空间数据结构(6学时)(四叉树编码)_理学...每个栅格单元的值以网格中心点对应的面域属性值确定...

计算流体力学网格划分方法的现状与发展-引用的文章.pdf

网格划分是将结构网格划分可分为三大 行离散化,...3.2 基于栅格的技术 这类技术近年来国内研究的较多...徐国艳等基于四叉树法 提出了一种全四边形网格单元...

任意平面区域有限元三角形网格全自动剖分_图文.pdf

研 究并取得了很大进展 , 然而对于任意形体 的全 自动 网格生成技术仍有 ...网格 生成技术的方法很多、、、 , 、 、 三角剖分网格前沿法改进四叉树法...

空间索引使用的意义及网格索引和四叉树索引简单介绍.doc

tree)类似于前面介绍的网格索引,也是对地理空间进行网格划分,对地理空间递归进行四分 来构建四叉树,本文将在普通四叉树的基础上,介绍一种改进的四叉树索引结构。...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com