Provably Good Moving Least Squares

We analyze a moving least squares (MLS) interpolation scheme for reconstructing a surface from point cloud data. The input is a sufficiently dense set of sample points that lie near a closed surface F with approximate surface normals. The output is a reconstructed surface passing near the sample points. For each sample point s in the input, we define a linear point function that represents the local shape of the surface near s. These point functions are combined by a weighted average, yielding a three-dimensional function I. The reconstructed surface is implicitly defined as the zero set of I. We prove that the function I is a good approximation to the signed distance function of the sampled surface F and that the reconstructed surface is geometrically close to and isotopic to F. Our sampling requirements are derived from the local feature size function used in Delaunay-based surface reconstruction algorithms. Our analysis can handle noisy data provided the amount of noise in the input dataset is small compared to the feature size of F.