散乱点的快速曲面重建方法

A Fast Algorithm for Surface Reconstruction from Unorganized Points

空间散乱点的曲面重建有着广泛的应用前景 ,是当前国际上的研究热点之一 .Crust算法是一种基于计算几何中的 Voronoi周期图的曲面重建算法 ,它算法简单 ,重建结果精细 ,但是由于计算量太大 ,其应用受到了限制 ,为此提出了一种依据采样点的局部特征尺度对原始采样集进行不均匀降采样的方法 ,在保证采样集能够满足重建要求的前提下 ,使参与重建的表面点数大为降低 ,减少了重建算法的计算量 ,从而提高了重建的速度 .这一方法还可以应用于网格简化 。

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.