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

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