“Progressive parameterizations” by Liu, Ye, Ni and Fu

  • ©Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu



Entry Number: 41


    Progressive parameterizations

Session/Category Title: A Race to the Bottom (of the Geometric Energy Plot)




    We propose a novel approach, called Progressive Parameterizations, to compute foldover-free parameterizations with low isometric distortion on disk topology meshes. Instead of using the input mesh as a reference to define the objective function, we introduce a progressive reference that contains bounded distortion to the parameterized mesh and is as close as possible to the input mesh. After optimizing the bounded distortion energy between the progressive reference and the parameterized mesh, the parameterized mesh easily approaches the progressive reference, thereby also coming close to the input. By iteratively generating the progressive reference and optimizing the bounded distortion energy to update the parameterized mesh, our algorithm achieves high-quality parameterizations with strong practical reliability and high efficiency. We have demonstrated that our algorithm succeeds on a massive test data set containing over 20712 complex disk topology meshes. Compared to the state-of-the-art methods, our method has achieved higher computational efficiency and practical reliability.


    1. Noam Aigerman, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Spherical Orbifold Tutte Embeddings. ACM Trans. Graph. (SIGGRAPH) 36, 4 (2017), 90:1–90:13. Google ScholarDigital Library
    2. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM Trans. Graph. (SIGGRAPH ASIA) 34, 6 (2015), 190:1–190:12. Google ScholarDigital Library
    3. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. (SIGGRAPH ASIA) 35, 6 (2016), 190:1–190:12. Google ScholarDigital Library
    4. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted Bijections for Low Distortion Surface Mappings. ACM Trans. Graph. (SIGGRAPH) 33, 4 (2014), 69:1–69:12. Google ScholarDigital Library
    5. Marc Alexa. 2002. Linear Combination of Transformations. ACM Trans. Graph. 21, 3 (2002), 380–387. Google ScholarDigital Library
    6. Marc Alexa, Daniel Cohen-Or, and David Levin. 2000. As-Rigid-As-Possible Shape Interpolation. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’00). 157–164. Google ScholarDigital Library
    7. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-Integer Quadrangulation. ACM Trans. Graph. (SIGGRAPH) 28, 3 (2009), 77:1–77:10. Google ScholarDigital Library
    8. Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic Global Parametrization with Rational Holonomy. ACM Trans. Graph. (SIGGRAPH) 36, 4 (2017), 89:1–89:15. Google ScholarDigital Library
    9. Renjie Chen, Ofir Weber, Daniel Keren, and Mirela Ben-Chen. 2013. Planar Shape Interpolation with Bounded Distortion. ACM Trans. Graph. (SIGGRAPH) 32, 4 (2013), 108:1–108:12. Google ScholarDigital Library
    10. Edward Chien, Renjie Chen, and Ofir Weber. 2016a. Bounded Distortion Harmonic Shape Interpolation. ACM Trans. Graph. (SIGGRAPH) 35, 4 (2016), 105:1–105:15. Google ScholarDigital Library
    11. Edward Chien, Zohar Levi, and Ofir Weber. 2016b. Bounded Distortion Parametrization in the Space of Metrics. ACM Trans. Graph. (SIGGRAPH ASIA) 35, 6 (2016), 215:1–215:16. Google ScholarDigital Library
    12. S Claici, M Bessmeltsev, S Schaefer, and J Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. Comput. Graph. Forum (SGP) 36, 5 (2017), 37–47. Google ScholarDigital Library
    13. P. Degener, J. Meseth, and R. Klein. 2003. An Adaptable Surface Parameterization Method. In Int. Meshing Roundtable. 201–213.Google Scholar
    14. Michael S. Floater. 2003. One-to-one Piecewise Linear Mappings over Triangulations. Math. Comput. 72 (2003), 685–696. Google ScholarDigital Library
    15. Michael S. Floater and Kai Hormann. 2005. Surface Parameterization: A Tutorial and Survey. In In Advances in Multiresolution for Geometric Modelling. Springer, 157–186.Google Scholar
    16. Xiao-Ming Fu and Yang Liu. 2016. Computing Inversion-Free Mappings by Simplex Assembly. ACM Trans. Graph. (SIGGRAPH ASIA) 35, 6 (2016). Google ScholarDigital Library
    17. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing Locally Injective Mappings by Advanced MIPS. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 71:1–71:12. Google ScholarDigital Library
    18. Xiao-Ming Fu, Yang Liu, John Snyder, and Baining Guo. 2014. Anisotropic Simplicial Meshing Using Local Convex Functions. ACM Trans. Graph. (SIGGRAPH ASIA) 33, 6 (2014), 182:1–182:11. Google ScholarDigital Library
    19. F Sebastian Grassia. 1998. Practical Parameterization of Rotations Using the Exponential Map. Journal of graphics tools 3, 3 (1998), 29–48. Google ScholarDigital Library
    20. Xianfeng Gu, Steven J. Gortler, and Hugues Hoppe. 2002. Geometry Images. ACM Trans. Graph. (SIGGRAPH) 21, 3 (2002), 355–361. Google ScholarDigital Library
    21. 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
    22. Kai Hormann, Bruno Lévy, and Alla Sheffer. 2007. Mesh Parameterization: Theory and Practice. In ACM SIGGRAPH 2007 Courses (SIGGRAPH ’07). Google ScholarDigital Library
    23. Xin Hu, Xiao-Ming Fu, and Ligang Liu. 2018. Advanced Hierarchical Spherical Parameterizations. IEEE. T. Vis. Comput. Gr. 24, 6 (2018), 1930–1941.Google ScholarCross Ref
    24. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. (SIGGRAPH ASIA) 36, 6 (2017), 186:1–186:9. Google ScholarDigital Library
    25. Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2015. Large-scale Bounded Distortion Mappings. ACM Trans. Graph. (SIGGRAPH ASIA) 34, 6 (2015), 191:1–191:10. Google ScholarDigital Library
    26. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. (SIGGRAPH) 35, 4 (2016), 134:1–134:11. 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 Trans. Graph. (SIGGRAPH) 21, 3 (2002), 362–371. Google ScholarDigital Library
    28. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. (SIGGRAPH) 31, 4 (2012), 108:1–108:13. Google ScholarDigital Library
    29. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local/Global Approach to Mesh Parameterization. Comput. Graph. Forum (SGP) 27, 5 (2008), 1495–1504. Google ScholarDigital Library
    30. Cosmin G. Petra, Olaf Schenk, and Mihai Anitescu. 2014a. Real-time Stochastic Optimization of Complex Energy Systems on High-performance Computers. IEEE Computing in Science & Engineering 16, 5 (2014), 32–42.Google ScholarCross Ref
    31. Cosmin G. Petra, Olaf Schenk, Miles Lubin, and Klaus Gartner. 2014b. An Augmented Incomplete Factorization Approach for Computing the Schur Complement in Stochastic Optimization. SIAM Journal on Scientific Computing 36, 2 (2014), C139–C162.Google ScholarCross Ref
    32. Roi Poranne, Marco Tarini, Sandro Huber, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Autocuts: Simultaneous Distortion and Cut Optimization for UV Mapping. ACM Trans. Graph. (SIGGRAPH ASIA) 36, 6 (2017), 215:1–215:11. Google ScholarDigital Library
    33. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Maps. ACM Trans. Graph. 36, 2 (2017). Google ScholarDigital Library
    34. Jarek Rossignac and Álvar Vinacua. 2011. Steady Affine Motions and Morphs. ACM Trans. Graph. 30, 5 (2011), 116. Google ScholarDigital Library
    35. Olaf Schenk, Andreas Wächter, and Michael Hagemann. 2007. Mtching-based Preprocessing Algorithms to the Solution of Saddle-point Problems in Large-scale Nonconvex Interior-point Optimization. Computational Optimization and Applications 36, 2 (2007), 321–341. Google ScholarDigital Library
    36. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. Comput. Graph. Forum (SGP) 32, 5 (2013), 125–135. Google ScholarDigital Library
    37. Alla Sheffer. 2002. Spanning Tree Seams for Reducing Parameterization Distortion of Triangulated Surfaces. In Shape Modeling International. 61–66. Google ScholarDigital Library
    38. Alla Sheffer and John C Hart. 2002. Seamster: Inconspicuous Low-distortion Texture Seam Layout. In Proceedings of the conference on Visualization’02. 291–298. Google ScholarDigital Library
    39. Alla Sheffer, Bruno Levy, Maxim Mogilnitsky, and Alexander Bogomyakov. 2005. ABF++: Fast and Robust Angle Based Flattening. ACM Trans. Graph. 24, 2 (2005), 311–330. Google ScholarDigital Library
    40. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh Parameterization Methods and Their Applications. Found. Trends. Comput. Graph. Vis. 2, 2 (2006), 105–171. Google ScholarDigital Library
    41. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans. Graph. (SIGGRAPH) 36, 4 (2017), 38:1–38:11. Google ScholarDigital Library
    42. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 70:1–70:9. Google ScholarDigital Library
    43. Olga Sorkine and Marc Alexa. 2007. As-Rigid-As-Possible Surface Modeling. In Symposium on Geometry Processing. 109–116. Google ScholarDigital Library
    44. Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, and Dani Lischinski. 2002. Bounded-distortion Piecewise Mesh Parameterization. In Proceedings of the Conference on Visualization ’02. 355–362. Google ScholarDigital Library
    45. W. T. Tutte. 1963. How to Draw A Graph. In Proceedings of the London Mathematical Society, Vol. 13. 747–767.Google Scholar
    46. Ofir Weber and Craig Gotsman. 2010. Controllable Conformal Maps for Shape Deformation and Interpolation. ACM Trans. Graph. (SIGGRAPH) 29, 4 (2010), 78:1–78:11. Google ScholarDigital Library
    47. Ofir Weber and Denis Zorin. 2014. Locally Injective Parametrization with Arbitrary Fixed Boundaries. ACM Trans. Graph. (SIGGRAPH) 33, 4 (2014), 75:1–75:12. Google ScholarDigital Library
    48. Kun Zhou, John Synder, Baining Guo, and Heung-Yeung Shum. 2004. Iso-charts: Stretch-driven Mesh Parameterization Using Spectral Analysis. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 45–54. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: