【作者】 梁义；

【导师】 郑耀；

【作者基本信息】 浙江大学 ， 计算机科学与技术， 2009， 博士

【摘要】 基于偏微分方程的数值模拟在工程与科学计算中有着广泛应用,作为其前处理关键步骤,网格生成一直以来是相关学科研究的热点。表面网格(包括平面网格和曲面网格)是表面问题建模的主要构成元素,也是三维实体问题建模的输入条件,其质量对整个数值模拟至关重要,一直是网格生成研究的主要对象之一。此外,表面网格在计算机图形学、地理信息系统等领域也有重要应用。实际应用中,几何模型通常包含大量几何特征,网格生成时应在它们附近生成小尺寸的网格单元,保证网格离散的几何精度和单元质量;在其余部分生成大尺寸单元,避免网格规模不必要扩大。利用人工的网格尺寸控制手段达到上述目的费时且易错,开展自适应网格生成研究可有效缓解上述瓶颈问题。本文围绕自适应表面网格生成这一主要目标,结合黎曼度量和Delaunay方法,提出并实现了一系列算法和框架,对包括平面、连续曲面和离散曲面在内的各种表面问题域的自适应网格生成进行了研究。另外,本文还讨论了平面并行网格生成。首先研究自适应表面网格生成的基础算法,其重点是平面各向异性网格生成和自适应网格尺寸控制。在各向同性算法中引入黎曼度量表征单元尺寸,计算两点距离,获得黎曼度量场下的Bowyer-Watson增量插点内核,实现平面各向异性Delaunay网格生成。分别使用欧拉度量下和黎曼度量下边界采样点集的约束Delaunay三角化计算形体中轴,据此实现形体邻近特征识别,结合曲率计算,可实现平面问题和曲面问题的自适应网格生成。特别地,基于曲面邻近特征和曲率特征,融合传统网格尺寸控制技术,创建曲面自适应尺寸场并自适应地离散曲面边界,形成一个通用的自适应曲面网格生成框架。以组合Coons参数曲面为例,将上述基础算法应用于连续曲面模型的网格生成。重点讨论两种黎曼度量的计算:(1)参数曲面内在度量用于识别邻近特征,结合曲率特征,可自动识别参数曲面的几何特征,实现自适应;(2)融合尺寸控制的黎曼度量用于控制参数平面各向异性网格生成。上述计算结合基于映射法的曲面网格生成算法,实现了组合连续曲面的自适应网格生成。以STL模型为例,将上述基础算法应用于离散曲面模型的网格生成。首先给出一类非自适应的STL曲面网格生成方法,它采用保特征的子域识别方法将模型分割为多个子域,并为每个子域构建参数平面,利用各向同性方法生成参数平面网格。在此基础上通过为子域重建G~1连续三角B-B曲面,给出子域参数平面上点的黎曼度量计算方法。考虑映射畸变,基于黎曼度量在参数平面生成各向异性网格;使用黎曼度量下边界采样点集的约束Delaunay三角化计算曲面邻近特征,结合曲率估算实现自适应网格生成。最后,针对大规模数值模拟的需要,在序列化算法基础上,利用预置的几何区域分解过程,实现了一个稳定、高效、可扩展的并行平面Delaunay网格生成算法。新算法在并行网格生成前定义表征子域连接关系的子域图,利用子域图分区实现负载平衡和通信最小化,可在并行网格生成结束时得到高分区质量的分布式网格。与传统的基于网格图分区的算法相比,新算法可降低甚至消除网格重分区的代价,当网格规模非常庞大时,这将显著提高整个并行求解过程的效率。更多还原

【Abstract】 Mesh generation is the key pre-process of numerical simulations based on partial differential equations in engineering and scientific computing. One of its important research areas is surface mesh generation. Not only could surface mesh be applied directly to surface modeling, but also it is the input of volume mesh generation. Besides numerical simulations, surface mesh generation also is of many other applications in various fields, such as computer graphics and geographic information systems.As an input of surface mesh generation, complex geometry models usually contain many features. To generate good meshes for numerical analyses, the mesh size should be small near the features to achieve high geometry accuracy and element quality, and large elsewhere to avoid increasing the number of mesh elements unnecessarily. However, manual size control on complex models is time consuming and prone to errors to achieve such goals. Instead, adaptive mesh generation is capable of overcoming this bottleneck problem, effectively.Based on the Delaunay method and Riemannian metric, in this thesis, adaptive mesh generation for all kinds of surfaces, including planes, continuous curved surfaces and discrete curved surfaces, is systematically studied. Additionally, a parallel algorithm for planar mesh generation is also presented.Firstly, some fundamental algorithms for adaptive surface mesh generation are discussed, mainly including planar anisotropic mesh generation algorithms and adaptive mesh size control algorithms. Riemannian metric is introduced to define mesh sizes and to calculate point-to-point distances, thus a traditional isotropic Bowyer-Watson kernel for Delaunay mesh generation is revised for Riemannian context of planar anisotropic mesh generation. To recognize shape proximity over plane or curved surfaces, constrained Delaunay triangulations of sample points on boundary curves are used to produce the discrete medial axes, with help of Euclid metric for planes or Riemannian metric for curved surfaces, respectively. Coupled with curvature calculations, adaptive surface meshes of planar or curved surfaces can be produced. Moreover, by combining adaptive and traditional mesh size control strategies, a general framework for adaptive mesh generation over curved surfaces is presented.Taking composite Coons surfaces as an example, the above fundamental algorithms are applied for continuous curved surface mesh generation. The approaches to calculate Riemannian metric and curvature are studied, and two kinds of Riemannian metrics are discussed: (1) The intrinsic metric is used to recognize proximity, for adaptive mesh size control together with curvatures. (2) The Riemannian metric coupled with mesh sizes is used to generate anisotropic meshes on parametric planes. Combining these two kinds of metrics and a surface mesh generation algorithm based on mapping transformation, an adaptive mesh generator for continuous curved surfaces is implemented.Taking STL surfaces as an example, the above fundamental algorithms are applied for discrete curved surface mesh generation. Firstly, a fast surface mesh generation algorithm is proposed. The initial model is divided into many sub-domains with features preserved at sub-domain boundaries, and then the parametric plane for every sub-domain is constructed to dedimension the sub-domain mesh generation, where a planar isotropic algorithm is applied. To enhance this algorithm, G~1 continuous triangular B-B surfaces are reconstructed for sub-domains to calculate the Riemannian metrics for points on parametric planes. In the Riemannian context, high quality isotropic surface meshes are generated with anisotropic meshes generated in parametric planes, and constrained Delaunay triangulations for sample points on surface boundaries are computed to recognize proximity. Coupled with curvature calculation, adaptive meshes for STL models can be generated.Parallel mesh generation is used to generate large-scale meshes for engineering and scientific computing. With a geometry domain decomposition as the pre-process, a stable, effective and scalable parallel planar Delaunay mesh generator is built on the serial isotropic mesh generation algorithm. It defines Sub-Domain Graph (SDG) to represent the sub-domain connections, then partitions the graph dynamically to achieve dual goals of loading balance and communication minimization, and finally generates distributed meshes with high partitioning quality simultaneously with parallel mesh generation. Compared with traditional algorithms based on mesh graph partitioning, this algorithm can reduce or eliminate the cost of mesh repartitioning, which can accelerate the whole simulation process significantly for large-scale meshes.更多还原