“Computing sparse integer-constrained cones for conformal parameterizations” by Li, Fang, Ouyang, Liu and Fu

We propose a novel method to generate sparse integer-constrained cone singularities with low distortion constraints for conformal parameterizations. Inspired by [Fang et al. 2021; Soliman et al. 2018], the cone computation is formulated as a constrained optimization problem, where the objective is the number of cones measured by the ℓ0-norm of Gaussian curvature of vertices, and the constraint is to restrict the cone angles to be multiples of π/2 and control the distortion while ensuring that the Yamabe equation holds. Besides, the holonomy angles for the non-contractible homology loops are additionally required to be multiples of π/2 for achieving rotationally seamless conformal parameterizations. The Douglas-Rachford (DR) splitting algorithm is used to solve this challenging optimization problem, and our success relies on two key components. First, replacing each integer constraint with the intersection of a box set and a sphere enables us to manage the subproblems in DR splitting update steps in the continuous domain. Second, a novel solver is developed to optimize the ℓ0-norm without any approximation. We demonstrate the effectiveness and feasibility of our algorithm on a data set containing 3885 models. Compared to state-of-the-art methods, our method achieves a better tradeoff between the number of cones and the parameterization distortion.

1. Edoardo Amaldi and Viggo Kann. 1998. On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems. Theor. Comput. Sci. 209, 1–2 (1998), 237–260.Google ScholarDigital Library
2. Thierry Aubin. 2013. Some nonlinear problems in Riemannian geometry. Springer Science & Business Media.Google Scholar
3. Mirela Ben-Chen, Adrian Butscher, Justin Solomon, and Leonidas Guibas. 2010. On discrete killing vector fields and patterns on surfaces. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1701–1711.Google Scholar
4. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. In Computer Graphics Forum, Vol. 27. 449–458.Google ScholarCross Ref
5. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid maps for reliable quad meshing. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–12.Google ScholarDigital Library
6. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing: A Survey. Comput. Graph. Forum 32, 6 (2013), 51–76.Google ScholarDigital Library
7. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Transactions On Graphics (TOG) 28, 3 (2009), 1–10.Google ScholarDigital Library
8. Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, and Denis Zorin. 2021. Efficient and Robust Discrete Conformal Equivalence with Boundary. arXiv preprint arXiv:2104.04614 (2021).Google Scholar
9. Marcel Campen, Hanxiao Shen, Jiaran Zhou, and Denis Zorin. 2019. Seamless Parametrization with Arbitrary Cones for Arbitrary Genus. ACM Trans. Graph. 39 (2019).Google Scholar
10. Emmanuel J Candes, Michael B Wakin, and Stephen P Boyd. 2008. Enhancing sparsity by reweighted ℓ1 minimization. Journal of Fourier analysis and applications 14, 5–6 (2008), 877–905.Google ScholarCross Ref
11. Pascal Cherrier. 1984. Problemes de Neumann non linéaires sur les variétés riemanniennes. Journal of Functional Analysis 57, 2 (1984), 154–206.Google ScholarCross Ref
12. Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial connections on discrete surfaces. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1525–1533.Google Scholar
13. Tamal K Dey, Fengtao Fan, and Yusu Wang. 2013. An efficient computation of handle and tunnel loops via Reeb graphs. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–10.Google ScholarDigital Library
14. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Designing N-PolyVector fields with complex polynomials. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 1–11.Google ScholarDigital Library
15. Jim Douglas and H. H. Rachford. 1956. On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables. Trans. Amer. Math. Soc. 82, 2 (1956), 421–439.Google ScholarCross Ref
16. Qing Fang, Wenqing Ouyang, Mo Li, Ligang Liu, and Xiao-Ming Fu. 2021. Computing sparse cones with bounded distortion for conformal parameterizations. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–9.Google ScholarDigital Library
17. Nahum Farchi and Mirela Ben-Chen. 2018. Integer-only cross field computation. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–13.Google ScholarDigital Library
18. Matthew Fisher, Peter Schröder, Mathieu Desbrun, and Hugues Hoppe. 2007. Design of tangent vector fields. ACM transactions on graphics (TOG) 26, 3 (2007), 56–es.Google Scholar
19. Christodoulos A Floudas. 1995. Nonlinear and mixed-integer optimization: fundamentals and applications. Oxford University Press.Google Scholar
20. G Anthony Gorry, Jeremy F Shapiro, and Laurence A Wolsey. 1972. Relaxation methods for pure and mixed integer programming problems. Management Science 18, 5-part-1 (1972), 229–239.Google ScholarDigital Library
21. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
22. Lei He and Scott Schaefer. 2013. Mesh denoising via ℓ 0 minimization. ACM Trans. Graph. 32, 4 (2013), 1–8.Google ScholarDigital Library
23. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. Quadcover-surface parameterization using branched coverings. In Computer graphics forum, Vol. 26. Wiley Online Library, 375–384.Google Scholar
24. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412–438.Google ScholarDigital Library
25. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. ACM Transactions on Graphics (ToG) 32, 4 (2013), 1–10.Google ScholarDigital Library
26. G Hosein Mohimani, Massoud Babaie-Zadeh, and Christian Jutten. 2007. Fast sparse representation based on smoothed ℓ0 norm. In International Conference on Independent Component Analysis and Signal Separation. 389–396.Google ScholarDigital Library
27. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4 (2012), 1–11.Google ScholarDigital Library
28. B. K. Natarajan. 1995. Sparse Approximate Solutions to Linear Systems. SIAM J. Comput. 24, 2 (1995), 227–234.Google ScholarDigital Library
29. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Trans. Graph. 37, 1 (2017), 5:1–5:14.Google ScholarDigital Library
30. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal Cone Singularities for Conformal Flattening. ACM Trans. Graph. 37, 4 (2018).Google ScholarDigital Library
31. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal Equivalence of Triangle Meshes. ACM Trans. Graph. 27, 3 (2008), 1–11.Google ScholarDigital Library
32. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional field synthesis, design, and processing. Comput. Graph. Forum 35, 2 (2016), 545–572.Google ScholarCross Ref
33. Ke Wang, Yiying Tong, Mathieu Desbrun, and Peter Schröder. 2006. Edge subdivision schemes and the construction of smooth vector fields. ACM Transactions on Graphics (TOG) 25, 3 (2006), 1041–1048.Google ScholarDigital Library
34. Baoyuan Wu and Bernard Ghanem. 2018. ℓP-Box ADMM: A Versatile Framework for Integer Programming. IEEE transactions on pattern analysis and machine intelligence 41, 7 (2018), 1695–1708.Google Scholar
35. Li Xu, Cewu Lu, Yi Xu, and Jiaya Jia. 2011. Image smoothing via ℓ 0 gradient minimization. In Proceedings of the 2011 SIGGRAPH Asia Conference. 1–12.Google ScholarDigital Library
36. Tianyu Zhu, Chunyang Ye, Shuangming Chai, and Xiao-Ming Fu. 2020. Greedy Cut Construction for Parameterizations. Comput. Graph. Forum 39, 2 (2020), 191–202.Google ScholarCross Ref