Abstract
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 differentials. 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 (AM) 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.
Similar content being viewed by others
References
Ahlfors L.: Conformality with respect to Riemannian matrices. Ann. Acad. Sci. Fenn. Ser. 206, 1–22 (1955)
Ahlfors L.: Lectures in Quasiconformal Mappings. Van Nostrand Reinhold, New York (1966)
Ben-Chen M., Gotsman C., Bunin G.: Conformal flattening by curvature prescription and metric scaling. Comput. Graph. Forum 27(2), 449–458 (2008)
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)
Bers L.: Mathematical Aspects of Subcritical and Transonic Gas Dynamics. Wiley, New York (1958)
Bers L.: Quasiconformal mappings, with applications to differential equations, function theory and topology. Am. Math. Soc. Bull. 83(6), 1083–1100 (1977)
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)
Bobenko, A., Springborn, B., Pinkall, U.: Discrete conformal equivalence and ideal hyperbolic polyhedra (2012, in press)
Bobenko A.I., Springborn B.A.: Variational principles for circle patterns and koebe’s theorem. Trans. Am. Math. Soc. 356, 659–689 (2004)
Bowers, P.L., Hurdal, M.: Planar conformal mapping of piecewise flat surfaces. In: Visualization and Mathematics III, pp. 3–34. Springer, Berlin (2003)
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)
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)
Carleson L., Gamelin T.: Complex Dynamics. Springer, New York (1993)
Chow B.: The Ricci flow on the 2-sphere. J. Differ. Geom. 33(2), 325–334 (1991)
Chow B., Luo F.: Combinatorial Ricci flows on surfaces. J. Differ. Geom. 63(1), 97–129 (2003)
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)
Daripa P.: On a numerical method for quasiconformal grid generation. J. Comput. Phys. 96, 229–236 (1991)
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)
Daripa P., Masha D.: An efficient and novel numerical method for quasiconformal mappings of doubly connected domains. Numer. Algorithm 18, 159–175 (1998)
Desbrun M., Meyer M., Alliez P.: Intrinsic parameterizations of surface meshes. Comput. Graph. Forum (Proc. Eurographics 2002) 21(3), 209–218 (2002)
Farkas H.M., Kra I.: Riemann Surfaces. Springer, Berlin (2004)
Floater, M.S., Hormann, K.: Surface parameterization: a tutorial and survey. In: Advances in Multiresolution for Geometric Modelling, pp. 157–186. Springer, Berlin (2005)
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)
Gotsman C., Gu X., Sheffer A.: Fundamentals of spherical parameterization for 3D meshes. ACM Trans. Graph. 22(3), 358–363 (2003)
Grimm, C., Hughes, J.F.: Parameterizing N-holed tori. In: IMA Conference on the Mathematics of Surfaces, pp. 14–29 (2003)
Grotzsch H.: Uber die verzerrung bei schlichten nichtkonformen abbildungen und eine damit zusammenh angende erweiterung des picardschen. Rec. Math. 80, 503–507 (1928)
Gu X., He Y., Qin H.: Manifold splines. Graph. Models 68(3), 237–254 (2006)
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)
Gu, X., Yau, S.T.: Global conformal parameterization. In: Symposium on Geometry Processing, pp. 127–137 (2003)
Guggenheimer H.W.: Differential Geometry. Dover Publications, New York (1977)
Hamilton R.S.: Three manifolds with positive Ricci curvature. J. Differ. Geom. 17, 255–306 (1982)
Hamilton R.S.: The Ricci flow on surfaces. Math. Gen. Relativ. 71, 237–262 (1988)
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)
Hormann, K., Levy, B., Sheffer, A.: Mesh parameterization. SIGGRAPH 2007 Course Notes 2 (2007)
Jin M., Kim J., Luo F., Gu X.: Discrete surface Ricci flow. IEEE Trans. Vis. Comput. Graph. 14(5), 1030–1043 (2008)
Kharevych L., Springerborn B., Schröder P.: Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25(2), 412–438 (2006)
Kalberer F., Nieser M., Polthicr K.: Quadcover—surface parameterization using branched coverings. Comput. Graph. 26(3), 375–384 (2007)
Lavrentjev M.: Sur une classe de representations continues. Rec. Math. 48, 407–423 (1935)
Lehto O., Virtanen K.: Quasiconformal Mapping in the Plane. Springer, Berlin (1973)
Lévy, B., Petitjean, S., Ray, N., Maillot, J.: Least squares conformal maps for automatic texture atlas generation. SIGGRAPH 2002 pp. 362–371 (2002)
Lipman Y., Chen X., Daubechies I., Funkhouser T.: Symmetry factored embedding and distance. ACM Trans. Graph. 29(4), 1–12 (2010)
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)
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)
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)
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)
Luo F.: Combinatorial Yamabe flow on surfaces. Commun. Contemp. Math. 6(5), 765–780 (2004)
Mastin C., Thompson J.: Discrete quasiconformal mappings. Z. Angew. Math. Phys. 29, 1–11 (1978)
Mastin C., Thompson J.: Quasiconformal mappings and grid generation. SIAM J. Sci. Stat. Comput. 5(2), 305–310 (1984)
Morrey C.: On the solutions of quasi-linear elliptic differential equations. Trans. Am. Math. Soc. 43, 126–166 (1938)
Praun E., Hoppe H.: Spherical parametrization and remeshing. ACM Trans. Graph. 22(3), 340–349 (2003)
Ray N., Li W.C., Levy B., Sheffer A., Alliez P.: Periodic global parameterization. ACM Trans. Graph. 25(4), 1460–1485 (2005)
Sheffer A., Lévy B., Mogilnitsky M., Bogomyakov A.: ABF++: fast and robust angle based flattening. ACM Trans. Graph. 24(2), 311–330 (2005)
Sheffer, A., Praun, E., Rose, K.: Mesh parameterization methods and their applications. Foundations and Trends® in Computer Graphics and Vision (2012, in press)
Sheffer A., de Sturler E.: Parameterization of faced surfaces for meshing using angle based flattening. Eng. Comput. 17(3), 326–337 (2001)
Springborn B., Schröder P., Pinkall U.: Conformal equivalence of triangle meshes. ACM Trans. Graph. 27(3), 1–11 (2008)
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)
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)
Weisel J.: Numerische ermittlung quasikonformer abbildungen mit finiten elementen. Numer. Math. 35, 201–222 (1980)
Zayer, R., Levy, B., Seidel, H.P.: Linear angle based parameterization. In: In Symposium on Geometry Processing, pp. 135–141 (2007)
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)
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)
Zeng W., Samaras D., Gu X.: Ricci flow for 3D shape analysis. IEEE Trans. Pattern Anal. Mach. Intell. 32(4), 662–677 (2010)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
T. F. Chan is supported by NSF GEO0610079, NSF IIS0914580, NIH U54RR021813 and ONR N000140910105. D. X. Gu is supported by NIH R01EB0075300A1, NSF IIS0916286, NSF CCF0916235, NSF CCF0830550, NSF III0713145, and ONR N000140910228. L.M. Lui is supported by CUHK Direct Grant (Project ID: 2060413).
Rights and permissions
About this article
Cite this article
Zeng, W., Lui, L.M., Luo, F. et al. Computing quasiconformal maps using an auxiliary metric and discrete curvature flow. Numer. Math. 121, 671–703 (2012). https://doi.org/10.1007/s00211-012-0446-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-012-0446-z