Algorithms For Automatic Generation Of Surface Triangular Meshes With Arbitrarily Topology From Scatter Points

Surface reconstruction from scatter points is an important part of computer geometric modeling and plays an essential role in computer graphics. It is of a great interest for many applications such as reverse engineering, medicine image processing, and virtual environments. It is a basic step for the follow up processing, such as editing of?sw~face, simplifying and compressing of the triangular meshes. The difficult point of the reconstruction is that the sample points are absolutely unorganized. We get only the 3D coordinate of these points without any other correlative information. However, the topology of the unknown surface may be very complex some time. It is really a hard work to generate the complex surface just by these scatter points. In order to solve this problem, we select the 揷rust?algorithm that is a Voronoi-based 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 those are all the sample points. These triangles gel~erate the crust of the unknown surface. Additionally, the mesh with these triangles is the same as the original surface in the topological structure. But the mesh of the crust is not always satisfied. It may include the tetrahedron or complex inner surface sometimes. And some holes may appear in the mesh surface. These defects are induced by the data or by the method: itself. For these reasons, the twt follow-tip steps are accepted. One is 搈inimal dihedral algorithm? the other is 揻illing 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 app~ications.