Discrete conformal mappings via circle patterns

ABSTRACT

We introduce a novel method for the construction of discrete conformal mappings from surface meshes of arbitrary topology to the plane. Our approach is based on circle patterns, that is, arrangements of circles---one for each face---with prescribed intersection angles. Given these angles, the circle radii follow as the unique minimizer of a convex energy. The method supports very flexible boundary conditions ranging from free boundaries to control of the boundary shape via prescribed curvatures. Closed meshes of genus zero can be parameterized over the sphere. To parameterize higher genus meshes, we introduce cone singularities at designated vertices. The parameter domain is then a piecewise Euclidean surface. Cone singularities can also help to reduce the often very large area distortion of global conformal maps to moderate levels. Our method involves two optimization problems: a quadratic program and the unconstrained minimization of the circle pattern energy. The latter is a convex function of logarithmic radius variables with simple explicit expressions for gradient and Hessian. We demonstrate the versatility and performance of our algorithm with a variety of examples.

REFERENCES

• 1: Marshall W. Bern , David Eppstein, Optimal Möbius Transformations for Information Visualization and Meshing, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.14-25, August 08-10, 2001
• 2: Bobenko, A. I. and Springborn, B. A. 2004. Variational principles for circle patterns and Koebe's Theorem. Trans. Amer. Math. Soc. 356, 659--689.
• 3: Bobenko, A. I. and Springborn, B. A. 2005. A discrete Laplace-Beltrami operator for simplicial surfaces. http://arxiv.org/abs/math.DG/0503219.
• 4: Bowers, P. L. and Hurdal, M. K. 2003. Planar conformal mappings of piecewise flat surfaces. In Visualization and Mathematics III, H.-C. Hege and K. Polthier, Eds. Mathematics and Visualization. Springer-Verlag, Berlin, Germany, 3--34.
• 5: Brägger, W. 1992. Kreispackungen und Triangulierungen. L'Enseignement Mathématique 38, 201--217.
• 6: Colin de Verdière, Y. 1991. Un principe variationnel pour les empilements de cercles. Inventiones Mathematicae 104, 655--669.
• 7: Charles R. Collins , Kenneth Stephenson, A circle packing algorithm, Computational Geometry: Theory and Applications, v.25 n.3, p.233-256, July 2003 [doi>10.1016/S0925-7721(02)00099-8]
• 8: Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. In Proceedings of Eurographics Computer Graphics Forum 21, 3, 209--218.
• 9: Michael B. Dillencourt , Warren D. Smith, Graph-theoretical conditions for inscribability and Delaunay realizability, Discrete Mathematics, v.161 n.1-3, p.63-77, Dec. 5, 1996 [doi>10.1016/0012-365X(95)00276-3 ]
• 10: Erickson, J. and Har-Peled, S. 2004. Optimally cutting a surface into a disk. Discrete Computat. Geometry 31, 1, 37--59.
• 11: Friedel, I., Schröder, P., and Desbrun, M. 2005. Unconstrained spherical parameterization. (http://multires.caltech.edu/pubs/SParam_JGT.pdf). Submitted for Publication.
• 12: Michael Garland , Andrew Willmott , Paul S. Heckbert, Hierarchical face clustering on polygonal surfaces, Proceedings of the 2001 symposium on Interactive 3D graphics, p.49-58, March 2001 [doi>10.1145/364338.364345]
• 13: Grünbaum, B. 2003. Convex Polytopes, 2nd Ed. Graduate Texts in Mathematics, vol. 221. Springer-Verlag, New York, NY.
• 14: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 15: Xianfeng Gu , Shing-Tung Yau, Global conformal surface parameterization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 16: Anil Nirmal Hirani , Jerrold E. Marsden, Discrete exterior calculus, 2003
• 17: C. Indermitte , Th. Liebling , M. Troyanov , H. Clémençon, Voronoi diagrams on piecewise flat surfaces and an application to biological growth, Theoretical Computer Science, v.263 n.1-2, p.268-274, July 28 2001
• 18: Miao Jin , Yalin Wang , Shing-Tung Yau , Xianfeng Gu, Optimal Global Conformal Surface Parameterization, Proceedings of the conference on Visualization '04, p.267-274, October 10-15, 2004 [doi>10.1109/VIS.2004.75]
• 19: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 20: Andrei Khodakovsky , Nathan Litke , Peter Schröder, Globally smooth parameterizations with low distortion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 21: Leibon, G. 2002. Characterizing the Delaunay decompositions of compact hyperbolic surfaces. Geometry Topolo. 6, 361--391.
• 22: Bruno Lévy , Sylvain Petitjean , Nicolas Ray , Jérome Maillot, Least squares conformal maps for automatic texture atlas generation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 23: Mercat, C. 2001. Discrete Riemann surfaces and the Ising model. Comm. Math. Physics 218, 1, 177--216.
• 24: Mosek. 2005. Constrained quadratic minimization software. Version 3.1r42. http://www.mosek.com/.
• 25: Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2, 1, 15--36.
• 26: Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2005. Periodic global parameterizations. (http://www.loria.fr/~levy/publications/papers/2005/PGP/pgp.pdf). Submitted for publication.
• 27: Rivin, I. 1994. Euclidean structures on simplicial surfaces and hyperbolic volume. Annals of Math. 139, 3, 553--580.
• 28: Rodin, B. and Sullivan, D. 1987. The convergence of circle packings to the Riemann mapping. J. Differ. Geometry 26, 2, 349--360.
• 29: Pedro V. Sander , John Snyder , Steven J. Gortler , Hugues Hoppe, Texture mapping progressive meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.409-416, August 2001 [doi>10.1145/383259.383307]
• 30: P. V. Sander , Z. J. Wood , S. J. Gortler , J. Snyder , H. Hoppe, Multi-chart geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 31: Sheffer, A. and de Sturler, E. 2000. Surface Parameterization for meshing by triangulation flattening. In Proceedings of the 9th International Meshing Roundtable. Sandia National Labs, 161--172.
• 32: Alla Sheffer , John C. Hart, Seamster: inconspicuous low-distortion texture seam layout, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 33: Alla Sheffer , Bruno Lévy , Maxim Mogilnitsky , Alexander Bogomyakov, ABF++: fast and robust angle based flattening, ACM Transactions on Graphics (TOG), v.24 n.2, p.311-330, April 2005 [doi>10.1145/1061347.1061354]
• 34: Olga Sorkine , Daniel Cohen-Or , Rony Goldenthal , Dani Lischinski, Bounded-distortion piecewise mesh parameterization, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 35: Springborn, B. A. 2005. A unique representation of polyhedral types. Centering via Möbius transformations. Mathematische Zeitschrift 249, 3, 513--517.
• 36: Marco Tarini , Kai Hormann , Paolo Cignoni , Claudio Montani, PolyCube-Maps, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 37: Thurston, W. P. 1980. The geometry and topology of three-manifolds. Available at http://www.msri.org/publications/books/gt3m/.
• 38: Thurston, W. P. 1985. The finite Riemann mapping theorem. At the Symposium on the Occasion of the Proof of the Bieberbach Conjecture. Purdue University (March).
• 39: Troyanov, M. 1991. Prescribing curvature on compact surfaces with conical singularities. Trans. Amer. Math. Society 324, 793--821.
• 40: Zayer, R., Rössl, C., and Seidel, H.-P. 2003. Convex boundary angle based flattening. In Proceedings of Vision, Modeling and Visualiza. 281--288.
• 41: Eugene Zhang , Konstantin Mischaikow , Greg Turk, Feature-based surface parameterization and texture mapping, ACM Transactions on Graphics (TOG), v.24 n.1, p.1-27, January 2005 [doi>10.1145/1037957.1037958]
• 42: Ziegler, G. M. 2004. Convex polytopes: Extremal constructions and f-vector shapes. IAS/Park City Mathematics Series, vol. 14. http://arxiv.org/abs/math/0411400. To Appear.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
Conformal parameterizations, circle patterns, discrete analytic functions, discrete differential geometry, meshing, texture mapping