“A Linear Method to Consistently Orient Normals of a 3D Point Cloud” – ACM SIGGRAPH HISTORY ARCHIVES

“A Linear Method to Consistently Orient Normals of a 3D Point Cloud”

  • ©

Conference:


Type(s):


Title:

    A Linear Method to Consistently Orient Normals of a 3D Point Cloud

Presenter(s)/Author(s):



Abstract:


    Consistently orienting the normals of a point cloud is vital for subsequent geometry processing. We use Stokes’ theorem to turn this problem into finding the least-squares solution of a sparse linear system. Our method successfully orients normals computed locally from a point cloud and is considerably faster than state-of-the-art methods.

References:


    [1]
    Fr?d?ric Cazals and Marc Pouget. 2005. Estimating differential quantities using polynomial fitting of osculating jets. Computer Aided Geometric Design 22, 2 (Feb. 2005), 121?146. https://doi.org/10.1016/j.cagd.2004.09.004

    [2]
    Susan Jane Colley. 2012. Vector Calculus (4th ed.). Pearson, Boston.

    [3]
    Chaojing Duan, Siheng Chen, and Jelena Kovacevic. 2018. Weighted multi-projection: 3D point cloud denoising with tangent planes. In Proceedings of the 6th Global Conference on Signal and Information Processing(GlobalSIP 2018), Dinei Florencio, Amy Reibman, and Lee Swindlehurst (Eds.). IEEE, Piscataway, 725?729. https://doi.org/10.1109/GlobalSIP.2018.8646331

    [4]
    Lawrence C. Evans. 2010. Partial Differential Equations (2nd ed.). Graduate Studies in Mathematics, Vol. 19. American Mathematical Society, Providence.

    [5]
    Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1992. Surface reconstruction from unorganized points. ACM SIGGRAPH Computer Graphics 26, 2 (July 1992), 71?78. https://doi.org/10.1145/133994.134011

    [6]
    Johannes Jakob, Christoph Buchenau, and Michael Guthe. 2019. Parallel globally consistent normal orientation of raw unorganized point clouds. Computer Graphics Forum 38, 5 (Aug. 2019), 163?173. https://doi.org/10.1111/cgf.13797

    [7]
    Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Proceedings of the 4th Symposium on Geometry Processing(SGP ?06), Alla Sheffer and Konrad Polthier (Eds.). Eurographics, Aire-la-Ville, 61?70. https://doi.org/10.2312/SGP/SGP06/061-070

    [8]
    Michael Kazhdan and Hugues Hoppe. 2013. Screened Poisson surface reconstruction. ACM Transactions on Graphics 32, 3, Article 29 (July 2013), 13 pages. https://doi.org/10.1145/2487228.2487237

    [9]
    S?ren K?nig and Stefan Gumhold. 2009. Consistent propagation of normal orientations in point clouds. In Proceedings of Vision, Modeling, and Visualization 2009(VMV ?09), Marcus Magnor, Bodo Rosenhahn, and Holger Theisel (Eds.). Otto-von-Guericke-Universit?t, Magdeburg, 83?92.

    [10]
    Siyou Lin, Dong Xiao, Zuoqiang Shi, and Bin Wang. 2023. Surface reconstruction from point clouds without normals by parametrizing the Gauss formula. ACM Transactions on Graphics 42, 2, Article 14 (April 2023), 19 pages. https://doi.org/10.1145/3554730

    [11]
    Wenjia Lu, Zuoqiang Shi, Jian Sun, and Bin Wang. 2019. Surface reconstruction based on the modified Gauss formula. ACM Transactions on Graphics 38, 1, Article 2 (Feb. 2019), 18 pages. https://doi.org/10.1145/3233984

    [12]
    Jonas Lundgren. 2019. TSPSEARCH ? Heuristic method for Traveling Salesman Problem (TSP). MATLAB Central File Exchange. Retrieved November 29, 2023 from https://www.mathworks.com/matlabcentral/fileexchange/71226-tspsearch

    [13]
    Gal Metzer, Rana Hanocka, Denis Zorin, Raja Giryes, Daniele Panozzo, and Daniel Cohen-Or. 2021. Orienting point clouds with dipole propagation. ACM Transactions on Graphics 40, 4, Article 165 (Aug. 2021), 14 pages. https://doi.org/10.1145/3450626.3459835

    [14]
    Niloy J. Mitra, An Nguyen, and Leonidas Guibas. 2004. Estimating surface normals in noisy point cloud data. International Journal of Computational Geometry & Applications 14, 4 & 5 (Oct. 2004), 261?276. https://doi.org/10.1142/S0218195904001470

    [15]
    Peter J. Olver. 1983. Conservation laws and null divergences. Mathematical Proceedings of the Cambridge Philosophical Society 94, 3 (Nov. 1983), 529?540. https://doi.org/10.1017/S030500410000092X

    [16]
    Julia Sanchez, Florence Denis, David Coeurjolly, Florent Dupont, Laurent Trassoudaine, and Paul Checchin. 2020. Robust normal vector estimation in 3D point clouds through iterative principal component analysis. ISPRS Journal of Photogrammetry and Remote Sensing 163 (May 2020), 18?35. https://doi.org/10.1016/j.isprsjprs.2020.02.018

    [17]
    Nico Schertler, Bogdan Savchynskyy, and Stefan Gumhold. 2017. Towards globally optimal normal orientations for large point clouds. Computer Graphics Forum 36, 1 (Jan. 2017), 197?208. https://doi.org/10.1111/cgf.12795

    [18]
    Rui Xu, Zhiyang Dou, Ningna Wang, Shiqing Xin, Shuangmin Chen, Mingyan Jiang, Xiaohu Guo, Wenping Wang, and Changhe Tu. 2023. Globally consistent normal orientation for point clouds by regularizing the winding-number field. ACM Transactions on Graphics 42, 4, Article 111 (July 2023), 15 pages. https://doi.org/10.1145/3592129 ? The GCNO source code is available at https://github.com/Xrvitd/GCNO.


ACM Digital Library Publication:



Overview Page:



Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org