“Variational implicit point set surfaces” by Huang, Carr and Ju
Conference:
Type:
Title:
- Variational implicit point set surfaces
Session/Category Title: Sound Graphics
Presenter(s)/Author(s):
Abstract:
We propose a new method for reconstructing an implicit surface from an un-oriented point set. While existing methods often involve non-trivial heuristics and require additional constraints, such as normals or labelled points, we introduce a direct definition of the function from the points as the solution to a constrained quadratic optimization problem. The definition has a number of appealing features: it uses a single parameter (parameter-free for exact interpolation), applies to any dimensions, commutes with similarity transformations, and can be easily implemented without discretizing the space. More importantly, the use of a global smoothness energy allows our definition to be much more resilient to sampling imperfections than existing methods, making it particularly suited for sparse and non-uniform inputs.
References:
1. Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin, and Claudio T Silva. 2003. Computing and rendering point set surfaces. IEEE Transactions on visualization and computer graphics 9, 1 (2003), 3–15. Google ScholarDigital Library
2. P. Alliez, D. Cohen-Steiner, Y. Tong, and M. Desbrun. 2007. Voronoi-based Variational Reconstruction of Unoriented Point Sets. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (SGP ’07). 39–48. Google ScholarDigital Library
3. Nina Amenta and Marshall Bern. 1999. Surface reconstruction by Voronoi filtering. Discrete & Computational Geometry 22, 4 (1999), 481–504.Google ScholarCross Ref
4. Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. 2001. The power crust. In Proceedings of the sixth ACM symposium on Solid modeling and applications. ACM, 249–266. Google ScholarDigital Library
5. Nina Amenta and Yong Joo Kil. 2004. Defining point-set surfaces. ACM Transactions on Graphics (TOG) 23, 3 (2004), 264–270. Google ScholarDigital Library
6. Gavin Barill, Neil G Dickson, Ryan Schmidt, David IW Levin, and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Transactions on Graphics (TOG) 37, 4 (2018), 43. Google ScholarDigital Library
7. 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. Computer Graphics Forum 36, 1 (2017), 301–329. Google ScholarDigital Library
8. Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Cláudio Silva, and Gabriel Taubin. 1999. The ball-pivoting algorithm for surface reconstruction. IEEE transactions on visualization and computer graphics 5, 4 (1999), 349–359. Google ScholarDigital Library
9. Mikhail Bessmeltsev, Caoyu Wang, Alla Sheffer, and Karan Singh. 2012. Design-driven quadrangulation of closed 3D curves. ACM Transactions on Graphics (TOG) 31, 6 (2012), 178. Google ScholarDigital Library
10. Jules Bloomenthal. 1994. Graphics Gems IV. Chapter An Implicit Surface Polygonizer, 324–349. Google ScholarDigital Library
11. Jean-Daniel Boissonnat and Frédéric Cazals. 2002. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Computational Geometry 22, 1–3 (2002), 185–203. Google ScholarDigital Library
12. Jean-Daniel Boissonnat and Steve Oudot. 2005. Provably Good Sampling and Meshing of Surfaces. Graph. Models 67, 5 (Sept. 2005), 405–451. Google ScholarDigital Library
13. Alexandre Boulch and Renaud Marlet. 2012. Fast and Robust Normal Estimation for Point Clouds with Sharp Features. Computer Graphics Forum (2012). Google ScholarDigital Library
14. Alexandre Boulch and Renaud Marlet. 2016. Deep Learning for Robust Normal Estimation in Unstructured Point Clouds. Computer Graphics Forum (2016).Google Scholar
15. E Brazil, Ives Macedo, M Costa Sousa, Luiz Henrique de Figueiredo, and Luiz Velho. 2010. Sketching variational hermite-rbf implicits. In Proceedings of the Seventh Sketch-Based Interfaces and Modeling Symposium. Eurographics Association, 1–8. Google ScholarDigital Library
16. Martin D Buhmann. 2003. Radial basis functions: theory and implementations. Vol. 12. Cambridge university press. Google ScholarDigital Library
17. Jonathan C Carr, Richard K Beatson, Jon B Cherrie, Tim J Mitchell, W Richard Fright, Bruce C McCallum, and Tim R Evans. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. ACM, 67–76. Google ScholarDigital Library
18. F. Cazals and M. Pouget. 2003. Estimating Differential Quantities Using Polynomial Fitting of Osculating Jets. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’03). 177–187. Google ScholarDigital Library
19. Massimiliano Corsini, Paolo Cignoni, and Roberto Scopigno. 2012. Efficient and flexible sampling with blue noise properties of triangular meshes. IEEE Transactions on Visualization and Computer Graphics 18, 6 (2012), 914–924. Google ScholarDigital Library
20. Tamal K Dey. 2006. Curve and surface reconstruction: algorithms with mathematical analysis. Vol. 23. Cambridge University Press. Google ScholarDigital Library
21. Tamal K Dey and Samrat Goswami. 2003. Tight cocone: a water-tight surface reconstructor. Journal of Computing and Information Science in Engineering 3, 4 (2003), 302–307.Google ScholarCross Ref
22. Tamal K. Dey and Samrat Goswami. 2004. Provable surface reconstruction from noisy samples. In Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8–11, 2004. 330–339. Google ScholarDigital Library
23. 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
24. Huong Quynh Dinh, Greg Turk, and Greg Slabaugh. 2002. Reconstructing surfaces by volumetric regularization using radial basis functions. IEEE transactions on pattern analysis and machine intelligence 24, 10 (2002), 1358–1371. Google ScholarDigital Library
25. Petros Drineas and Michael W. Mahoney. 2005. On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning. J. Mach. Learn. Res. 6 (Dec. 2005), 2153–2175. Google ScholarDigital Library
26. Jean Duchon. 1977. Splines minimizing rotation-invariant semi-norms in Sobolev spaces. In Constructive theory of functions of several variables. Springer, 85–100.Google Scholar
27. Simon Giraudot, David Cohen-Steiner, and Pierre Alliez. 2013. Noise-adaptive shape reconstruction from raw point sets. In Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing. Eurographics Association, 229–238. Google ScholarDigital Library
28. Gaël Guennebaud and Markus Gross. 2007. Algebraic point set surfaces. ACM Transactions on Graphics (TOG) 26, 3 (2007), 23. Google ScholarDigital Library
29. Paul Guerrero, Yanir Kleiman, Maks Ovsjanikov, and Niloy J. Mitra. 2018. PCPNet: Learning Local Shape Properties from Raw Point Clouds. Computer Graphics Forum 37, 2 (2018), 75–85.Google ScholarCross Ref
30. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1992. Surface reconstruction from unorganized points. Vol. 26. ACM. Google ScholarDigital Library
31. Alexander Hornung and Leif Kobbelt. 2006. Robust reconstruction of watertight 3 d models from non-uniformly sampled point clouds without normal information. In Symposium on geometry processing. Citeseer, 41–50. Google ScholarDigital Library
32. Hui Huang, Dan Li, Hao Zhang, Uri Ascher, and Daniel Cohen-Or. 2009. Consolidation of Unorganized Point Clouds for Surface Reconstruction. ACM Trans. Graph. 28, 5, Article 176 (Dec. 2009), 176:1–176:7 pages. Google ScholarDigital Library
33. Zhiyang Huang and Tao Ju. 2016. Extrinsically Smooth Direction Fields. Comput. Graph. 58, C (Aug. 2016), 109–117. Google ScholarDigital Library
34. Takashi Ijiri, Shin Yoshizawa, Yu Sato, Masaaki Ito, and Hideo Yokota. 2013. Bilateral Hermite Radial Basis Functions for Contour-based Volume Segmentation. Computer Graphics Forum 32, 2 (2013), 123–132. Proc. of EUROGRAPHICS’13.Google ScholarCross Ref
35. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson Surface Reconstruction. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing (SGP ’06). 61–70. Google ScholarDigital Library
36. Michael Kazhdan and Hugues Hoppe. 2013. Screened poisson surface reconstruction. ACM Transactions on Graphics (ToG) 32, 3 (2013), 29. Google ScholarDigital Library
37. Ravikrishna Kolluri. 2008. Provably good moving least squares. ACM Transactions on Algorithms (TALG) 4, 2 (2008), 18. Google ScholarDigital Library
38. Sören König and Stefan Gumhold. 2009. Consistent Propagation of Normal Orientations in Point Clouds. In VMV.Google Scholar
39. Bao Li, Ruwen Schnabel, Reinhard Klein, Zhiquan Cheng, Gang Dang, and Jin Shiyao. 2010. Robust normal estimation for point clouds with sharp features. Computers & Graphics 34, 2 (2010), 94–106. Google ScholarDigital Library
40. Shengjun Liu, Charlie C.L. Wang, Guido Brunnett, and Jun Wang. 2016. A Closed-form Formulation of HRBF-based Surface Reconstruction by Approximate Solution. Comput. Aided Des. 78, C (Sept. 2016), 147–157. Google ScholarDigital Library
41. Xiuping Liu, Jie Zhang, Junjie Cao, Bo Li, and Ligang Liu. 2015. Quality Point Cloud Normal Estimation by Guided Least Squares Representation. Comput. Graph. 51, C (Oct. 2015), 106–116. Google ScholarDigital Library
42. DanFeng Lu, HongKai Zhao, Ming Jiang, ShuLin Zhou, and Tie Zhou. 2005. A surface reconstruction method for highly noisy point clouds. In International Workshop on Variational, Geometric, and Level Set Methods in Computer Vision. Springer, 283–294. Google ScholarDigital Library
43. Wenjia Lu, Zuoqiang Shi, Jian Sun, and Bin Wang. 2018. Surface Reconstruction Based on the Modified Gauss Formula. ACM Trans. Graph. 38, 1, Article 2 (Dec. 2018), 18 pages. Google ScholarDigital Library
44. Josiah Manson, Guergana Petrova, and Scott Schaefer. 2008. Streaming surface reconstruction using wavelets. Computer Graphics Forum 27, 5 (2008), 1411–1420. Google ScholarDigital Library
45. Quentin Merigot, Maks Ovsjanikov, and Leonidas J. Guibas. 2011. Voronoi-Based Curvature and Feature Estimation from Point Clouds. IEEE Transactions on Visualization and Computer Graphics 17, 6 (June 2011), 743–756. Google ScholarDigital Library
46. N. J. Mitra, A. Nguyen, and L. Guibas. 2004. Estimating Surface Normals in Noisy Point Cloud Data. In special issue of International Journal of Computational Geometry and Applications, Vol. 14. 261–276.Google Scholar
47. B. S. Morse, T. S. Yoo, P. Rheingans, D. T. Chen, and K. R. Subramanian. 2001. Interpolating implicit surfaces from scattered surface data using compactly supported radial basis functions. In Proceedings International Conference on Shape Modeling and Applications. 89–98. Google ScholarDigital Library
48. Patrick Mullen, Fernando De Goes, Mathieu Desbrun, David Cohen-Steiner, and Pierre Alliez. 2010. Signing the unsigned: Robust surface reconstruction from raw pointsets. Computer Graphics Forum 29, 5 (2010), 1733–1741.Google ScholarCross Ref
49. Yutaka Ohtake, Alexander Belyaev, Marc Alexa, Greg Turk, and Hans-Peter Seidel. 2003a. Multi-level partition of unity implicits. In ACM Transactions on Graphics (TOG), Vol. 22. ACM, 463–470. Google ScholarDigital Library
50. Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel. 2003b. A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions. In Shape Modeling International, 2003. IEEE, 153–161. Google ScholarDigital Library
51. A Cengiz Öztireli, Gael Guennebaud, and Markus Gross. 2009. Feature preserving point set surfaces based on non-linear kernel regression. Computer Graphics Forum 28, 2 (2009), 493–501.Google ScholarCross Ref
52. Hao Pan, Yang Liu, Alla Sheffer, Nicholas Vining, Changjian Li, and Wenping Wang. 2015. Flow Aligned Surfacing of Curve Networks. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015). Google ScholarDigital Library
53. Rongjiang Pan and Vaclav Skala. 2012. Surface Reconstruction with higher-order smoothness. The Visual Computer 28, 2 (2012), 155–162. Google ScholarDigital Library
54. Mark Pauly, Richard Keiser, Leif P. Kobbelt, and Markus Gross. 2003. Shape Modeling with Point-sampled Geometry. ACM Trans. Graph. 22, 3 (July 2003), 641–650. Google ScholarDigital Library
55. Roi Poranne, Craig Gotsman, and Daniel Keren. 2010. 3D surface reconstruction using a generalized distance function. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 2479–2491.Google Scholar
56. Vaughan Pratt. 1987. Direct Least-squares Fitting of Algebraic Surfaces. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’87). 145–152. Google ScholarDigital Library
57. M. Samozino, M. Alexa, P. Alliez, and M. Yvinec. 2006. Reconstruction with Voronoi Centered Radial Basis Functions. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing. 51–60. Google ScholarDigital Library
58. Nico Schertler, Bogdan Savchynskyy, and Stefan Gumhold. 2017. Towards Globally Optimal Normal Orientations for Large Point Clouds. Comput. Graph. Forum 36, 1 (Jan. 2017), 197–208. Google ScholarDigital Library
59. Bernhard Schölkopf, Joachim Giesen, and Simon Spalinger. 2004. Kernel Methods for Implicit Surface Modeling. In Proceedings of the 17th International Conference on Neural Information Processing Systems (NIPS’04). 1193–1200. Google ScholarDigital Library
60. Chen Shen, James F. O’Brien, and Jonathan R. Shewchuk. 2004. Interpolating and Approximating Implicit Surfaces from Polygon Soup. ACM Trans. Graph. 23, 3 (Aug. 2004), 896–904. Google ScholarDigital Library
61. Alex J. Smola and Bernhard Schökopf. 2000. Sparse Greedy Matrix Approximation for Machine Learning. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML ’00). 911–918. Google ScholarDigital Library
62. Tibor Stanko, Stefanie Hahmann, Georges-Pierre Bonneau, and Nathalie Saguin-Sprynski. 2016. Surfacing curve networks with normal control. Computers & Graphics 60 (2016), 1–8. Google ScholarDigital Library
63. Gabriel Taubin. 2012. Smooth signed distance surface reconstruction and applications. In Iberoamerican Congress on Pattern Recognition. Springer, 38–45.Google ScholarCross Ref
64. Greg Turk and James F. O’Brien. 2002. Modelling with Implicit Surfaces That Interpolate. ACM Trans. Graph. 21, 4 (Oct. 2002), 855–873. Google ScholarDigital Library
65. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional field synthesis, design, and processing. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 545–572.Google Scholar
66. C. Walder, O. Chapelle, and B. Schölkopf. 2005. Implicit Surface Modelling as an Eigenvalue Problem. In Proceedings of the 22nd International Conference on Machine Learning. ACM, 937–944. Google ScholarDigital Library
67. Christian Walder, Olivier Chapelle, and Bernhard Schölkopf. 2007. Implicit surfaces with globally regularised and compactly supported basis functions. In Advances in Neural Information Processing Systems. 273–280. Google ScholarDigital Library
68. Jun Wang, Zhouwang Yang, and Falai Chen. 2011. A variational model for normal computation of point clouds. The Visual Computer 28 (2011), 163–174. Google ScholarDigital Library
69. Holger Wendland. 2004. Scattered data approximation. Vol. 17. Cambridge university press.Google Scholar
70. Hui Xie, Jianning Wang, Jing Hua, Hong Qin, and Arie E. Kaufman. 2003. Piecewise C1 Continuous Surface Reconstruction of Noisy Point Cloud via Local Implicit Quadric Regression. In 14th IEEE Visualization 2003 Conference, VIS 2003, Seattle, WA, USA, October 19–24, 2003. 91–98. Google ScholarDigital Library
71. Hong-Kai Zhao, Stanley Osher, and Ronald Fedkiw. 2001. Fast surface reconstruction using the level set method. In Proceedings IEEE Workshop on Variational and Level Set Methods in Computer Vision. IEEE, 194–201. Google ScholarDigital Library
