Eurographics Symposium on Geometry Processing (2005)M. Desbrun, H. Pottmann (Editors)An Adaptive MLS Surface for Reconstruction withGuaranteesTamal K. Dey and Jian Sun†AbstractRecent work have shown that moving least squares (MLS) surfaces can be used effectively to reconstruct surfacesfrom possibly noisy point cloud data. Several variants of MLS surfaces have been suggested, some of which havebeen analyzed theoretically for guarantees. These analyses, so far, have assumed uniform sampling density. Wepropose a new variant of the MLS surface that, for the first time, incorporates local feature sizes in its formulation,and we analyze it for reconstruction guarantees using a non-uniform sampling density. The proposed variant ofthe MLS surface has several computational advantages over existing MLS methods.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Line and Curve Genera-tion1. IntroductionIn surface reconstruction, if the input point cloud is noisy,a surface fitting through the points can be too bumpy forpractical use. A remedy to this problem is to define a tar-get smooth surface and project or generate points on thissmooth surface for reconstruction. Of course, the main prob-lem is to choose a suitable smooth surface that resemblesthe original surface which the input point cloud presumablysampled. Several such target surfaces have been proposed re-cently with different algorithms for their computations. Theradial basis function of Carr et al. [JCCCM∗01], the multi-level partition of unity of Ohtake et al. [OBA∗03], the naturalneighbor surface of Boissonnat and Cazasls [BC00] and themoving least squares of Alexa et al. [ABCO∗01] are exam-ples of such surfaces, to name a few.The moving least squares surfaces (MLS), originally pro-posed by Levin [Lev98] and later adopted by Alexa etal. [ABCO∗01] for reconstruction have been widely used formodeling and rendering [AA03, MVdF03, PKKG03]. Thepopular open source software PointShop 3D [ZPKG02] im-plements the MLS surfaces and shows the effectiveness ofthe MLS surfaces on real world scanned data. Recently, thework of Amenta and Kil [AK04] and Kolluri [Kol05] havebroaden the understanding of the MLS surfaces. Kolluri con-†Dept. of CSE, The Ohio State University, Columbus, OH 43210.{tamaldey,sunjia}@cse.ohio-state.edusidered an implicit version of the MLS surfaces and proved,for the first time, theoretical guarantees about them. Sub-sequently, Dey, Goswami and Sun [DGS05] proved simi-lar guarantees for the variant of MLS proposed by Amentaand Kil. These theoretical results assume a globally uni-form sampling density which is quite restrictive. For exam-ple, in Figure 1, the globally uniform sampling conditionneeds more than 104points to sample the arc ab becauseof a small feature somewhere else. Our aim is to prove guar-antees about MLS surfaces under an adaptive sampling con-dition similar to the one used by Amenta and Bern [AB99] inthe context of noise-free reconstruction. Under such adaptivesampling, one needs only 6 points to sample the arc in Fig-ure 1. To accommodate an adaptive sampling, we come upwith a new variant of the MLS surfaces, which incorporatesthe local feature sizes of the sampled surface in its formula-tion. Our results show that this new MLS surface has severaladvantages over other existing MLS methods.60r/10^4rbaFigure 1: The dash-dot lines represent the medial axis.c The Eurographics Association 2005.T. K. Dey and J. Sun / An Adaptive MLS Surface for Reconstruction with Guarantees1.1. MLS surfacesMoving least squares is an extension of the well known leastsquares technique to fit a surface to a given set of data points.The term ‘moving’ refers to the various weighting of thepoints in calculating their contributions to the solution atdifferent locations. This unified view of the moving leastsquares is nicely explained by Shen et al. [SOS04]. Thereare mainly two types of MLS surfaces considered in the lit-erature in the context of surface reconstructions.1.1.1. Implicit MLSShen et al.[SOS04] defined a MLS surface implicitly by afunction which they called IMLS surface. This surface isspecified by the moving least-squares solution to a set ofconstraints that force the function to assume given valuesat the sample points and also force its upward gradient tomatch the assigned normals at the sample points. Each con-straint is associated with a weight function. In the simplestcase, the implicit function can be taken asI(x) =∑p∈P[(x − p)Tvp]θp(x)∑p∈Pθp(x)(1.1)where θpis a weighting function and vpis the normal as-signed to a sample point p. Kolluri [Kol05] considered thissurface and showed that the IMLS surface is indeed isotopic(stronger than homeomorphic) to the sampled surface if theinput sample is sufficiently dense.1.1.2. Projection MLSLevin [Lev98] pioneered a MLS surface that is defined as aset of stationary points of a projection operator. We call thisprojection based MLS surfaces as PMLS surfaces. Amentaand Kil [AK04] gave a more explicit definition for PMLSsurfaces as the local minima of an energy function alongthe directions given by a vector field. Based on this explicitdefinition, they gave an implicit form for PMLS surfaces.Specifically, they showed that the PMLS surface defined byLevin [Lev98] is actually the implicit surface given by thezero-level set of the implicit functionJ(x) = n(x)T(∂E(y,n(x))∂y|x)where n : R3→ R3is a given vector field, E: R3×R3→R is an energy function given by E(y, n(x)) =12∑p∈P[(y −p)Tn(x)]2θp(y) with θpas a weighting function. If θpis aGaussian with width h thenJ(x) =∑p∈P(x−p)Tn(x)[1−((x − p)Tn(x)h)2]θp(x). (1.2)The PMLS surface definition inherently leads to a projectionmethod by which points can be projected onto the surface.Dey, Goswami and Sun [DGS05] prove theoretical guaran-tees for PMLS surfaces.1.1.3. Variation of PMLS (VMLS)If we define the energy function as E(y,n(x)) =12∑p∈P[(y−p)Tn(x)]2θp(x) where the weighting function θpvaries withx instead of y, we obtain a variant definition of PMLS sur-faces, which we call VMLS in short. Indeed, this is the MLSsurface actually implemented in PointShop 3D by Zwickeret al. [ZPKG02]. It has a very simple implicit formG(x) =∑p∈P[(x − p)Tn(x)]θp(x). (1.3)An advantage of this definition is that, unlike the standardPMLS surfaces, its inherent projection procedure does notrequire any non-linear optimization, which makes the