Efficient conformal parameterization of multiply-connected surfaces using quasi-conformal theory. (English) Zbl 1465.65019
Summary: Conformal mapping, a classical topic in complex analysis and differential geometry, has become a subject of great interest in the area of surface parameterization in recent decades with various applications in science and engineering. However, most of the existing conformal parameterization algorithms only focus on simply-connected surfaces and cannot be directly applied to surfaces with holes. In this work, we propose two novel algorithms for computing the conformal parameterization of multiply-connected surfaces. We first develop an efficient method for conformally parameterizing an open surface with one hole to an annulus on the plane. Based on this method, we then develop an efficient method for conformally parameterizing an open surface with \(k\) holes onto a unit disk with \(k\) circular holes. The conformality and bijectivity of the mappings are ensured by quasi-conformal theory. Numerical experiments and applications are presented to demonstrate the effectiveness of the proposed methods.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52C26 | Circle packings and discrete conformal geometry |
| 30C20 | Conformal mappings of special domains |
Keywords:
surface parameterization; conformal mapping; quasi-conformal theory; multiply-connected surfaces; annulus; poly-annulusReferences:
| [1] | Floater, M.S., Hormann, K.: Surface parameterization: a tutorial and survey. In: Advances in Multiresolution for Geometric Modelling, pp. 157-186, Springer (2005) · Zbl 1065.65030 |
| [2] | Sheffer, A.; Praun, E.; Rose, K., Mesh parameterization methods and their applications, Found. Trends Comput. Graph. Vis., 2, 2, 105-171 (2006) · Zbl 1112.68130 · doi:10.1561/0600000011 |
| [3] | Hormann, K., Lévy, B., Sheffer, A.: Mesh parameterization: theory and practice. In: ACM SIGGRAPH 2007 Courses. Association for Computing Machinery, New York, NY, USA (2007) |
| [4] | Pinkall, U.; Polthier, K., Computing discrete minimal surfaces and their conjugates, Exp. Math., 2, 1, 15-36 (1993) · Zbl 0799.53008 · doi:10.1080/10586458.1993.10504266 |
| [5] | Gu, X.; Wang, Y.; Chan, TF; Thompson, PM; Yau, S-T, Genus zero surface conformal mapping and its application to brain surface mapping, IEEE Trans. Med. Imaging, 23, 8, 949-958 (2004) · doi:10.1109/TMI.2004.831226 |
| [6] | Choi, PT; Lam, KC; Lui, LM, FLASH: Fast landmark aligned spherical harmonic parameterization for genus-0 closed brain surfaces, SIAM J. Imaging Sci., 8, 1, 67-94 (2015) · Zbl 1316.65028 · doi:10.1137/130950008 |
| [7] | Choi, GP-T; Ho, KT; Lui, LM, Spherical conformal parameterization of genus-0 point clouds for meshing, SIAM J. Imaging Sci., 9, 4, 1582-1618 (2016) · Zbl 1354.65034 · doi:10.1137/15M1037561 |
| [8] | Choi, GP-T; Lui, LM, A linear formulation for disk conformal parameterization of simply-connected open surfaces, Adv. Comput. Math., 44, 1, 87-114 (2018) · Zbl 1425.68431 · doi:10.1007/s10444-017-9536-x |
| [9] | Lévy, B.; Petitjean, S.; Ray, N.; Maillot, J., Least squares conformal maps for automatic texture atlas generation, ACM Trans. Graph., 21, 3, 362-371 (2002) · doi:10.1145/566654.566590 |
| [10] | Desbrun, M.; Meyer, M.; Alliez, P., Intrinsic parameterizations of surface meshes, Comput. Graph. Forum, 21, 3, 209-218 (2002) · doi:10.1111/1467-8659.00580 |
| [11] | Gu, X., Yau, S.-T.: Global conformal surface parameterization. In: Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, pp. 127-137 (2003) |
| [12] | Luo, F., Combinatorial Yamabe flow on surfaces, Commun. Contemp. Math., 6, 5, 765-780 (2004) · Zbl 1075.53063 · doi:10.1142/S0219199704001501 |
| [13] | Sheffer, A.; de Sturler, E., Parameterization of faceted surfaces for meshing using angle-based flattening, Eng. Comput., 17, 3, 326-337 (2001) · Zbl 0983.68566 · doi:10.1007/PL00013391 |
| [14] | Sheffer, A.; Lévy, B.; Mogilnitsky, M.; Bogomyakov, A., ABF++: fast and robust angle based flattening, ACM Trans. Graph., 24, 2, 311-330 (2005) · doi:10.1145/1061347.1061354 |
| [15] | Kharevych, L.; Springborn, B.; Schröder, P., Discrete conformal mappings via circle patterns, ACM Trans. Graph., 25, 2, 412-438 (2006) · doi:10.1145/1138450.1138461 |
| [16] | Springborn, B.; Schröder, P.; Pinkall, U., Conformal equivalence of triangle meshes, ACM Trans. Graph., 27, 3, 1-11 (2008) · doi:10.1145/1360612.1360676 |
| [17] | Jin, M.; Kim, J.; Luo, F.; Gu, X., Discrete surface Ricci flow, IEEE Trans. Vis. Comput. Graph., 14, 5, 1030-1043 (2008) · doi:10.1109/TVCG.2008.57 |
| [18] | Yang, Y-L; Guo, R.; Luo, F.; Hu, S-M; Gu, X., Generalized discrete Ricci flow, Comput. Graph. Forum, 28, 7, 2005-2014 (2009) · doi:10.1111/j.1467-8659.2009.01579.x |
| [19] | Yang, Y-L; Kim, J.; Luo, F.; Hu, S-M; Gu, X., Optimal surface parameterization using inverse curvature map, IEEE Trans. Vis. Comput. Graph., 14, 5, 1054-1066 (2008) · doi:10.1109/TVCG.2008.54 |
| [20] | Zhang, M.; Zeng, W.; Guo, R.; Luo, F.; Gu, XD, Survey on discrete surface Ricci flow, J. Comput. Sci. Technol., 30, 3, 598-613 (2015) · doi:10.1007/s11390-015-1548-8 |
| [21] | Mullen, P.; Tong, Y.; Alliez, P.; Desbrun, M., Spectral conformal parameterization, Comput. Graph Forum, 27, 5, 1487-1494 (2008) · doi:10.1111/j.1467-8659.2008.01289.x |
| [22] | Ben-Chen, M.; Gotsman, C.; Bunin, G., Conformal flattening by curvature prescription and metric scaling, Comput. Graph. Forum, 27, 2, 449-458 (2008) · doi:10.1111/j.1467-8659.2008.01142.x |
| [23] | Marshall, DE; Rohde, S., Convergence of a variant of the zipper algorithm for conformal mapping, SIAM J. Numer. Anal., 45, 6, 2577-2609 (2007) · Zbl 1157.30006 · doi:10.1137/060659119 |
| [24] | Choi, GPT; Leung-Liu, Y.; Gu, X.; Lui, LM, Parallelizable global conformal parameterization of simply-connected surfaces via partial welding, SIAM J. Imaging Sci., 13, 3, 1049-1083 (2020) · Zbl 1456.65014 · doi:10.1137/19M125337X |
| [25] | Sawhney, R.; Crane, K., Boundary first flattening, ACM Trans. Graph., 37, 1, 1-14 (2017) · doi:10.1145/3132705 |
| [26] | Yueh, M-H; Lin, W-W; Wu, C-T; Yau, S-T, An efficient energy minimization for conformal parameterizations, J. Sci. Comput., 73, 1, 203-227 (2017) · Zbl 1380.65049 · doi:10.1007/s10915-017-0414-y |
| [27] | Choi, PT; Lui, LM, Fast disk conformal parameterization of simply-connected open surfaces, J. Sci. Comput., 65, 3, 1065-1090 (2015) · Zbl 1329.65050 · doi:10.1007/s10915-015-9998-2 |
| [28] | Meng, TW; Choi, GP-T; Lui, LM, TEMPO: Feature-endowed Teich \({\ddot{{\rm m}}}\) uller extremal mappings of point clouds, SIAM J. Imaging Sci., 9, 4, 1922-1962 (2016) · Zbl 1369.30046 · doi:10.1137/15M1049117 |
| [29] | Lui, LM; Lam, KC; Wong, TW; Gu, X., Texture map and video compression using Beltrami representation, SIAM J. Imaging Sci., 6, 4, 1880-1902 (2013) · Zbl 1281.65036 · doi:10.1137/120866129 |
| [30] | Yung, CP; Choi, GPT; Chen, K.; Lui, LM, Efficient feature-based image registration by mapping sparsified surfaces, J. Vis. Commun. Image Represent., 55, 561-571 (2018) · doi:10.1016/j.jvcir.2018.07.005 |
| [31] | Lipman, Y., Bounded distortion mapping spaces for triangular meshes, ACM Trans. Graph., 31, 4, 1-13 (2012) · doi:10.1145/2185520.2185604 |
| [32] | Weber, O.; Myles, A.; Zorin, D., Computing extremal quasiconformal maps, Comput. Graph. Forum, 31, 5, 1679-1689 (2012) · doi:10.1111/j.1467-8659.2012.03173.x |
| [33] | Wong, TW; Zhao, H-K, Computation of quasi-conformal surface maps using discrete Beltrami flow, SIAM J. Imaging Sci., 7, 4, 2675-2699 (2014) · Zbl 1307.30050 · doi:10.1137/14097104X |
| [34] | Lui, LM; Lam, KC; Yau, S-T; Gu, X., Teichmüller mapping (T-map) and its applications to landmark matching registration, SIAM J. Imaging Sci., 7, 1, 391-426 (2014) · Zbl 1296.65028 · doi:10.1137/120900186 |
| [35] | Choi, GP-T; Man, MH-Y; Lui, LM, Fast spherical quasiconformal parameterization of genus-\(0\) closed surfaces with application to adaptive remeshing, Geom. Imaging Comput., 3, 1, 1-29 (2016) · Zbl 1396.65027 |
| [36] | Choi, GPT; Dudte, LH; Mahadevan, L., Programming shape using kirigami tessellations, Nat. Mater., 18, 9, 999-1004 (2019) · doi:10.1038/s41563-019-0452-y |
| [37] | Zeng, W.; Marino, J.; Gurijala, KC; Gu, X.; Kaufman, A., Supine and prone colon registration using quasi-conformal mapping, IEEE Trans. Vis. Comput. Graph., 16, 6, 1348-1357 (2010) · doi:10.1109/TVCG.2010.200 |
| [38] | Choi, GPT; Chen, Y.; Lui, LM; Chiu, B., Conformal mapping of carotid vessel wall and plaque thickness measured from 3D ultrasound images, Med. Biol. Eng. Comput., 55, 12, 2183-2195 (2017) · doi:10.1007/s11517-017-1656-4 |
| [39] | Choi, GPT; Mahadevan, L., Planar morphometrics using Teichmüller maps, Proc. R. Soc. A, 474, 2217, 20170905 (2018) · Zbl 1407.92016 · doi:10.1098/rspa.2017.0905 |
| [40] | Choi, GPT; Chan, HL; Yong, R.; Ranjitkar, S.; Brook, A.; Townsend, G.; Chen, K.; Lui, LM, Tooth morphometry using quasi-conformal theory, Pattern Recognit., 99, 107064 (2020) · doi:10.1016/j.patcog.2019.107064 |
| [41] | Choi, GPT; Qiu, D.; Lui, LM, Shape analysis via inconsistent surface registration, Proc. R. Soc. A, 476, 2242, 20200147 (2020) · Zbl 1472.53108 · doi:10.1098/rspa.2020.0147 |
| [42] | Yin, X., Dai, J., Yau, S.-T., Gu, X.: Slit map: Conformal parameterization for multiply connected surfaces. In: International Conference on Geometric Modeling and Processing, pp. 410-422. Springer (2008) |
| [43] | Wang, Y., Gu, X., Chan, T. F., Thompson, P. M., Yau, S.-T.: Conformal slit mapping and its applications to brain surface parameterization. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 585-593. Springer (2008) |
| [44] | Koebe, P., Über die konforme abbildung mehrfach zusammenhängender bereiche, Jahresbericht der Deutschen Mathematiker-Vereinigung, 19, 339-348 (1910) · JFM 41.0747.07 |
| [45] | Zeng, W., Yin, X., Zhang, M., Luo, F., Gu, X.: Generalized Koebe’s method for conformal mapping multiply connected domains. In: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling. pp. 89-100 (2009) |
| [46] | Kropf, E.; Yin, X.; Yau, S-T; Gu, XD, Conformal parameterization for multiply connected domains: combining finite elements and complex analysis, Eng. Comput., 30, 4, 441-455 (2014) · doi:10.1007/s00366-013-0348-4 |
| [47] | Ho, KT; Lui, LM, QCMC: quasi-conformal parameterizations for multiply-connected domains, Adv. Comput. Math., 42, 2, 279-312 (2016) · Zbl 1337.65017 · doi:10.1007/s10444-015-9424-1 |
| [48] | Bobenko, A. I., Sechelmann, S., Springborn, B.: Discrete conformal maps: Boundary value problems, circle domains, Fuchsian and Schottky uniformization. In: Advances in Discrete Differential Geometry, pp. 1-56, Springer, Berlin (2016) · Zbl 1354.30042 |
| [49] | Lehto, O., Quasiconformal Mappings in the Plane (1973), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 0194.11302 · doi:10.1007/978-3-642-65513-5 |
| [50] | Gardiner, FP; Lakic, N., Quasiconformal Teichmüller Theory (2000), New York: American Mathematical Society, New York · Zbl 0949.30002 |
| [51] | Ahlfors, LV, Lectures on Quasiconformal Mappings (2006), New York: American Mathematical Society, New York · Zbl 1103.30001 |
| [52] | Birdal, T.: Maximum inscribed circle using Voronoi diagram. https://www.mathworks.com/matlabcentral/fileexchange/32543-maximum-inscribed-circle-using-voronoi-diagram |
| [53] | Gu, X.: RiemannMapper: a mesh parameterization toolkit. https://www3.cs.stonybrook.edu/ gu/software/RiemannMapper/ |
| [54] | Persson, P-O; Strang, G., A simple mesh generator in MATLAB, SIAM Rev., 46, 2, 329-345 (2004) · Zbl 1061.65134 · doi:10.1137/S0036144503429121 |
| [55] | Ng, TC; Gu, X.; Lui, LM, Teichmüller extremal map of multiply-connected domains using Beltrami holomorphic flow, J. Sci. Comput., 60, 2, 249-275 (2014) · Zbl 1316.65036 · doi:10.1007/s10915-013-9791-z |
| [56] | Crowdy, D., The Schwarz-Christoffel mapping to bounded multiply connected polygonal domains, Proc. R. Soc. A, 461, 2061, 2653-2678 (2005) · Zbl 1186.30005 · doi:10.1098/rspa.2005.1480 |
| [57] | Crowdy, D.; Marshall, J., Conformal mappings between canonical multiply connected domains, Comput. Methods Funct. Theory, 6, 1, 59-76 (2006) · Zbl 1101.30010 · doi:10.1007/BF03321118 |
| [58] | Crowdy, D., Schwarz-Christoffel mappings to unbounded multiply connected polygonal regions, Math. Proc. Camb. Philos. Soc., 142, 2, 319 (2007) · Zbl 1111.30007 · doi:10.1017/S0305004106009832 |
| [59] | Nasser, MMS, Numerical conformal mapping via a boundary integral equation with the generalized Neumann kernel, SIAM J. Sci. Comput., 31, 3, 1695-1715 (2009) · Zbl 1198.30009 · doi:10.1137/070711438 |
| [60] | Nasser, MMS, PlgCirMap: A MATLAB toolbox for computing conformal mappings from polygonal multiply connected domains onto circular domains, SoftwareX, 11, 100464 (2020) · doi:10.1016/j.softx.2020.100464 |
| [61] | Crowdy, D.: Solving problems in multiply connected domains. NSF-CBMS Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia (2020) · Zbl 1451.30001 |
| [62] | Zeng, W.; Lui, LM; Gu, X.; Yau, S-T, Shape analysis by conformal modules, Methods Appl. Anal., 15, 4, 539-556 (2008) · Zbl 1184.30035 |
| [63] | Zhao, J., Qi, X., Wen, C., Lei, N., Gu, X.: Automatic and robust skull registration based on discrete uniformization. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 431-440, (2019) |
| [64] | Li, S.; Zeng, W.; Zhou, D.; Gu, X.; Gao, J., Compact conformal map for greedy routing in wireless mobile sensor networks, IEEE Trans. Mobile Comput., 15, 7, 1632-1646 (2015) · doi:10.1109/TMC.2015.2475752 |
| [65] | Zhao, X.; Su, Z.; Gu, XD; Kaufman, A.; Sun, J.; Gao, J.; Luo, F., Area-preservation mapping using optimal mass transport, IEEE Trans. Vis. Comput. Graph., 19, 12, 2838-2847 (2013) · doi:10.1109/TVCG.2013.135 |
| [66] | Su, K.; Cui, L.; Qian, K.; Lei, N.; Zhang, J.; Zhang, M.; Gu, XD, Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation, Comput. Aided Geom. Des., 46, 76-91 (2016) · Zbl 1418.65036 · doi:10.1016/j.cagd.2016.05.005 |
| [67] | Pumarola, A., Sanchez-Riera, J., Choi, G. P. T., Sanfeliu, A., Moreno-Noguer, F.: 3DPeople: modeling the geometry of dressed humans. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 2242-2251 (2019) |
| [68] | Giri, A.; Choi, GPT; Kumar, L., Open and closed anatomical surface description via hemispherical area-preserving map, Signal Process., 180, 107867 (2021) · doi:10.1016/j.sigpro.2020.107867 |
| [69] | Choi, GPT; Rycroft, CH, Density-equalizing maps for simply connected open surfaces, SIAM J. Imaging Sci., 11, 2, 1134-1178 (2018) · Zbl 1401.68347 · doi:10.1137/17M1124796 |
| [70] | Choi, GPT; Chiu, B.; Rycroft, CH, Area-preserving mapping of 3D carotid ultrasound images using density-equalizing reference map, IEEE Trans. Biomed. Eng., 67, 9, 1507-1517 (2020) · doi:10.1109/TBME.2019.2963783 |
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.
