A fast surface-based procedure for object reconstruction from 3D scattered points

In this paper, a new fast three-phase method for object reconstruction from 3D scattered points is presented, The first phase is founded on a novel fast triangulation algorithm, which generates a base approximation of the object surface. By inserting bridges, the triangulation algorithm also handles surfaces with genus greater than zero and determines the genus of the reconstructed surface. From results of the first phase, the object surface features, such as sharp edges, silhouette polylines, and corners, are extracted in the next phase. Sharp edges and corners are used as constraints for triangular mesh fairing later in the final phase, where a new improved decimation and a novel mesh refinement procedure are introduced, while silhouette polylines can be applied for generation of a wire-frame model of the reconstructed object. The overall object reconstruction procedure has a tested linear time complexity. (C) 1998 Academic Press.