×

Numerical computation of surface conformal mappings. (English) Zbl 1238.53023

In this survey article, the authors present methods for numerically computing conformal mappings between surfaces. The main tools are Ricci flow, Hodge theory (computation of the group of holomorphic 1-forms), and harmonic maps. The authors describe the classical smooth theory and then pass on to the modern discrete setting which lends itself better to numerical computations. Particular emphasis is put on applicability to surfaces of different topology. The article concludes with a section on applications of the theory. The examples are from the authors’ own works cover the fields of computer graphics, geometric modeling, medical imaging, and wireless sensor networks. The numerous figures to illustrate the presented theory are quite remarkable, the list of references is exhaustive.

MSC:

53C20 Global Riemannian geometry, including pinching
53A30 Conformal differential geometry (MSC2010)
52C26 Circle packings and discrete conformal geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] T. Aubin, Equations differéntielles non linéaires et problème de Yamabe concernant la courbure scalaire, J. Math. Pures Appl. 55 no.3 (1976), 269–296. · Zbl 0336.53033
[2] L. Banjai and L. N. Trefethen, A multipole method for Schwarz-Christoffel mapping of polygon with thousands of sides, SIAM J. Comput. 25 no.3 (2003), 1042–1065. · Zbl 1060.30012 · doi:10.1137/S1064827502411675
[3] I. Binder, M. Braverman and M. Yampolsky, On the computational complexity of the Riemann mapping, Ark. Mat. 45 no.2 (2007), 221–239. · Zbl 1153.30005 · doi:10.1007/s11512-007-0045-x
[4] C. J. Bishop, Conformal mapping in linear time, Discrete Comput. Geom. 44 no.2 (2010), 330–428. · Zbl 1206.30007 · doi:10.1007/s00454-010-9269-9
[5] A. I. Bobenko and B. A. Springborn, Variational principles for circle patterns and Koebe’s theorem, Trans. Amer. Math. Soc. 356 (2004), 659–689. · Zbl 1044.52009 · doi:10.1090/S0002-9947-03-03239-2
[6] A. I. Bobenko, B. A. Springborn and U. Pinkall, Discrete conformal equivalence and ideal hyperbolic polyhedra, arXiv:1005.2698 (2010).
[7] P. L. Bowers and M. K. Hurdal, Planar conformal mapping of piecewise flat surfaces; in: H.-C. Hege et al. (eds.), Visualization and Mathematics III, Outgrowth of the 3rd international workshop, Berlin, Germany, May 22–25, 2002; Berlin, Springer, 2003, 3–34, 425–426; Math. Vis. III (2003), 3–34. · Zbl 1069.30011
[8] S.-S. Chern, An elementary proof of the existence of isothermal parameters on a surface, Proc. Amer. Math. Soc. 6 (1955), 771–782. · Zbl 0066.15402 · doi:10.1090/S0002-9939-1955-0074856-1
[9] B. Chow, P. Lu and L. Ni, Hamilton’s Ricci Flow, Amer. Math. Soc., 2006. · Zbl 1118.53001
[10] B. Chow and F. Luo, Combinatorial Ricci flows on surfaces, J. Differential Geom. 63 no.1 (2003), 97–129. · Zbl 1070.53040
[11] Y. Colin de Verdiére, Un principe variationnel pour les empilements de cercles, Invent. Math. 104 no.3 (1991), 655–669. · Zbl 0745.52010 · doi:10.1007/BF01245096
[12] C. Costa, Example of a complete minimal immersion in \(\mathbb{R}\)3 of genus one and three embedded ends, Bol Soc. Bras. Mat. 15 (1984), 47–54. · Zbl 0613.53002 · doi:10.1007/BF02584707
[13] C. Collins and K. Stephenson, A circle packing algorithm, Comput. Geom. 25 (2003), 233–256. · Zbl 1023.52005 · doi:10.1016/S0925-7721(02)00099-8
[14] K. Crane, M. Desbrun and P. Schröder, Trivial connections on discrete surfaces, Comput. Graph. Forum 29 no.5 (2010), 1525–1533. · doi:10.1111/j.1467-8659.2010.01761.x
[15] D. G. Crowdy, The Schwarz-Christoffel mapping to bounded multiply connected polygonal domains, Proc. R. Soc. A 461 (2005), 2653–2678. · Zbl 1186.30005 · doi:10.1098/rspa.2005.1480
[16] D. G. Crowdy and J. S. Marshall, Conformal mappings between canonical multiply connected domains, Comput. Methods Funct. Theory 6 no.1 (2006), 59–76. · Zbl 1101.30010 · doi:10.1007/BF03321118
[17] T. K. DeLillo, The accuracy of numerical conformal mapping methods: a survey of examples and results, SIAM J. Numer. Anal. 31 no.3 (1994), 788–812. · Zbl 0808.30006 · doi:10.1137/0731043
[18] T. K. DeLillo, A. R. Elcrat and J. A. Pfaltzgraff, Schwarz-Christoffel mapping of multiply connected domains, J. Analyse Math. 94 no.1 (2004), 17–47. · Zbl 1080.30008 · doi:10.1007/BF02789040
[19] M. Desbrun, M. Meyer and P. Alliez, Intrinsic parameterizations of surface meshes, Computer Graphics Forum (Proc. Eurographics 2002) 21 no.3 (2002), 209–218. · Zbl 02180130 · doi:10.1111/1467-8659.00580
[20] T. A. Driscoll and L. N. Trefethen, Schwarz-Christoffel Mapping, Cambridge Press, 2002. · Zbl 1003.30005
[21] T. A. Driscoll and S. A. Vavasis, Numerical conformal mapping using cross-ratios and Delaunay triangulation, SIAM Sci. Comp. 19 (1998), 1783–803. · Zbl 0915.30006 · doi:10.1137/S1064827596298580
[22] H. M. Farkas and I. Kra, Riemann Surfaces, Graduate Texts in Mathematics 71, Springer-Verlag, 1991.
[23] M. S. Floater, Mean value coordinates, Comput. Aided Geom. Design 20 no.1 (2003), 19–27. · Zbl 1069.65553 · doi:10.1016/S0167-8396(03)00002-5
[24] M. S. Floater and K. Hormann, Surface Parameterization: a Tutorial and Survey, Advances in Multiresolution for Geometric Modelling, 157–186, Springer, 2005. · Zbl 1065.65030
[25] D. Glickenstein, Discrete conformal variations and scalar curvature on piecewise flat two and three dimensional manifolds, arXiv:0906.1560 (2009). · Zbl 1243.52014
[26] S. J. Gortler, C. Gotsman and D. Thurston, Discrete one-forms on meshes and applications to 3D mesh parameterization, Comput. Aided Geom. Design 23 no.2 (2005), 83–112. · Zbl 1088.65015 · doi:10.1016/j.cagd.2005.05.002
[27] C. Gotsman, X. Gu and A. Sheffer, Fundamentals of spherical parameterization for 3D meshes, ACM Transactions on Graphics 22 no.3 (2003), 358–363. · Zbl 05457302 · doi:10.1145/882262.882276
[28] X. Gu, Y. He and H. Qin, Manifold splines, Graphical Models 68 no.3 (2006), 237–254. · Zbl 1110.68153 · doi:10.1016/j.gmod.2006.03.004
[29] X. Gu and S.-T. Yau, Global conformal parameterization, Symposium on Geometry Processing (2003), 127–137.
[30] –, Computational Conformal Geometry, Advanced Lectures in Mathematics, Vol 3, International Press and Higher Education Press, 2007.
[31] X. Gu, Y. Wang, T. F. Chan, P. M. Thompson and S.-T. Yau, Genus zero surface conformal mapping and its application to brain surface mapping, IEEE Trans. Med. Imaging 23 no.8 (2004), 949–958. · doi:10.1109/TMI.2004.831226
[32] X. Gu, S. Zhang, P. Huang, L. Zhang, S.-T. Yau and R. Martin, Holoimages, Proc. ACM Solid and Physical Modeling (2006), 129–138.
[33] R. Guo, Local rigidity of inversive distance circle packing, Trans. Amer. Math. Soc. 36 (2011), 4757–4778. · Zbl 1252.52019 · doi:10.1090/S0002-9947-2011-05239-6
[34] R. S. Hamilton, The Ricci flow on surfaces, in: Mathematics and General Relativity (Santa Cruz, CA, 1986), Contemp. Math. Amer. Math. Soc., Providence, RI, vol. 71, 1988. · Zbl 0591.30001
[35] R. S. Hamilton, Three manifolds with positive Ricci curvature, J. Differential Geom. 17 (1982), 255–306. · Zbl 0504.53034
[36] Z.-X. He and O. Schramm, Fixed points, Koebe uniformization and circle packings, Ann. of Math. 137 no.2 (1993), 369–406. · Zbl 0777.30002 · doi:10.2307/2946541
[37] P. Henrici, Applied and Computational Complex Analysis, Vol 3: Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps, Univalent Functions, Wiley-Interscience, 1993 · Zbl 1107.30300
[38] A. N. Hirani, Discrete exterior calculus, PhD thesis, California Institute of Technology, 2003.
[39] W. Hong, X. Gu, F. Qiu, M. Jin and A. E. Kaufman, Conformal virtual colon flattening, Symposium on Solid and Physical Modeling (2006), 85–93.
[40] V. I. Ivanov and M. K. Trubetskov, Handbook of Conformal Mapping with Computer-Aided Visualization, CRC Press, Boca Raton, FL, 1995. · Zbl 0853.30005
[41] M. Jin, J. Kim, F. Luo and X. Gu, Discrete surface Ricci flow, IEEE Transactions on Visualization and Computer Graphics (TVCG) 14 no.5 (2008), 1030–1043. · Zbl 05340049 · doi:10.1109/TVCG.2008.57
[42] M. Jin, W. Zeng, D. Ning and X. Gu, Computing Fenchel-Nielsen coordinates in Teichmüller shape space, IEEE International Conference on Shape Modeling and Applications (SMI), 2009. · Zbl 1186.68504
[43] L. Kharevych, B. Springborn and P. Schröder, Discrete conformal mappings via circle patterns, ACM Trans. Graph. 25 no.2 (2006), 412–438. · Zbl 05457389 · doi:10.1145/1138450.1138461
[44] Koebe, Kontaktprobleme der konformen Abbildung, Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88 (1936), 141–164.
[45] V. Kraevoy and A. Sheffer, Cross-parameterization and compatible remeshing of 3D models, ACM Transactions on Graphics 23 no.3 (2004), 861–869. · Zbl 05457400 · doi:10.1145/1015706.1015811
[46] Y. Lai, M. Jin, X. Xie, Y. He, J. Palacios, E. Zhang, S. Hu and X. Gu, Metric-driven RoSy fields design, IEEE Transaction on Visualization and Computer Graphics (TVCG) 15 no.3 (2010), 95–108.
[47] S. Lang, Differential and Riemannian Manifolds, Graduate Texts in Mathematics 160, Springer-Verlag New York, 1995. · Zbl 0824.58003
[48] J. M. Lee and T. H. Parker, The Yamabe problem, Bull. Amer. Math. Soc. 17 no.1 (1987), 37–91. · Zbl 0633.53062 · doi:10.1090/S0273-0979-1987-15514-5
[49] B. Lévy, S. Petitjean, N. Ray and J. Maillot, Least squares conformal maps for automatic texture atlas generation, SIGGRAPH 2002 (2002), 362–371.
[50] F. Luo, Combinatorial Yamabe flow on surfaces, Commun. Contemp. Math. 6 no.5 (2004), 765–780. · Zbl 1075.53063 · doi:10.1142/S0219199704001501
[51] D. E. Marshall and S. Rohde, Convergence of a variant of the zipper algorithm for conformal mapping, SIAM J. Numer. 45 no.6 (2007), 2577–2609. · Zbl 1157.30006 · doi:10.1137/060659119
[52] C. Mercat, Discrete Riemann surfaces and the Ising model, Comm. Math. Physics 218 no.1 (2004), 177–216. · Zbl 1043.82005 · doi:10.1007/s002200000348
[53] U. Pinkall and K. Polthier, Computing discrete minimal surfaces and their conjugates, Experiment. Math. 2 no.1 (1993), 15–36. · Zbl 0799.53008 · doi:10.1080/10586458.1993.10504266
[54] B. Rodin and D. Sullivan, The convergence of circle packings to the Riemann mapping, J. Differential Geom. 26 no.2 (1987), 349–360. · Zbl 0694.30006
[55] R. Sarkar, X. Yin, J.Gao and X. Gu, Greedy routing with guaranteed delivery using Ricci flows, Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN’09), Apr, 2009, 121–132.
[56] R. Sarkar, W. Zeng, J.Gao and X. Gu, Covering space for in-network sensor data storage, Proc. of the 9th International Symposium on Information Processing in Sensor Networks (IPSN’10), Apr, 2010, 232–243.
[57] R. Schinzinger and P. A. Laura, Conformal Mapping: Methods and Applications, Dover Publications, 2003. · Zbl 1063.30007
[58] R. Schoen, Conformal deformation of a Riemannian metric to constant scalar curvature, J. Differential Geom. 20 no.2 (1984), 479–495. · Zbl 0576.53028
[59] R. Schoen and S.-T. Yau, Lectures on Harmonic Maps, Conference Proceedings and Lecture Notes in Geometry and Topology, 2. Cambridge, MA, International Press, 1997, 394 p. · Zbl 0886.53004
[60] K. Stephenson, Introduction to Circle Packing: the Theory of Discrete Analytic Functions, Univ. Press, Cambridge, 2005. · Zbl 1074.52008
[61] G. Tewari, C. Gotsman and S. J. Gortler, Meshing genus-1 point clouds using discrete one-forms, Comput. Graph. 30 no.6 (2006), 917–926. · doi:10.1016/j.cag.2006.08.019
[62] W. P. Thurston, Geometry and Topology of Three-Manifolds, Lecture Notes at Princeton University, 1980. · Zbl 0435.58019
[63] –, The Finite Riemann Mapping Theorem, invited talk at the International Symposium at Purdue University on the occasion of the proof of the Bieberbach conjecture, 1985.
[64] Y. Tong, P. Alliez, D. Cohen-Steiner and M. Desbrun, Designing quadrangulations with discrete harmonic forms, Symposium on Geometry Processing (2006), 201–210.
[65] L. N. Trefethen (ed.), Numerical Conformal mapping, North-Holland Publishing Co., Amsterdam, 1986; reprint of J. Comput. Appl. Math. 14 no.1-2 (1986). · Zbl 0572.00018
[66] N. S. Trudinger, Remarks concerning the conformal deformation of Riemannian structures on compact manifolds, Ann. Scuola Norm. Sup. Pisa 22 no.2 (1968), 265–274. · Zbl 0159.23801
[67] S. Wang, Y. Wang, M. Jin, X. D. Gu and D. Samaras, Conformal geometry and its applications on 3D shape matching, recognition, and stitching, IEEE Trans. Pattern Anal. Mach. Intell. 29 no.7 (2007), 1209–1220. · Zbl 05340891 · doi:10.1109/TPAMI.2007.1050
[68] R. Wegmann, Methods for numerical conformal mapping, in: Handbook of Complex Analysis Vol. 2: Geometric Function Theory, Elsevier, Amsterdam, 2005, 351–377. · Zbl 1131.30004
[69] H. Yamabe, The Yamabe problem, Osaka Math. J. 12 no.1 (1960), 21–37.
[70] Y.-L. Yang, R. Guo, F. Luo, S.-M. Hu and X. Gu, Generalized discrete Ricci flow, Comput. Graph. Forum 28 no.7 (2009), 2005–2014. · Zbl 05650660 · doi:10.1111/j.1467-8659.2009.01579.x
[71] X. Yin, J. Dai, S.-T. Yau, and X. Gu, Slit Map: conformal parameterization for multiply connected surfaces, Geometric Modeling and Processing (GMP) (2008), 410–422.
[72] W. Zeng, M. Jin, F. Luo and X. Gu, Computing canonical homotopy class representative using hyperbolic structure, IEEE International Conference on Shape Modeling and Applications (SMI), 2009.
[73] W. Zeng, L. M. Lui, X. Gu, and S.-T. Yau, Shape analysis by conformal modulus, Methods Appl. Anal. 15 (2008), 539–556. · Zbl 1184.30035
[74] W. Zeng, F. Luo, S-T Yau and X. Gu, Surface quasi-conformal mapping by solving Beltrami equations, IMA Conference on the Mathematics of Surfaces (2009), 391–408. · Zbl 1259.65032
[75] W. Zeng, D. Samaras and X. Gu, Ricci Flow for 3D shape analysis, IEEE Transaction of Pattern Analysis and Machine Intelligence (PAMI) 32 no.4 (2010), 662–677. · doi:10.1109/TPAMI.2009.201
[76] W. Zeng, R. Sarkar, F. Luo, X. Gu and J. Gao, Resilient routing for sensor networks using hyperbolic embedding of universal covering space, Proc. of the 29th IEEE Conference on Computer Communications (INFOCOM’10), Mar 15–19, 2010.
[77] W. Zeng, X. Yin, M. Zhang, F. Luo and X. Gu, Generalized Koebe’s method for conformal mapping multiply connected domains, SIAM/ACM Joint Conference on Geometric and Physical Modeling (SPM) (2009), 89–100.
[78] W. Zeng, Y. Zeng, Y. Wang, X. Yin, X. Gu, and D. Samaras, 3D non-rigid surface matching and registration based on holomorphic differentials, The 10th European Conference on Computer Vision (ECCV) 2008 (2008), 1–14. Xianfeng David Gu
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.