Provable surface reconstruction from noisy samples (Q2507163)

The problem of surface reconstruction asks to approximate a surface from a set of point samples. This problem has been the focus of research across many fields because of its wide applications. In this paper the authors present an algorithm for surface reconstruction from noisy point cloud data. Under a reasonable noise model, it is shown that the algorithm has theoretical guarantees. The model allows the points to be scattered around the sampled surface and the range of the scatter is restricted to the local feature size. The algorithm works with the Delaunay/Voronoi diagrams of the input points and draws upon some of the principles of the power crust algorithm. In the power crust algorithm it is observed that the union of a set of Delaunay balls called polar balls approximates the solid bounded by the sampled surface. This property does not hold in presence of noise. Nevertheless, the authors observe that, under the assumed noise model, some of the Delaunay balls are relatively big and can play the role of the polar balls. These balls are identified and partitioned into inner and outer balls. It is shown that the boundary of the union of the outer (or inner) big Delaunay balls is homeomorphic to the sampled surface. This provides a homeomorphic surface reconstruction though the reconstructed surface may not interpolate the sample points. The authors extend the algorithm further to compute a homeomorphic surface interpolating a subset of the input sample points. These points reside on the outer (or inner) big Delaunay balls. The rest of the points are deleted. It is shown that the Delaunay triangulation of the chosen sample points restricted to the boundary of the chosen big Delaunay balls is homeomorphic to the sampled surface. Also performance of the algorithm is illustrated by experimental results.