“Quadrangulation through morse-parameterization hybridization” by Fang, Bao, Tong, Desbrun and Huang

  • ©Xianzhong Fang, Hujun Bao, Yiying Tong, Mathieu Desbrun, and Jin Huang



Entry Number: 92


    Quadrangulation through morse-parameterization hybridization

Session/Category Title:   Fields and Remeshing




    We introduce an approach to quadrilateral meshing of arbitrary triangulated surfaces that combines the theoretical guarantees of Morse-based approaches with the practical advantages of parameterization methods. We first construct, through an eigensolver followed by a few Gauss-Newton iterations, a periodic four-dimensional vector field that aligns with a user-provided frame field and/or a set of features over the input mesh. A field-aligned parameterization is then greedily computed along a spanning tree based on the Dirichlet energy of the optimal periodic vector field, from which quad elements are efficiently extracted over most of the surface. The few regions not yet covered by elements are then upsampled and the first component of the periodic vector field is used as a Morse function to extract the remaining quadrangles. This hybrid parameterization- and Morse-based quad meshing method is not only fast (the parameterization is greedily constructed, and the Morse function only needs to be upsampled in the few uncovered patches), but is guaranteed to provide a feature-aligned quad mesh with non-degenerate cells that closely matches the input frame field over an arbitrary surface. We show that our approach is much faster than Morse-based techniques since it does not require a densely tessellated input mesh, and is significantly more robust than parameterization-based techniques on models with complex features.


    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, Article 98 (2013). Google ScholarDigital Library
    2. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio 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
    3. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-Integer Quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (2009). Google ScholarDigital Library
    4. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized Global Parametrization. ACM Trans. Graph. 34, 6, Article 192 (2015). Google ScholarDigital Library
    5. Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial Connections on Discrete Surfaces. Comput. Graph. Forum 29, 5 (2010), 1525–1533.Google ScholarCross Ref
    6. Fernando de Goes, Mathieu Desbrun, and Yiying Tong. 2015. Vector Field Processing on Triangle Meshes. In ACM SIGGRAPH Asia 2015 Courses. Article 17. Google ScholarDigital Library
    7. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable PolyVector Fields. ACM Trans. Graph. 34, 4, Article 38 (2015). Google ScholarDigital Library
    8. Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, and John C. Hart. 2006. Spectral Surface Quadrangulation. ACM Trans. Graph. 25, 3 (2006), 1057–1066. Google ScholarDigital Library
    9. Hans-Christian Ebke, David Bommes, Marcel Campen, and Leif Kobbelt. 2013. QEx: Robust Quad Mesh Extraction. ACM Trans. Graph. 32, 6, Article 168 (2013). Google ScholarDigital Library
    10. Hans-Christian Ebke, Patrick Schmidt, Marcel Campen, and Leif Kobbelt. 2016. Interactively Controlled Quad Remeshing of High Resolution 3D Models. ACM Trans. Graph. 35, 6, Article 218 (2016). Google ScholarDigital Library
    11. Herbert Edelsbrunner, John Harer, and Afra Zomorodian. 2003. Hierarchical Morse-Smale Complexes for Piecewise Linear 2-Manifolds. Discrete Comput. Geom. 30, 1 (2003), 87–107.Google ScholarCross Ref
    12. David Eppstein. 1999. Linear complexity hexahedral mesh generation. Computational Geometry 12, 1-2 (1999), 3–16. Google ScholarDigital Library
    13. Jin Huang, Muyang Zhang, Jin Ma, Xinguo Liu, Leif Kobbelt, and Hujun Bao. 2008. Spectral Quadrangulation with Orientation and Alignment Control. ACM Trans. Graph. 27, 5, Article 147 (2008). Google ScholarDigital Library
    14. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant Field-aligned Meshes. ACM Trans. Graph. 34, 6, Article 189 (2015). Google ScholarDigital Library
    15. Tengfei Jiang, Xianzhong Fang, Jin Huang, Hujun Bao, Yiying Tong, and Mathieu Desbrun. 2015. Frame Field Generation Through Metric Customization. ACM Trans. Graph. 34, 4, Article 40 (2015). Google ScholarDigital Library
    16. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover: Surface Parameterization using Branched Coverings. Comp. Graph. Forum 26, 3 (2007), 375–384.Google ScholarCross Ref
    17. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2011. Stripe Parameterization of Tubular Surfaces. In Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications, Valerio Pascucci, Xavier Tricoche, Hans Hagen, and Julien Tierny (Eds.). Springer Berlin Heidelberg, 13–26.Google Scholar
    18. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2015. Stripe Patterns on Surfaces. ACM Trans. Graph. 34, 4, Article 39 (2015). Google ScholarDigital Library
    19. Patrick M. Knupp. 2000. Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II-A framework for volume mesh optimization and the condition number of the Jacobian matrix. Internat. J. Numer. Methods Engrg. 48, 8 (2000), 1165–1185.Google ScholarCross Ref
    20. Yu-Kun Lai, Miao Jin, Xuexiang Xie, Ying He, Jonathan Palacios, Eugene Zhang, Shi-Min Hu, and Xianfeng Gu. 2010. Metric-Driven RoSy Field Design and Remeshing. IEEE Trans. Vis. Comput. Graph. 16, 1 (2010), 95–108. Google ScholarDigital Library
    21. Ruotian Ling, Jin Huang, Bert Jüttler, Feng Sun, Hujun Bao, and Wenping Wang. 2014. Spectral Quadrangulation with Feature Curve Alignment and Element Size Control. ACM Trans. Graph. 34, 1, Article 11 (2014). Google ScholarDigital Library
    22. Beibei Liu, Yiying Tong, Fernando De Goes, and Mathieu Desbrun. 2016. Discrete Connection and Covariant Derivative for Vector Field Analysis and Design. ACM Trans. Graph. 35, 3, Article 23 (2016). Google ScholarDigital Library
    23. Scott A. Mitchell. 1996. A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume. Symp. Theor. Comput. Sci. (1996), 465–476. Google ScholarDigital Library
    24. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (2014). Google ScholarDigital Library
    25. Ashish Myles and Denis Zorin. 2013. Controlled-distortion Constrained Global Parametrization. ACM Trans. Graph. 32, 4, Article 105 (2013). Google ScholarDigital Library
    26. Jonathan Palacios and Eugene Zhang. 2007. Rotational Symmetry Field Design on Surfaces. ACM Trans. Graph. 26, 3 (2007), Art. 55. Google ScholarDigital Library
    27. Daniele Panozzo, Enrico Puppo, Marco Tarini, and Olga Sorkine-Hornung. 2014. Frame Fields: Anisotropic and Non-orthogonal Cross Fields. ACM Trans. Graph. 33, 4, Article 134 (2014). Google ScholarDigital Library
    28. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4 (2006), 1460–1485. Google ScholarDigital Library
    29. Jonathan R. Shewchuk. 1997. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete Comput. Geom. 18, 3 (1997), 305–363.Google ScholarCross Ref
    30. 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
    31. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. Comput. Graph. Forum 35, 2 (2016), 545–572.Google ScholarCross Ref
    32. Muyang Zhang, Jin Huang, Xinguo Liu, and Hujun Bao. 2010. A Wave-based Anisotropic Quadrangulation Method. ACM Trans. Graph. 29, 4, Article 118 (2010). Google ScholarDigital Library
    33. Afra J. Zomorodian. 2009. Topology for Computing. Cambridge University Press. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: