“Conformal equivalence of triangle meshes” by Springborn, Schröder and Pinkall

  • ©Boris Springborn, Peter Schröder, and Ulrich Pinkall




    Conformal equivalence of triangle meshes



    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.


    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/.Google Scholar
    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.Google ScholarCross Ref
    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.Google Scholar
    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.Google ScholarCross Ref
    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.Google Scholar
    6. Bowers, P. L., and Hurdal, M. K. 2003. Planar Conformal Mappings of Piecewise Flat Surfaces. In Vis. and Math. III. Springer, 3–34.Google Scholar
    7. Chow, B., and Luo, F. 2003. Combinatorial Ricci Flows on Surfaces. J. Diff. Geom. 63, 1, 97–129.Google ScholarCross Ref
    8. Colin de Verdière, Y. 1991. Un Principe Variationnel pour les Empilements de Cercles. Invent. Math. 104, 655–669.Google ScholarCross Ref
    9. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic Parameterizations of Surface Meshes. Comp. Graph. Forum 21, 3, 209–218.Google ScholarCross Ref
    10. Duffin, R. J. 1956. Basic Properties of Discrete Analytic Functions. Duke Math. J. 23, 335–363.Google ScholarCross Ref
    11. Duffin, R. 1959. Distributed and Lumped Networks. J. Math. Mech. {continued as Indiana Univ. Math. J.} 8, 793–826.Google ScholarCross Ref
    12. Erickson, J., and Whittlesey, K. 2005. Greedy Optimal Homotopy and Homology Generators. In Proc. ACM/SIAM Symp. on Disc. Alg., SIAM, 1038–1046. Google ScholarDigital Library
    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.Google Scholar
    14. Gu, X., and Yau, S.-T. 2003. Global Conformal Surface Parameterization. In Proc. Symp. Geom. Proc., Eurographics, 127–137. Google ScholarDigital Library
    15. Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry Images. ACM Trans. Graph. 21, 3, 355–361. Google ScholarDigital Library
    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. Google ScholarDigital Library
    17. Kälberer, F., Nieser, M., and Polthier, K. 2007. QuadCover—Surface Parameterization using Branched Coverings. Comp. Graph. Forum 26, 3, 375–384.Google ScholarCross Ref
    18. Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete Conformal Mappings via Circle Patterns. ACM Trans. Graph. 25, 2, 412–438. Google ScholarDigital Library
    19. Leibon, G. 2002. Characterizing the Delaunay Decompositions of Compact Hyperbolic Surfaces. Geom. Topol. 6, 361–391.Google ScholarCross Ref
    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. Google ScholarDigital Library
    21. Lewin, L. 1981. Polylogarithms and Associated Functions. North Holland.Google Scholar
    22. Luo, F. 2004. Combinatorial Yamabe Flow on Surfaces. Commun. Contemp. Math. 6, 765–780.Google ScholarCross Ref
    23. Macleod, A. J. 1996. Algorithm 757: MISCFUN, a Software Package to Compute Uncommon Special Functions. ACM Trans. Math. Softw. 22, 3, 288–301. Google ScholarDigital Library
    24. Mercat, C. 2001. Discrete Riemann Surfaces and the Ising Model. Comm. in Math. Physics 218, 1, 177–216.Google ScholarCross Ref
    25. Milnor, J. 1982. Hyperbolic Geometry: The First 150 Years. Bul. Amer. Math. Soc. 6, 1, 9–24.Google ScholarCross Ref
    26. Pinkall, U., and Polthier, K. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experiment. Math. 2, 1, 15–36.Google ScholarCross Ref
    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. Google ScholarDigital Library
    28. Rivin, I. 1994. Euclidean Structures on Simplicial Surfaces and Hyperbolic Volume. Ann. of Math. (2) 139, 553–580.Google Scholar
    29. Sheffer, A., and Hart, J. C. 2002. Seamster: Inconspicuous Low-Distortion Texture Seam Layout. In Proc. IEEE Vis., IEEE Comp. Soc., 291–298. Google ScholarDigital Library
    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. Google ScholarDigital Library
    31. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh Parameterization Methods and their Applications. Found. Trends Comput. Graph. Vis. 2, 2, 105–171. Google ScholarDigital Library
    32. Springborn, B. 2005. A Unique Representation of Polyhedral Types. Centering via Möbius Transformations. Math. Z. 249, 513–517.Google ScholarCross Ref
    33. Steihaug, T. 1983. The Conjugate Gradient Method and Trust Regions in Large Scale Optimization. SIAM J. Numer. Anal. 20, 3, 626–637.Google ScholarDigital Library
    34. Stephenson, K. 2003. Circle Packing: A Mathematical Tale. Notices Amer. Math. Soc. 50, 11, 1376–1388.Google Scholar
    35. Stephenson, K. 2005. Introduction to Circle Packing. Cambridge University Press.Google Scholar
    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. Google ScholarDigital Library
    37. Troyanov, M. 1986. Les Surfaces Euclidiennes à Singularités Coniques. Enseign. Math. (2) 32, 79–94.Google Scholar
    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). Google ScholarDigital Library
    39. Zayer, R., Lévy, B., and Seidel, H.-P. 2007. Linear Angle Based Parameterization. In Proc. Symp. Geom. Proc., Eurographics, 135–141. Google ScholarDigital Library

ACM Digital Library Publication: