research-article

Provably good moving least squares

Author:

Ravikrishna KolluriAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 4, Issue 2

Article No.: 18, Pages 1 - 25

https://doi.org/10.1145/1361192.1361195

Published: 29 May 2008 Publication History

Abstract

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.

References

[1]

Adamson, A. and Alexa, M. 2003. Approximating and intersecting surfaces from points. In Proceedings of the Eurographics Symposium on Geometry Processing. Eurographics Association, 230--239.

Digital Library

[2]

Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and T. Silva, C. 2003. Computing and rendering point set surfaces. IEEE Trans. Visualiz. Comput. Graph. 9, 1, 3--15.

Digital Library

[3]

Amenta, N. and Bern, M. 1999. Surface reconstruction by voronoi filtering. Discr. Comput. Geom. 22, 481--504.

[4]

Amenta, N., Choi, S., Dey, T. K., and Leekha, N. 2002. A simple algorithm for homeomorphic surface reconstruction. Int. J. Comp. Geom. Appli 12, 1--2, 125--141.

[5]

Amenta, N., Choi, S., and Kolluri, R. 2001. The power crust. In Proceedings of the 6th Symposium on Solid Modeling. ACM, 249--260.

Digital Library

[6]

Amenta, N. and Kil, Y. 2004. Defining point-set surfaces. In Proceedings of ACM SIGGRAPH. ACM.

Digital Library

[7]

Amenta, N., Peters, T. J., and Russell, A. C. 2003. Computational topology: Ambient isotopic approximation of 2-manifolds. Theor. Comput. Scie. 305, 1, 3--15.

Digital Library

[8]

Belytschko, T., Krongauz, Y., Fleming, M., Organ, D., and Liu, W. K. 1996. Meshless methods: An overview and recent developments. J. Computat. Appl. Math. 74, 111--126.

Digital Library

[9]

Bloomenthal, J., Ed. 1997. Introduction to Implicit Surfaces. Morgan Kaufman.

Digital Library

[10]

Boissonnat, J.-D. and Cazals, F. 2000. Smooth surface reconstruction via natural neighbour interpolation of distance functions. In Proceedings of the 16th Annual Symposium on Computational Geometry. ACM, 223--232.

Digital Library

[11]

Boissonnat, J.-D., Cohen-Steiner, D., and Vegter, G. 2004. Isotopic implicit surface meshing. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. 301--309.

Digital Library

[12]

Boissonnat, J. D. and Oudot, S. 2003. Provably good surface sampling and approximation. In Proceedings of the Eurographics Symposium on Geometry Processing. Eurographics Association, 9--18.

Digital Library

[13]

Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and Representation of 3D objects with radial basis functions. In Computer Graphics SIGGRAPH Proceedings. 67--76.

Digital Library

[14]

Curless, B. and Levoy, M. 1996. A Volumetric method for building complex models from range images. In Computer Graphics SIGGRAPH' Proceedings. 303--312.

Digital Library

[15]

Dey, T. K. and Goswami, S. 2004. Provable surface reconstruction from noisy samples. In Proceedings of the 20th Annual ACM Symposium on Computational Geometry.

Digital Library

[16]

Dey, T. K. and Sun, J. 2005. An adaptive MLS surface for reconstruction with guarantees. In Proceedings of the Eurographics Symposium on Geometry Processing. 43--52.

Digital Library

[17]

Fleishman, S., Alexa, M., Cohen-Or, D., and Silva, C. T. 2003. Progressive point set surfaces. ACM Trans. Comput. Grap. 22, 4.

Digital Library

[18]

Fréchet, M. 1924. Sur La Distance de Deux Surfaces. Ann. Soc. Polonaise Math. 3, 4--19.

[19]

Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Computer Graphics SIGGRAPH Proceedings. 71--78.

Digital Library

[20]

Lancaster, P. and Salkauskas, K. 1981. Surfaces generated by moving least squares methods. Math. Comput. 37, 155, 141--158.

[21]

Levin, D. 2003. Mesh-independent surface interpolation. In Geometric Modeling for Scientific Visualization, G. Brunett, B. Hamann, K. Mueller, and L. Linsen, Eds. Springer-Verlag.

[22]

Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., and Fulk, D. 2000. The Digital Michelangelo Project: 3D scanning of large statues. In Computer Graphics SIGGRAPH Proceedings. 131--144.

Digital Library

[23]

Lorensen, W. E. and Cline, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In Computer Graphics (SIGGRAPH Proceedings). 163--170.

Digital Library

[24]

Mitra, N. J., Gelfand, N., Pottmann, H., and Guibas, L. 2004. Registration of point cloud data from a geometric optimization perspective. In Symposium on Geometry Processing.

Digital Library

[25]

Mitra, N. J., Nguyen, A., and Guibas, L. 2004. Estimating surface normals in noisy point cloud data. Int. J. Comput. Geom. Appl. 14, 4--5, 261--276.

[26]

Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-level partition of unity implicits. ACM Trans. Graph. 22, 3, 463--470.

Digital Library

[27]

Osher, S. and Fedkiw, R. 2003. The Level Set Method and Dynamic Implicit Surfaces. Springer-Verlag, Berlin, Germany.

[28]

Pauly, M., Keiser, R., Kobbelt, L. P., and Gross, M. 2003. Shape modeling with point-sampled geometry. ACM Trans. Graph. 22, 3, 641--650.

Digital Library

[29]

Plantinga, S. and Vegter, G. 2004. Isotopic approximation of implicit curves and surfaces. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. ACM, 245--254.

Digital Library

[30]

Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge Monograph on Applied and Computational Mathematics. Cambridge University Press.

[31]

Shen, C., O'Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. In Proceedings of ACM SIGGRAPH.

Digital Library

[32]

Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 23rd ACM National Conference. ACM, 517--524.

Digital Library

[33]

Turk, G. and O'Brien, J. 1999. Shape transformation using variational implicit functions. In Computer Graphics SIGGRAPH Proceedings. 335--342.

Digital Library

[34]

Zhao, H.-K., Osher, S., and Fedkiw, R. 2001. Fast surface reconstruction using the level set method. In 1st IEEE Workshop on Variational and Level Set Methods. 194--202.

Digital Library

Cited By

Jiang XXie YNa CYu WMeng Y(2024)Algorithm for Point Cloud Dust Filtering of LiDAR for Autonomous Vehicles in Mining AreaSustainability10.3390/su1607282716:7(2827)Online publication date: 28-Mar-2024
https://doi.org/10.3390/su16072827
Aijazi AChecchin P(2024)Non-Repetitive Scanning LiDAR Sensor for Robust 3D Point Cloud Registration in Localization and Mapping ApplicationsSensors10.3390/s2402037824:2(378)Online publication date: 8-Jan-2024
https://doi.org/10.3390/s24020378
Wang ZWang PWang PDong QGao JChen SXin STu CWang W(2024)Neural-IMLS: Self-Supervised Implicit Moving Least-Squares Network for Surface ReconstructionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.328423330:8(5018-5033)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3284233
Show More Cited By

Index Terms

Provably good moving least squares
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models

Recommendations

Provably good moving least squares
SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

We analyze a moving least squares algorithm for reconstructing a surface from point cloud data. Our algorithm defines an implicit function I whose zero set U is the reconstructed surface. We prove that I is a good approximation to the signed distance ...
Parabolic-cylindrical moving least squares surfaces

Moving least squares (MLS) surface approximation is a popular tool for the processing and reconstruction of non-structured and noisy point clouds. This paper introduces a new variant improving the approximation quality when the underlying surface is ...
Toward an efficient triangle-based spherical harmonics representation of 3D objects

In classical frequency-based surface decomposition, there is always a restriction about the genus number of the object to obtain the spherical harmonics decomposition of spherical functions representing these objects. Such spherical functions are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 4, Issue 2

May 2008

204 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1361192

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 2008

Accepted: 01 April 2007

Revised: 01 October 2006

Received: 01 May 2005

Published in TALG Volume 4, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
1,079
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang XXie YNa CYu WMeng Y(2024)Algorithm for Point Cloud Dust Filtering of LiDAR for Autonomous Vehicles in Mining AreaSustainability10.3390/su1607282716:7(2827)Online publication date: 28-Mar-2024
https://doi.org/10.3390/su16072827
Aijazi AChecchin P(2024)Non-Repetitive Scanning LiDAR Sensor for Robust 3D Point Cloud Registration in Localization and Mapping ApplicationsSensors10.3390/s2402037824:2(378)Online publication date: 8-Jan-2024
https://doi.org/10.3390/s24020378
Wang ZWang PWang PDong QGao JChen SXin STu CWang W(2024)Neural-IMLS: Self-Supervised Implicit Moving Least-Squares Network for Surface ReconstructionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.328423330:8(5018-5033)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3284233
Edirimuni DLu XLi GRobles-Kelly A(2024)Contrastive Learning for Joint Normal Estimation and Point Cloud FilteringIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.326386630:8(4527-4541)Online publication date: Aug-2024
https://doi.org/10.1109/TVCG.2023.3263866
Hu JJones DDogar MValdastri P(2024)Occlusion-Robust Autonomous Robotic Manipulation of Human Soft Tissues With 3-D Surface FeedbackIEEE Transactions on Robotics10.1109/TRO.2023.333569340(624-638)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TRO.2023.3335693
Ouasfi ABoukhayma A(2024)Unsupervised Occupancy Learning from Sparse Point Cloud2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02053(21729-21739)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02053
Ouasfi ABoukhayma A(2024)Mixing-Denoising Generalizable Occupancy Networks2024 International Conference on 3D Vision (3DV)10.1109/3DV62453.2024.00086(1103-1114)Online publication date: 18-Mar-2024
https://doi.org/10.1109/3DV62453.2024.00086
Ouasfi ABoukhayma AOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Robustifying generalizable implicit shape networks with a tunable non-parametric modelProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667251(25958-25970)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667251
Li HWu GTao SYin HQi KZhang SGuo WNinomiya SMu Y(2023)Automatic Branch–Leaf Segmentation and Leaf Phenotypic Parameter Estimation of Pear Trees Based on Three-Dimensional Point CloudsSensors10.3390/s2309457223:9(4572)Online publication date: 8-May-2023
https://doi.org/10.3390/s23094572
Nie MShi WFan WXiang H(2023)Automatic Extrinsic Calibration of Dual LiDARs With Adaptive Surface Normal EstimationIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2022.322971472(1-11)Online publication date: 2023
https://doi.org/10.1109/TIM.2022.3229714
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents