A Fast Algorithm for Delaunay based Surface Reconstruction

Shan Gao, Han-Qing Lu
National Laboratory of Pattern Recognition, Chinese Academy of Science
100080 Beijing 
P.R. China

Keywords: surface reconstruction, Delaunay triangulation, geometric modeling

Abstract

Advanced 3D scanning technologies enable us to obtain dense and accurate surface sample point sets. From sufficiently dense sample point set, Crust algorithm, which is based on Voronoi diagram and its dual Delaunay triangulation, can reconstruct a triangle mesh that is topologically valid and convergent to the original surface. However, the algorithm is restricted in the practical application because of its long running time. Based on the fact that we do not need dense sample in featureless area for successful reconstruction, we propose a non-uniformly sampling method to resample the input data set according to the local feature size before reconstruction. In this way, we increase the speed of reconstruction without losing the details we need .