“Reliable feature-line driven quad-remeshing” by Pietroni, Nuvoli, Alderighi, Cignoni and Tarini

We present a new algorithm for the semi-regular quadrangulation of an input surface, driven by its line features, such as sharp creases. We define a perfectly feature-aligned cross-field and a coarse layout of polygonal-shaped patches where we strictly ensure that all the feature-lines are represented as patch boundaries. To be able to consistently do so, we allow non-quadrilateral patches and T-junctions in the layout; the key is the ability to constrain the layout so that it still admits a globally consistent, T-junction-free, and pure-quad internal tessellation of its patches. This requires the insertion of additional irregular-vertices inside patches, but the regularity of the final-mesh is safeguarded by optimizing for both their number and for their reciprocal alignment. In total, our method guarantees the reproduction of feature-lines by construction, while still producing good quality, isometric, pure-quad, conforming meshes, making it an ideal candidate for CAD models. Moreover, the method is fully automatic, requiring no user intervention, and remarkably reliable, requiring little assumptions on the input mesh, as we demonstrate by batch processing the entire Thingi10K repository, with less than 0.5% of the attempted cases failing to produce a usable mesh.

1. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid maps for reliable quad meshing. ACM Trans. Graph 32, 4 (2013), 98:1–98:12.Google ScholarDigital Library
2. David Bommes, Timm Lempfer, and Leif Kobbelt. 2011. Global Structure Optimization of Quadrilateral Meshes. Comput. Graph. Forum 30, 2 (2011), 375–384.Google ScholarCross Ref
3. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Cláudio T. Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing: A Survey. Comput. Graph. Forum 32, 6 (2013), 51–76.Google ScholarDigital Library
4. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77.Google ScholarDigital Library
5. Marcel Campen. 2017. Partitioning Surfaces Into Quadrilateral Patches: A Survey. Comput. Graph. Forum 36, 8 (2017), 567–588.Google ScholarCross Ref
6. Marcel Campen, David Bommes, and Leif Kobbelt. 2012. Dual loops meshing: quality quad layouts on manifolds. ACM Trans. Graph. 31, 4 (2012), 110:1–110:11.Google ScholarDigital Library
7. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized global parametrization. ACM Trans. Graph 34, 6 (2015), 192:1–192:12.Google ScholarDigital Library
8. Marcel Campen, Martin Heistermann, and Leif Kobbelt. 2013. Practical Anisotropic Geodesy. Comput. Graph. Forum 32, 5 (2013), 63–71.Google ScholarDigital Library
9. Paolo Cignoni, Guido Ranzuglia, Marco Callieri, Massimiliano Corsini, Matteo Dellepiane, Marco Di Benedetto, Fabio Ganovelli, Giorgio Marcias, Gianpaolo Palma, Nico Pietroni, Federico Ponchio, Luigi Malomo, Marco Tarini, and Roberto Scopigno. 2013. MeshLab: an Open-Source Mesh Processing Tool. http://www.meshlab.net.Google Scholar
10. CNR. 2013. The Visualization and Computer Graphics Library. http://vcg.isti.cnr.it/vcglib/.Google Scholar
11. Massimiliano Corsini, Paolo Cignoni, and Roberto Scopigno. 2012. Efficient and Flexible Sampling with Blue Noise Properties of Triangular Meshes. IEEE Trans. Vis. Comput. Graph 18, 6 (2012), 914–924. Google ScholarDigital Library
12. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Designing N-PolyVector Fields with Complex Polynomials. Comput. Graph. Forum 33, 5 (2014), 1–11.Google ScholarDigital Library
13. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable PolyVector fields. ACM Trans. Graph 34, 4 (2015), 38:1–38:12.Google ScholarDigital Library
14. Xianzhong Fang, Hujun Bao, Yiying Tong, Mathieu Desbrun, and Jin Huang. 2018. Quadrangulation through Morse-Parameterization Hybridization. ACM Trans. Graph. 37, 4, Article 92 (July 2018), 15 pages. Google ScholarDigital Library
15. LLC Gurobi Optimization. 2018. Gurobi Optimizer Reference Manual. http://www.gurobi.comGoogle Scholar
16. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1993. Mesh Optimization. In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques (Anaheim, CA) (SIGGRAPH ’93). Association for Computing Machinery, New York, NY, USA, 19–26. Google ScholarDigital Library
17. Jingwei Huang, Yichao Zhou, Matthias Niessner, Jonathan Richard Shewchuk, and Leonidas J. Guibas. 2018. QuadriFlow: A Scalable and Robust Method for Quadrangulation. Computer Graphics Forum 37, 5 (2018), 147–160. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.13498 Google ScholarCross Ref
18. Alec Jacobson, Daniele Panozzo, et al. 2013. libigl: A simple C++ geometry processing library. http://igl.ethz.ch/projects/libigl/.Google Scholar
19. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant field-aligned meshes. ACM Trans. Graph. 34, 6 (2015), 189:1–189:15.Google ScholarDigital Library
20. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover – Surface Parameterization using Branched Coverings. Comput. Graph. Forum 26, 3 (2007), 375–384.Google ScholarCross Ref
21. Marco Livesu, Nico Pietroni, Enrico Puppo, Alla Sheffer, and Paolo Cignoni. 2020. LoopyCuts: practical feature-preserving block decomposition for strongly hex-dominant meshing. ACM Trans. Graph 39, 4 (2020), 121.Google ScholarDigital Library
22. Albert Matveev, Alexey Artemov, Ruslan Rakhimov, Gleb Bobrovskikh, Daniele Panozzo, Denis Zorin, and Evgeny Burnaev. 2020. DEF: Deep Estimation of Sharp Geometric Features in 3D Shapes. arXiv:2011.15081 [cs.CV]Google Scholar
23. Alessandro Muntoni and Stefano Nuvoli. 2021. CG3Lib: A C++ geometry processing library. Google ScholarCross Ref
24. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. 33, 4 (2014), 135:1–135:14.Google ScholarDigital Library
25. Ashish Myles and Denis Zorin. 2013. Controlled-distortion constrained global parametrization. ACM Trans. Graph. 32, 4, Article 105 (July 2013), 14 pages. Google ScholarDigital Library
26. Stefano Nuvoli, Alex Hernandez, Claudio Esperança, Riccardo Scateni, Paolo Cignoni, and Nico Pietroni. 2019. QuadMixer: layout preserving blending of quadrilateral meshes. ACM Trans. Graph 38, 6 (2019), 180:1–180:13.Google ScholarDigital Library
27. Daniele Panozzo, Yaron Lipman, Enrico Puppo, and Denis Zorin. 2012. Fields on symmetric surfaces. ACM Trans. Graph 31, 4 (2012), 111:1–111:12.Google ScholarDigital Library
28. Daniele Panozzo, Enrico Puppo, Marco Tarini, Nico Pietroni, and Paolo Cignoni. 2011. Automatic Construction of Quad-Based Subdivision Surfaces using Fitmaps. IEEE Transaction on Visualization and Computer Graphics 17, 10 (october 2011), 1510–1520. Google ScholarCross Ref
29. Nico Pietroni, Enrico Puppo, Giorgio Marcias, Roberto Scopigno, and Paolo Cignoni. 2016. Tracing Field-Coherent Quad Layouts. Comput. Graph. Forum 35, 7 (2016), 485–496.Google ScholarDigital Library
30. Nico Pietroni, Davide Tonelli, Enrico Puppo, Maurizio Froli, Roberto Scopigno, and Paolo Cignoni. 2015. Statics Aware Grid Shells. Comput. Graph. Forum 34, 2 (2015), 627–641.Google ScholarDigital Library
31. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4 (Oct. 2006), 1460–1485. Google ScholarDigital Library
32. Faniry H. Razafindrazaka and Konrad Polthier. 2017. Optimal base complexes for quadrilateral meshes. Computer Aided Geometric Design 52-53 (2017), 63 — 74. Geometric Modeling and Processing 2017. Google ScholarDigital Library
33. Faniry H. Razafindrazaka, Ulrich Reitebuch, and Konrad Polthier. 2015. Perfect Matching Quad Layouts for Manifold Meshes. Comput. Graph. Forum 34, 5 (2015), 219–228.Google ScholarDigital Library
34. Nico Schertler, Daniele Panozzo, Stefan Gumhold, and Marco Tarini. 2018. Generalized Motorcycle Graphs for Imperfect Quad-Dominant Meshes. ACM Trans. Graph. 37, 4, Article 155 (July 2018), 16 pages. Google ScholarDigital Library
35. CJ Stimpson, CD Ernst, P Knupp, PP Pébay, and D Thompson. 2007. The Verdict library reference manual.Google Scholar
36. Kenshi Takayama, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Pattern-Based Quadrangulation for N-Sided Patches. Comput. Graph. Forum 33, 5 (2014), 177–184.Google ScholarDigital Library
37. Marco Tarini. 2021. Closed-form Quadrangulation of N-Sided Patches. arXiv:2101.11569 [cs.GR]Google Scholar
38. Marco Tarini, Nico Pietroni, Paolo Cignoni, Daniele Panozzo, and Enrico Puppo. 2010. Practical quad mesh simplification. Comput. Graph. Forum 29, 2 (2010), 407–418.Google ScholarCross Ref
39. Marco Tarini, Enrico Puppo, Daniele Panozzo, Nico Pietroni, and Paolo Cignoni. 2011. Simple quad domains for field aligned mesh parametrization. ACM Trans. Graph. 30, 6 (2011), 142:1–142:12.Google ScholarDigital Library
40. Francesco Usai, Marco Livesu, Enrico Puppo, Marco Tarini, and Riccardo Scateni. 2016. Extraction of the Quad Layout of a Triangle Mesh Guided by Its Curve Skeleton. ACM Trans. Graph. 35, 1, Article 6 (Dec. 2016), 13 pages. Google ScholarDigital Library
41. Amir Vaxman, Marcel Campen, Olga Diamanti, David Bommes, Klaus Hildebrandt, Mirela Ben-Chen Technion, and Daniele Panozzo. 2017. Directional Field Synthesis, Design, and Processing. In ACM SIGGRAPH 2017 Courses (Los Angeles, California) (SIGGRAPH ’17). Association for Computing Machinery, New York, NY, USA, Article 12, 30 pages. Google ScholarDigital Library
42. Paul Zhang, Josh Vekhter, Edward Chien, David Bommes, Etienne Vouga, and Justin Solomon. 2020. Octahedral Frames for Feature-Aligned Cross Fields. ACM Trans. Graph. 39, 3 (2020), 25:1–25:13. Google ScholarDigital Library
43. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv:1605.04797 [cs.GR]Google Scholar