“Harmonic global parametrization with rational holonomy”

  • ©Alon Bright, Edward (Ed) Chien, and Ofir Weber




    Harmonic global parametrization with rational holonomy

Session/Category Title: Global Parameterization




    We present a method for locally injective seamless parametrization of triangular mesh surfaces of arbitrary genus, with or without boundaries, given desired cone points and rational holonomy angles (multiples of 2π/q for some positive integer q). The basis of the method is an elegant generalization of Tutte’s “spring embedding theorem” to this setting. The surface is cut to a disk and a harmonic system with appropriate rotation constraints is solved, resulting in a harmonic global parametrization (HGP) method. We show a remarkable result: that if the triangles adjacent to the cones and boundary are positively oriented, and the correct cone and turning angles are induced, then the resulting map is guaranteed to be locally injective. Guided by this result, we solve the linear system by convex optimization, imposing convexification frames on only the boundary and cone triangles, and minimizing a Laplacian energy to achieve harmonicity. We compare HGP to state-of-the-art methods and see that it is the most robust, and is significantly faster than methods with comparable robustness.


    1. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM Trans. Graph. 34, 6, Article 190 (Oct. 2015), 12 pages. Google ScholarDigital Library
    2. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. 35, 6, Article 217 (Nov. 2016), 14 pages. Google ScholarDigital Library
    3. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted bijections for low distortion surface mappings. ACM Transactions on Graphics (TOG) 33, 4 (2014), 69.Google ScholarDigital Library
    4. MOSEK ApS. 2015. The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28). http://docs.mosek.com/7.1/toolbox/index.htmlGoogle Scholar
    5. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27, 2 (2008), 449–458. Google ScholarCross Ref
    6. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013. Quad-Mesh Generation and Processing: A Survey. Computer Graphics Forum 32, 6 (2013), 51–76. Google ScholarDigital Library
    7. D. Bommes, H. Zimmer, and L. Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77. Google ScholarDigital Library
    8. Renjie Chen and Ohr Weber. 2015. Bounded distortion harmonic mappings in the plane. ACM Transactions on Graphics (TOG) 34, 4 (2015), 73.Google ScholarDigital Library
    9. Edward Chien, Renjie Chen, and Ofir Weber. 2016a. Bounded Distortion Harmonic Shape Interpolation. ACM TOG 35, 4 (2016). Google ScholarDigital Library
    10. Edward Chien, Zohar Levi, and Ofir Weber. 2016b. Bounded Distortion Parametrization in the Space of Metrics. ACM Trans. Graph. 35, 6, Article 215 (Nov. 2016), 16 pages. Google ScholarDigital Library
    11. Keenan Crane, Fernando De Goes, Mathieu Desbrun, and Peter Schröder. 2013. Digital Geometry Processing with Discrete Exterior Calculus. In ACM SIGGRAPH 2013 courses (SIGGRAPH ’13). ACM, New York, NY, USA, 126.Google ScholarDigital Library
    12. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable PolyVector Fields. ACM Trans. Graph. 34, 4, Article 38 (July 2015), 12 pages. Google ScholarDigital Library
    13. S. Dong, S. Kircher, and M. Garland. 2005. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Computer Aided Geometric Design 22, 5 (2005), 392 — 423. Google ScholarDigital Library
    14. M.S. Floater. 1997. Parametrization and smooth approximation of surface triangulations* 1. Computer Aided Geometric Design 14, 3 (1997), 231–250. Google ScholarDigital Library
    15. M.S. Floater and K. Hormann. 2005. Surface Parameterization: a Tutorial and Survey. Advances In Multiresolution For Geometric Modelling (2005).Google Scholar
    16. Michael S Floater. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1 (2003), 19–27.Google ScholarDigital Library
    17. Xiao-Ming Fu and Yang Liu. 2016. Computing Inversion-free Mappings by Simplex Assembly. ACM Trans. Graph. 35, 6, Article 216 (Nov. 2016), 12 pages. Google ScholarDigital Library
    18. 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
    19. X. Gu and ST. Yau. 2003. Global conformal surface parameterization. Symposium on Geometry Processing (2003), 127–137.Google Scholar
    20. K. Hormann, B. Lévy, and A. Sheffer. 2007. Mesh parameterization: Theory and practice. SIGGRAPH Course Notes (2007).Google Scholar
    21. Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded Biharmonic Weights for Real-time Deformation. ACM Trans. Graph. 30, 4, Article 78 (July 2011), 8 pages. Google ScholarDigital Library
    22. 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
    23. L. Kharevych, B. Springborn, and P. Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412–438. Google ScholarDigital Library
    24. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2015. Stripe Patterns on Surfaces. ACM Trans. Graph. 34, 4, Article 39 (July 2015), 11 pages. Google ScholarDigital Library
    25. Zohar Levi and Ofir Weber. 2016. On the Convexity and Feasibility of the Bounded Distortion Harmonic Mapping Problem. ACM TOG 35, 4 (2016). Google ScholarDigital Library
    26. Zohar Levi and Denis Zorin. 2014. Strict minimizers for geometric optimization. ACM Transactions on Graphics (TOG) 33, 6 (2014), 185.Google ScholarDigital Library
    27. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics (TOG) 21, 3 (2002), 362–371. Google ScholarDigital Library
    28. Yaron Lipman. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 108.Google ScholarDigital Library
    29. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (July 2014), 14 pages. Google ScholarDigital Library
    30. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4, Article 109 (July 2012), 11 pages. Google ScholarDigital Library
    31. 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
    32. M. Nieser, J. Palacios, K. Polthier, and E. Zhang. 2012. Hexagonal Global Parameterization of Arbitrary Surfaces. IEEE Transactions on Visualization and Computer Graphics 18, 6 (June 2012), 865–878. Google ScholarDigital Library
    33. Alla Sheffer and Eric de Sturler. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineering with Computers 17, 3 (2001), 326–337. Google ScholarCross Ref
    34. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Transactions on Graphics (TOG) 27, 3 (2008), 77.Google ScholarDigital Library
    35. Y. Tong, P. Alliez, D. Cohen-Steiner, and M. Desbrun. 2006. Designing Quadrangulations with Discrete Harmonic Forms. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing (SGP ’06). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 201–210. http://dl.acm.org/citation.cfm?id=1281957.1281983Google Scholar
    36. W.T. Tutte. 1963. How to draw a graph. Proc. London Math. Soc 13, 3 (1963), 743–768. Google ScholarCross Ref
    37. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing – State of the Art Report. Computer Graphics Forum 35, 2 (2016). Google ScholarDigital Library
    38. Max Wardetzky, Saurabh Mathur, Felix Kälberer, and Eitan Grinspun. 2007. Discrete Laplace operators: no free lunch. In Symposium on Geometry processing. 33–37.Google Scholar

ACM Digital Library Publication:

Overview Page: