The Triangulation Of Points Cloud On The Space Surface

This thesis is on antriangulation from 3D scatered points.Efective approach to the method of the a low computational complexity and high mesh quality algorithm has great application merit in the research of computational geometry, surface reconstruction and visualization of 3D data.At first, the typical 2D and 3D triangulation algorithm of scattered points is discussed in this paper.delaunay is the most stable algorithm in all the algorithm I have ever seen.And the algorithm of delaunay is on the base of the theory of mathmatics.So the triangulation got from the algorithm of delaunay can be trust.The mesh got from the algorithm of delaunay is the most optimum.as far as this advantage be concerd the algorithm of delaunay can be replaced with other algorithm.the algorithm of delaunay can be applied to 2D and it can also be applied to 3D.In the space the algorithm of delaunay also have advantage.But also it have disadvantage. The advantage is that the each two triangles got from the algorithm of delaunay can not be crossed with each other .The algorithm based on the delaunay about points cloud for 3D have two important steps.The first step is to get the triangles got from the algorithm of delaunay.the other step is to select the suitable triangles to form a mensh .In fact that this algorithm is the combination of the algorithm of delaunay and the algorithm of front wave .The front wave algorithm is based on the crowed points. For the point is crowed ,the two triangles got in the mesh contained one public edge must have large face angle .this is the essential of the algorithm of front wave.the algorithm of delaunay also have disadvantages.For example,the algorithm of delaunay can not solve all the problem of the point cloud .it can only generet a mesh that have a convex hull.But the cloud we have to face are usually rather complex.for example the point cloud of the a rabbit and the point cloud of the horse.At the same time the algorithm of delaunay can deal with the complex point cloud more easily and fast,and it is more flexible than the algorithm of the delaunay.The advantage of the algorithm of delaunay is that it is more easily to realize and the speed is more fast than the algorithm based on the algorithm of dealuny.But it also have disadvantage that the triangles got from the algorithm of delaunay may have the two triangles that the two triangles croosed each other.If you want to avid this problem,you have to spend a lot of time.The more points you have to deal with the more time you have to spend.the algorithom are not on any theory of mathmatics so the result mesh can not be trust essily.Then a space partition strategy with its corresponding data structure and encoding method is proposed by the author in order to improve the triangulating and searching efficiency according to the trend of larger and larger points set. The direct triangulation algorithm from 3D scattered data which great improve the triangulating eficiency and mesh quality based on the local mesh generation method is described in the third chapter. The computational complexity of this algorithm is O(N) . The concept of living boarder edge and dead boarder edge is firstly put forward in this paper.In the process of the trianglating I put out some parameters the first one is the miner angle of the triangle .The second parameter is the miner angle of the two triangle shared a common edge .the last parameter is the ridus of the ball that is used to delete points too near to a certain point .The mesh wo got finaly are depended the three parameter wo specified .Usually wo have to specify the parameter according to the featrues of the points,especially the third parameter .We can reference to the distant a point to the nearset one.For the speed of my algorithm is very fast ,we can a just the three para meter if you are not satisied with mesh based on the three parameters.This paper also analyzed some key problems in 3D triangulation from scattered points. At the end of this paper, the future research area of triangulation from 3D scattered points are demonstrated。.