A Fast Algorithm for Surface Reconstruction from Unorganized Points
散乱点的快速曲面重建方法

Surface reconstruction from unorganized points has numerous applications, and it is widely studied all over the world nowadays. Crust algorithm, which is based on Voronoi diagram and its dual Delaunay triangulation, can reconstruct the original surface from sufficiently dense sample point set. It is simple and direct in theory and its result is also very fine. However, the algorithm is restricted in the practical application because of its long running time. In practice, the sampling density required by Crust algorithm for successful reconstruction is varied in different area: dense in detailed areas and sparse in featureless ones. Based on this fact, a method for non uniformly sampling the dense data set according to the local feature size is presented in this paper. With the guarantee that the remaining points are sufficient to reconstruction, the amount of points used in reconstruction is largely decreased, and then the speed of reconstruction is improved. The results show that the details are kept well in the reconstructed surface. However, since the points are sparse in featureless region, the triangles approximating the surface are comparatively large there. That makes reconstructed surface look very coarse. Gouraud shading can give an acceptable visual effect. The method of non uniformly down sampling can also be used to decimate the vertices of mesh to realize mesh simplification.