四叉树

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

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

学号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

参考文献

ree-badAdaptiveCartesianQuadGridFlowSolver

ForNavier-StokesEquations[J].Computers&Fluids,1998,Vol.27,No.4,

pp.529±549,

amet，TheQuadtreeandRelatedHierarehiealDataStrueture[J].

ComutingSurveys，1984:16(2):187-260

rdM.S.，Amodifiedquadtreeapproachtofinite

elementmeshgeneration[J].IEEEComPuterGraphiesandApplications,

1983:3(l):39-46

.H,etal,Quadtree/Oetreemeshingwithadaptiveanalysis[J].

NumeriealGridGenerationinComputationalFluidmechanies;Pineridge

Press:Swana,1988;633-642

rd,napproachinautomaticfiniteelement

meshgeneration[J].ComputersinEngineeringvol3(rt，Ed，).

.1982,PP,21-28

，Approachingtheautomaticgeneration

offiniteelementmeshes[J].ComputersinMeshEngng,1983;1(4):49-56

rd,Automaticthree-dimensionalmesh

generationbythemodified-octreetechnique[J].lntemationalJournalfor

NumericMethodsinEngineering,1984;20,1965-1990

nn,,geometricallybadautomatictwo-

dimensionmeshgeneration[J].InternationalJournalforNumericMethods

inEngineering,1987;24.1043-1078

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

士学位论文.

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

力学,2008第29卷,第6期：663-675

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

AcademicJournalElectronicPublishingHou:246-255

12.王肇,宋红军,尹协振.二维翼型非定常运动的涡流场显示—2俯仰运动和沉浮/

俯仰联合运动[J],流体力学实验与测量,2004,第18卷,第4期：38-42

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

展,2004,第19卷,增刊：896-903

14.魏瑞轩,胡明朗,郭庆,孔韬.仿鸟扑翼飞行器动力学建模[J],系统仿真学

报,2009,第21卷,第15期：4811-4814

imoyama,HMiura,-likemicrorobotswith

externalskeletons[J],IEEEControlSystemsmagazine,1993,37-41

,nthewingsofflyingmicro

robots[J].ticsandAutomation,SanDiego,CA，May

1994，834-839

uzuki,-modelbadmicrorobotwith

elastichinges[J].JournalofMicroelectromechanicalSystems,1994,3(l):4-

9

g,KChiang,MDickinson,issionmechanismfora

micromechanicalflyinginct[J].

RoboticsandAutomation，SanFrancisco，CA，USA，Apr.2000，1509~1516

,DCampolo,JYan,pmentofPZTandPZN-PTbad

unimorphaetuatorsformicromechanicalflappingmechanisms[J].

ticsandAutomation,Korea,2001

ato,linctflightsimulators:asoftwaretestbed

forinctflight[J].ticsand

Automation，2001

,RJWood,SAvadhanula,sflappingwingcontrolfora

micromechanicalflyinginct[J].

RoboticsandAutomationSeoul,SouthKorea,May2001,3901-3908

ato,XDeng,controlsystemforamicro

mechanicalflyinginct:architectureandimplemeniation[J].InProcof

enceonRobotiesandAutomation,Soul,SouthKorea,May

2002

in-Sirirak,YCTai,dy-stateaerodynamic

PerformanceofMEMSwings[J].InternationalSymposiumonSmartStructures

andMicrosystems,TheJoekeyClub,HongKong,Oetober19-21,2000

sin-Sirirak,SWLee,HNasf,ngtechnologyfora

battery-Poweredornithoper[J].Proeeedingsof13thIEEEAnnual

InternationalConfereneeonMEMS2000,Miyazaki,Japan,2000,799-804

CMichelson,onflappingwingmicroair

vehiclereareh:ongoingworktodevelopaflappingwing

crawling“EntomoPter”[J].13thBristolInternationalRPV

Conferenee,BristolEngland,30March-1April,1998

CMichelson,rocatingchemicalmule(RCM)for

microairvehiele“Entermopter”flight[J].1997Proceedingsofthe

AssoeiationforUnmannedVehieleSystems,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)有限元相关书籍

(2)计算几何学和VC++编程相关书籍

(3)实验室计算机一台

(4)VisualC++，Gambit，Fluent，Tecplot等软件

2．所需经费，包含经费来源、开支预算（工程设备、材料须填写名称、规格、数

量）

五、工作计划

序

号

阶段及内容

工作量

估计

（时

数）

起止日期

阶段成

果形式

1

2

3

4

5

6

查阅资料，选择应用软件工具，确定研究方案

熟悉编程软件，实现四叉树网格初始梯度划分、悬

点处理、移点处理、边界切割、切割图形四边形化

总结前期工作，申请专利并发表国际期刊论文

处理多区域问题的四叉树网格划分实现方式

完善结果：针对不足之处，寻找方法，解决弥补

总结结果，汇总文献，完成毕业论文

320

240

120

240

240

400

2010.7-

2010.9

2010.10-

2010.11

2010.12

2011.1-

2011.2

2011.2-

2011.3

2011.4-

2011.6

开题报

告

具体过

程及结

果

具体过

程及结

果

具体过

程及结

果

具体过

程及结

果

学位论

文

合计

六、评审意见

导师（或导师组）对本课题的评价

导师签名

年月日

评审小组

组成姓名职称所在单位签字

组长张振伟副教授东北大学机械工程与自动化学院

成员

评审小组的审查结论

课题结合实际，开发一种CFD中的网格划分方法。查阅文献较丰富，研究方案可

行，进度安排合理，希望尽快进入课题研究工作，按时完成编程工作完成论文。

(注意创新点的总结)

组长

2011年12月25日

东北大学硕士研究生学位论文选题报告评分表

评审项目

权

重

评分标准

得分

（百分

制）

一、选题依据

（A）

30%

80~100

分

选题有较强的理论意义、实用价值，深刻的学术

研究内涵。

60~80

分

选题有一定的理论意义、实用价值，有一定的学

术研究内涵。

60分以

下

选题缺乏理论意义和实用价值。

二、理论基础

和专门知识

(B)

20%

80~100

分

较好的掌握坚实宽广的理论基础和系统专业知识

60~80

分

基本的掌握坚实宽广的理论基础和系统专业知识

60分以

下

未能掌握坚实宽广的理论基础和系统知识

三、选题难度

及先进性(C)

30%

80~100

分

研究课题属本学科发展方向并居前沿位置，具有

自己独特的思考、研究课题具有较强的先进性

60~80

分

研究课题属本学科的发展方向，并具有先进性。

60分以

下

研究课题与本学科的发展方向先进性不明显，难

度欠佳。

四、文字表达

（D）

10%

80~100

分

条理清晰，分析严谨，文笔流畅

60~80

分

条理较好，层次分明，文笔较流畅

60分以

下

写作能力较差

五、口头报告

(E)

10%

80~100

分

论文严密、逻辑性强、表达清楚。

60~80

分

基本概念清晰、层次分明。表达较清楚。

60分以

下

表达较差

总分总分=0.3A+0.2B+0.3C+0.1D+0.1E

备注：评审专家只对五项指标每一项的最后一栏内打分（百分制），不必计

算总分。