“Optimal cone singularities for conformal flattening” by Soliman, Slepcev and Crane

  • ©Yousuf Soliman, Dejan Slepcev, and Keenan Crane



Entry Number: 105

Session Title:

    Flattening, Unflattening and Sampling


    Optimal cone singularities for conformal flattening




    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.


    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

ACM Digital Library Publication: