Sampling and Reconstructing Manifolds Using Alpha-Shapes

Abstract

There is a growing interest for the problem of reconstructing the shape of an object from multiple range images. Several methods, based on heuristics, have been described in the literature. We propose the use of alpha-shapes, which allow us to give a formal characterization of the reconstruction problem and to prove that, when certain sampling requirements are satisfied, the reconstructed alpha-shape is homeomorphic to the original object and approximate it within a fixed error bound. In a companion paper, we describe practical methods to automatically select an optimal alpha value, to deal with less-than-ideal scans, and to fit smooth piecewise algebraic surface to the data points. 1 Introduction Cheaper, easier-to-use 3D digitizers are fostering a growing interest for the problem of shapereconstruction. Automatic methods for reconstructing an accurate geometric model of an object from a set of digital scans have applications in reverse engineering, shape analysis, virtual worlds aut...