Study The Surface Reconstruction Algorithm Based On Voronoi Diagram

How to compute a piecewise linear approximation to a surface from a set of sampling points abstracted from the surface, which is called surface reconstruction terminologically, is a topic covers so many fields such as computer graphics, reverse engineering, image processing, mathematics and chemistry. In this thesis, we pay much effort to develop an algorithm for surface reconstruction from scattered data set. That means in the input there is only 3-D coordinate of the points. And the output is a triangular network curved surface and which is homeomorphic to the original surface. The whole content of this thesis can be divided into two parts:In the first part we describe the development and applications about visualization of 3D spatial data sets and also the main techniques for 3D data visualization. And surface reconstruction is one of topics in 3D data visualization, hi this part we also summarize the theoretical approaches for surface reconstruction and describe their strengths, weaknesses, and relative performance. Taxonomy groups the methods into classes that highlight their similarities. The Voronoi and Delaunay based algorithms for surface reconstruction has been studied intensely in recent years because of their easiness to understand and implement. Besides, they have theoretical guarantee of computing a topologically correct and geometrically close surface under certain condition on sampling density. We also attach importance to this method. In this part we analyse two algorithms in this field: Crust algorithm and Cocone algorithm. From the analysis we gain the knowledge about their strong suit and the inherence shortcoming.In the second part we select Cocone algorithm as the base for our algorithm, which improved Crust both in theory and practice. And then we announce a new algorithm for surface reconstruction. Compared with Cocone algorithm, ours has three improvements. They are : 1) we present two algorithms: one is Voronoi-vertex-movement algorithm and the other is surface normal correlative algorithm. The algorithms mean to remove the overlapped triangles and to avoid the manifold extraction step. 2) We introduce an algorithm to detect the undersampling patch in the input data and to avoid appearance of the wrong connected triangles around the boundary. 3) We present a Delaunay-based algorithm to fill up the holes in the result surface. This means make our output to be water-tight surface, which is appreciated in many applications such as CAD. The Delaunay-base one proves to be efficient and the output triangles have better geometry shape than other ones.In the conclusion we figure out some shortcoming existing in our algorithm. And we make some plans for future work.