四叉树网格划分研究.docx

四叉树网格划分研究.docx

《四叉树网格划分研究.docx》由会员分享，可在线阅读，更多相关《四叉树网格划分研究.docx（16页珍藏版）》请在冰点文库上搜索。

四叉树网格划分研究

硕士学位论文开题报告及论文工作计划书

课题名称 四叉树网格划分研究 

学  号   1070105    

姓  名    张   

专  业   机械工程   

学  院机械工程与自动化学院

导  师    马    

副导师    陈    

选题时间   年  月  日

东北大学研究生院

年 月 日

填表说明

1、本表一、二、三、四、五项在导师指导下如实填写。

2、学生在通过开题后一周内将该材料交到所在学院、研究所。

3、学生入学后第三学期应完成论文开题报告，按有关规定，没有完成开题报告的学生不能申请论文答辩。

一、立论依据

课题来源、选题依据和背景情况、课题研究目的、理论意义和实际应用价值

1.课题来源

有限元分析（FEA,FiniteElementAnalysis），即有限元方法（冯康首次发现时称为基于变分原理的差分方法），是一种用于求解微分方程组或积分方程组数值解的数值技术.这一解法基于完全消除微分方程,即将微分方程转化为代数方程组（稳定情形）;或将偏微分方程（组）改写为常微分方程（组）的逼近,这样可以用标准的数值技术（例如欧拉法,龙格-库塔方法等）求解。

FEA的基本思路是用较简单的问题代替复杂问题后再求解。

它将求解域看成是由许多称为有限元的小的互连子域组成，对每一单元假定一个合适的（较简单的）近似解，然后推导求解这个域总的满足条件（如结构的平衡条件），从而得到问题的解。

这个解不是准确解，而是近似解，因为实际问题被较简单的问题所代替。

由于大多数实际问题难以得到准确解，而有限元不仅计算精度高，而且能适应各种复杂形状，因而成为行之有效的工程分析手段。

网格划分是有限元分析中不可缺少的前处理阶段，被处理对象只有在被网格化之后才能运用有限元方法进行求解分析。

网格生成的方法多种多样，整体上可以分为两大类：

结构化网格生成方法和非结构化网格生成方法。

按照求解问题的复杂程度又可划分为结构化网格生成方法、非结构化网格生成方法和笛卡尔网格生成方法。

其中笛卡尔法是特殊的非结构网格生成方法。

[1]结构化方法数据结构简单，运算速度快，适用于相对简单的边界情况；非结构化方法适用于复杂的边界形状，数据结构比结构化方法稍复杂；笛卡尔方法是三者中数据结构最为复杂的，但其计算精度高、易于实现、便于网格自动划分，故适用于更为复杂的边界情况。

按照网格类型网格划分方法可分为三角形网格划分、四边形网格划分和混合网格划分。

其中混合网格划分是指生成的网格中既有三角形网格又有四边形网格。

三角形网格生成容易，有良好的理论基础，但移点时网格需要局部重划分；四边形网格需要处理好边界切割情况，可以灵活地调整点的位置而不必重新划分网格。

混合网格结合了三角形网格和四边形网格的优点，有很好的适应性。

四边形网格的划分方法也有多种，常见的有三角形合并法（也称间接法）、铺砌法（Paving）、推进波前法（AdvancingFrontMethod）、基于栅格法等。

本课题将要研究的四叉树网格划分就属于基于栅格法。

2.选题依据和背景情况

四叉树是一种具有继承性的数据结构，但它对应的是一种空间分解方法.Samet[2]详述了四叉树的起源、应用及相关算法.四叉树最初是用来进行二进制的计算机图像处理，存储图像信息。

Hunter第一次给出了“四叉树”这个命名。

将四叉树空间分解方法应用于网格生成的引路人是Yerry和Shephard.其基本思想如下:

首先将目标区域用一尽可能小的正方形圈定，然后将此正方形分解成四个相同大小的子区域，对每一个子域，测试其是否完全在目标域外面或是满足密度控制的要求，若满足所给定的条件则停止对此子域的细分，否则将之细分，该过程迭代执行下去直至达到预定的离散要求.这样目标区域被一些相互不重叠的各种大小的方形子域拼成的图形所逼近，这些子域是由最初的正方形分解而成，但目标区域本身自始至终并不被分解.

从1983年四叉树网格划分的提出到现在，四叉树网格划分方法的发展大致经历了以

下几个阶段：

早期的四叉树、早期的修改四叉树以及改进的修改四叉树。

然而四叉树网格划分方法在理论方面仍没有三角形网格划分那样成熟。

3.课题研究目的

1）解决四叉树网格划分的边界切割处理问题，增强网格的自适应性；

2）改进网格的悬点处理方法，使悬点处理更加合理；

3）在不增添新的悬点的前提下，四边形化边界切割处理后的图形，增强网格边界的自适应性；

4）解决四叉树网格划分的多边界网格划分的问题，增强四叉树网格划分的应用范围；

5）解决四叉树网格划分的局部加密问题，增强网格的自适应性；

6）将四叉树网格划分方法应用于三维曲面划分，解决相关问题；

4.理论意义和实际意义

研究四叉树网格划分方法，提高四叉树网格划分效率，有利于将四叉树网格算法应用于商业软件，解决实际问题。

四叉树网格划分方法的研究具有以下的理论意义和实用价值：

（1）四叉树网格划分得到的网格都是四边形网格，可以很方便的调节网格的大小和某些点的位置，不会像三角形网格那样，调整点时还要局部重新划分网格；

（2）四叉树网格划分可以很好的控制网格梯度，提高划分效率和计算效率；

（3）采用四叉树网格划分方法，对它的研究是对网格划分方法的进一步探索，四叉树网格划分方法具有较为完备的数据结构，有利于有限元方法的计算的进行；

（4）四叉树网格划分方法可以为有限元方法提供新的网格划分选择。

二、文献综述

国内外研究现状、发展动态；所阅文献的查阅范围及手段.

1.国内外四叉树网格生成技术的研究与发展

1.1早期四叉树网格及其缺陷

将四叉树空间分解方法应用于网格生成的引路人是Yerry和Shephard.其基本思想如下:

首先将目标区域用一尽可能小的正方形圈定，然后将此正方形分解成四个相同大小的子区域，对每一个子域，测试其是否完全在目标域外面或是满足密度控制的要求，若满足所给定的条件则停止对此子域的细分，否则将之细分，该过程迭代执行下去直至达到预定的离散要求.这样目标区域被一些相互不重叠的各种大小的方形子域拼成的图形所逼近，这些子域是由最初的正方形分解而成，但目标区域本身自始至终并不被分解.

四叉树表示虽然很吸引人，Yerry和shephard[3]和cheng等[4]也肯定了四叉树在有限元网格生成中的优势。

但将其直接用作有限元网格生成器时还存在一些缺陷，包括[3,5]:

（l）物体内部（即目标区域内）可能由少量的大元素组成:

（2）相邻的正方形可能细分的层次不同，因此必须特别关注元素间的连续性;

（3）因为物体由许多正方形拼合而成，所以所有非水平方向和非竖直方向上的边界将由一系列逼近此边界的正方形的角表示;

（4）对大多数边界而言，要想达到令人满意的几何表示，且达到通常的求解精度，需要更多的元素。

综合以上的缺陷可见，边界逼近的效果不好是最主要的问题。

为了克服这一系列不足，许多方法被提出且不断完善，最具代表性的是修改的四分树（modified-quadtree）的提出，混合网格的出现及边界布点控制方法的提出.

1.2早期的修改四叉树

Yeny和shephard[3,6,7]提出修改的四叉树，对四叉树网格中存在的不足进行了针对性的研究。

为了减少不想要的90°角，并能在某一给定的四叉树层上得到更好的几何表示，修正了四分树网格生成技术:

切去那些落在目标区域以外的正方形的角，并保留整数树结构。

切割正方形子域的某条线段的端点可能是此正方形任意两条边上的1/4点，中点或顶点.虽然有限数量的切割并没有考虑任何角的定义，但许多可能的确考虑了在一给定的四叉树层上大大改善的近似.由于最终的有限元网格修改考虑了角的调整，所以这种表示证明完全足够.引入的切割正方形也延用了四叉树编码中的基本树结构。

为了限制可能存在的过渡情况的数目，对四又树进行了第二次修改，以确保相邻的子域最多只能相差一级的分划水平。

最后关键的两步是把网格边界点拖到物体的实际边界上，并使内部节点的位置光滑化.

1.3改进的修改四叉树

早期的修改四叉树亦有不足，其主要缺陷是边界正方形有限的几何表示，也就是说，它只用了边界正方形的边上有限个具体位置表示物体的几何特征，对边界与正方形边的交点，只允许是此边的顶点、1/4点和中点等五个点。

不仅如此，一个正方形网格只允许一条离散边界线段和一个顶点，这限制了复杂几何外形物体的表示.

Baehmann等人[8]对早期的修改四叉树进行了改进，在四叉树数据结构中，对物体内的拓扑实体进行更明确的表示，从而去掉几何体拓扑复杂性的限制。

实行的改进包括:

利用单个树结构表示多个区域组成的空间，明确地存储顶点位置及实际边的交点。

这些改进对早期的修改四叉树的树结构没有不利影响，只需重写数据库。

在存储的信息中，还多了这样一条重要的链:

沿着这条链，可以由有限元单元到达形成此有限元单元的正方形网格，还可由此正方形网格到达最初的几何信息。

这些链对下面将要谈到的网格自适应分析有着重要意义。

在改进的修改四叉树网格生成过程中，首次使用了对应于实体边界的网格控制参数（r）控制网格逼近边界的质量和局部加密的程度。

在处理离散边信息时，亦有两大改进:

（l）边界离散边与最终正方形网格的交点用实数坐标表示，而不是将此交点拖至此正方形边的五个整数点上:

（2）在用实数坐标交点编程的过程中，允许顶点落在正方形网格内，而不是将其拖至它所在正方形的最近角上。

修改四叉树网格生成后，都要转化为有限元网格拓扑，文献[7]提供了三种不同的网格拓扑，即全三角形单元网格，混合单元网格（由四边形和三角形两种单元网格组成，和全四边形单元网格。

[9]

2．所阅文献范围及手段

文中大部分资料通过学校购买的数据库（中国学术期刊网、万方数据库、重庆维普数据库等）获得，其它从校外资源网上的可靠性方面等的专业网站获得，少数从图书馆图书、期刊获得。

中文数据库：

中国学术期刊全文数据库1988-2011

中国优秀博硕士论文1994-2011

重庆维普全文数据库1999-2011

万方数据库2000-2011

中国学术会议论文数据库2000-2011

中国学位论文数据库2000-2011

外文数据库：

SpringerLINK全文数据库2000-2011

WorldSciNet电子期刊数据库2000-2011

WileyInterScience期刊数据库2000-2011

IEEE/IEEElectronicLibrary2000-2011

CambridgeUniversityPress期刊全文2000-2011

Nature周刊2000-2011

INSPEC科学文摘1994-2011

SCI科学引文索引1994-2011

参考文献

1.Z.J.WANG.AQuadtree-basedAdaptiveCartesianQuadGridFlowSolverForNavier-StokesEquations[J].Computers&Fluids,1998,Vol.27,No.4,pp.529±549,

2.HananSamet，TheQuadtreeandRelatedHierarehiealDataStrueture[J].ComutingSurveys，1984:

16

（2）:

187-260

3.YerryM.A.ShePhardM.S.，Amodifiedquadtreeapproachtofiniteelementmeshgeneration[J].IEEEComPuterGraphiesandApplications,1983:

3（l）:

39-46

4.ChengJ.H,etal,Quadtree/Oetreemeshingwithadaptiveanalysis[J].NumeriealGridGenerationinComputationalFluidmechanies;PineridgePress:

Swansea,1988;633-642

5.M.S.Shephard,M.A.YerryAnapproachinautomaticfiniteelementmeshgeneration[J].ComputersinEngineeringvol3（L.EHulbert，Ed，）.BookNo.G00217.ASME.1982,PP,21-28

6.M.S.ShephardandM.A.Yerry，Approachingtheautomaticgenerationoffiniteelementmeshes[J].ComputersinMeshEngng,1983;1（4）:

49-56

7.M.A.YerryandM.S.Shephard,Automaticthree-dimensionalmeshgenerationbythemodified-octreetechnique[J].lntemationalJournalforNumericMethodsinEngineering,1984;20,1965-1990

8.P.L.Baehmann,etal.Robust,geometricallybasedautomatictwo-dimensionmeshgeneration[J].InternationalJournalforNumericMethodsinEngineering,1987;24.1043-1078

9.张弢.简单高效的复杂边界四叉树有限元网格生成技术[D],湖南:

湖南大学硕士学位论文.

10.杜　刚,孙　茂.昆虫拍动翅的非定常变形对其气动力的影响[J],应用数学和力学,2008第29卷,第6期：

663-675

11.唐敏中.从超音速卡门涡街到非定常复杂流场实验研究[J],1994-2010ChinaAcademicJournalElectronicPublishingHouse:

246-255

12.王肇,宋红军,尹协振.二维翼型非定常运动的涡流场显示—2俯仰运动和沉浮/俯仰联合运动[J],流体力学实验与测量,2004,第18卷,第4期：

38-42

13.宋红军,王肇,尹协振.二维翼型非定常运动数值模拟[J],水动力学研究与进展,2004,第19卷,增刊：

896-903

14.魏瑞轩,胡明朗,郭庆,孔韬.仿鸟扑翼飞行器动力学建模[J],系统仿真学报,2009,第21卷,第15期：

4811-4814

15.IsaoShimoyama,HMiura,KSuzuki.Insect-likemicrorobotswithexternalskeletons[J],IEEEControlSystemsmagazine,1993,37-41

16.YKubo,IsaoShimoyama.Studyonthewingsofflyingmicrorobots[J].IEEEint.Conf.onRoboticsandAutomation,SanDiego,CA，May1994，834-839

17.KenjiSuzuki,IsaoShimoyama.Insect-modelbasedmicrorobotwithelastichinges[J].JournalofMicroelectromechanicalSystems,1994,3（l）:

4-9

18.R.Fearing,KChiang,MDickinson,etal.Transmissionmechanismforamicromechanicalflyinginsect[J].InProc.oftheIEEEInt.Conf.onRoboticsandAutomation，SanFrancisco，CA，USA，Apr.2000，1509~1516

19.MSitti,DCampolo,JYan,etal.DevelopmentofPZTandPZN-PTbasedunimorphaetuatorsformicromechanicalflappingmechanisms[J].InProc.oftheIEEEInt.Conf.onRoboticsandAutomation,Korea,2001

20.LSchemato,XDeng.Virtualinsectflightsimulators:

asoftwaretestbedforinsectflight[J].InProc.oftheIEEEInt.Conf.onRoboticsandAutomation，2001

21.JYan,RJWood,SAvadhanula,etal.Towardsflappingwingcontrolforamicromechanicalflyinginsect[J].InProcoftheIEEEInt.ConfonRoboticsandAutomationSeoul,SouthKorea,May2001,3901-3908

22.LSchenato,XDeng,SSastary.Flightcontrolsystemforamicromechanicalflyinginsect:

architectureandimplemeniation[J].InProcoftheIEEEInt.ConferenceonRobotiesandAutomation,Soul,SouthKorea,May2002

23.TNPorsin-Sirirak,YCTai,HNassefetal.Unsteady-stateaerodynamicPerformanceofMEMSwings[J].InternationalSymposiumonSmartStructuresandMicrosystems,TheJoekeyClub,HongKong,Oetober19-21,2000

24.TNPornsin-Sirirak,SWLee,HNassef,etal.MEMSwingtechnologyforabattery-Poweredornithoper[J].Proeeedingsof13thIEEEAnnualInternationalConfereneeonMEMS2000,Miyazaki,Japan,2000,799-804

25.RobertCMichelson,StevenReeee.Updateonflappingwingmicroairvehiclereseareh:

ongoingworktodevelopaflappingwingcrawling“EntomoPter”[J].13thBristolInternationalRPVConferenee,BristolEngland,30March-1April,1998

26.RobertCMichelson,DHelmiek.Areciprocatingchemicalmusele（RCM）formicroairvehiele“Entermopter”flight[J].1997ProceedingsoftheAssoeiationforUnmannedVehieleSystems,International,June1997,50-51

三、研究内容

1．研究构想与思路、主要研究内容及拟解决的关键技术

研究构想与思路

通过研究四叉树的数据结构特点和四叉树网格划分的特点，归纳四叉树网格划分的一般规律，运用编程技术实现这些规律。

主要研究内容

（1）研究边界切割特点和规律，为边界切割的程序实现提供理论指导。

（2）研究切割图形的特点以及切割图形的四边形化特点，在不增添悬点的基础上将边界切割得到的图形四边形化。

（3）研究悬点的分布规律和特点，为悬点的处理提供理论指导，在最低波及邻居的情况下处理悬点。

（4）提高算法效率和程序健壮性，为工程应用准备条件。

（5）完善四叉树网格生成程序，与商业软件网格划分作比较或工程实际问题结合，检验程序性能。

拟解决关键技术

（1）掌握边界切割规律，找到边界切割图形获取方法，解决边界切割问题。

（2）掌握切割图形四边形化规律，在不增加悬点的基础上解决切割图形的四边形化问题。

（3）掌握悬点的分布规律和特点，较好的解决悬点处理问题。

2．拟采取的研究方法、技术路线、实施方案及可行性分析

拟采用的研究方法

使用VisualStudio中的C++模块编写四叉树网格划分方法程序代码，并以Tecplot360文件的方式输出结果，在Tecplot360中对结果进行分析和改进。

将代码输出文件导入Gambit中,设置建立边界条件，并输出Fluent能输入的格式。

在Fluent中定义求解器参数，设置边界条件参数，并求解。

在后处理软件Tecplot360中对结果进行分析。

对比试验数据，验证仿真结果，改进网格质量和网格划分方法。

技术路线和实施方案

（1）查阅文献了解目前四叉树网格划分算法的研究现状，掌握方法中的优点和不足，针对目前方法中的某些缺点提出解决方案。

（2）首先将待计算域进行四叉树等级划分处理，使网格与其邻居间级数最多相差一级，这样也便于悬点处理；并且应使边界切割最多是双边切割。

（3）在进行边界切割处理之前应先进行悬点处理，再进行移点处理。

进行悬点处理是为移点处理做准备的，防止移点时将带悬点的网格转化为多边形网格；进行移点处理是尽量避免边界切割时生成畸形图形。

（4）进行边界切割处理，切割出来的图形为三角形，四边形（凹四、凸四），五边形（凹五、凸五），六边形（凹六、凸六），七边形（凹七）。

（5）对切割后的图形进行四边形化，四边形化时优先进行七边形、五边形、六边形和凸四边形的四边形化，然后进行凹四边形的四边形化，最后进行三角形的四边形化。

（6）优化处理。

使网格分布均匀。

可行性分析：

CFD计算流体力学方法在工程上已经广泛的应用，如流场模拟，强度分析，形变分析等。

上述模拟分析之前都要将问题进行有限元网格划分，目前的网格划分已有多种，四边形网格划分方法也有很多，而四叉树网格划分方法能很好的控制网格梯度，四叉树数据结构也有较好的算法效率是较为成熟的数据结构。

本论文利用编程的方式研究、实现和改进四叉树算法作者认为是可行的。

四、研究基础

1．所需实验手段、研究条件和实验条件

所需实验手段

（1）计算几何学

（2）网格划分相关文献

（3）四叉树网格划分相关文献

（4）网格划分基本理论

（5）VC++相关书籍

（6）Gambit，Fluent，Tecplot相关知识

研究条件和实验条件

（1）有限元