Conformal equivalence of triangle meshes

ABSTRACT

We present a new algorithm for conformal mesh parameterization. It is based on a precise notion of discrete conformal equivalence for triangle meshes which mimics the notion of conformal equivalence for smooth surfaces. The problem of finding a flat mesh that is discretely conformally equivalent to a given mesh can be solved efficiently by minimizing a convex energy function, whose Hessian turns out to be the well known cot-Laplace operator. This method can also be used to map a surface mesh to a parameter domain which is flat except for isolated cone singularities, and we show how these can be placed automatically in order to reduce the distortion of the parameterization. We present the salient features of the theory and elaborate the algorithms with a number of examples.

REFERENCES

• 1: Balay, S., Buschelman, K., Eijkhout, V., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2007. PETSc Users Manual. Tech. Rep. ANL-95/11 (Revision 2.3.3), Argonne National Laboratory. http://www.mcs.anl.gov/petsc/.
• 2: Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. Comp. Graph. Forum 27 2, 449--458.
• 3: Benson, S., McInnes, L. C., Moré, J., Munson, T., and Sarich, J. 2007. TAO User Manual. Tech. Rep. ANL/MCS-TM-242 (Revision 1.9), Argonne National Laboratory. http://www.mcs.anl.gov/tao.
• 4: Bobenko, A. I., and Springborn, B. A. 2004. Variational Principles for Circle Patterns and Koebe's Theorem. Trans. Amer. Math. Soc. 356, 2, 659--689.
• 5: Bobenko, A. I., and Suris, Y. B., 2005. Discrete Differential Geometry. Consistency as Integrability. Preprint arXiv:math/0504358v1. To appear in Graduate Studies in Mathematics of the AMS.
• 6: Bowers, P. L., and Hurdal, M. K. 2003. Planar Conformal Mappings of Piecewise Flat Surfaces. In Vis. and Math. III. Springer, 3--34.
• 7: Chow, B., and Luo, F. 2003. Combinatorial Ricci Flows on Surfaces. J. Diff. Geom. 63, 1, 97--129.
• 8: Colin de Verdière, Y. 1991. Un Principe Variationnel pour les Empilements de Cercles. Invent. Math. 104, 655--669.
• 9: Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic Parameterizations of Surface Meshes. Comp. Graph. Forum 21, 3, 209--218.
• 10: Duffin, R. J. 1956. Basic Properties of Discrete Analytic Functions. Duke Math. J. 23, 335--363.
• 11: Duffin, R. 1959. Distributed and Lumped Networks. J. Math. Mech. {continued as Indiana Univ. Math. J.} 8, 793--826.
• 12: Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: Floater, M. S., and Hormann, K. 2005. Surface Parameterization: a Tutorial and Survey. In Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization. Springer, 157--186.
• 14: Xianfeng Gu , Shing-Tung Yau, Global conformal surface parameterization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 15: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 16: Jin, M., Kim, J., and Gu, X. D. 2007. Discrete Surface Ricci Flow: Theory and Applications. In Mathematics of Surfaces 2007, R. Martin, M. Sabin, and J. Winkler, Eds., Vol. 4647 of Lecture Notes in Computer Science. Springer, 209--232.
• 17: Kälberer, F., Nieser, M., and Polthier, K. 2007. QuadCover---Surface Parameterization using Branched Coverings. Comp. Graph. Forum 26, 3, 375--384.
• 18: Liliya Kharevych , Boris Springborn , Peter Schröder, Discrete conformal mappings via circle patterns, ACM Transactions on Graphics (TOG), v.25 n.2, p.412-438, April 2006 [doi>10.1145/1138450.1138461]
• 19: Leibon, G. 2002. Characterizing the Delaunay Decompositions of Compact Hyperbolic Surfaces. Geom. Topol. 6, 361--391.
• 20: Bruno Lévy , Sylvain Petitjean , Nicolas Ray , Jérome Maillot, Least squares conformal maps for automatic texture atlas generation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 21: Lewin, L. 1981. Polylogarithms and Associated Functions. North Holland.
• 22: Luo, F. 2004. Combinatorial Yamabe Flow on Surfaces. Commun. Contemp. Math. 6, 765--780.
• 23: Allan J. MacLeod, Algorithm 757: MISCFUN, a software package to compute uncommon special functions, ACM Transactions on Mathematical Software (TOMS), v.22 n.3, p.288-301, Sept. 1996 [doi>10.1145/232826.232846]
• 24: Mercat, C. 2001. Discrete Riemann Surfaces and the Ising Model. Comm. in Math. Physics 218, 1, 177--216.
• 25: Milnor, J. 1982. Hyperbolic Geometry: The First 150 Years. Bul. Amer. Math. Soc. 6, 1, 9--24.
• 26: Pinkall, U., and Polthier, K. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experiment. Math. 2, 1, 15--36.
• 27: Nicolas Ray , Wan Chiu Li , Bruno Lévy , Alla Sheffer , Pierre Alliez, Periodic global parameterization, ACM Transactions on Graphics (TOG), v.25 n.4, p.1460-1485, October 2006 [doi>10.1145/1183287.1183297]
• 28: Rivin, I. 1994. Euclidean Structures on Simplicial Surfaces and Hyperbolic Volume. Ann. of Math. (2) 139, 553--580.
• 29: Alla Sheffer , John C. Hart, Seamster: inconspicuous low-distortion texture seam layout, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 30: Alla Sheffer , Bruno Lévy , Maxim Mogilnitsky , Alexander Bogomyakov, ABF++: fast and robust angle based flattening, ACM Transactions on Graphics (TOG), v.24 n.2, p.311-330, April 2005 [doi>10.1145/1061347.1061354]
• 31: Alla Sheffer , Emil Praun , Kenneth Rose, Mesh parameterization methods and their applications, Foundations and Trends® in Computer Graphics and Vision, v.2 n.2, p.105-171, January 2006 [doi>10.1561/0600000011]
• 32: Springborn, B. 2005. A Unique Representation of Polyhedral Types. Centering via Möbius Transformations. Math. Z. 249, 513--517.
• 33: Steihaug, T. 1983. The Conjugate Gradient Method and Trust Regions in Large Scale Optimization. SIAM J. Numer. Anal. 20, 3, 626--637.
• 34: Stephenson, K. 2003. Circle Packing: A Mathematical Tale. Notices Amer. Math. Soc. 50, 11, 1376--1388.
• 35: Stephenson, K. 2005. Introduction to Circle Packing. Cambridge University Press.
• 36: Y. Tong , P. Alliez , D. Cohen-Steiner , M. Desbrun, Designing quadrangulations with discrete harmonic forms, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 37: Troyanov, M. 1986. Les Surfaces Euclidiennes à Singularités Coniques. Enseign. Math. (2) 32, 79--94.
• 38: Yong-Liang Yang , Junho Kim , Feng Luo , Shi-Min Hu , Xianfeng Gu, Optimal Surface Parameterization Using Inverse Curvature Map, IEEE Transactions on Visualization and Computer Graphics, v.14 n.5, p.1054-1066, September 2008 [doi>10.1109/TVCG.2008.54]
• 39: Rhaleb Zayer , Bruno Lévy , Hans-Peter Seidel, Linear angle based parameterization, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Design, Measurement

Keywords:
cone singularities, conformal equivalence, conformal parameterization, discrete Riemannian metric, discrete differential geometry, texture mapping