“Optimal cone singularities for conformal flattening” by Soliman, Slepcev and Crane
Conference:
Type(s):
Entry Number: 105
Title:
- Optimal cone singularities for conformal flattening
Session/Category Title: Flattening, Unflattening and Sampling
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Angle-preserving or conformal surface parameterization has proven to be a powerful tool across applications ranging from geometry processing, to digital manufacturing, to machine learning, yet conformal maps can still suffer from severe area distortion. Cone singularities provide a way to mitigate this distortion, but finding the best configuration of cones is notoriously difficult. This paper develops a strategy that is globally optimal in the sense that it minimizes total area distortion among all possible cone configurations (number, placement, and size) that have no more than a fixed total cone angle. A key insight is that, for the purpose of optimization, one should not work directly with curvature measures (which naturally represent cone configurations), but can instead apply Fenchel-Rockafellar duality to obtain a formulation involving only ordinary functions. The result is a convex optimization problem, which can be solved via a sequence of sparse linear systems easily built from the usual cotangent Laplacian. The method supports user-defined notions of importance, constraints on cone angles (e.g., positive, or within a given range), and sophisticated boundary conditions (e.g., convex, or polygonal). We compare our approach to previous techniques on a variety of challenging models, often achieving dramatically lower distortion, and demonstrating that global optimality leads to extreme robustness in the presence of noise or poor discretization.
References:
1. Noam Aigerman, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Spherical Orbifold Tutte Embeddings. ACM Trans. Graph. 36, 4 (2017). Google ScholarDigital Library
2. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM Trans. Graph. 34, 6 (2015). Google ScholarDigital Library
3. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. 35, 6 (2016). Google ScholarDigital Library
4. Luigi Ambrosio, Edoardo Mainini, and Sylvia Serfaty. 2011. Gradient flow of the Chapman-Rubinstein-Schatzman model for signed vortices. In Annales de l’Institut Henri Poincare Non Linear Analysis, Vol. 28.Google Scholar
5. Thierry Aubin. 1998. Some nonlinear problems in Riemannian geometry. Springer Science & Business Media.Google Scholar
6. Heinz H Bauschke and Patrick L Combettes. 2017. Convex Analysis and Monotone Operator Theory in Hubert Spaces. Springer. Google ScholarDigital Library
7. 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
8. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4 (2013). Google ScholarDigital Library
9. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing. (2013).Google Scholar
10. Haim Brezis. 2010. Functional analysis, Sobolev spaces and partial differential equations. Springer Science & Business Media.Google Scholar
11. Eduardo Casas, Christian Clason, and Karl Kunisch. 2012. Approximation of elliptic control problems in measure spaces with sparse solutions. SIAM Journal on Control and Optimization 50, 4 (2012).Google ScholarCross Ref
12. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A Simple Geometric Model for Elastic Deformations. ACM Trans. Graph. 29, 4 (2010). Google ScholarDigital Library
13. Xiaojun Chen, Zuhair Nashed, and Liqun Qi. 2000. Smoothing methods and semismooth methods for nondifferentiable operator equations. SIAM J. Numer. Anal. 38, 4 (2000). Google ScholarDigital Library
14. Christian Clason and Karl Kunisch. 2012. A measure space approach to optimal source placement. Computational Optimization and Applications 53, 1 (2012). Google ScholarDigital Library
15. Christian Clason and Anton Schiela. 2017. Optimal control of elliptic equations with positive measures. ESAIM: Cont., Opt. and Calc. of Var. 23, 1 (2017).Google Scholar
16. Teresa D’Aprile, Francesca De Marchis, and Isabella Ianni. 2016. Prescribed Gauss curvature problem on singular surfaces. arXiv preprint arXiv:1612.03657 (2016).Google Scholar
17. Francesca De Marchis and Rafael López-Soriano. 2016. Existence and non existence results for the singular Nirenberg problem. Calculus of Variations and Partial Differential Equations 55, 2 (2016).Google Scholar
18. Manuel Del Pino and Carlos Román. 2015. Large conformal metrics with prescribed sign-changing Gauss curvature. Calculus of Variations and Partial Differential Equations 54, 1 (2015).Google Scholar
19. Jeff Erickson and Sariel Har-Peled. 2004. Optimally cutting a surface into a disk. Discrete & Computational Geometry 31, 1 (2004). Google ScholarDigital Library
20. James S. Gao, Alexander G. Huth, Mark D. Lescroart, and Jack L. Gallant. 2015. Pycortex: an interactive surface visualizer for fMRI. Front. in Neuro. 9 (2015).Google Scholar
21. Andreas Günther and Moulay Hicham Tber. 2016. A goal-oriented adaptive Moreau-Yosida algorithm for control-and state-constrained elliptic control problems. Advances in Applied Mathematics and Mechanics 8, 3 (2016).Google Scholar
22. Lester La Verne Helms. 2009. Potential theory. Springer.Google Scholar
23. Heinrich Hencky. 1928. Über die Form des Elastizitätsgesetzes bei ideal elastischen Stoffen. Zeitschrift für technische Physik 9 (1928).Google Scholar
24. M. Hintermüller, K. Ito, and K. Kunisch. 2002. The Primal-Dual Active Set Strategy As a Semismooth Newton Method. SIAM J. on Optimization 13, 3 (2002). Google ScholarDigital Library
25. Michael Hinze. 2005. A Variational Discretization Concept in Control Constrained Optimization: The Linear-Quadratic Case. Comp. Opt. and Appl. 30, 1 (2005). Google ScholarDigital Library
26. Kazufumi Ito and Karl Kunisch. 2003a. Semi-smooth Newton methods for state-constrained optimal control problems. Systems & Control Letters 50, 3 (2003).Google ScholarCross Ref
27. Kazufumi Ito and Karl Kunisch. 2003b. Semi-smooth Newton methods for variational inequalities of the first kind. ESAIM: Math. Model. and Num. Anal. 37, 1 (2003).Google Scholar
28. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete Conformal Mappings via Circle Patterns. ACM Trans. Graph. 25, 2 (2006). Google ScholarDigital Library
29. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. ACM Trans. Graph. 32, 4 (2013). Google ScholarDigital Library
30. Mina Konakovic, 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). Google ScholarDigital Library
31. Walter Littman, Guido Stampacchia, and Hans F Weinberger. 1963. Regular points for elliptic equations with discontinuous coefficients. Annali della Scuola Normale Superiore di Pisa-Classe di Scienze 17, 1–2 (1963).Google Scholar
32. Richard MacNeal. 1949. The Solution of Partial Differential Equations by Means of Electrical Networks. Ph.D. Dissertation. California Institute of Technology.Google Scholar
33. E. Mainini. 2012. A description of transport cost for signed measures. Journal of Mathematical Sciences 181 (2012).Google Scholar
34. Haggai Maron, Meirav Galun, Noam Aigerman, Miri Trope, Nadav Dym, Ersin Yumer, Vladimir G. Kim, and Yaron Lipman. 2017. Convolutional Neural Networks on Surfaces via Seamless Toric Covers. ACM Trans. Graph. 36, 4 (2017). Google ScholarDigital Library
35. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Transactions on Graphics (TOG) 31, 4 (2012). Google ScholarDigital Library
36. Ashish Myles and Denis Zorin. 2013. Controlled-distortion constrained global parametrization. ACM Transactions on Graphics (TOG) 32, 4 (2013). Google ScholarDigital Library
37. Herzog Roland and Kunisch Karl. 2010. Algorithms for PDE-constrained optimization. GAMM-Mitteilungen 33, 2 (2010), 163–176.Google ScholarCross Ref
38. E.B. Saff and V. Totik. 1997. Logarithmic Potentials with External Fields. Springer Berlin Heidelberg.Google Scholar
39. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Trans. Graph. 37, 1 (2017). Google ScholarDigital Library
40. Ryan Schmidt and Karan Singh. 2010. Meshmixer: An Interface for Rapid Mesh Composition. In ACM SIGGRAPH 2010 Talks (SIGGRAPH ’10). Google ScholarDigital Library
41. Nick Sharp and Keenan Crane. 2018. Variational Surface Cutting. ACM Trans. Graph. 37, 4 (2018). Google ScholarDigital Library
42. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh Parameterization Methods and Their Applications. Found. Trends. Comput. Graph. Vis. 2, 2 (2006). Google ScholarDigital Library
43. Yousuf Soliman. 2018. Conformal Cone Parameterization through Optimal Control. Master’s thesis. Carnegie Mellon University.Google Scholar
44. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible Surface Modeling. In Proc. Symp. Geom. Proc. (SGP ’07). Google ScholarDigital Library
45. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. In ACM Transactions on Graphics (TOG), Vol. 27. Google ScholarDigital Library
46. Guido Stampacchia. 1965. Le problème de Dirichlet pour les équations elliptiques du second ordre à coefficients discontinus. Ann. Inst. Fourier 15, 1 (1965).Google Scholar
47. William Thurston. 2002. The Geometry and Topology of 3-Manifolds. (2002).Google Scholar
48. Marc Troyanov. 1989. Metrics of constant curvature on a sphere with two conical singularities. Lect. Notes Math 1410 (1989).Google Scholar
49. Marc Troyanov. 1991. Prescribing curvature on compact surfaces with conical singularities. Trans. Amer. Math. Soc. 324, 2 (1991).Google ScholarCross Ref
50. 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 Information Processing in Medical Imaging. Google ScholarDigital Library
51. M. Ulbrich. 2002. Nonsmooth Newton-like Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, Habilitationsschrift. Fakultät für Mathematik, Technische Universität München, Germany.Google Scholar
52. Michael Ulbrich. 2011. Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. Google ScholarDigital Library
53. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. Computer Graphics Forum (2016).Google Scholar
54. Ana Vintescu, Florent Dupont, Guillaume Lavoué, Pooran Memari, and Julien Tierny. 2017a. Least Squares Affine Transitions for Global Parameterization. In WSCG 2017 5th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2017.Google Scholar
55. Ana-Maria Vintescu, Florent Dupont, Guillaume Lavoué, Pooran Memari, and Julien Tierny. 2017b. Conformal Factor Persistence for Fast Hierarchical Cone Extraction. In Eurographics Short Papers.Google Scholar
56. Eugene Zhang, Konstantin Mischaikow, and Greg Turk. 2005. Feature-based Surface Parameterization and Texture Mapping. ACM Trans. Graph. 24, 1 (2005). Google ScholarDigital Library
