skip to main content
research-article

Conformal equivalence of triangle meshes

Published: 01 August 2008 Publication History

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.

Supplementary Material

MOV File (a77-springborn.mov)

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]
Erickson, J., and Whittlesey, K. 2005. Greedy Optimal Homotopy and Homology Generators. In Proc. ACM/SIAM Symp. on Disc. Alg., SIAM, 1038--1046.
[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]
Gu, X., and Yau, S.-T. 2003. Global Conformal Surface Parameterization. In Proc. Symp. Geom. Proc., Eurographics, 127--137.
[15]
Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry Images. ACM Trans. Graph. 21, 3, 355--361.
[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]
Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete Conformal Mappings via Circle Patterns. ACM Trans. Graph. 25, 2, 412--438.
[19]
Leibon, G. 2002. Characterizing the Delaunay Decompositions of Compact Hyperbolic Surfaces. Geom. Topol. 6, 361--391.
[20]
Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21, 3, 362--371.
[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]
Macleod, A. J. 1996. Algorithm 757: MISCFUN, a Software Package to Compute Uncommon Special Functions. ACM Trans. Math. Softw. 22, 3, 288--301.
[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]
Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4, 1460--1485.
[28]
Rivin, I. 1994. Euclidean Structures on Simplicial Surfaces and Hyperbolic Volume. Ann. of Math. (2) 139, 553--580.
[29]
Sheffer, A., and Hart, J. C. 2002. Seamster: Inconspicuous Low-Distortion Texture Seam Layout. In Proc. IEEE Vis., IEEE Comp. Soc., 291--298.
[30]
Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. ABF++: Fast and Robust Angle Based Flattening. ACM Trans. Graph. 24, 2, 311--330.
[31]
Sheffer, A., Praun, E., and Rose, K. 2006. Mesh Parameterization Methods and their Applications. Found. Trends Comput. Graph. Vis. 2, 2, 105--171.
[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]
Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2007. Designing Quadrangulations with Discrete Harmonic Forms. In Proc. Symp. Geom. Proc., Eurographics, 201--210.
[37]
Troyanov, M. 1986. Les Surfaces Euclidiennes à Singularités Coniques. Enseign. Math. (2) 32, 79--94.
[38]
Yang, Y., Kim, J., Luo, F., Hu, S., and Gu, D. 2008. Optimal Surface Parameterization Using Inverse Curvature Map. IEEE Trans. Vis. Comp. Graph. (to appear).
[39]
Zayer, R., Lévy, B., and Seidel, H.-P. 2007. Linear Angle Based Parameterization. In Proc. Symp. Geom. Proc., Eurographics, 135--141.

Cited By

View all
  • (2025)Programming evolution of geometry in shape-morphing sheets via spatio-temporal activationProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences10.1098/rspa.2024.0387481:2306Online publication date: 30-Jan-2025
  • (2024)Seamless Parametrization in Penner CoordinatesACM Transactions on Graphics10.1145/365820243:4(1-13)Online publication date: 19-Jul-2024
  • (2024)Surface Cutting and Flattening to Target ShapesComputer Graphics Forum10.1111/cgf.1522343:7Online publication date: 24-Oct-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 27, Issue 3
August 2008
844 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1360612
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2008
Published in TOG Volume 27, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. cone singularities
  2. conformal equivalence
  3. conformal parameterization
  4. discrete Riemannian metric
  5. discrete differential geometry
  6. texture mapping

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)87
  • Downloads (Last 6 weeks)8
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Programming evolution of geometry in shape-morphing sheets via spatio-temporal activationProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences10.1098/rspa.2024.0387481:2306Online publication date: 30-Jan-2025
  • (2024)Seamless Parametrization in Penner CoordinatesACM Transactions on Graphics10.1145/365820243:4(1-13)Online publication date: 19-Jul-2024
  • (2024)Surface Cutting and Flattening to Target ShapesComputer Graphics Forum10.1111/cgf.1522343:7Online publication date: 24-Oct-2024
  • (2024)Practical Integer-Constrained Cone Construction for Conformal ParameterizationsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.328730330:8(5227-5239)Online publication date: Aug-2024
  • (2024)Decorated Discrete Conformal Maps and Convex Polyhedral CuspsInternational Mathematics Research Notices10.1093/imrn/rnae0162024:12(9505-9534)Online publication date: 1-Apr-2024
  • (2024)Conformal surface splinesDifferential Geometry and its Applications10.1016/j.difgeo.2024.10220097(102200)Online publication date: Dec-2024
  • (2024)Fast ellipsoidal conformal and quasi-conformal parameterization of genus-0 closed surfacesJournal of Computational and Applied Mathematics10.1016/j.cam.2024.115888447(115888)Online publication date: Sep-2024
  • (2024)Anisotropic triangular meshing using metric-adapted embeddingsComputer Aided Geometric Design10.1016/j.cagd.2024.102314(102314)Online publication date: Apr-2024
  • (2024)The Convergence of Discrete Uniformizations for Genus Zero SurfacesDiscrete & Computational Geometry10.1007/s00454-022-00458-w71:3(1057-1080)Online publication date: 1-Apr-2024
  • (2023)Fundamental Theory and R-linear Convergence of Stretch Energy Minimization for Spherical Equiareal ParameterizationJournal of Numerical Mathematics10.1515/jnma-2022-0072Online publication date: 24-Aug-2023
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media