Computing quasiconformal maps using an auxiliary metric and discrete curvature flow. (English) Zbl 1246.30037
Summary: Surface mapping plays an important role in geometric processing, which induces both area and angular distortions. If the angular distortion is bounded, the mapping is called a quasiconformal mapping (QC-mapping). Many surface mappings in our physical world are quasiconformal. The angular distortion of a QC mapping can be represented by the Beltrami differential. According to QC Teichmüller theory, there is a one-to-one correspondence between the set of Beltrami differentials and the set of QC surface mappings under normalization conditions. Therefore, every QC surface mapping can be fully determined by the Beltrami differential and reconstructed by solving the so-called Beltrami equation. In this work, we propose an effective method to solve the Beltrami equation on general Riemann surfaces. The solution is a QC mapping associated with the prescribed Beltrami differential. The main strategy is to define an auxiliary metric on the domain surface, such that the original QC mapping becomes conformal under the auxiliary metric. The desired QC-mapping can then be obtained by using the conventional conformal mapping method. In this paper, we first formulate a discrete analogue of QC mappings on triangular meshes. Then, we propose an algorithm to compute discrete QC mappings using the discrete Yamabe flow method. To the best of our knowledge, it is the first work to compute the discrete QC mappings for general Riemann surfaces, especially with different topologies. Numerically, the discrete QC mapping converges to the continuous solution as the mesh grid size approaches to 0. We tested our algorithm on surfaces scanned from real life with different topologies. Experimental results demonstrate the generality and accuracy of our auxiliary metric method.
MSC:
| 30C62 | Quasiconformal mappings in the complex plane |
| 65E05 | General theory of numerical methods in complex analysis (potential theory, etc.) |
| 30C30 | Schwarz-Christoffel-type mappings |
| 30F99 | Riemann surfaces |
Software:
ABF++References:
| [1] | Ahlfors L.: Conformality with respect to Riemannian matrices. Ann. Acad. Sci. Fenn. Ser. 206, 1–22 (1955) · Zbl 0067.30702 |
| [2] | Ahlfors L.: Lectures in Quasiconformal Mappings. Van Nostrand Reinhold, New York (1966) · Zbl 0138.06002 |
| [3] | 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 |
| [4] | Bers L., Nirenberg L.: On Linear and Nonlinear Elliptic Boundary Value Problems in the Plane, pp. 141–167. Convegno Internazionale Suelle Equaziono Cremeonese, Roma (1955) · Zbl 0067.32504 |
| [5] | Bers L.: Mathematical Aspects of Subcritical and Transonic Gas Dynamics. Wiley, New York (1958) · Zbl 0083.20501 |
| [6] | Bers L.: Quasiconformal mappings, with applications to differential equations, function theory and topology. Am. Math. Soc. Bull. 83(6), 1083–1100 (1977) · Zbl 0419.30016 · doi:10.1090/S0002-9904-1977-14390-5 |
| [7] | Bers L., Nirenberg L.: On a Representation Theorem for Linear Elliptic Systems with Discontinuous Coefficients and its Applications, pp. 111–140. Convegno Internazionale Suelle Equaziono Cremeonese, Roma (1955) · Zbl 0067.32503 |
| [8] | Bobenko, A., Springborn, B., Pinkall, U.: Discrete conformal equivalence and ideal hyperbolic polyhedra (2012, in press) · Zbl 1327.52040 |
| [9] | Bobenko A.I., Springborn B.A.: Variational principles for circle patterns and koebe’s theorem. Trans. Am. Math. Soc. 356, 659–689 (2004) · Zbl 1044.52009 · doi:10.1090/S0002-9947-03-03239-2 |
| [10] | Bowers, P.L., Hurdal, M.: Planar conformal mapping of piecewise flat surfaces. In: Visualization and Mathematics III, pp. 3–34. Springer, Berlin (2003) · Zbl 1069.30011 |
| [11] | Bucking, U.: On existence and convergence of conformally equivalent triangle meshes for conformal mappings and regular lattices. In: Barrett Memorial Lectures (May 17–21, 2010) |
| [12] | Belinskii P.P., Godunov S.K., Yanenko I.: The use of a class of quasiconformal mappings to construct difference nets in domains with curvilinear boundaries. USSR Comp. Math. Phys. 15, 133–144 (1975) · Zbl 0366.65039 · doi:10.1016/0041-5553(75)90209-8 |
| [13] | Carleson L., Gamelin T.: Complex Dynamics. Springer, New York (1993) |
| [14] | Chow B.: The Ricci flow on the 2-sphere. J. Differ. Geom. 33(2), 325–334 (1991) · Zbl 0734.53033 |
| [15] | Chow B., Luo F.: Combinatorial Ricci flows on surfaces. J. Differ. Geom. 63(1), 97–129 (2003) · Zbl 1070.53040 |
| [16] | Dai J., Luo W., Jin M., Zeng W., He Y., Yau S.T., Gu X.: Geometric accuracy analysis for discrete surface approximation. Comput. Aided Geom. Des. 24(6), 323–338 (2007) · Zbl 1171.65360 · doi:10.1016/j.cagd.2007.04.004 |
| [17] | Daripa P.: On a numerical method for quasiconformal grid generation. J. Comput. Phys. 96, 229–236 (1991) · Zbl 0726.76075 · doi:10.1016/0021-9991(91)90274-O |
| [18] | Daripa P.: A fast algorithm to solve nonhomogeneous Cauchy-Riemann equations in the complex plane. SIAM J. Sci. Stat. Comput. 13(6), 1418–1432 (1992) · Zbl 0762.65013 · doi:10.1137/0913080 |
| [19] | Daripa P., Masha D.: An efficient and novel numerical method for quasiconformal mappings of doubly connected domains. Numer. Algorithm 18, 159–175 (1998) · Zbl 0931.30010 · doi:10.1023/A:1019169431757 |
| [20] | Desbrun M., Meyer M., Alliez P.: Intrinsic parameterizations of surface meshes. Comput. Graph. Forum (Proc. Eurographics 2002) 21(3), 209–218 (2002) · doi:10.1111/1467-8659.00580 |
| [21] | Farkas H.M., Kra I.: Riemann Surfaces. Springer, Berlin (2004) |
| [22] | Floater, M.S., Hormann, K.: Surface parameterization: a tutorial and survey. In: Advances in Multiresolution for Geometric Modelling, pp. 157–186. Springer, Berlin (2005) · Zbl 1065.65030 |
| [23] | Gortler S.J., Gotsman C., Thurston D.: Discrete one-forms on meshes and applications to 3D mesh parameterization. Comput. Aided Geom. Des. 23(2), 83–112 (2005) · Zbl 1088.65015 · doi:10.1016/j.cagd.2005.05.002 |
| [24] | Gotsman C., Gu X., Sheffer A.: Fundamentals of spherical parameterization for 3D meshes. ACM Trans. Graph. 22(3), 358–363 (2003) · doi:10.1145/882262.882276 |
| [25] | Grimm, C., Hughes, J.F.: Parameterizing N-holed tori. In: IMA Conference on the Mathematics of Surfaces, pp. 14–29 (2003) · Zbl 1274.68628 |
| [26] | Grotzsch H.: Uber die verzerrung bei schlichten nichtkonformen abbildungen und eine damit zusammenh angende erweiterung des picardschen. Rec. Math. 80, 503–507 (1928) |
| [27] | Gu X., He Y., Qin H.: Manifold splines. Graph. Models 68(3), 237–254 (2006) · Zbl 1110.68153 · doi:10.1016/j.gmod.2006.03.004 |
| [28] | Gu X., Wang Y., Chan T.F., Thompson P.M., 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 |
| [29] | Gu, X., Yau, S.T.: Global conformal parameterization. In: Symposium on Geometry Processing, pp. 127–137 (2003) |
| [30] | Guggenheimer H.W.: Differential Geometry. Dover Publications, New York (1977) · Zbl 0357.53002 |
| [31] | Hamilton R.S.: Three manifolds with positive Ricci curvature. J. Differ. Geom. 17, 255–306 (1982) · Zbl 0504.53034 |
| [32] | Hamilton R.S.: The Ricci flow on surfaces. Math. Gen. Relativ. 71, 237–262 (1988) · Zbl 0663.53031 · doi:10.1090/conm/071/954419 |
| [33] | Hong, W., Gu, X., Qiu, F., Jin, M., Kaufman, A.E.: Conformal virtual colon flattening. In: Symposium on Solid and Physical Modeling, pp. 85–93 (2006) |
| [34] | Hormann, K., Levy, B., Sheffer, A.: Mesh parameterization. SIGGRAPH 2007 Course Notes 2 (2007) |
| [35] | 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 |
| [36] | Kharevych L., Springerborn B., Schröder P.: Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25(2), 412–438 (2006) · doi:10.1145/1138450.1138461 |
| [37] | Kalberer F., Nieser M., Polthicr K.: Quadcover–surface parameterization using branched coverings. Comput. Graph. 26(3), 375–384 (2007) · Zbl 1259.65025 |
| [38] | Lavrentjev M.: Sur une classe de representations continues. Rec. Math. 48, 407–423 (1935) · Zbl 0014.31905 |
| [39] | Lehto O., Virtanen K.: Quasiconformal Mapping in the Plane. Springer, Berlin (1973) · Zbl 0267.30016 |
| [40] | Lévy, B., Petitjean, S., Ray, N., Maillot, J.: Least squares conformal maps for automatic texture atlas generation. SIGGRAPH 2002 pp. 362–371 (2002) |
| [41] | Lipman Y., Chen X., Daubechies I., Funkhouser T.: Symmetry factored embedding and distance. ACM Trans. Graph. 29(4), 1–12 (2010) |
| [42] | Lui, L., Wong, T., Gu, X., Thompson, P., Chan, T., Yau, S.: Compression of surface diffeomorphism using Beltrami coefficient. IEEE Comput. Vis. Patt. Recogn. (CVPR), pp. 2839–2846 (2010) |
| [43] | Lui, L., Wong, T., Gu, X., Thompson, P., Chan, T., Yau, S.: Hippocampal shape registration using Beltrami holomorphic flow. Medical Image Computing and Computer Assisted Intervention(MICCAI), Part II. LNCS 6362, pp. 323–330 (2010) |
| [44] | Lui L., Wong T., Zeng W., Gu X., Thompson P., Chan T., Yau S.: Detecting shape deformations using yamabe flow and Beltrami coefficents. J. Inverse Probl. Imaging (IPI) 4(2), 311–333 (2010) · Zbl 1203.53015 · doi:10.3934/ipi.2010.4.311 |
| [45] | Lui, L., Wong, T., Zeng, W., Gu, X., Thompson, P., Chan, T., Yau, S.: Optimization of surface registrations using beltrami holomorphic flow. J. Scientific Comput. (2011) · Zbl 1244.65096 |
| [46] | Luo F.: Combinatorial Yamabe flow on surfaces. Commun. Contemp. Math. 6(5), 765–780 (2004) · Zbl 1075.53063 · doi:10.1142/S0219199704001501 |
| [47] | Mastin C., Thompson J.: Discrete quasiconformal mappings. Z. Angew. Math. Phys. 29, 1–11 (1978) · Zbl 0377.30018 · doi:10.1007/BF01797299 |
| [48] | Mastin C., Thompson J.: Quasiconformal mappings and grid generation. SIAM J. Sci. Stat. Comput. 5(2), 305–310 (1984) · Zbl 0542.65075 · doi:10.1137/0905022 |
| [49] | Morrey C.: On the solutions of quasi-linear elliptic differential equations. Trans. Am. Math. Soc. 43, 126–166 (1938) · JFM 64.0460.02 · doi:10.1090/S0002-9947-1938-1501936-8 |
| [50] | Praun E., Hoppe H.: Spherical parametrization and remeshing. ACM Trans. Graph. 22(3), 340–349 (2003) · doi:10.1145/882262.882274 |
| [51] | Ray N., Li W.C., Levy B., Sheffer A., Alliez P.: Periodic global parameterization. ACM Trans. Graph. 25(4), 1460–1485 (2005) · doi:10.1145/1183287.1183297 |
| [52] | 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 |
| [53] | Sheffer, A., Praun, E., Rose, K.: Mesh parameterization methods and their applications. Foundations and Trends® in Computer Graphics and Vision (2012, in press) · Zbl 1143.68620 |
| [54] | Sheffer A., de Sturler E.: Parameterization of faced surfaces for meshing using angle based flattening. Eng. Comput. 17(3), 326–337 (2001) · Zbl 0983.68566 · doi:10.1007/PL00013391 |
| [55] | 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 |
| [56] | Vlasyuk, A.: Automatic construction of conformal and quasiconformal mapping of doubly connected and triple connected domains. Akad. Nauk Ukrainy Inst. Mat., preprint (Akademiya Nauk Ukrainy Institut Matematiki, preprint) 57, 1–57 (1991) |
| [57] | Wang S., Wang Y., Jin M., Gu X.D., Samaras D.: Conformal geometry and its applications on 3D shape matching, recognition, and stitching. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1209–1220 (2007) · doi:10.1109/TPAMI.2007.1050 |
| [58] | Weisel J.: Numerische ermittlung quasikonformer abbildungen mit finiten elementen. Numer. Math. 35, 201–222 (1980) · Zbl 0441.30017 · doi:10.1007/BF01396316 |
| [59] | Zayer, R., Levy, B., Seidel, H.P.: Linear angle based parameterization. In: In Symposium on Geometry Processing, pp. 135–141 (2007) |
| [60] | Zeng, W., Jin, M., Luo, F., Gu, X.: Computing canonical homotopy class representative using hyperbolic structure. In: IEEE International Conference on Shape Modeling and Applications (SMI 2009) (2009) |
| [61] | Zeng W., Marino J., Gurijala K., Gu X., Kaufman A.: Supine and prone colon registration using quasi-conformal mapping. IEEE Trans. Vis. Comput. Graph. (IEEE TVCG) 16(6), 1348–1357 (2010) · doi:10.1109/TVCG.2010.200 |
| [62] | Zeng W., Samaras D., Gu X.: Ricci flow for 3D shape analysis. IEEE Trans. Pattern Anal. Mach. Intell. 32(4), 662–677 (2010) · doi:10.1109/TPAMI.2009.201 |
| [63] | Zeng, W., Zeng, Y., Wang, Y., Yin, X., Gu, X., Samaras, D.: 3D non-rigid surface matching and registration based on holomorphic differentials. In: The 10th European Conference on Computer Vision (ECCV) 2008, pp. 1–14 (2008) |
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.
