Surface Reconstruction Using Adaptive Clustering Methods

We present an automatic method for the generation of surface triangulations from sets of scattered points. Given a set of scattered points in three-dimensional space, without connectivity information, our method reconstructs a triangulated surface model in a two-step procedure. First, we apply an adaptive clustering technique to the given set of points, identifying point subsets in regions that are nearly planar. The output of this clustering step is a set of two-manifold "tiles" that locally approximate the underlying, unknown surface. Second, we construct a surface triangulation by triangulating the data within the individual tiles and the gaps between the tiles. This algorithm can generate multiresolution representations by applying the triangulation step to various resolution levels resulting from the hierarchical clustering step. We compute deviation measures for each cluster, and thus we can produce reconstructions with prescribed error bounds.