“Moving level-of-detail surfaces” by Mercier, Lescoat, Roussillon, Boubekeur and Thiery

We present a simple, fast, and smooth scheme to approximate Algebraic Point Set Surfaces using non-compact kernels, which is particularly suited for filtering and reconstructing point sets presenting large missing parts. Our key idea is to consider a moving level-of-detail of the input point set which is adaptive w.r.t. to the evaluation location, just such as the samples weights are output sensitive in the traditional moving least squares scheme. We also introduce an adaptive progressive octree refinement scheme, driven by the resulting implicit surface, to properly capture the modeled geometry even far away from the input samples. Similarly to typical compactly-supported approximations, our operator runs in logarithmic time while defining high quality surfaces even on challenging inputs for which only global optimizations achieve reasonable results. We demonstrate our technique on a variety of point sets featuring geometric noise as well as large holes.

1. Marc Alexa and Anders Adamson. 2009. Interpolatory point set surfaces – convexity and Hermite data. ToG 28, 2 (2009), 20.Google ScholarDigital Library
2. M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C. T. Silva. 2001. Point set surfaces. In Proceedings Visualization, 2001. VIS ’01. 21–29, 537.Google Scholar
3. Nina Amenta and Yong Joo Kil. 2004. Defining point-set surfaces. In ToG, Vol. 23. ACM, 264–270.Google ScholarDigital Library
4. Gavin Barill, Neil G Dickson, Ryan Schmidt, David IW Levin, and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ToG 37, 4 (2018), 43.Google ScholarDigital Library
5. Matthew Berger, Joshua A Levine, Luis Gustavo Nonato, Gabriel Taubin, and Claudio T Silva. 2013. A benchmark for surface reconstruction. ToG 32, 2 (2013), 20.Google ScholarDigital Library
6. Matthew Berger, Andrea Tagliasacchi, Lee M Seversky, Pierre Alliez, Gael Guennebaud, Joshua A Levine, Andrei Sharf, and Claudio T Silva. 2017. A survey of surface reconstruction from point clouds. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 301–329.Google Scholar
7. Jules Bloomenthal. 1988. Polygonization of implicit surfaces. Computer Aided Geometric Design 5, 4 (1988), 341–355.Google ScholarDigital Library
8. Mario Botsch and Leif Kobbelt. 2004. A remeshing approach to multiresolution modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing. 185–192.Google ScholarDigital Library
9. Fatih Calakli and Gabriel Taubin. 2011. SSD: Smooth signed distance surface reconstruction. Computer Graphics Forum 30, 7 (2011), 1993–2002.Google ScholarCross Ref
10. Stéphane Calderon and Tamy Boubekeur. 2014. Point Morphology. ToG (Proc. SIGGRAPH 2014) 33, 4, Article 45 (2014), 45:1–45:13 pages.Google Scholar
11. Junjie Cao, Andrea Tagliasacchi, Matt Olson, Hao Zhang, and Zhixun Su. 2010. Point Cloud Skeletons via Laplacian-Based Contraction. In Proc. of IEEE Conference on Shape Modeling and Applications’10. 187–197.Google ScholarDigital Library
12. J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and T. R. Evans. 2001. Reconstruction and Representation of 3D Objects with Radial Basis Functions. In Proc. SIGGRAPH (SIGGRAPH ’01). 67–76.Google Scholar
13. Jiazhou Chen, Gael Guennebaud, Pascal Barla, and Xavier Granier. 2013. Non-oriented MLS Gradient Fields. Computer Graphics Forum 32, 8 (Aug. 2013), 98–109.Google ScholarCross Ref
14. Tamal K Dey and Jian Sun. 2005. An Adaptive MLS Surface for Reconstruction with Guarantees.. In Symposium on Geometry processing. 43–52.Google ScholarDigital Library
15. Leslie Greengard and Vladimir Rokhlin. 1987. A fast algorithm for particle simulations. Journal of computational physics 73, 2 (1987), 325–348.Google ScholarDigital Library
16. Gaël Guennebaud, Marcel Germann, and Markus Gross. 2008. Dynamic Sampling and Rendering of Algebraic Point Set Surfaces. Computer Graphics Forum 27, 2 (2008), 653–662.Google ScholarCross Ref
17. Gaël Guennebaud and Markus Gross. 2007. Algebraic Point Set Surfaces. In ACM SIGGRAPH 2007 Papers (SIGGRAPH ’07). New York, NY, USA.Google Scholar
18. Thierry Guillemot, Andrès Almansa, and Tamy Boubekeur. 2012. Non Local Point Set Surfaces. In Proceedings of 3DIMPVT.Google ScholarDigital Library
19. Rana Hanocka, Gal Metzer, Raja Giryes, and Daniel Cohen-Or. 2020. Point2Mesh: A Self-Prior for Deformable Meshes. ToG 39, 4, Article 126 (July 2020), 12 pages.Google Scholar
20. Hui Huang, Shihao Wu, Daniel Cohen-Or, Minglun Gong, Hao Zhang, Guiqing Li, and Baoquan Chen. 2013. L1-medial skeleton of point cloud. ToG 32, 4 (2013), 65–1.Google ScholarDigital Library
21. Zhiyang Huang, Nathan Carr, and Tao Ju. 2019. Variational Implicit Point Set Surfaces. ToG 38, 4 (july 2019), 124:1–124:13.Google ScholarDigital Library
22. Zhongping Ji, Ligang Liu, and Yigang Wang. 2010. B-Mesh: A Modeling System for Base Meshes of 3D Articulated Shapes. Computer Graphics Forum 29 (09 2010), 2169–2177.Google Scholar
23. Tao Ju, Frank Losasso, Scott Schaefer, and Joe Warren. 2002. Dual contouring of hermite data. In ToG, Vol. 21. ACM, 339–346.Google ScholarDigital Library
24. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Proceedings of the fourth Eurographics symposium on Geometry processing, Vol. 7.Google ScholarDigital Library
25. Michael Kazhdan and Hugues Hoppe. 2013. Screened poisson surface reconstruction. ToG 32, 3 (2013), 29.Google ScholarDigital Library
26. David Levin. 1998. The approximation power of moving least-squares. Technical Report. Math. Comp.Google Scholar
27. David Levin. 2003. Mesh-Independent Surface Interpolation. Geometric Modeling for Scientific Visualization 3 (01 2003).Google Scholar
28. William E Lorensen and Harvey E Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In ACM siggraph computer graphics, Vol. 21. ACM, 163–169.Google Scholar
29. Wenjia Lu, Zuoqiang Shi, Jian Sun, and Bin Wang. 2018. Surface Reconstruction Based on the Modified Gauss Formula. ToG 38, 1 (2018), 2.Google Scholar
30. Nicolas Mellado, Gaël Guennebaud, Pascal Barla, Patrick Reuter, and Christophe Schlick. 2012. Growing Least Squares for the Analysis of Manifolds in Scale-Space. Comp. Graph. Forum 31, 5 (2012), 1691–1701.Google ScholarDigital Library
31. Guy M Morton. 1966. A computer oriented geodetic data base and a new technique in file sequencing. (1966).Google Scholar
32. Patrick Mullen, Fernando De Goes, Mathieu Desbrun, David Cohen-Steiner, and Pierre Alliez. 2010. Signing the unsigned: Robust surface reconstruction from raw pointsets. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1733–1741.Google Scholar
33. Georges Nader, Gael Guennebaud, and Nicolas Mellado. 2014. Adaptive Multi-scale Analysis for Point-based Surface Editing. Computer Graphics Forum 33, 7 (2014), 171–179.Google ScholarDigital Library
34. Yutaka Ohtake, Alexander Belyaev, Marc Alexa, Greg Turk, and Hans-Peter Seidel. 2003. Multi-level partition of unity implicits. Vol. 22.Google Scholar
35. A Cengiz Öztireli, Gael Guennebaud, and Markus Gross. 2009. Feature preserving point set surfaces based on non-linear kernel regression. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 493–501.Google Scholar
36. Daniel Rebain, Baptiste Angles, Julien Valentin, Nicholas Vining, Jiju Peethambaran, Shahram Izadi, and Andrea Tagliasacchi. 2019. LSMAT least squares medial axis transform. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 5–18.Google Scholar
37. Patrick Reuter, Pierre Joyot, Jean Trunzler, Tamy Boubekeur, and Christophe Schlick. 2005. Point set surfaces with sharp features. (03 2005).Google Scholar
38. Brett Ridel, Gael Guennebaud, Patrick Reuter, and Xavier Granier. 2015. Parabolic-cylindrical moving least squares surfaces. Computers and Graphics 51 (June 2015), 60–66.Google Scholar
39. Vladimir Rokhlin. 1985. Rapid solution of integral equations of classical potential theory. Journal of computational physics 60, 2 (1985), 187–207.Google ScholarCross Ref
40. Chun-Xia Xiao. 2011. Multi-Level Partition of Unity Algebraic Point Set Surfaces. J. Comput. Sci. Technol. 26, 2 (March 2011), 229–238.Google ScholarCross Ref
41. Tong Zhao, Pierre Alliez, Tamy Boubekeur, Laurent Busé, and Jean-Marc Thiery. 2021. Progressive Discrete Domains for Implicit Surface Reconstruction. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 143–156.Google Scholar