“Globally Consistent Normal Orientation for Point Clouds by Regularizing the Winding-Number Field” by Xu, Dou, Wang, Xin, Chen, et al. …

  • ©Rui Xu, Zhiyang Dou, Ningna Wang, Shiqing Xin, Shuangmin Chen, Mingyan Jiang, Xiaohu Guo, Wenping Wang, and Changhe Tu

Conference:


Type:


Title:

    Globally Consistent Normal Orientation for Point Clouds by Regularizing the Winding-Number Field

Session/Category Title: Surface Reconstruction

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Estimating normals with globally consistent orientations for a raw point cloud has many downstream geometry processing applications. Despite tremendous efforts in the past decades, it remains challenging to deal with an unoriented point cloud with various imperfections, particularly in the presence of data sparsity coupled with nearby gaps or thin-walled structures. In this paper, we propose a smooth objective function to characterize the requirements of an acceptable winding-number field, which allows one to find the globally consistent normal orientations starting from a set of completely random normals. By taking the vertices of the Voronoi diagram of the point cloud as examination points, we consider the following three requirements: (1) the winding number is either 0 or 1, (2) the occurrences of 1 and the occurrences of 0 are balanced around the point cloud, and (3) the normals align with the outside Voronoi poles as much as possible. Extensive experimental results show that our method outperforms the existing approaches, especially in handling sparse and noisy point clouds, as well as shapes with complex geometry/topology.

References:


    1. Pierre Alliez, David Cohen-Steiner, Yiying Tong, and Mathieu Desbrun. 2007. Voronoi-based variational reconstruction of unoriented point sets. In Proc. of Symp. of Geometry Processing, Vol. 7. 39–48.
    2. Nina Amenta and Marshall Bern. 1998. Surface reconstruction by Voronoi filtering. In Proceedings of the fourteenth annual symposium on Computational geometry. 39–48.
    3. Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. 2001. The power crust. In Proceedings of the sixth ACM symposium on Solid modeling and applications. 249–266.
    4. Samir Aroudj, Patrick Seemann, Fabian Langguth, Stefan Guthe, and Michael Goesele. 2017. Visibility-consistent thin surface reconstruction using multi-scale kernels. ACM Trans. on Graphics 36, 6 (2017), 1–13.
    5. Haim Avron, Andrei Sharf, Chen Greif, and Daniel Cohen-Or. 2010. ℓ1-sparse reconstruction of sharp point set surfaces. ACM Trans. on Graphics 29, 5 (2010), 1–12.
    6. Gavin Barill, Neil G Dickson, Ryan Schmidt, David IW Levin, and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Trans. on Graphics 37, 4 (2018), 1–12.
    7. Yizhak Ben-Shabat and Stephen Gould. 2020. Deepfit: 3d surface fitting via neural network weighted least squares. In ECCV. Springer, 20–34.
    8. Yizhak Ben-Shabat, Michael Lindenbaum, and Anath Fischer. 2019. Nesti-net: Normal estimation for unstructured 3d point clouds using convolutional neural networks. In IEEE CVPR. 10112–10120.
    9. Dobrina Boltcheva and Bruno Lévy. 2017. Surface reconstruction by computing restricted Voronoi cells in parallel. Computer-Aided Design 90 (2017), 123–134.
    10. Frédéric Cazals and Marc Pouget. 2005. Estimating differential quantities using polynomial fitting of osculating jets. Comp. Aided Geom. Design 22, 2 (2005), 121–146.
    11. Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. 2015. Shapenet: An information-rich 3d model repository. arXiv preprint arXiv:1512.03012 (2015).
    12. Cheng Chi and Shuran Song. 2021. GarmentNets: Category-Level Pose Estimation for Garments via Canonical Space Shape Completion. In IEEE ICCV. 3324–3333.
    13. Tamal K Dey and Samrat Goswami. 2004. Provable surface reconstruction from noisy samples. In Proceedings of the twentieth annual symposium on Computational Geometry. 330–339.
    14. Tamal K Dey, Gang Li, and Jian Sun. 2005. Normal estimation for point clouds: A comparison study for a Voronoi based method. In Proceedings Eurographics/IEEE VGTC Symposium Point-Based Graphics, 2005. IEEE, 39–46.
    15. Zhiyang Dou, Cheng Lin, Rui Xu, Lei Yang, Shiqing Xin, Taku Komura, and Wenping Wang. 2022. Coverage Axis: Inner Point Selection for 3D Shape Skeletonization. In Computer Graphics Forum, Vol. 41. Wiley Online Library, 419–432.
    16. Eleonora Grilli, Fabio Menna, and Fabio Remondino. 2017. A review of point clouds segmentation and classification algorithms. The International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences 42 (2017), 339.
    17. Cindy Grimm and William D Smart. 2011. Shape classification and normal estimation for non-uniformly sampled, noisy point data. Computers & Graphics 35, 4 (2011), 904–915.
    18. Paul Guerrero, Yanir Kleiman, Maks Ovsjanikov, and Niloy J Mitra. 2018. Pcpnet learning local shape properties from raw point clouds. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 75–85.
    19. Godfrey Harold Hardy, John Edensor Littlewood, George Pólya, György Pólya, et al. 1952. Inequalities. Cambridge university press.
    20. Taisuke Hashimoto and Masaki Saito. 2019. Normal Estimation for Accurate 3D Mesh Reconstruction with Point Cloud Model Incorporating Spatial Structure.. In CVPR workshops, Vol. 1.
    21. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1992. Surface reconstruction from unorganized points. In Proc. ACM SIGGRAPH. 71–78.
    22. Fei Hou, Chiyu Wang, Wencheng Wang, Hong Qin, Chen Qian, and Ying He. 2022. Iterative Poisson surface reconstruction (iPSR) for unoriented points. ACM Trans. on Graphics (Proc. SIGGRAPH) (2022).
    23. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast tetrahedral meshing in the wild. ACM Transactions on Graphics (TOG) 39, 4 (2020), 117–1.
    24. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. on Graphics (2018).
    25. Zhiyang Huang, Nathan Carr, and Tao Ju. 2019. Variational implicit point set surfaces. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–13.
    26. Zhangjin Huang, Yuxin Wen, Zihao Wang, Jinjuan Ren, and Kui Jia. 2022. Surface Reconstruction from Point Clouds: A Survey and a Benchmark. arXiv preprint arXiv:2205.02413 (2022).
    27. Alec Jacobson et al. 2021. gptoolbox: Geometry Processing Toolbox. http://github.com/alecjacobson/gptoolbox.
    28. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. on Graphics 32, 4 (2013), 1–12.
    29. Johannes Jakob, Christoph Buchenau, and Michael Guthe. 2019. Parallel globally consistent normal orientation of raw unorganized point clouds. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 163–173.
    30. V Jelic and F Marsiglio. 2012. The double-well potential in quantum mechanics: a simple, numerically exact formulation. European Journal of Physics 33, 6 (2012), 1651.
    31. Michael Kazhdan. 2005. Reconstruction of solid models from oriented point sets. In Eurographics Symposium on Geometry Processing. 73–es.
    32. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Eurographics Symposium on Geometry Processing, Vol. 7.
    33. Michael Kazhdan and Hugues Hoppe. 2013. Screened poisson surface reconstruction. ACM Trans. on Graphics 32, 3 (2013), 1–13.
    34. Ravikrishna Kolluri, Jonathan Richard Shewchuk, and James F O’Brien. 2004. Spectral surface reconstruction from noisy point clouds. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing. 11–21.
    35. Sören König and Stefan Gumhold. 2009. Consistent Propagation of Normal Orientations in Point Clouds. In VMV. 83–92.
    36. Jan Eric Lenssen, Christian Osendorfer, and Jonathan Masci. 2020. Deep iterative surface normal estimation. In IEEE CVPR. 11247–11256.
    37. David Levin. 1998. The approximation power of moving least-squares. Mathematics of computation 67, 224 (1998), 1517–1531.
    38. David Levin. 2004. Mesh-independent surface interpolation. In Geometric modeling for scientific visualization. Springer, 37–49.
    39. Bao Li, Ruwen Schnabel, Reinhard Klein, Zhiquan Cheng, Gang Dang, and Shiyao Jin. 2010. Robust normal estimation for point clouds with sharp features. Computers & Graphics 34, 2 (2010), 94–106.
    40. Shujuan Li, Junsheng Zhou, Baorui Ma, Yu-Shen Liu, and Zhizhong Han. 2022. NeAF: Learning Neural Angle Fields for Point Normal Estimation. arXiv preprint arXiv:2211.16869 (2022).
    41. Siyou Lin, Dong Xiao, Zuoqiang Shi, and Bin Wang. 2022. Surface Reconstruction from Point Clouds without Normals by Parametrizing the Gauss Formula. ACM Trans. on Graphics 42, 2 (2022), 19 pages.
    42. Xiuping Liu, Jie Zhang, Junjie Cao, Bo Li, and Ligang Liu. 2015. Quality point cloud normal estimation by guided least squares representation. Computers & Graphics 51 (2015), 106–116.
    43. Albrecht Ludwig Friedrich Meister. 1769. Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus.
    44. Quentin Mérigot, Maks Ovsjanikov, and Leonidas J Guibas. 2010. Voronoi-based curvature and feature estimation from point clouds. IEEE Trans. on Vis. and Comp. Graphics 17, 6 (2010), 743–756.
    45. Gal Metzer, Rana Hanocka, Denis Zorin, Raja Giryes, Daniele Panozzo, and Daniel Cohen-Or. 2021. Orienting Point Clouds with Dipole Propagation. ACM Trans. on Graphics 40, 4, Article 165 (jul 2021), 14 pages.
    46. Niloy J Mitra and An Nguyen. 2003. Estimating surface normals in noisy point cloud data. In special issue of International Journal of Computational Geometry and Applications. 322–328.
    47. Stefano Nuvoli, Nico Pietroni, Paolo Cignoni, Riccardo Scateni, and Marco Tarini. 2022. SkinMixer: Blending 3D Animated Models. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–15.
    48. Daoshan OuYang and Hsi-Yung Feng. 2005. On the normal vector estimation for point cloud data from smooth surfaces. Computer-Aided Design 37, 10 (2005), 1071–1079.
    49. Mark Pauly, Richard Keiser, Leif P Kobbelt, and Markus Gross. 2003. Shape modeling with point-sampled geometry. ACM Trans. on Graphics 22, 3 (2003), 641–650.
    50. François Pomerleau, Francis Colas, Roland Siegwart, et al. 2015. A review of point cloud registration algorithms for mobile robotics. Foundations and Trends® in Robotics 4, 1 (2015), 1–104.
    51. Silvia Sellán, Noam Aigerman, and Alec Jacobson. 2021. Swept volumes via spacetime numerical continuation. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–11.
    52. Silvia Sellán and Alec Jacobson. 2022. Stochastic Poisson Surface Reconstruction. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–12.
    53. Yujing Sun, Scott Schaefer, and Wenping Wang. 2015. Denoising point sets via L0 minimization. Comp. Aided Geom. Design 35 (2015), 2–15.
    54. Jun Wang, Zhouwang Yang, and Falai Chen. 2012. A variational model for normal computation of point clouds. The Visual Computer 28, 2 (2012), 163–174.
    55. Ningna Wang, Bin Wang, Wenping Wang, and Xiaohu Guo. 2022a. Computing Medial Axis Transform with Feature Preservation via Restricted Power Diagram. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–18.
    56. Pengfei Wang, Zixiong Wang, Shiqing Xin, Xifeng Gao, Wenping Wang, and Changhe Tu. 2022b. Restricted Delaunay Triangulation for Explicit Surface Reconstruction. ACM Transactions on Graphics (TOG) (2022).
    57. Zixiong Wang, Pengfei Wang, Qiujie Dong, Junjie Gao, Shuangmin Chen, Shiqing Xin, and Changhe Tu. 2021. Neural-IMLS: Learning Implicit Moving Least-Squares for Surface Reconstruction from Unoriented Point clouds. arXiv preprint arXiv:2109.04398 (2021).
    58. Hui Xie, Kevin T McDonnell, and Hong Qin. 2004. Surface reconstruction of noisy and defective data sets. In IEEE visualization 2004. IEEE, 259–266.
    59. Rui Xu, Zixiong Wang, Zhiyang Dou, Chen Zong, Shiqing Xin, Mingyan Jiang, Tao Ju, and Changhe Tu. 2022. RFEPS: Reconstructing Feature-Line Equipped Polygonal Surface. ACM Trans. on Graphics (Proc. SIGGRAPH Asia) 41, 6 (2022), 1–15.
    60. Mincheol Yoon, Yunjin Lee, Seungyong Lee, Ioannis Ivrissimtzis, and Hans-Peter Seidel. 2007. Surface and normal ensembles for surface reconstruction. Computer-Aided Design 39, 5 (2007), 408–420.
    61. Brayan S Zapata-Impata, Pablo Gil, Jorge Pomares, and Fernando Torres. 2019. Fast geometry-based computation of grasping points on three-dimensional point clouds. International Journal of Advanced Robotic Systems 16, 1 (2019), 1729881419831846.
    62. Jie Zhang, Junjie Cao, Xiuping Liu, He Chen, Bo Li, and Ligang Liu. 2018. Multi-normal estimation via pair consistency voting. IEEE Trans. on Vis. and Comp. Graphics 25, 4 (2018), 1693–1706.
    63. Jie Zhang, Junjie Cao, Xiuping Liu, Jun Wang, Jian Liu, and Xiquan Shi. 2013. Point cloud normal estimation via low-rank subspace clustering. Computers & Graphics 37, 6 (2013), 697–706.
    64. Jun Zhou, Hua Huang, Bin Liu, and Xiuping Liu. 2020. Normal estimation for 3d point clouds via local plane constraint and multi-scale selection. Computer-Aided Design 129 (2020), 102916.
    65. Runsong Zhu, Yuan Liu, Zhen Dong, Yuan Wang, Tengping Jiang, Wenping Wang, and Bisheng Yang. 2021. AdaFit: Rethinking Learning-based Normal Estimation on Point Clouds. In IEEE ICCV. 6118–6127.

ACM Digital Library Publication:


Overview Page: