Font Size: a A A

Optimization Of Surface Mesh Based On STL File And Study Of Algebraic Multigrid Method

Posted on:2009-01-30Degree:DoctorType:Dissertation
Country:ChinaCandidate:S Y YangFull Text:PDF
GTID:1100360302455746Subject:Computational Mathematics
Abstract/Summary:PDF Full Text Request
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.
Keywords/Search Tags:STL file, feature line extraction, surface Delaunay mesh, surface CVT mesh, Delaunay tetrahedral grid, AMG method
PDF Full Text Request
Related items