非结构网格生成：理论、算法和应用
	曾用价	118.00
	出版社	科学出版社
	版次	1
	出版时间	2016年04月
	开本	16
	著译编者	郑耀，陈建军
	装帧	圆脊精装
	页数	288
	字数	344
	ISBN编码	9787030472830

网格生成是一类偏微分方程数值求解的前处理步骤，它研究如何将给定的几何区域离散成几何单元的组合。鉴于网格生成对数值模拟的重要性及其自动化方法的复杂性，它逐渐吸引了各领域众多有深厚功底的研究人员的关注，并不断从计算几何和计算机图形学等领域吸取养分，从而已发展成为一个独立的研究领域。 本书重点介绍作者二十多年来在网格生成理论、算法和应用等方面取得的相关研究成果，内容包括 Delaunay 网格生成、参数曲面网格生成、前沿推进网格生成、单元尺寸及几何自适应网格生成、六面体网格生成、并行网格生成以及相应的前处理软件系统。系统性强，内容新颖。


郑耀、陈建军编*的《非结构网格生成--理论算法和应用(精)》内容限定在非结构网格。内容包括Delaunay三角化、前沿推进法等主流非结构网格生成方法，也包括这些方法应用与复杂曲面和实体网格生成时的关键技术。此外，也讨论了当前非结构网格生成的前沿热点问题的研究进展，如尺寸场的控制、六面体网格生成和并行网格生成等。此外，以自主知识产权网格生成软件HEDP/PRE为例，自顶向下分析了网格生成软件的设计和实现方法，展示了HEDP/PRE在复杂数值模拟问题中的应用实例。

目录
第1章 引言1
1.1 物理背景和基本概念2
1.1.1 偏微分方程数值求解的基本流程2
1.1.2 网格生成的基本概念3
1.2 结构网格生成方法9
1.2.1 单块结构网格生成方法10
1.2.2 分块结构网格生成方法12
1.2.3 直角网格生成方法14
1.3 非结构网格生成方法15
1.3.1 三角形和四面体网格生成方法16
1.3.2 四边形网格生成方法17
1.3.3 六面体网格生成方法19
1.3.4 混合网格生成方法19
1.4 本书的特色和结构20
第2章 Delaunay网格生成22
2.1Delaunay三角化的定义22
2.2Delaunay网格生成的常用算法23
2.2.1 B-W算法24
2.2.2 边／面交换算法25
2.2.3 凸包法26
2.2.4 算法比较27
2.3 关键问题及其研究进展27
2.3.1 内部点生成27
2.3.2 边界恢复28
2.3.3 网格质量优化30
2.3.4 算法效率31
2.3.5 算法鲁棒性32
2.4 Delaunay网格生成程序范例 33
2.4.1程序介绍 34
2.4.2算法流程 34
2.4.3数据结构 36
2.4.4鲁棒的B-W插点算法 37
2.4.5边界点插入 38
2.4.6 内部点的生成和插入 39
2.4.7二维边界恢复 40
2.4.8三维边界恢复 41
2.4.9外部单元删除 50
2.4.10网格质量优化 51
2.4.11数值实验 51
2.5 结束语 55
第3章 参数曲面网格生成 56
3.1 参数曲线和曲面及黎曼度量的基本理论 56
3.1.1参数曲线 56
3.1.2参数曲面 57
3.1.3黎曼度量 57
3.1.4黎曼距离 58
3.1.5单位网格 59
3.2参数曲面网格生成算法研究的*新进展 60
3.2.1映射法 60
3.2.2直接法 62
3.3 简化的几何引擎范例 63
3.3.1边界表征 63
3.3.2几何定义 64
3.4组合参数曲面网格生成程序范例 67
3.4.1程序介绍 67
3.4.2算法流程 68
3.4.3 曲线离散 69
3.4.4实空问到参数空间的投影 70
3.4.5参数平面边界网格的绕向规整 71
3.4.6基于Delaunay算法的参数平面网格生成 71
3.4.7参数网格质量优化 74
3.4.8教值实验 76
3.5结束语79
第4章 前沿推进网格生成80
4.1 经典前沿推进算法80
4.1.1经典前沿推进算法流程80
4.1.2经典前沿推进算法的关键技术81
4.1.3前沿推进算法和Delaunay算法的比较86
4.2前沿推进思想在网格生成中的拓展应用86
4.2.1 前沿推进-Delaunay耦合算法87
4.2.2前沿层进四边形网格生成算法（铺路法）88
4.2.3 Q-Morph算法90
4.3前沿推进参数曲面网格生成程序范例92
4.3.1程序介绍92
4.3.2平面各向同性前沿推进三角形网格生成算法92
4.3.3参数平面前沿推进三角形网格生成算法94
4.3.4前沿推进曲面四边形网格生成算法95
4.3.5数值实验99
4.4结束语103
第5章 单元尺寸及几何自适应网格生成104
5.1单元尺寸的基本概念105
5.1.1单元尺寸场105
5.1.2黎曼空问和单位网格107
5.1.3单元尺寸场和网格边数的基本关系108
5.1.4单元尺寸的融合109
5.1.5单元尺寸的插值110
5.1.6单元尺寸的过渡控制112
5.2交互式单元尺寸场定义119
5.2.1全局尺寸119
5.2.2边界驱动120
5.2.3背录网格120
5.2.4网格源120
5.3几何自适应单元尺寸122
5.3.1几何特征分类123
5.3.2几何特征识别124
5.3.3几何自适应尺寸场的计算125
5.4几何自适应单元尺寸计算程序范例126
5.4.1程序结构和算法流程 126
5.4.2尺寸场的初始化 127
5.4.3尺寸场的后处理 130
5.4.4尺寸场插值 132
5.4.5数值实验 133
5.5 结束语 135
第6章 六面体网格生成136
6.1六面体网格生成的困难137
6.2任意形体六面体网格生成方法研究综述138
6.2.1栅格法138
6.2.2 H-Morph算法140
6.2.3铺层法141
6.2.4编织缠绕法141
6.2.5无约束铺层法143
6.3扫掠体的分类及扫掠法的研究进展144
6.3.1 扫掠体的分类144
6.3.2扫掠法的研究进展145
6.4多源多目标扫掠体全六面体网格程序范例148
6.4.1程序介绍148
6.4.2单源扫掠法148
6.4.3 多源扫掠法155
6.4.4多源多目标扫掠法158
6.4.5数值实验165
6.5结束语168
第7章 并行网格生成169
7.1基本概念170
7.1.1 并行网格生成算法的分类170
7.1.2评价并行网格生成算法优劣的标准171
7.1.3区域分解172
7.1.4负载平衡172
7.2研究趋势173
7.3典型算法174
7.3.1 同步处置类并行网格生成算法175
7.3.2后置处理类并行网格生成算法177
7.3.3前置处理类并行网格生成算法180
7.4并行四面体网格生成程序范例183
7.4.1程序介绍183
7.4.2程序基本流程184
7.4.3区域分解方法185
7.4.4网格生成及质量优化196
7.4.5数值试验198
7.5 结束语205
第8章 基于非结构网格的前处理软件系统206
8.1国内外现状综述207
8.2 HEDP和HEDP/PRE的基本情况209
8.2.1 HEDP的基本情况209
8.2.2 HEDP/PRE的基本情况213
8.3几何模块217
8.3.1 基于分层软件结构的几何引擎217
8.3.2 连续曲面和离散曲面 218
8.3.3 虚拓扑 220
8.3.4 几何算法 221
8.4 单元尺寸模块224
8.5 网格模块226
8.5.1算法流程226
8.5.2数据结构228
8.5.3网格算法229
8.6系统应用234
8.6.1 复杂几何形状的非结构网格生成234
8.6.2流体力学应用237
8.6.3结构力学应用245
8.6.4燃烧学应用248
8.7结束语251
参考文献252



第1章 引 言
简而言之，网格生成研究的问题是如何将给定的几何区域划分成有限个基本几何形体的组合，而这些基本几何形体被称为单元。对平面或曲面区域，基本几何形体常采用三角形或四边形；对三维区域，基本几何形体往往采用四面体、六面体等。网格生成技术在很多领域都有广泛的应用，如计算机图形学、计算机视觉、可视化、地理信息系统，因此研究者众多，但由于研究的层次、角度和需求不尽相同，所采用的方法和面临的挑战也互有差异。本书讨论的网格生成技术，其主要应用对象是偏微分方程（Partial Differential Equation，PDE）的数值求解[1-14]。当然，这些技术也可拓展应用于其他领域。
通过建立合理的模型，很多物理现象的模拟可归结为偏微分方程的求解。由于求解区域、边界条件及材料特性等因素的影响，这些方程通常无法利用解析的方法求解，只能退而求其次，结合计算机技术进行数值求解。典型偏微分方程数值解法包括有限单元法( Finite Element Method，FEM) [15]、有限体积法(Finite Volume Method，FVM) [16]、边界单元法(Boundary Element Method，BEM) [17]双有限差分法( Finite DifferenceMethod，FDM)[18]。网格生成是应用这些方法的前处理步骤，网格生成后，一个包含无限自由度的连续物理场问题被离散成一个包含有限自由度的离散系统。通常情形下，该离散系统可利用大规模矩阵的数值计算方法求解。
网格生成在整个数值模拟过程中的地位是极其重要的。一方面，网格的“好”与“坏”可决定后续计算过程的精度、效率乃至成败；另一方面，复杂问题的网格生成过程依赖于操作人员的经验，且无法完全自动化，涉及大量人工操作，其所消耗的工作量可能会占整个数值模拟过程的绝大部分。网格生成*初是伴随数值模拟方法的研究而产生的研究分支，但鉴于其在数值模拟中的特殊地位，它逐渐吸引了各领域众多有深厚功底的研究人员，并不断从计算几何和计算机图形学等其他领域吸取养分，*终发展成为一个独立的研究领域。
本章1.1节将着重介绍网格生成相关的背景知识、基本概念和分类方法，并以时间为轴，简要回顾网格生成方法的发展历史。由于本书后续章节主要关注非结构网格生成方法，不失完整性，1.2节将回顾另一类主流的网格生成方法一一结构网格生成的研究现状。与之呼应，1.3节则回顾非结构网格生成的研究现状，但重点关注后续章节不涉及的一些技术内容。1.4节梳理全书的脉络，以期读者能理解本书的写作宗旨和特色。
1.1 物理背景和基本概念.
1.1.1 偏微分方程数值求解的基本流程.
科学计算被广泛认为是理论和实验之外认识自然界各种物理现象和规律的第三类手段。开展科学计算的首要步骤是建立问题的数学模型，针对自然界的流、固、热、电、磁等种种物理现象，科学家已建立了一系列精妙的偏微分方程予以描述，如适用流体问题的欧拉方程和Navier-Stokes方程，适用电磁场的麦克斯韦方程。尽管基于这些方程进行理论分析仍然是认识自然规律的有效途径，但更多情况下，尤其是在实际的工程设计中，无法解析求解这些方程。随着计算机技术的发展，人们尝试使用诸如FEM、FDM和FVM等数值方法求解这些问题，取得了巨大的成功。
图1.1示意了基于自适应技术开展偏微分方程数值求解的典型过程，它包含六个主要步骤。
(1)几何建模。传统的正向设计中，操作人员利用CAD软件构建问题的几何外形，这些外形通常由很多连续的自由曲线和曲面通过一定的拓扑关系组合而成。目前，激光扫描、基于图像重建等反向建模技术己大量应用，这些技术直接产生的模型通常为三角面片表征的离散模型。无论正向设计得到的连续模型还是反向设计得到的离散模型，均育可能不满足后续网格生成的要求（不封闭、自相交、不符合二边流形准则等），或包含过多的几何细节（使得网格不必要加密，从而增加计算量），因此，在网格化这类模型前需对其进行必要的修复和简化。
(2)初始网格生成。网格生成是一个“设计”过程，操作人员需在一定程度上掌握所计算问题的背景知识，并据此确定网格的类型、规模以及单元的分布等，形成“设计”策略，而策略的执行通常伴随大量的人工干涉。网格质量对计算的精度、效率和收敛性至关重要，在开展计算前，需对网格的有效性及质量进行分析，并结合一些自动算法提高网格质量。当生成网格失败或生成的网格质量不满足数值求解要求时，需修正网格生成策略，甚至重新定义或修改几何模型。
(3)边界条件定义。边界条件通常是方程求解的定解条件，附加在几何模型或网格模型上。此外，这一环节还需定义材料参数以及与计算程序相关的求解参数。
(4)计算及误差分析。计算网格以及定义在其上的边界条件、材料参数等共同构成了计算模型，将其输入计算程序得到初步计算结果后，需进行必要的误差分析。如果误差满足预设要求，则可停止计算，进入后续的数据处理阶段；否则，需根据误差信息，调整网格并重启计算。
l.几何建模 2.初始网格生成 3.边界条件定义 4.计算及误差分析 5.自适应网格生成 6.可视化 图1.1 自适应数值模拟流程.
(5)自适应网格生成。对计算结果进行误差分析后，可以得到误差在计算域的分布信息，根据这类后验知识调整网格，并重启计算过程，以期获得更精确的计算结果。网格的调整策略有三类：调整单元疏密（h-自适应）、调整网格节点分布（r-自适应）或调整单元的插值格式(p-自适应)。h-自适应、r-自适应以及hr-耦合自适应在实际计算中*为常。
(6)可视化。计算结果通常规模很大，且具有很复杂的几何或拓扑结构，可视化尝试利用计算机图形学技术，利用可视的图形、图像或统计工具来表征物理量及其分布规律，帮助分析人员从计算结果中快速得到全局或局部物理规律，并定性或定量表征这些规律。
1.1.2 网格生成的基本概念.
1．网格的分类
为满足不同应用需求，网格形式林林总总有很多，可以从不同角度去归类。例如非结构网格生成：理论、算法和应用从几何维度看，主要可分为平面、曲面和实体等网格；从单元类型看，可分为三角形、四边形、四面体、六面体和任意多面体网格，以及包含多种单元形式的混合单元网格。此外，从单元形状是否规则的角度可将网格分为各向同性网格和各向异性网格：各向同性网格要求单元为边长比（单元的长边和短边边长比）接近于1的“正”多边形，各向异性网格则是边长比非常大的狭长或扁平单元，以适应曲率特征或物理特征的各向异性。
*为常用的分类方法是根据网格的单元拓扑是否具有某种规律将其分为结构网格( structured mesh)和非结构网格(unstructured mesh)。狭义的结构网格定义非常严格，要求每个内部网格节点都被相同数目的单元所包含。若按一定规则对结构网格的节点进行编号，则节点相邻关系等网格拓扑信息可隐藏于节点编号之中。反之，非结构网格中包含每个内部节点的单元数目是不确定的，网格拓扑需显式表达。与非结构网格相比，存储及访问结构网格数据的代价都较小，相应数值计算的时空效率也更有优势。结构网格的另一个优势是其单元具有很好的正交性和贴边性，相应数值计算的精度也更高。与结构网格相比，非结构网格因其灵活的单元连接方式，能更好地适应复杂几何定义，更好地实施单元疏密变化，因此，其生成方法的自动性及自适应计算的能力都更高。
严格意义上的结构网格只存在于区域边界非常简单的情形，还有一些网格形式因其网格拓扑具备规律性通常也被归类为结构网格。一类是基于四（八）叉树法生成的直角网格（图1.2（a1，图片来自NASA，即美国国家航空航天局），它在计算流体动力学(Computational Fluid Dynamics，CFD)的欧拉方程求解中有着广泛应用，在地形可视化领域通常称这类网格为半规则( semi-regular)网格。另一类则是分块结构网格(图1.2(b1)，它是当前CFD应用中的主流网格形式之一[7，19]，其生成是典型的分而治之过程：首先分解问题域为子块；随后在每个子块上生成结构网格；*终合并子块网格为整体网格。
(a)直角网格（来自NASA Cart3D） (b)分块结构网格（来自DLR MegaCads）图1.2两类特殊的结构网格形式.
在结构网格和非结构网格之间，还有一类特殊的半结构网格，这类网格的单元拓扑仅在某个方向呈现结构化规律。例如，基于扫掠法生成的网格（图1.3），当源面形状复杂时，其源面网格通常为非结构网格，但沿扫掠路径方向的侧面网格则呈现结构化特性。此外，在粘性流体计算中，为适应边界层附近各向异性的物理现象，其边界层网格在垂直物面方向呈现结构化特性，而平行物面方向则布置非结构三角形和四边形网格(图1.4)。 图1.3基于扫掠法生成的六面体网格及其剖切视图 图1.4带短舱F6飞机标模的粘性计算混合网格（见彩图）
为结合结构网格和非结构网格各自的长处，很多模拟中应用的网格配置可能是结构网格和非结构网格共同组成的，我们称这种网格形式为混合网格。这里需要注意区分混合网格( hybrid mesh)和混合单元网格(mixed-element mesh)，后者仅是单元几何类型的混合，而非网格拓扑类型的混合。常用的混合网格有两类，一类是图1.4所展示的粘性计算网格，它在近物面区域（边界层）布置半结构网格，而在远物面区域布置非结构网格；另一类是分块网格技术衍生出来的网格形式：在大部分区域分块使用结构网格，但在块与块邻近的医域使用非结构网格连接。本书**作者郑耀在NASA工作期间研制的三维DRAGON (Direct Replacement of Arbitrary Grid Overlapping byNonstructured grid)网格程序即用于生成第二类混合网格[20.21]（图1.5）。为叙述方便，我们将**类混合网格归类为非结构网格，第二类混合网格归类为结构网格。
图1.5 DRAGON I网络技术应用于气膜冷却涡轮叶片分析（见彩图）
2．网格生成算法的分类
*直接的网格生成算法分类方法是根据其产生的网格进行分类，如分为平面、曲面或实体网格生成算法；三角形、四边形、四面体或六面体网格生成算法；各向同性或各向异性网格生成算法；结构或非结构网格生成算法等。
当然，也可以从算法本身所具备的一些共性特征对其进行归类。例如，Frey等就尝试将主要的网格生成算法归成五类【2】。
第1类主要指早期通过手工或半自动方式指定网格几何和拓扑信息的方法，只适用于简单几何情形。
第2类是基于参数化和映射技术的算法，它将物理空间不规则区域的网格生成问题通过映射函数转换为参数空间规则区域的网格生成问题。映射函数的确定主要有两类途径：一是通过代数插值，二是通过求解PDE方程。此外，三维参数曲面网格生成也可基于映射思想简化为二维问题。
第3类是基于区域分解技术的算法，它基于分而治之思想，分解原区域为多个子区域，将复杂区域的网格生成问题转换为多个相对简单的子区域网格生成问题的组合，如分块结构网格生成及四／八叉树法网格生成。
第4粪是插点／连元算法，通常以区域边界为输入，逐步在区域内部增加新的网格节点或创建新的单元，直至区域按照预定要求被完全网格化，如Delaunay三角化和前沿推进算法。
第5类是构造型算法，根据问题的特性将问题域分成很多个子区域，每个子区域可以采用上述任意一种算法生成网格，*终网格则为所有子区域网格的组合，如混合网格生成算法。
3．网格质量的评价标准
在评价一套网格质量的优劣前，需首先确认其几何有效性和拓扑有效性，几何有效条件诸如要求所有单元具有正面积或正体积（保证雅可比矩阵为正），单元之间互不