“Computing sparse cones with bounded distortion for conformal parameterizations” by Fang, Ouyang, Li, Liu and Fu
Conference:
Type(s):
Title:
- Computing sparse cones with bounded distortion for conformal parameterizations
Session/Category Title: Surface Parameterization and Texturing
Presenter(s)/Author(s):
Abstract:
We propose a novel method to generate sparse cone singularities with bounded distortion constraints for conformal parameterizations. It is formulated as minimizing the ℓ0-norm of Gaussian curvature of vertices with hard constraints of bounding the distortion that is measured by the ℓ2-norm of the log conformal factor. We use the reweighted ℓ1-norm to approximate the ℓ0-norm and solve each convex weighted ℓ1 minimization subproblem by the Douglas-Rachford (DR) splitting scheme. To quickly generate sparse cones, we modify DR splitting by weighting the ℓ2-norm of the proximal mapping to force the small Gaussian curvature to quickly approach zero. Accordingly, compared with the conventional DR splitting, the modified method performs one to two orders of magnitude faster. Besides, we perform variable substitution of log conformal factors to simplify the computation process for acceleration. Our algorithm is able to bound distortion to compute sparse cone singularities, so that the resulting conformal parameterizations achieve a favorable tradeoff between the area distortion and the number of cones. We demonstrate its effectiveness and feasibility on a large number of models.
References:
1. P. Alliez, E. C. de Verdire, O. Devillers, and M. Isenburg. 2003. Isotropic surface remeshing. In 2003 Shape Modeling International. 49–58.
2. 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.
3. Thierry Aubin. 2013. Some nonlinear problems in Riemannian geometry. Springer Science & Business Media.
4. Sebahattin Bektas. 2014. Orthogonal distance from an ellipsoid. Boletim de Ciěncias Geodésicas 20 (10 2014), 970–983.
5. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. Comput. Graph. Forum 27, 2 (2008), 449–458.
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. Comput. Graph. Forum 32, 6 (2013), 51–76.
7. Guy Bunin. 2008. A continuum theory for unstructured mesh generation in two dimensions. Comput. Aided Geom. Des. 25, 1 (2008).
8. T Tony Cai and Anru Zhang. 2013. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Trans. Inf. Theory 60, 1 (2013), 122–132.
9. Marcel Campen, Hanxiao Shen, Jiaran Zhou, and Denis Zorin. 2019. Seamless Parametrization with Arbitrary Cones for Arbitrary Genus. ACM Trans. Graph. 39, 1 (2019).
10. Emmanuel J Candes, Michael B Wakin, and Stephen P Boyd. 2008. Enhancing sparsity by reweighted ℓ1 minimization. J. Fourier Anal. Appl. 14, 5-6 (2008), 877–905.
11. S. Chai, X.-M. Fu, X. Hu, Y. Yang, and L. Liu. 2018. Sphere-based Cut Construction for Planar Parameterizations. Comput. Graph. 74 (2018), 66–75.
12. Shuangming Chai, Xiao-Ming Fu, and Ligang Liu. 2021. Voting for Distortion Points in Geometric Processing. IEEE. T. Vis. Comput. Gr. 27, 4 (2021), 2469–2480.
13. Keenan Crane. 2019. The n-dimensional cotangent formula. https://www.cs.cmu.edu/kmcrane/Projects/Other/nDCotanFormula.pdf.
14. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic Parameterizations of Surface Meshes. Comput. Graph. Forum (2002).
15. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable polyvector fields. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–12.
16. 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.
17. Qing Fang, Zheng-Yu Zhao, Zhong-Yuan Liu, Ligang Liu, and Xiao-Ming Fu. 2020. Metric first reconstruction for interactive curvature-aware modeling. Computer-Aided Design 126 (2020), 102863.
18. Nahum Farchi and Mirela Ben-Chen. 2018. Integer-only cross field computation. ACM Trans. Graph. 37, 4 (2018), 1–13.
19. Michel Fortin and Roland Glowinski. 2000. Augmented Lagrangian methods: applications to the numerical solution of boundary-value problems.
20. Simon Foucart and Ming-Jun Lai. 2009. Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0 < q ≤ 1. Appl. Comput. Harmon. Anal. 26, 3 (2009), 395–407.
21. Xiao-Ming Fu, Jian-Ping Su, Zheng-Yu Zhao, Qing Fang, Chunyang Ye, and Ligang Liu. 2021. Inversion-free geometric mapping construction: A survey. Computational Visual Media 7, 3 (2021), 289–318.
22. Pontus Giselsson and Stephen Boyd. 2017. Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM. IEEE Trans. Automat. Control 62, 2 (2017), 532–544.
23. Xianfeng Gu, Steven J. Gortler, and Hugues Hoppe. 2002. Geometry Images. ACM Trans. Graph. 21, 3 (2002), 355–361.
24. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
25. Lei He and Scott Schaefer. 2013. Mesh denoising via ℓ 0 minimization. ACM Trans. Graph. 32, 4 (2013).
26. Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun. 2014. ℓ1-Based Construction of Polycube Maps from Complex Shapes. ACM Trans. Graph. 33, 3 (2014).
27. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412–438.
28. Yu N Kiseliov. 1994. Algorithms of projection of a point onto an ellipsoid. Lithuanian Mathematical Journal 34, 2 (1994), 141–159.
29. Mina Konaković, Keenan Crane, Bailin Deng, Sofien Bouaziz, Daniel Piker, and Mark Pauly. 2016. Beyond Developable: Computational Design and Fabrication with Auxetic Materials. ACM Trans. Graph. 35, 4 (2016).
30. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (2002), 362–371.
31. Hao-Yu Liu, Xiao-Ming Fu, Chunyang Ye, Shuangming Chai, and Ligang Liu. 2019. Atlas Refinement with Bounded Packing Efficiency. ACM Trans. Graph. 38, 4 (2019).
32. 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.
33. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4 (2012), 1–11.
34. B. K. Natarajan. 1995. Sparse Approximate Solutions to Linear Systems. SIAM J. Comput. 24, 2 (1995), 227–234.
35. Wenqing Ouyang, Yue Peng, Yuxin Yao, Juyong Zhang, and Bailin Deng. 2020. Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting. Comput. Graph. Forum 39, 5 (2020), 221–239.
36. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Trans. Graph. 37, 1 (2017), 5:1–5:14. Aviv Segall, Orestis Vantzos, and Mirela Ben-Chen. 2016. Hele-Shaw Flow Simulation with Interactive Control using Complex Barycentric Coordinates. In Eurographics/ACM SIGGRAPH Symposium on Computer Animation.
37. Alla Sheffer. 2002. Spanning tree seams for reducing parameterization distortion of triangulated surfaces. In Shape Modeling International. 61–66.
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.
39. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal Cone Singularities for Conformal Flattening. ACM Trans. Graph. 37, 4 (2018).
40. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal Equivalence of Triangle Meshes. ACM Trans. Graph. 27, 3 (2008), 1–11.
41. Jian-Ping Su, Chunyang Ye, Ligang Liu, and Xiao-Ming Fu. 2020. Efficient bijective parameterizations. ACM Trans. Graph. 39, 4 (2020).
42. W. Tong, X. Yang, M. Pan, and F. Chen. 2020. Spectral Mesh Segmentation via ℓ0 Gradient Minimization. IEEE. T. Vis. Comput. Gr. 26, 4 (2020), 1807–1820.
43. 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.
44. Baoyuan Wu and Bernard Ghanem. 2018. ℓp-Box ADMM: A Versatile Framework for Integer Programming. IEEE Trans. Pattern Anal. Mach. Intell. 41, 7 (2018), 1695–1708.
45. Li Xu, Cewu Lu, Yi Xu, and Jiaya Jia. 2011. Image smoothing via ℓ0 gradient minimization. ACM Trans. Graph. 30, 6 (2011).
46. Linlin Xu, Ruimin Wang, Juyong Zhang, Zhouwang Yang, Jiansong Deng, Falai Chen, and Ligang Liu. 2015. Survey on sparsity in geometric modeling and processing. Graphical Models 82 (2015), 160 — 180.
47. Chi Zhang, Mao-Feng Xu, Shuangming Chai, and Xiao-Ming Fu. 2020. Robust Atlas Generation via Angle-based Segmentation. Comput. Aided Geom. Des. 79 (2020), 101854.
48. Yun-Bin Zhao. 2018. Sparse optimization theory and methods. CRC Press.
49. Zichun Zhong, Liang Shuai, Miao Jin, and Xiaohu Guo. 2014. Anisotropic surface meshing with conformal embedding. Graphical Models 76, 5 (2014), 468 — 483.
50. Tianyu Zhu, Chunyang Ye, Shuangming Chai, and Xiao-Ming Fu. 2020. Greedy Cut Construction for Parameterizations. Comput. Graph. Forum 39, 2 (2020), 191–202.
