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.