Smooth-surface reconstruction in near-linear time
Stefan Funke, Edgar A. Ramos · 2002
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that contains the sample points. Variants of this problem have received considerable attention in computer vision and computer graphics and more recently in computational geometry. In the latter area, three different algorithms (Amenta and Bern `98, and refined in Amenta, Choi, Dey and Leekha `00; Amenta, Choi and Kolluri `00; Boissonnat and Cazals `00) have been proposed. These algorithms have a correctness guarantee: if the sample is sufficiently dense then the output is a good approximation to the original surface. They have unfortunately a worst-case running time that is quadratic in the size of the input. This is so because they are based on the construction of 3-d Voronoi diagrams or Delaunay tetrahedrizations, which can have quadratic size. Even worse, according to recent work (Erickson `01), there are surfaces for which this is the case even when the sample set is "locally uniform" on the surface. In this paper, we describe a new algorithm that also has a correctness guarantee but whose worst-case running time is almost linear. In fact, O(n log n) where n is the input size. As in some of the previous algorithms, the piece-wise linear approximation produced by the new algorithm is a subset of the 3-d Delaunay tetrahedrization; however, this is obtained by computing only the relevant parts of the 3-d Delaunay structure. The algorithm first estimates for each sample point the surface normal and a parameter that is then used to "decimate" the set of samples. The resulting subset of sample points is locally uniform and so a reconstruction based on it can be compu...