The Research On Crust-based Surface Reconstruction Algorithm

Surface reconstruction from scatter points is an important part of computer geometric modeling and plays an essential role in computer graphics. The technique of surface reconstruction from scatter points has extensive use in many applications such as reverse engineering, medicine intage processing, and virtual environments. We get only the 3D coordinate of these points without any other correlative information. It is really a hard work to generate the complex surface just by these scatter points.First, in order to solve this problem, we select the crust-based surface reconstruction algorithm. It calculates the poles of every sample point. then computes the Delaunay triangulation with sample points and the poles, at last, extracts the triangle that includes the three vertices which are all the sample points. These triangles generate the crust of the unknown surface. Additionally, the mesh with these triangles is the same as the original surface in the topological structure.Second, for generating the exact mesh of a unknown surface. the local structure of a scattered point set and its classical Delaunay triangulation algorithms are investigated. Because there is local feature of Delaunay triangulation,we suggested two algorithms for Delaunay triangulation from scattered points, one of which is from points in plane and the other from points in space.Last, because the mesh of the crust is not always satisfied. It may include the tetrahedron or may appear some holes in the mesh surface.These defects are induced by the data or by the method itself. For these reasons, the two follow-up steps are accepted. One is "minimal normal variation algorithm", the other is "filling the circle area".Experiments demonstrate triangular meshes generated in this thesis appear to be in good form and precision. The generation is also efficient and capable of satisfying need of applications.