“Variational Shape Reconstruction via Quadric Error Metrics” by Zhao, Busé, Cohen-Steiner, Boubekeur, Thiery, et al. …

  • ©Tong Zhao, Laurent Busé, David Cohen-Steiner, Tamy Boubekeur, Jean-Marc Thiery, and Pierre Alliez




    Variational Shape Reconstruction via Quadric Error Metrics

Session/Category Title: Surface Reconstruction




    Inspired by the strengths of quadric error metrics initially designed for mesh decimation, we propose a concise mesh reconstruction approach for 3D point clouds. Our approach proceeds by clustering the input points enriched with quadric error metrics, where the generator of each cluster is the optimal 3D point for the sum of its quadric error metrics. This approach favors the placement of generators on sharp features, and tends to equidistribute the error among clusters. We reconstruct the output surface mesh from the adjacency between clusters and a constrained binary solver. We combine our clustering process with an adaptive refinement driven by the error. Compared to prior art, our method avoids dense reconstruction prior to simplification and produces immediately an optimized mesh.


    1. Marco Attene, Bianca Falcidieno, Jarek Rossignac, and Michela Spagnuolo. 2003. Edge-Sharpener: Recovering sharp features in triangulations of non-adaptively re-meshed surfaces. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (Aachen, Germany) (SGP ’03). Eurographics Association, Goslar, DEU, 62–69.
    2. Haim Avron, Andrei Sharf, Chen Greif, and Daniel Cohen-Or. 2010. l1-Sparse reconstruction of sharp point set surfaces. ACM Transactions on Graphics 29, 5 (2010), 1–12.
    3. Jean-Philippe Bauchet and Florent Lafarge. 2020. Kinetic shape reconstruction. ACM Transactions on Graphics 39, 5 (2020), 14 pages. https://doi.org/10.1145/3376918
    4. Matthew Berger, Andrea Tagliasacchi, Lee M. Seversky, Pierre Alliez, Gaël 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.
    5. Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Claudio Silva, and Gabriel Taubin. 1999. The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics 5, 4 (1999), 349–359.
    6. Ksenia Bestuzheva, Mathieu Besançon, 2021. The SCIP optimization suite 8.0. Technical Report. Optimization Online. http://www.optimization-online.org/DB_HTML/2021/12/8728.html
    7. Ricard Campos, Rafael Garcia, Pierre Alliez, and Mariette Yvinec. 2013. Splat-based surface reconstruction from defect-laden point sets. Graphical Models 75, 6 (Nov. 2013), 346–361.
    8. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational shape approximation. ACM Transactions on Graphics 23, 3 (2004), 905–914.
    9. Zheng-Jie Deng, Xiao-Nan Luo, and Xiao-Ping Miao. 2011. Automatic cage building with quadric error metrics. Journal of Computer Science and Technology 26 (2011), 538–547.
    10. Tamal K. Dey. 2006. Curve and surface reconstruction: Algorithms with mathematical analysis. Cambridge University Press, Cambridge.
    11. Julie Digne, David Cohen-Steiner, Pierre Alliez, Fernando de Goes, and Mathieu Desbrun. 2014. Feature-preserving surface reconstruction and simplification from defect-laden point sets. Journal of Mathematical Imaging and Vision 48, 2 (2014), 369–382.
    12. Shachar Fleishman, Daniel Cohen-Or, and Cláudio T Silva. 2005. Robust moving least-squares fitting with sharp features. ACM Transactions on Graphics 24, 3 (2005), 544–552.
    13. Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. ACM, Los Angeles, 209–216.
    14. Gaël Guennebaud, Benoît Jacob, 2010. Eigen v3. http://eigen.tuxfamily.org
    15. Hugues Hoppe. 1999. New quadric metric for simplifiying meshes with appearance attributes. In Proceedings of the Conference on Visualization ’99: Celebrating Ten Years (San Francisco, California, USA) (VIS ’99). IEEE Computer Society Press, Washington, DC, USA, 59–66.
    16. Hugues Hoppe, Tony DeRose, Tom Duchamp, Mark Halstead, Hubert Jin, John McDonald, Jean Schweitzer, and Werner Stuetzle. 1994. Piecewise smooth surface reconstruction. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. ACM, Orlando, 295–302.
    17. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Symposium on Geometry Processing, Alla Sheffer and Konrad Polthier (Eds.). The Eurographics Association, Cagliari, Sardinia, 10 pages.
    18. Michael Kazhdan and Hugues Hoppe. 2013. Screened Poisson surface reconstruction. ACM Transactions on Graphics 32, 3, Article 29 (jul 2013), 13 pages.
    19. Hélène Legrand, Jean-Marc Thiery, and Tamy Boubekeur. 2019. Filtered quadrics for high-speed geometry smoothing and clustering. Computer Graphics Forum 38, 1 (2019), 663–677.
    20. Peter Lindstrom. 2000. Out-of-core simplification of large polygonal models. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. ACM, New Orleans, 259–262.
    21. Yujia Liu, Stefano D’Aronco, Konrad Schindler, and Jan Dirk Wegner. 2021. PC2WF: 3D wireframe reconstruction from raw point clouds. arXiv preprint arXiv:2103.02766 (2021).
    22. Albert Matveev, Ruslan Rakhimov, Alexey Artemov, Gleb Bobrovskikh, Vage Egiazarian, Emil Bogomolov, Daniele Panozzo, Denis Zorin, and Evgeny Burnaev. 2022. DEF: Deep estimation of sharp geometric features in 3D shapes. ACM Transactions on Graphics 41, 4 (2022), 1–22.
    23. Liangliang Nan and Peter Wonka. 2017. Polyfit: Polygonal surface reconstruction from point clouds. In Proceedings of the IEEE International Conference on Computer Vision. IEEE, Venice, 2353–2361.
    24. 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.
    25. Marie-Julie Rakotosaona, Paul Guerrero, Noam Aigerman, Niloy Mitra, and Maks Ovsjanikov. 2021. Learning Delaunay surface elements for mesh reconstruction. In CVPR – IEEE Conference on Computer Vision and Pattern Recognition. Computer Vision Foundation / IEEE, 22–31.
    26. Yusuf Sahillioglu and Yücel Yemez. 2010. Coarse-to-fine surface reconstruction from silhouettes and range data using mesh deformation. Computer Vision and Image Understanding 114, 3 (2010), 334–348.
    27. David Salinas, Florent Lafarge, and Pierre Alliez. 2015. Structure-aware mesh decimation. Computer Graphics Forum 34, 6 (2015), 211–227.
    28. Martin Skrodzki, Eric Zimmermann, and Konrad Polthier. 2020. Variational shape approximation of point set surfaces. Computer Aided Geometric Design 80 (2020), 101875.
    29. The CGAL Project. 2021. CGAL user and reference manual. https://doc.cgal.org/5.2.1/Manual/packages.html
    30. Jean-Marc Thiery, Émilie Guy, and Tamy Boubekeur. 2013. Sphere-Meshes: Shape approximation using spherical quadric error metrics. ACM Transactions on Graphics 32, 6, Article 178 (nov 2013), 12 pages.
    31. Philip Trettner and Leif Kobbelt. 2020. Fast and robust QEF minimization using probabilistic quadrics. Computer Graphics Forum 39, 2 (2020), 325–334.
    32. Jun Wang, Z Yu, W Zhu, and J Cao. 2013. Feature-preserving surface reconstruction from unoriented, noisy point data. Computer Graphics Forum 32, 1 (2013), 164–176.
    33. Jianhua Wu and Leif Kobbelt. 2005. Structure recovery via hybrid variational surface approximation. Computer Graphics Forum 24, 3 (2005), 277–284.
    34. 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 Transactions on Graphics 41, 6, Article 228 (nov 2022), 15 pages.
    35. Sunil Kumar Yadav, Ulrich Reitebuch, and Konrad Polthier. 2017. Robust and high fidelity mesh denoising.
    36. Mulin Yu and Florent Lafarge. 2022. Finding good configurations of planar primitives in unorganized point clouds. In CVPR – IEEE Conference on Computer Vision and Pattern Recognition. IEEE, La Nouvelle-Orléans, United States, 11 pages.
    37. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A dataset of 10,000 3D-printing models. arXiv preprint arXiv:1605.04797 (2016).
    38. Henrik Zimmer, Marcel Campen, Ralf Herkrath, and Leif Kobbelt. 2012. Variational tangent plane intersection for planar polygonal meshing. In Advances in Architectural Geometry. Springer, Paris, 14 pages.

ACM Digital Library Publication:

Overview Page: