“Spherical orbifold tutte embeddings” by Aigerman, Kovalsky and Lipman

  • ©Noam Aigerman, Shahar Z. Kovalsky, and Yaron Lipman




    Spherical orbifold tutte embeddings

Session/Category Title:   Global Parameterization




    This work presents an algorithm for injectively parameterizing surfaces into spherical target domains called spherical orbifolds. Spherical orbifolds are cone surfaces that are generated from symmetry groups of the sphere. The surface is mapped the spherical orbifold via an extension of Tutte’s embedding. This embedding is proven to be bijective under mild additional assumptions, which hold in all experiments performed.This work also completes the adaptation of Tutte’s embedding to orbifolds of the three classic geometries – Euclidean, hyperbolic and spherical – where the first two were recently addressed.The spherical orbifold embeddings approximate conformal maps and require relatively low computational times. The constant positive curvature of the spherical orbifolds, along with the flexibility of their cone angles, enables producing embeddings with lower isometric distortion compared to their Euclidean counterparts, a fact that makes spherical orbifolds a natural candidate for surface parameterization.


    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 Transactions on Graphics (TOG) 35, 6 (2016), 217.Google ScholarDigital Library
    3. Marc Alexa. 1999. Merging polyhedral shapes with scattered features. In Shape Modeling and Applications, 1999. Proceedings. Shape Modeling International’99. International Conference on. IEEE, 202–210. Google ScholarCross Ref
    4. Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2005. Consistent spherical parameterization. In International Conference on Computational Science. Springer, 265–272. Google ScholarDigital Library
    5. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer Quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages. Google ScholarDigital Library
    6. Samuel R Buss and Jay P Fillmore. 2001. Spherical averages and applications to spherical splines and interpolation. ACM Transactions on Graphics (TOG) 20, 2 (2001), 95–126. Google ScholarDigital Library
    7. Edward Chien, Zohar Levi, and Ofir Weber. 2016. Bounded distortion parametrization in the space of metrics. ACM Transactions on Graphics (TOG) 35, 6 (2016), 215.Google ScholarDigital Library
    8. John Horton Conway, Heidi Burgiel, and Chaim Goodman-Strauss. 2008. The symmetries of things. A.K. Peters, Wellesley (Mass.). http://opac.inria.fr/record=b1130158Google Scholar
    9. Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Robust Fairing via Conformal Curvature Flow. ACM Trans. Graph. 32, 4 (2013). Google ScholarDigital Library
    10. Michael Floater. 2003. One-to-one piecewise linear mappings over triangulations. Math. Comp. 72, 242 (2003), 685–696. Google ScholarDigital Library
    11. Ilja Friedel, Peter Schröder, and Mathieu Desbrun. 2007. Unconstrained spherical parameterization. Journal of Graphics, GPU, and Game Tools 12, 1 (2007), 17–26. Google ScholarCross Ref
    12. 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
    13. Craig Gotsman, Xianfeng Gu, and Alla Sheffer. 2003. Fundamentals of spherical parameterization for 3D meshes. ACM Transactions on Graphics (TOG) 22, 3 (2003), 358–363. Google ScholarDigital Library
    14. Xianfeng Gu, Yalin Wang, Tony F Chan, Paul M Thompson, and Shing-Tung Yau. 2003. Genus zero surface conformal mapping and its application to brain surface mapping. In Biennial International Conference on Information Processing in Medical Imaging. Springer, 172–184. Google ScholarCross Ref
    15. Steven Haker, Sigurd Angenent, Allen Tannenbaum, Ron Kikinis, Guillermo Sapiro, and Michael Halle. 2000. Conformal Surface Parameterization for Texture Mapping. IEEE Transactions on Visualization and Computer Graphics 6, 2 (April 2000), 181–189. Google ScholarDigital Library
    16. Kai Hormann, Bruno Lévy, and Alla Sheffer. 2007. Mesh Parameterization: Theory and Practice Video Files Associated with This Course Are Available from the Citation Page. In ACM SIGGRAPH 2007 Courses (SIGGRAPH ’07). ACM, New York, NY, USA, Article 1. Google ScholarDigital Library
    17. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover – Surface Parameterization using Branched Coverings. Comput. Graph. Forum, 375–384. Google ScholarCross Ref
    18. Michael Kazhdan, Jake Solomon, and Mirela Ben-Chen. 2012. Can Mean-Curvature Flow be Modified to be Non-singular?. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1745–1754.Google Scholar
    19. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. 35, 4, Article 134 (July 2016), 11 pages. Google ScholarDigital Library
    20. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2016. Towards Real-time Simulation of Hyperelastic Materials. arXiv preprint arXiv:1604.07378 (2016).Google Scholar
    21. László Lovász. 2004. Discrete analytic functions: an exposition. Surveys in differential geometry 9 (2004), 241–273.Google Scholar
    22. László Lovász and Alexander Schrijver. 1999. On the null space of a Colin de Verdiere matrix. In Annales de l’institut Fourier, Vol. 49. 1017–1026. Google ScholarCross Ref
    23. 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
    24. 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
    25. Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer Science & Business Media.Google Scholar
    26. Ulrich Pinkall and Konrad Polthier. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experimental Mathematics 2 (1993), 15–36. Google ScholarCross Ref
    27. Emil Praun and Hugues Hoppe. 2003. Spherical parametrization and remeshing. In ACM Transactions on Graphics (TOG), Vol. 22. ACM, 340–349. 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 (Oct. 2006), 1460–1485. Google ScholarDigital Library
    29. Shadi Saba, Irad Yavneh, Craig Gotsman, and Alla Sheffer. 2005. Practical spherical embedding of manifold triangle meshes. In International Conference on Shape Modeling and Applications 2005 (SMI’05). IEEE, 256–265. Google ScholarDigital Library
    30. Avner Shapiro and Ayellet Tal. 1998. Polyhedron realization for shape transformation. The Visual Computer 14, 8 (1998), 429–444. Google ScholarCross Ref
    31. Alla Sheffer, Craig Gotsman, and Nira Dyn. 2004. Robust spherical parameterization of triangular meshes. In Geometric Modelling. Springer, 185–193. Google ScholarCross Ref
    32. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh Parameterization Methods and Their Applications. Found. Trends. Comput. Graph. Vis. 2, 2 (Jan. 2006), 105–171. Google ScholarDigital Library
    33. 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
    34. 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
    35. Alex Tsui, Devin Fenton, Phong Vuong, Joel Hass, Patrice Koehl, Nina Amenta, David Coeurjolly, Charles DeCarli, and Owen Carmichael. 2013. Globally Optimal Cortical Surface Matching with Exact Landmark Correspondence. In Proceedings of the 23rd International Conference on Information Processing in Medical Imaging (IPMI’13). Springer-Verlag, Berlin, Heidelberg, 487–498. Google ScholarDigital Library
    36. William T Tutte. 1963. How to draw a graph. Proc. London Math. Soc 13, 3 (1963), 743–768.Google ScholarCross Ref
    37. Chunxue Wang, Zheng Liu, and Ligang Liu. 2014. As-rigid-as-possible spherical parametrization. Graphical Models 76, 5 (2014), 457–467. Google ScholarDigital Library
    38. Ofir Weber and Denis Zorin. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Transactions on Graphics (TOG) 33, 4 (2014), 75.Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: