“Harmonic global parametrization with rational holonomy”
Conference:
Type:
Title:
- Harmonic global parametrization with rational holonomy
Session/Category Title: Global Parameterization
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
