Algorithms For Generation Of Surface Triangular Meshes From Unorganized Points

In this thesis, the surface reconstruction for unorganized points, and the design and implementation of the system for constructing the finite element mesh.During reconstruction it is difficult to get the proper topological connections among points in the data set just according to the three-dimensional coordinates of the points. In this thesis, we study some mainstream surface reconstruction algorithms for unorganized data set and adopt the algorithms based on Delaunay Triangulation. First we get a mesh from the data set by the improved Cocone Algorithm. In the mesh the local geometric and topological property can be clearly described with its adjacent points for a given point. Then the Delaunay Triangulation technique in two dimensions is used to delete and modify the illegal triangles in the resulting mesh. Finally we will get a 2-dimensional manifold mesh. The algorithm works well for models with arbitrary topology and can tolerate the sampling noise at some degree. In addition, boundaries can be detected automatically during reconstruction.In order to dispose the large data, we use the divide and conquer method to improve the algorithm mentioned above.In practice the surface triangulation with given points set on the surface is a familiar issue. In this thesis we bring forward a method for the issue based on the algorithm in the thesis.At last we design a system for constructing the finite element mesh based on the algorithms mentioned above, which can dispose many kinds of input data.