More Web Proxy on the site http://driver.im/

research-article

Public Access

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

Authors:

Shuangmin Chen,

Changhe TuAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 42, Issue 4

Article No.: 111, Pages 1 - 15

https://doi.org/10.1145/3592129

Published: 26 July 2023 Publication History

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.

Supplementary Material

ZIP File (papers_322-supplemental.zip)

supplemental material.

Download
18.94 MB

MP4 File (papers_322_VOD.mp4)

presentation

Download
538.43 MB

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[52]

Silvia Sellán and Alec Jacobson. 2022. Stochastic Poisson Surface Reconstruction. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1--12.

Digital Library

[53]

Yujing Sun, Scott Schaefer, and Wenping Wang. 2015. Denoising point sets via L0 minimization. Comp. Aided Geom. Design 35 (2015), 2--15.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Cited By

Chen TCao RLi ZZang YSun L(2024)Deep3DSketch-im: rapid high-fidelity AI 3D model generation by single freehand sketchesDeep3DSketch-im:基于人工智能从单个手绘草图快速生成高保真三维模型Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.230031425:1(149-159)Online publication date: 8-Feb-2024
https://doi.org/10.1631/FITEE.2300314
Chen HMiller BGkioulekas I(2024)3D Reconstruction with Fast Dipole SumsACM Transactions on Graphics10.1145/368791443:6(1-19)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687914
Lin SShi ZLiu Y(2024)Fast and Globally Consistent Normal Orientation based on the Winding Number Normal ConsistencyACM Transactions on Graphics10.1145/368789543:6(1-19)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687895
Show More Cited By

Index Terms

Globally Consistent Normal Orientation for Point Clouds by Regularizing the Winding-Number Field
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Point-based models

Recommendations

Fast and Globally Consistent Normal Orientation based on the Winding Number Normal Consistency

Estimating consistently oriented normals for point clouds enables a number of important applications in computer graphics such as surface reconstruction. While local normal estimation is possible with simple techniques like principal component analysis (...
Mendable consistent orientation of point clouds

Consistent normal orientation is challenging in the presence of noise, non-uniformities and thin sharp features. None of any existing local or global methods is capable of orienting all point cloud models consistently, and none of them offers a mechanism ...
Robust inside-outside segmentation using generalized winding numbers

Solid shapes in computer graphics are often represented with boundary descriptions, e.g. triangle meshes, but animation, physically-based simulation, and geometry processing are more realistic and accurate when explicit volume representations are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 42, Issue 4

August 2023

1912 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3609020

Issue’s Table of Contents

Copyright © 2023 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 the author(s) 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: 26 July 2023

Published in TOG Volume 42, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Key R&D Program of China
National Natural Science Foundation of China
Natural Science Foundation of Shandong Province
National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
860
Total Downloads

Downloads (Last 12 months)618
Downloads (Last 6 weeks)102

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen TCao RLi ZZang YSun L(2024)Deep3DSketch-im: rapid high-fidelity AI 3D model generation by single freehand sketchesDeep3DSketch-im:基于人工智能从单个手绘草图快速生成高保真三维模型Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.230031425:1(149-159)Online publication date: 8-Feb-2024
https://doi.org/10.1631/FITEE.2300314
Chen HMiller BGkioulekas I(2024)3D Reconstruction with Fast Dipole SumsACM Transactions on Graphics10.1145/368791443:6(1-19)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687914
Lin SShi ZLiu Y(2024)Fast and Globally Consistent Normal Orientation based on the Winding Number Normal ConsistencyACM Transactions on Graphics10.1145/368789543:6(1-19)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687895
Sun HWang JBao HHuang J(2024)GauWN: Gaussian-smoothed Winding Number and its DerivativesSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687569(1-9)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3680528.3687569
Xu ZLamba HAi QTetreault JJaimes AOosterhuis HBast HXiong C(2024)CFE2: Counterfactual Editing for Search Result ExplanationProceedings of the 2024 ACM SIGIR International Conference on Theory of Information Retrieval10.1145/3664190.3672508(145-155)Online publication date: 2-Aug-2024
https://dl.acm.org/doi/10.1145/3664190.3672508
Zhang LWang ZZhang QQiu QPang AJiang HYang WXu LYu J(2024)CLAY: A Controllable Large-scale Generative Model for Creating High-quality 3D AssetsACM Transactions on Graphics10.1145/365814643:4(1-20)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658146
Liu WWang XZhao HXue XWu ZLu XHe Y(2024)Consistent Point Orientation for Manifold Surfaces via Boundary IntegrationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657475(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657475
Gotsman CHormann K(2024)A Linear Method to Consistently Orient Normals of a 3D Point CloudACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657429(1-10)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657429
Scrivener DColdren EChien E(2024)Winding Number Features for Vector Sketch ColorizationComputer Graphics Forum10.1111/cgf.1514143:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15141
Li QFeng HShi KGao YFang YLiu YHan Z(2024)Learning Signed Hyper Surfaces for Oriented Point Cloud Normal EstimationIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.343122146:12(9957-9974)Online publication date: Dec-2024
https://doi.org/10.1109/TPAMI.2024.3431221
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents