Generalized Koebe's method for conformal mapping multiply connected domains

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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Keywords:
circular, conformal, differential form, holomorphic, multiply connected domain, uniformization