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 .

No abstract available.

Given a sample of points from the boundary of an object IR3, we construct a representation of the object as a union of balls. We use many fewer balls than previous constructions, but our shape representation is better. We bound the distance from the surface of the union to the original object surface, and show that when the sampling is sufficiently dense the two are homeomorphic. This implies a topolgical relationship between the true medial axis of the object and both the medial axis, and the α-shape, of the union of balls. We show that the set of ball centers in our construction converges to the true medial axis as the sampling density increases.