“Discrete conformal equivalence of polyhedral surfaces” by Gillespie, Springborn and Crane

This paper describes a numerical method for surface parameterization, yielding maps that are locally injective and discretely conformal in an exact sense. Unlike previous methods for discrete conformal parameterization, the method is guaranteed to work for any manifold triangle mesh, with no restrictions on triangulatiothat each task can be formulated as a convex problem where the triangulation is allowed to change—we complete the picture by introducing the machinery needed to actually construct a discrete conformal map. In particular, we introduce a new scheme for tracking correspondence between triangulations based on normal coordinates, and a new interpolation procedure based on layout in the light cone. Stress tests involving difficult cone configurations and near-degenerate triangulations indicate that the method is extremely robust in practice, and provides high-quality interpolation even on meshes with poor elements.

1. William Abikoff. 1981. The Uniformization Theorem. The American Mathematical Monthly 88, 8 (1981).Google Scholar
2. Ian Agol, Joel Hass, and William Thurston. 2006. The Computational Complexity of Knot Genus and Spanning Area. Trans. Amer. Math. Soc. 358, 9 (2006).Google Scholar
3. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Transactions on Graphics 35, 6 (2016).Google ScholarDigital Library
4. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted Bijections for Low Distortion Surface Mappings. ACM Transactions on Graphics 33, 4 (2014).Google ScholarDigital Library
5. DV Alekseevskij, Eh B Vinberg, and AS Solodovnikov. 1993. Geometry of Spaces of Constant Curvature. In Geometry II. Springer.Google Scholar
6. Alex Baden, Keenan Crane, and Misha Kazhdan. 2018. Möbius Registration. Computer Graphics Forum 37, 5 (2018).Google Scholar
7. Satish Balay, Shrirang Abhyankar, Mark F. Adams, Jed Brown, Peter Brune, Kris Buschelman, Lisandro Dalcin, Alp Dener, Victor Eijkhout, William D. Gropp, Dmitry Karpeyev, Dinesh Kaushik, Matthew G. Knepley, Dave A. May, Lois Curfman McInnes, Richard Tran Mills, Todd Munson, Karl Rupp, Patrick Sanan, Barry F. Smith, Stefano Zampini, Hong Zhang, and Hong Zhang. 2019. PETSc Users Manual. Technical Report ANL-95/11 – Revision 3.11. Argonne National Laboratory.Google Scholar
8. Satish Balay, William D. Gropp, Lois Curfman McInnes, and Barry F. Smith. 1997. Efficient Management of Parallelism in Object Oriented Numerical Software Libraries. In Modern Software Tools in Scientific Computing, E. Arge, A. M. Bruaset, and H. P. Langtangen (Eds.). Birkhäuser Press.Google ScholarDigital Library
9. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. In Computer Graphics Forum, Vol. 27.Google ScholarCross Ref
10. Steve Benson, Lois Curfman McInnes, Jorge J More, and Jason Sarich. 2003. TAO Users Manual. Technical Report. Argonne National Lab., IL (US).Google Scholar
11. Pierre Blanchard, Desmond J Higham, and Nicholas J Higham. 2019. Accurate Computation of the Log-Sum-Exp and Softmax Functions. arXiv preprint (2019).Google Scholar
12. Alexander I Bobenko, Ulrich Pinkall, and Boris A Springborn. 2015. Discrete Conformal Maps and Ideal Hyperbolic Polyhedra. Geometry & Topology 19, 4 (2015).Google Scholar
13. Alexander I Bobenko, Stefan Sechelmann, and Boris Springborn. 2016. Discrete Conformal Maps: Boundary Value Problems, Circle Domains, Fuchsian and Schottky Uniformization. In Advances in Discrete Differential Geometry. Springer.Google Scholar
14. Alexander I Bobenko and Boris A Springborn. 2007. A Discrete Laplace-Beltrami Operator for Simplicial Surfaces. Disc. & Comp. Geom. 38, 4 (2007).Google Scholar
15. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Lévy. 2010. Polygon Mesh Processing. CRC press.Google Scholar
16. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge university press.Google ScholarDigital Library
17. Doug M Boyer, Yaron Lipman, Elizabeth St Clair, Jesus Puente, Biren A Patel, Thomas Funkhouser, Jukka Jernvall, and Ingrid Daubechies. 2011. Algorithms to Automatically Quantify the Geometric Similarity of Anatomical Surfaces. Proceedings of the National Academy of Sciences 108, 45 (2011).Google Scholar
18. Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic Global Parametrization with Rational Holonomy. ACM Transactions on Graphics 36, 4 (2017).Google ScholarDigital Library
19. Kevin Q Brown. 1979. Voronoi Diagrams from Convex Hulls. Information processing letters 9, 5 (1979).Google Scholar
20. Ulrike Bücking. 2016. Approximation of Conformal Mappings Using Conformally Equivalent Triangular Lattices. In Adv. in Disc. Diff. Geom. Springer.Google Scholar
21. Ulrike Bücking. 2018. C∞-Convergence of Conformal Mappings for Conformally Equivalent Triangular Lattices. Results in Mathematics 73, 2 (2018).Google Scholar
22. Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, and Denis Zorin. 2021. Efficient and Robust Discrete Conformal Equivalence with Boundary. (2021). arXiv:cs.CG/2104.04614Google Scholar
23. Marcel Campen, Hanxiao Shen, Jiaran Zhou, and Denis Zorin. 2019. Seamless Parametrization with Arbitrary Cones for Arbitrary Genus. ACM Transactions on Graphics 39, 1 (2019).Google Scholar
24. Marcel Campen and Denis Zorin. 2017a. On Discrete Conformal Seamless Similarity Maps. arXiv preprint (2017).Google Scholar
25. Marcel Campen and Denis Zorin. 2017b. Similarity Maps and Field-Guided T-Splines: A Perfect Couple. ACM Transactions on Graphics 36, 4 (2017).Google ScholarDigital Library
26. James W Cannon, William J Floyd, Richard Kenyon, Walter R Parry, et al. 1997. Hyperbolic Geometry. Flavors of geometry 31 (1997).Google Scholar
27. Pafnutĭ L’vovich Chebyshev. 1899. Œuvres de P.L. Tchebychef. Vol. 1. Commissionaires de l’Académie Impériale des Sciences.Google Scholar
28. Wei Chen, Min Zhang, Na Lei, and Xianfeng David Gu. 2016. Dynamic Unified Surface Ricci Flow. Geom., Img. and Com. 3, 1 (2016).Google Scholar
29. Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. ACM Transactions on Mathematical Software (TOMS) 35, 3 (2008).Google ScholarDigital Library
30. Edward Chien, Zohar Levi, and Ofir Weber. 2016. Bounded Distortion Parametrization in the Space of Metrics. ACM Transactions on Graphics 35, 6 (2016).Google ScholarDigital Library
31. Keenan Crane. 2020. An Excursion through Discrete Differential Geometry. Proceedings of Symposia in Applied Mathematics, Vol. 76. American Mathematical Society, Chapter Conformal Geometry of Simplicial Surfaces.Google Scholar
32. Keenan Crane, Fernando de Goes, Mathieu Desbrun, and Peter Schröder. 2013a. Digital Geometry Processing with Discrete Exterior Calculus. In ACM SIGGRAPH 2013 Courses (SIGGRAPH ’13). ACM, New York, NY, USA, Article 7.Google ScholarDigital Library
33. Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013b. Robust Fairing via Conformal Curvature Flow. ACM Trans. Graph. 32, 4 (2013).Google ScholarDigital Library
34. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic Parameterizations of Surface Meshes. In Computer Graphics Forum, Vol. 21.Google ScholarCross Ref
35. Nadav Dym, Raz Slutsky, and Yaron Lipman. 2019. Linear Variational Principle for Riemann Mappings and Discrete Conformality. Proceedings of the National Academy of Sciences 116, 3 (2019).Google ScholarCross Ref
36. Jeff Erickson and Amir Nayyeri. 2013. Tracing Compressed Curves in Triangulated Surfaces. Discrete & Computational Geometry 49, 4 (2013).Google Scholar
37. François Fillastre. 2008. Polyhedral Hyperbolic Metrics on Surfaces. Geometriae Dedicata 134, 1 (2008).Google Scholar
38. Matthew Fisher, Boris Springborn, Peter Schröder, and Alexander I Bobenko. 2007. An Algorithm for the Construction of Intrinsic Delaunay Triangulations with Applications to Digital Geometry Processing. Computing 81, 2-3 (2007).Google ScholarDigital Library
39. Mark Galassi, Jim Davies, James Theiler, Brian Gough, Gerard Jungman, Patrick Alken, Michael Booth, Fabrice Rossi, and Rhys Ulerich. 1994. GNU Scientific Library. Vol. 20. ACM New York, NY, USA.Google Scholar
40. Xianfeng David Gu, Feng Luo, Jian Sun, and Tianqi Wu. 2018a. A Discrete Uniformization Theorem for Polyhedral Surfaces. Journal of Differential Geometry 109, 2 (2018).Google Scholar
41. Xianfeng David Gu, Ren Guo, Feng Luo, Jian Sun, and Tianqi Wu. 2018b. A Discrete Uniformization Theorem for Polyhedral Surfaces II. Journal of Differential Geometry 109, 3 (2018).Google Scholar
42. Xianfeng David Gu, Feng Luo, and Tianqi Wu. 2019. Convergence of Discrete Conformal Geometry and Computation of Uniformization Maps. Asian Journal of Mathematics 23, 1 (2019).Google ScholarCross Ref
43. Xianfeng David Gu, Feng Luo, and Shing-Tung Yau. 2020. Computational Conformal Geometry behind Modern Technologies. Notices of the American Mathematical Society 67, 10 (2020).Google Scholar
44. Xianfeng David Gu, Yalin Wang, Tony F Chan, Paul M Thompson, and Shing-Tung Yau. 2004. Genus Zero Surface Conformal Mapping and Its Application to Brain Surface Mapping. IEEE transactions on medical imaging 23, 8 (2004).Google ScholarCross Ref
45. Wolfgang Haken. 1961. Theorie Der Normalflächen: Ein Isotopiekriterium Für Den Kreisknoten. Acta Mathematica 105, 3-4 (1961).Google ScholarCross Ref
46. A. Hatcher. 2002. Algebraic Topology. Cambridge University Press.Google Scholar
47. Eden Fedida Hefetz, Edward Chien, and Ofir Weber. 2019. A Subspace Method for Fast Locally Injective Harmonic Mapping. In Computer Graphics Forum, Vol. 38.Google ScholarCross Ref
48. David Hilbert. 1901. Ueber Flächen von Constanter Gaussscher Krümmung. Trans. Amer. Math. Soc. 2, 1 (1901).Google Scholar
49. Claude Indermitte, Th M Liebling, Marc Troyanov, and Heinz Clémençon. 2001. Voronoi Diagrams on Piecewise Flat Surfaces and an Application to Biological Growth. Theoretical Computer Science 263, ARTICLE (2001).Google Scholar
50. Miao Jin, Yalin Wang, Shing-Tung Yau, and Xianfeng David Gu. 2004. Optimal Global Conformal Surface Parameterization. In IEEE Visualization 2004.Google ScholarDigital Library
51. Michael Kazhdan, Jake Solomon, and Mirela Ben-Chen. 2012. Can Mean-Curvature Flow Be Modified to Be Non-Singular?. In Computer Graphics Forum, Vol. 31.Google ScholarDigital Library
52. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete Conformal Mappings via Circle Patterns. ACM Transactions on Graphics 25, 2 (2006).Google ScholarDigital Library
53. Hellmuth Kneser. 1929. Geschlossene Flächen in Dreidimensionalen Mannigfaltigkeiten. Jahresbericht der Deutschen Mathematiker-Vereinigung 38 (1929).Google Scholar
54. Patrice Koehl and Joel Hass. 2015. Landmark-Free Geometric Methods in Biological Shape Analysis. Journal of The Royal Society Interface 12, 113 (2015).Google ScholarCross Ref
55. 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).Google ScholarDigital Library
56. Zohar Levi and Denis Zorin. 2014. Strict Minimizers for Geometric Optimization. ACM Transactions on Graphics 33, 6 (2014).Google ScholarDigital Library
57. 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 21, 3 (2002).Google ScholarDigital Library
58. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Transactions on Graphics 31, 4 (2012).Google ScholarDigital Library
59. Yaron Lipman and Ingrid Daubechies. 2011. Conformal Wasserstein Distances: Comparing Surfaces in Polynomial Time. Advances in Mathematics 227, 3 (2011).Google Scholar
60. Feng Luo. 2004. Combinatorial Yamabe Flow on Surfaces. Communications in Contemporary Mathematics 6, 5 (2004).Google Scholar
61. Richard H MacNeal. 1949. The Solution of Partial Differential Equations by Means of Electrical Networks. Ph.D. Dissertation. California Institute of Technology.Google Scholar
62. Manish Mandad and Marcel Campen. 2019. Exact Constraint Satisfaction for Truly Seamless Parametrization. In Computer Graphics Forum, Vol. 38.Google ScholarCross Ref
63. 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
64. Lee Mosher. 1988. Tiling the Projective Foliation Space of a Punctured Surface. Trans. Amer. Math. Soc. (1988).Google Scholar
65. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral Conformal Parameterization. In Computer Graphics Forum, Vol. 27.Google ScholarCross Ref
66. Todd Munson, Jason Sarich, Stefan Wild, Steve Benson, and Lois Curfman McInnes. 2014. Toolkit for Advanced Optimization (TAO) Users Manual. Technical Report ANL/MCS-TM-322 – Revision 3.5. Argonne National Laboratory.Google Scholar
67. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-Aligned Global Parametrization. ACM Transactions on Graphics 33, 4 (2014).Google ScholarDigital Library
68. Robert C. Penner. 2012. Decorated Teichmüller Theory. European Mathematical Society (EMS), Zürich.Google Scholar
69. Roman Prosanov. 2020. Ideal Polyhedral Surfaces in Fuchsian Manifolds. Geometriae Dedicata 206 (2020).Google Scholar
70. Igor Rivin. 1994. Intrinsic Geometry of Convex Ideal Polyhedra in Hyperbolic 3-Space. In Analysis, Algebra, and Computers in Mathematical Research (Luleå, 1992). Lect. Notes Pure Appl. Math., Vol. 156.Google Scholar
71. Igor Rivin. 1996. A Characterization of Ideal Polyhedra in Hyperbolic 3-Space. Annals of Mathematics. Second Series 143, 1 (1996).Google Scholar
72. M. Roček and R. M. Williams. 1984. The Quantization of Regge Calculus. Zeitschrift für Physik C Particles and Fields 21, 4 (1984).Google Scholar
73. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Transactions on Graphics 37, 1 (2017).Google Scholar
74. Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. 2002. Algorithms for Normal Curves and Surfaces. In International Computing and Combinatorics Conference.Google Scholar
75. Nick Sharp and Keenan Crane. 2018. Variational Surface Cutting. ACM Trans. Graph. 37, 4 (2018).Google ScholarDigital Library
76. Nicholas Sharp and Keenan Crane. 2020. A Laplacian for Nonmanifold Triangle Meshes. In Computer Graphics Forum, Vol. 39.Google ScholarCross Ref
77. Nicholas Sharp, Keenan Crane, et al. 2019a. Geometry-Central. (2019).Google Scholar
78. Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019b. Navigating Intrinsic Triangulations. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
79. Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019c. The Vector Heat Method. ACM Trans. Graph. 38, 3 (2019).Google ScholarDigital Library
80. Alla Sheffer, Bruno Lévy, Maxim Mogilnitsky, and Alexander Bogomyakov. 2005. ABF++: Fast and Robust Angle Based Flattening. ACM Transactions on Graphics 24, 2 (2005).Google ScholarDigital Library
81. Hanxiao Shen, Zhongshi Jiang, Denis Zorin, and Daniele Panozzo. 2019. Progressive Embedding. ACM Transactions on Graphics 38, 4 (2019).Google ScholarDigital Library
82. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal Cone Singularities for Conformal Flattening. ACM Trans. Graph. 37, 4 (2018).Google ScholarDigital Library
83. Boris Springborn. 2019. Ideal Hyperbolic Polyhedra and Discrete Uniformization. Discrete & Computational Geometry (2019).Google Scholar
84. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal Equivalence of Triangle Meshes. In ACM SIGGRAPH 2008 Papers.Google Scholar
85. Jian Sun, Tianqi Wu, Xianfeng David Gu, and Feng Luo. 2015. Discrete Conformal Deformation: Algorithm and Experiments. SIAM Journal on Imaging Sciences 8, 3 (2015).Google Scholar
86. Dylan Thurston and Qiaochu Yuan. 2012. Notes on Curves on Surfaces. (2012).Google Scholar
87. Marc Troyanov. 1991. Prescribing Curvature on Compact Surfaces with Conical Singularities. Trans. Amer. Math. Soc. 324, 2 (1991).Google Scholar
88. Ana Maria Vintescu, Florent Dupont, and Guillaume Lavoué. 2017. Least Squares Affine Transitions for Global Parameterization. (2017).Google Scholar
89. Tianqi Wu. 2014. Finiteness of Switches in Discrete Yamabe Flow. Ph.D. Dissertation. Tsinghua University.Google Scholar
90. BT Thomas Yeo, Mert R Sabuncu, Tom Vercauteren, Nicholas Ayache, Bruce Fischl, and Polina Golland. 2009. Spherical Demons: Fast Diffeomorphic Landmark-Free Surface Registration. IEEE transactions on medical imaging 29, 3 (2009).Google Scholar
91. Xiaokang Yu, Na Lei, Yalin Wang, and Xianfeng David Gu. 2017. Intrinsic 3D Dynamic Surface Tracking Based on Dynamic Ricci Flow and Teichmuller Map. In IEEE Vis.Google Scholar
92. Min Zhang, Ren Guo, Wei Zeng, Feng Luo, Shing-Tung Yau, and Xianfeng David Gu. 2014. The Unified Discrete Surface Ricci Flow. Graphical Models 76, 5 (2014).Google Scholar
93. Jiaran Zhou, Changhe Tu, Denis Zorin, and Marcel Campen. 2020. Combinatorial Construction of Seamless Parameter Domains. In Computer Graphics Forum, Vol. 39.Google ScholarCross Ref