【作者】 杨晟院；

【导师】 舒适；

【作者基本信息】 湘潭大学 ， 计算数学， 2008， 博士

【摘要】 三维网格生成在科学与工程计算、逆向工程和几何造型等众多领域有着广泛的应用。曲面网格的质量是影响四面体网格质量的重要因素,为获得高质量的曲面网格一般需要进行网格优化处理。与平面网格优化不同,曲面网格优化更为复杂,它通常包括曲面网格特征线提取、曲面网格重分、曲面Delaunay和CVT网格的生成与优化等。现在虽然有许多相关的研究工作,但是还不太成熟,如还没有一种统一、有效的特征线提取方法;对于一般曲面网格,还没有一种普适的曲面Delaunay和CVT网格定义以及相应的网格生成算法等等。因此,如何利用基于STL文件的曲面网格特性,给出更有效、更健壮的特征线提取方法以及曲面Delaunay和CVT网格的生成算法是一项值得关注的研究工作。另外,曲面网格的质量还会影响四面体网格生成算法的复杂性,如一般需要进行边界还原等。因此,如何给出一种边界自动还原的四面体网格生成算法也是一项重要的研究工作。偏微分方程数值求解在科学工程计算与数值仿真中起着十分重要的作用,如何快速求解偏微分方程离散化系统是其中的瓶颈问题之一。代数多层网格(AMG)法是目前国际上求解偏微分方程离散化系统最有效的方法之一。四面体网格的质量与AMG法的效率密切相关,因此,针对四面体网格下的二阶椭圆边值问题离散化系统,设计高效AMG法(或基于AMG预条件子的Krylov子空间迭代法)是一项有意义的工作。本文针对上述问题进行了深入研究,获得了一批算法和理论结果,文章主要由以下四个部分组成:第一部分,比较系统地研究了基于STL文件的曲面网格特征线提取方法。首先,针对STL文件给出一种新的曲面网格快速重建算法;其次,针对由基本几何曲面所构成的组合曲面网格,提出一种建立基本几何曲面网格二面角阈值数据库的思想,给出了一种自适应获取特征线阈值的组合曲面网格特征线提取算法;然后,针对一般曲面网格,在基于特征线阈值的基础上,结合G1插值法、边长比值法、断点连接法,以及利用曲面网格分割的思想,给出了若干特征线提取算法。数值实验表明了新算法的有效性和健壮性,并且能获得更丰富的特征信息。第二部分,首先,针对已确定特征线的基于STL文件的曲面网格进行网格重分处理;然后,利用重分网格的特性,引入了新的更为简洁的曲面Delaunay和CVT网格的定义,并给出了相应的生成算法。数值实验表明,我们的新算法能够生成高质量的曲面CVT网格。第三部分,首先,利用曲面CVT网格,并结合已有的四面体网格生成技术,给出一种边界自动还原的四面体网格生成算法;接着,给出了一种四面体网格的并行生成算法,从而提高了生成四面体网格的效率。第四部分,首先,通过考察不同质量的四面体网格对AMG-PCG法的影响,发现新的高质量四面体网格能大幅度提高求解二阶椭圆边值问题的线性有限元方程的AMG-PCG法效率;接着,针对高次有限元方程,设计了一种基于辅助变分问题的新的并行AMG预条件子,并从理论上严格证明了该预条件子的条件数的一致有界性。数值实验验证了理论结果的正确性及相应预条件共轭梯度(PCG)法的高效性和健壮性。更多还原

【Abstract】 Three-dimensional grid generation have been widely used in computing science and engineering, reverse engineering and geometric sculpts, and many other fields. The quality of surface mesh is an important factor for high-quality tetrahe-dral grid generation. In order to obtain high-quality surface mesh, usually it need mesh optimization. Different to the plane mesh optimization, the optimization of surface mesh is more complex. It usually includes feature line extraction for surface mesh, surface remeshing, the Delaunay and Centroidal Voronoi Tessellation (CVT) surface mesh generation and optimization, and so on. Although there are many related research works, there are not satisfied. For example, there is no unified and effective feature line extraction method; no universal definition of Delaunay and CVT surface mesh in general case, and its corresponding surface mesh generation algorithm, and so on. Therefore, how to make use of the surface mesh’s characteristic based on STL file, and give a more effective and robust methods for feature line extraction, as well as the Delaunay and CVT surface mesh generation algorithms is an interesting and important in our research. In addition, the qualities of surface mesh also affect the complexity of tetrahedral grid generation algorithms, such as it needs boundary recovery, and so on. Therefore, how to give a tetrahedral grid generation algorithm for boundary recovering automatically is also an important research.Solving partial differential equations (PDEs) by numerical methods plays an important role in science and engineering computing, and numerical simulation. How to quickly solve the discretization system of PDEs is one of the bottlenecks. Algebraic multigrid (AMG) method is one of the most effective methods for solving the discretization system of PDEs in the world. The quality of tetrahedral grid is closely related to the efficiency of the AMG method. So, for the discretization system of the second-order elliptic boundary value problems under the tetrahedral grids, how to design a high-performance AMG method (or a Krylov subspace iteration method based on the preconditioner of AMG method) is a significant work.In this thesis, the above-mentioned issues have been deeply researched; we obtained a number of algorithms and theoretical results. This thesis is mainly composed of the following four parts:Part I, we systematically studied the feature line extraction methods for the surface mesh based on STL files. First, we gave a new surface mesh rapid reconstruction algorithm for STL file. Second, for the composite surface mesh which is composed of some basic geometric surfaces, we proposed an idea of establishing a basic geometric surface mesh dihedral angle threshold database, and gave a feature line extraction method for the composite surface mesh in which the dihedral angle obtained adaptively. Last, for the surface mesh in general case, we proposed many methods of feature line extraction based on the feature line threshold, combining with the methods of G1 interpolation, the ratio of the side of triangle, connecting the break point, as well as making use of the surface mesh segmentation. Numerical experiments show that the new methods are effective and robust, and we can get more information on the features.Part II, first, for the surface mesh based on STL file in which its feature lines have been extracted, we did the remeshing. Second, according to the characteristic of the remeshed surface mesh, we introduced a new and laconic definition of surface Delaunay and CVT mesh, and gave its corresponding surface mesh generation algorithm. Numerical experiments show that our new algorithm can generate high-quality surface CVT mesh.Part III, making use of the surface CVT mesh, and combining with the tetrahedral mesh generation technologies, we gave a new tetrahedral mesh generation algorithm in which the boundary recovered automatically. Then, we gave a parallel algorithm of tetrahedral grid generation, which can enhance the efficiency of the tetrahedral grids generation.Part IV, according to study the AMG-PCG method for the different quality of tetrahedral grids, we found that the new high-quality tetrahedral grid can be substantial increase the AMG-PCG method’s efficiency in solving linear finite element equations for second-order elliptic boundary value problems. Second, for the high-order finite element equations, a new parallel AMG preconditioner based on the auxiliary variational problems was proposed. We theoretically proved the uniform bounded property for the condition numbers of the proposed preconditioner. Various numerical experiments support our theoretical results; show the high efficiency and robustness of the resulting preconditioned conjugate gradient (PCG) method.更多还原