skip to main content
10.1145/1629255.1629267acmotherconferencesArticle/Chapter ViewAbstractPublication PagesspmConference Proceedingsconference-collections
research-article

Generalized Koebe's method for conformal mapping multiply connected domains

Published: 05 October 2009 Publication History

Abstract

Surface parameterization refers to the process of mapping the surface to canonical planar domains, which plays crucial roles in texture mapping and shape analysis purposes. Most existing techniques focus on simply connected surfaces. It is a challenging problem for multiply connected genus zero surfaces. This work generalizes conventional Koebe's method for multiply connected planar domains. According to Koebe's uniformization theory, all genus zero multiply connected surfaces can be mapped to a planar disk with multiply circular holes. Furthermore, this kind of mappings are angle preserving and differ by Möbius transformations. We introduce a practical algorithm to explicitly construct such a circular conformal mapping. Our algorithm pipeline is as follows: suppose the input surface has n boundaries, first we choose 2 boundaries, and fill the other n -- 2 boundaries to get a topological annulus; then we apply discrete Yamabe flow method to conformally map the topological annulus to a planar annulus; then we remove the filled patches to get a planar multiply connected domain. We repeat this step for the planar domain iteratively. The two chosen boundaries differ from step to step. The iterative construction leads to the desired conformal mapping, such that all the boundaries are mapped to circles. In theory, this method converges quadratically faster than conventional Koebe's method. We give theoretic proof and estimation for the converging rate. In practice, it is much more robust and efficient than conventional non-linear methods based on curvature flow. Experimental results demonstrate the robustness and efficiency of the method.

References

[1]
Boris Springborn, P. S., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Transactions on Graphics 27, 3, 1--11.
[2]
Chow, B., and F. Luo. 2003. Combinatorial ricci flows on surfaces. Journal of Differential Geometry 63, 1, 97--129.
[3]
Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. Computer Graphics Forum (Proc. Eurographics 2002) 21, 3, 209--218.
[4]
Desbrun, M. 2006. Discrete differential forms and applications to surface tiling. In SoCG '06: Proceedings of the twenty-second annual symposium on Computational geometry, ACM, 40--40.
[5]
Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling. Springer, 157--186.
[6]
Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19--27.
[7]
Gortler, S. J., Gotsman, C., and Thurston, D. 2005. Discrete oneforms on meshes and applications to 3D mesh parameterization. Computer Aided Geometric Design 23, 2, 83--112.
[8]
Gotsman, C., Gu, X., and Sheffer, A. 2003. Fundamentals of spherical parameterization for 3d meshes. ACM Transactions on Graphics 22, 3, 358--363.
[9]
Gu, X., and Yau, S.-T. 2003. Global conformal parameterization. In Symposium on Geometry Processing, 127--137.
[10]
Gu, X., Wang, Y., Chan, T. F., Thompson, P. M., and Yau, S.-T. 2004. Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Trans. Med. Imaging 23, 8, 949--958.
[11]
Gu, X., He, Y., and Qin, H. 2006. Manifold splines. Graphical Models 68, 3, 237--254.
[12]
Guggenheimer, H. W. 1977. Differential Geometry. Dover Publications.
[13]
Hamilton, R. S. 1982. Three manifolds with positive ricci curvature. Journal of Differential Geometry 17, 255--306.
[14]
Henrici, P. 1993. Applide and Computational Complex Analysis, Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps, Univalent Functions, vol. 3. Wiley-Interscience.
[15]
Hirani, A. N. 2003. Discrete exterior calculus. PhD thesis, California Institute of Technology.
[16]
Hong, W., Gu, X., Qiu, F., Jin, M., and Kaufman, A. E. 2006. Conformal virtual colon flattening. In Symposium on Solid and Physical Modeling, 85--93.
[17]
Jin, M., Wang, Y., Yau, S.-T., and Gu, X. 2004. Optimal global conformal surface parameterization. In IEEE Visualization 2004, 267--274.
[18]
Jin, M., Luo, F., and Gu, X. 2006. Computing surface hyperbolic structure and real projective structure. In SPM '06: Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling, 105--116.
[19]
Jin, M., Kim, J., Luo, F., and Gu, X. 2008. Discrete surface ricci flow. IEEE TVCG 14, 5, 1030--1043.
[20]
Jin, M., Zeng, W., Luo, F., and Gu, X. 2008. Computing teichmüller shape space. IEEE TVCG 99, 2, 1030--1043.
[21]
Kraevoy, V., and Sheffer, A. 2004. Cross-parameterization and compatible remeshing of 3d models. ACM Transactions on Graphics 23, 3, 861--869.
[22]
Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. SIGGRAPH 2002, 362--371.
[23]
Li, X., Bao, Y., Guo, X., Jin, M., Gu, X., and Qin, H. 2008. Globally optimal surface mapping for surfaces with arbitrary topology. IEEE TVCG 14, 4, 805--819.
[24]
Luo, F. 2004. Combinatorial yamabe flow on surfaces. Commun. Contemp. Math. 6, 5, 765--780.
[25]
Mercat, C. 2004. Discrete riemann surfaces and the ising model. Communications in Mathematical Physics 218, 1, 177--216.
[26]
Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1, 15--36.
[27]
Tewari, G., Gotsman, C., and Gortler, S. J. 2006. Meshing genus-1 point clouds using discrete one-forms. Comput. Graph. 30, 6, 917--926.
[28]
Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing, 201--210.
[29]
Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Symposium on Geometry Processing, 201--210.
[30]
Wang, Y., Gupta, M., Zhang, S., Wang, S., Gu, X., Samaras, D., and Huang, P. 2005. High resolution tracking of non-rigid 3d motion of densely sampled data using harmonic maps. In ICCV, 388--395.
[31]
Wang, S., Wang, Y., Jin, M., Gu, X. D., and Samaras, D. 2007. Conformal geometry and its applications on 3d shape matching, recognition, and stitching. IEEE Trans. Pattern Anal. Mach. Intell. 29, 7, 1209--1220.
[32]
Weitraub, S. H. 2007. Differential Forms: A Complement to Vector Calculus. Academic Press.
[33]
Xu, G. 2008. Finite element methods for geometric modeling and processing using general fourth order geometric flows. In GMP, 164--177.
[34]
Yin, X., Dai, J., Yau, S.-T., and Gu, X. 2008. Slit map: Conformal parameterization for multiply connected surfaces. In Advances in Geometric Modeling and Processing, 5th International Conference, GMP, Springer, vol. 4975 of Lecture Notes in Computer Science, 410--422.
[35]
Zeng, W., Yin, X., Zeng, Y., Wang, Y., Gu, X., and Samaras, D. 2008. 3d face matching and registration based on hyperbolic ricci flow. In CVPR 2008 Workshop on 3D Face Processing.
[36]
Zeng, W., Zeng, Y., Wang, Y., Yin, X., Gu, X., and Samaras, D. 2008. 3d non-rigid surface matching and registration based on holomorphic differentials. In The 10th European Conference on Computer Vision (ECCV) 2008, 1--14.
[37]
Zeng, W., Jin, M., Luo, F., and Gu, X. 2009. Canonical homotopy class representative using hyperbolic structure. In IEEE SMI.
[38]
Zeng, W., Lui, L.-M., Gu, X., and Yau, S.-T. 2009. Shape analysis by conformal modules. Methods and Applications of Analysis.

Cited By

View all
  • (2023)Recent Developments of Surface Parameterization Methods Using Quasi-conformal GeometryHandbook of Mathematical Models and Algorithms in Computer Vision and Imaging10.1007/978-3-030-98661-2_113(1483-1523)Online publication date: 25-Feb-2023
  • (2023)Computational Conformal Geometric Methods for VisionHandbook of Mathematical Models and Algorithms in Computer Vision and Imaging10.1007/978-3-030-98661-2_107(1739-1790)Online publication date: 25-Feb-2023
  • (2022)Parallelizable Global Quasi-Conformal Parameterization of Multiply Connected Surfaces via Partial WeldingSIAM Journal on Imaging Sciences10.1137/21M146632315:4(1765-1807)Online publication date: 1-Jan-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling
October 2009
380 pages
ISBN:9781605587110
DOI:10.1145/1629255
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

  • SIAM Activity Group on Geometric Design

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 October 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. circular
  2. conformal
  3. differential form
  4. holomorphic
  5. multiply connected domain
  6. uniformization

Qualifiers

  • Research-article

Funding Sources

Conference

SIAM '09
Sponsor:

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)1
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Recent Developments of Surface Parameterization Methods Using Quasi-conformal GeometryHandbook of Mathematical Models and Algorithms in Computer Vision and Imaging10.1007/978-3-030-98661-2_113(1483-1523)Online publication date: 25-Feb-2023
  • (2023)Computational Conformal Geometric Methods for VisionHandbook of Mathematical Models and Algorithms in Computer Vision and Imaging10.1007/978-3-030-98661-2_107(1739-1790)Online publication date: 25-Feb-2023
  • (2022)Parallelizable Global Quasi-Conformal Parameterization of Multiply Connected Surfaces via Partial WeldingSIAM Journal on Imaging Sciences10.1137/21M146632315:4(1765-1807)Online publication date: 1-Jan-2022
  • (2022)Recent Developments of Surface Parameterization Methods Using Quasi-conformal GeometryHandbook of Mathematical Models and Algorithms in Computer Vision and Imaging10.1007/978-3-030-03009-4_113-1(1-41)Online publication date: 6-May-2022
  • (2021) Computation of free boundary minimal surfaces via extremal Steklov eigenvalue problems ESAIM: Control, Optimisation and Calculus of Variations10.1051/cocv/202103327(34)Online publication date: 30-Apr-2021
  • (2021)Efficient Conformal Parameterization of Multiply-Connected Surfaces Using Quasi-Conformal TheoryJournal of Scientific Computing10.1007/s10915-021-01479-y87:3Online publication date: 1-Jun-2021
  • (2021)Computational Conformal Geometric Methods for VisionHandbook of Mathematical Models and Algorithms in Computer Vision and Imaging10.1007/978-3-030-03009-4_107-1(1-52)Online publication date: 26-Aug-2021
  • (2020)An Efficient Data Retrieval Parallel Reeb Graph AlgorithmAlgorithms10.3390/a1310025813:10(258)Online publication date: 12-Oct-2020
  • (2020)Modeling the Space of Point Landmark Constrained DiffeomorphismsComputer Vision – ECCV 202010.1007/978-3-030-58577-8_22(357-373)Online publication date: 24-Sep-2020
  • (2019)Automatic and Robust Skull Registration Based on Discrete Uniformization2019 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV.2019.00052(431-440)Online publication date: Oct-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media