“Which cross fields can be quadrangulated?: global parameterization from prescribed holonomy signatures” by Shen, Zhu, Capouellez, Panozzo, Campen, et al. …

  • ©Hanxiao Shen, Leyi Zhu, Ryan Capouellez, Daniele Panozzo, Marcel Campen, and Denis Zorin




    Which cross fields can be quadrangulated?: global parameterization from prescribed holonomy signatures



    We describe a method for the generation of seamless surface parametrizations with guaranteed local injectivity and full control over holonomy. Previous methods guarantee only one of the two. Local injectivity is required to enable these parametrizations’ use in applications such as surface quadrangulation and spline construction. Holonomy control is crucial to enable guidance or prescription of the parametrization’s isocurves based on directional information, in particular from cross-fields or feature curves, and more generally to constrain the parametrization topologically. To this end we investigate the relation between cross-field topology and seamless parametrization topology. Leveraging previous results on locally injective parametrization and combining them with insights on this relation in terms of holonomy, we propose an algorithm that meets these requirements. A key component relies on the insight that arbitrary surface cut graphs, as required for global parametrization, can be homeomorphically modified to assume almost any set of turning numbers with respect to a given target cross-field.


    1. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM Trans. Graph. 34, 6 (2015), 190:1–190:12.Google ScholarDigital Library
    2. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. 35, 6, Article 217 (2016), 14 pages.Google ScholarDigital Library
    3. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. Computer Graphics Forum (2008).Google Scholar
    4. 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
    5. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing: A Survey. In Computer Graphics Forum. Wiley Online Library.Google Scholar
    6. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77.Google ScholarDigital Library
    7. Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic Global Parametrization with Rational Holonomy. ACM Trans. Graph. 36, 4 (2017).Google ScholarDigital Library
    8. Marcel Campen. 2017. Partitioning Surfaces Into Quadrilateral Patches: A Survey. Computer Graphics Forum 36, 8 (2017), 567–588.Google ScholarCross Ref
    9. Marcel Campen, David Bommes, and Leif Kobbelt. 2012. Dual Loops Meshing: Quality Quad Layouts on Manifolds. ACM Trans. Graph. 31, 4 (2012).Google ScholarDigital Library
    10. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized global parametrization. ACM Trans. Graph. 34, 6 (2015), 192.Google ScholarDigital Library
    11. Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, and Denis Zorin. 2021. Efficient and Robust Discrete Conformal Equivalence with Boundary. ACM Trans. Graph. 40, 6 (2021).Google ScholarDigital Library
    12. Marcel Campen and Leif Kobbelt. 2014. Dual Strip Weaving: Interactive Design of Quad Layouts Using Elastica Strips. ACM Trans. Graph. 33, 6 (2014), 183:1–183:10.Google ScholarDigital Library
    13. Marcel Campen, Hanxiao Shen, Jiaran Zhou, and Denis Zorin. 2019. Seamless Parametrization with Arbitrary Cones for Arbitrary Genus. ACM Trans. Graph. 39, 1 (2019).Google Scholar
    14. Marcel Campen and Denis Zorin. 2017. Similarity Maps and Field-Guided T-Splines: a Perfect Couple. ACM Trans. Graph. 36, 4 (2017).Google ScholarDigital Library
    15. Wei Chen, Xiaopeng Zheng, Jingyao Ke, Na Lei, Zhongxuan Luo, and Xianfeng Gu. 2019. Quadrilateral mesh generation I: Metric based method. Comput. Methods Appl. Mech. Engrg. 356 (2019), 652–668.Google ScholarCross Ref
    16. Wei Chen, Xiaopeng Zheng, Jingyao Ke, Na Lei, Zhongxuan Luo, and Xianfeng Gu. 2020. Quadrilateral Mesh Generation II: Meoromorphic Quartic Differentials and Abel-Jacobi Condition. Comput. Methods Appl. Mech. Engrg. 366 (2020).Google Scholar
    17. Edward Chien, Zohar Levi, and Ofir Weber. 2016. Bounded Distortion Parametrization in the Space of Metrics. ACM Trans. Graph. 35, 6 (2016).Google ScholarDigital Library
    18. Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial Connections on Discrete Surfaces. Computer Graphics Forum 29, 5 (2010), 1525–1533.Google ScholarCross Ref
    19. Pablo Diaz-Gutierrez, David Eppstein, and Meenakshisundaram Gopi. 2009. Curvature aware fundamental cycles. In Computer Graphics Forum, Vol. 28. 2015–2024.Google ScholarCross Ref
    20. 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 (2016), 218:1–218:13.Google ScholarDigital Library
    21. Jeff Erickson and Kim Whittlesey. 2005. Greedy optimal homotopy and homology generators. In SODA, Vol. 5. 1038–1046.Google Scholar
    22. Xianzhong Fang, Hujun Bao, Yiying Tong, Mathieu Desbrun, and Jin Huang. 2018. Quadrangulation through morse-parameterization hybridization. ACM Trans. Graph. 37, 4 (2018), 92.Google ScholarDigital Library
    23. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing Locally Injective Mappings by Advanced MIPS. ACM Trans. Graph. 34, 4 (2015).Google ScholarDigital Library
    24. Mark Gillespie, Boris Springborn, and Keenan Crane. 2021. Discrete Conformal Equivalence of Polyhedral Surfaces. ACM Trans. Graph. 40, 4 (2021).Google ScholarDigital Library
    25. Steven J. Gortler, Craig Gotsman, and Dylan Thurston. 2006. Discrete one-forms on meshes and applications to 3D mesh parameterization. Computer Aided Geometric Design 23, 2 (2006), 83 — 112.Google ScholarDigital Library
    26. Xianfeng Gu and Shing-Tung Yau. 2003. Global conformal surface parameterization. In Proc. Symp. Geometry Processing 2003. 127–137.Google Scholar
    27. Xianfeng David Gu, Feng Luo, Jian Sun, and Tianqi Wu. 2018. A discrete uniformization theorem for polyhedral surfaces. Journal of differential geometry 109, 2 (2018).Google Scholar
    28. Allen Hatcher. 2002. Algebraic Topology. Cambridge University Press.Google Scholar
    29. Eden Fedida Hefetz, Edward Chien, and Ofir Weber. 2019. A Subspace Method for Fast Locally Injective Harmonic Mapping. In Computer Graphics Forum, Vol. 38. 105–119.Google ScholarCross Ref
    30. K. Hormann and G. Greiner. 2000. MIPS: An Efficient Global Parametrization Method. In Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153–162.Google Scholar
    31. Ernest Jucovič and Marián Trenkler. 1973. A theorem on the structure of cell-decompositions of orientable 2–manifolds. Mathematika 20, 01 (1973), 63–82.Google ScholarCross Ref
    32. F. Kälberer, M. Nieser, and K. Polthier. 2007. QuadCover: Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3 (2007), 375–384.Google ScholarCross Ref
    33. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25 (April 2006), 412–438. Issue 2.Google ScholarDigital Library
    34. P. Knupp. 1995. Mesh Generation Using Vector Fields. J. Comput. Phys. 119, 1 (1995).Google ScholarDigital Library
    35. Denis Kovacs, Ashish Myles, and Denis Zorin. 2011. Anisotropic quadrangulation. Computer Aided Geometric Design 28, 8 (2011), 449 — 462.Google ScholarDigital Library
    36. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. 35, 4 (2016), 134:1–134:11.Google ScholarDigital Library
    37. W. Li, B. Vallet, N. Ray, and B. Levy. 2006. Representing Higher-Order Singularities in Vector Fields on Piecewise Linear Surfaces. IEEE TVCG 12, 5 (2006), 1315–1322.Google Scholar
    38. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4 (2012), 108:1–108:13.Google ScholarDigital Library
    39. Max Lyon, Marcel Campen, David Bommes, and Leif Kobbelt. 2019. Parametrization Quantization with Free Boundaries for Trimmed Quad Meshing. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
    40. Manish Mandad and Marcel Campen. 2020. Efficient piecewise higher-order parametrization of discrete surfaces with local and global injectivity. Computer-Aided Design 127 (2020).Google Scholar
    41. Martin Marinov, Marco Amagliani, Tristan Barback, Jean Flower, Stephen Barley, Suguru Furuta, Peter Charrot, Iain Henley, Nanda Santhanam, G. Thomas Finnigan, Siavash Meshkat, Justin Hallet, Maciej Sapun, and Pawel Wolski. 2019. Generative Design Conversion to Editable and Watertight Boundary Representation. Computer-Aided Design 115 (2019), 194 — 205.Google ScholarDigital Library
    42. 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
    43. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4 (2012), 109.Google ScholarDigital Library
    44. Ashish Myles and Denis Zorin. 2013. Controlled-distortion constrained global parametrization. ACM Transactions on Graphics 32, 4 (2013), 105.Google ScholarDigital Library
    45. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2 (2017), 16:1–16:16.Google ScholarDigital Library
    46. Nicolas Ray, Bruno Vallet, Laurent Alonso, and Bruno Levy. 2009. Geometry-Aware Direction Field Processing. ACM Trans. Graph. 29, 1 (2009).Google ScholarDigital Library
    47. Nicolas Ray, Bruno Vallet, Wan Chiu Li, and Bruno Lévy. 2008. N-Symmetry Direction Field Design. ACM Trans. Graph. 27, 2 (2008).Google ScholarDigital Library
    48. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. Computer Graphics Forum 32, 5 (2013), 125–135.Google ScholarDigital Library
    49. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans. Graph. 36, 4 (2017), 38:1–38:11.Google ScholarDigital Library
    50. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (2015), 9 pages.Google ScholarDigital Library
    51. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal Cone Singularities for Conformal Flattening. ACM Trans. Graph. 37, 4 (2018), 105:1–105:17.Google ScholarDigital Library
    52. Boris Springborn. 2019. Ideal Hyperbolic Polyhedra and Discrete Uniformization. Discrete & Computational Geometry (2019), 1–46.Google Scholar
    53. Y. Tong, P. Alliez, D. Cohen-Steiner, and M. Desbrun. 2006. Designing quadrangulations with discrete harmonic forms. Symposium on Geometry Processing (2006), 201–210.Google Scholar
    54. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. Comp. Graph. Forum 35, 2 (2016).Google Scholar
    55. Jiaran Zhou, Marcel Campen, Denis Zorin, Changhe Tu, and Claudio T Silva. 2018. Quadrangulation of non-rigid objects using deformation metrics. Computer Aided Geometric Design 62 (2018), 3–15.Google ScholarDigital Library
    56. J. Zhou, C. Tu, D. Zorin, and M. Campen. 2020. Combinatorial Construction of Seamless Parameter Domains. Computer Graphics Forum 39, 2 (2020), 179–190.Google ScholarCross Ref
    57. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasinewton for Distortion Optimization. ACM Trans. Graph. 37, 4 (2018), 40:1–40:14.Google ScholarDigital Library

ACM Digital Library Publication: