Computing surface hyperbolic structure and real projective structure

ABSTRACT

Geometric structures are natural structures of surfaces, which enable different geometries to be defined on the surfaces. Algorithms designed for planar domains based on a specific geometry can be systematically generalized to surface domains via the corresponding geometric structure. For example, polar form splines with planar domains are based on affine invariants. Polar form splines can be generalized to manifold splines on the surfaces which admit affine structures and are equipped with affine geometries.Surfaces with negative Euler characteristic numbers admit hyperbolic structures and allow hyperbolic geometry. All surfaces admit real projective structures and are equipped with real projective geometry. Because of their general existence, both hyperbolic structures and real projective structures have the potential to replace the role of affine structures in defining manifold splines.This paper introduces theoretically rigorous and practically simple algorithms to compute hyperbolic structures and real projective structures for general surfaces. The method is based on a novel geometric tool - discrete variational Ricci flow. Any metric surface admits a special uniformization metric, which is conformal to its original metric and induces constant curvature. Ricci flow is an efficient method to calculate the uniformization metric, which determines the hyperbolic structure and real projective structure.The algorithms have been verified on real surfaces scanned from sculptures. The method is efficient and robust in practice. To the best of our knowledge, this is the first work of introducing algorithms based on Ricci flow to compute hyperbolic structure and real projective structure.More importantly, this work introduces the framework of general geometric structures, which enable different geometries to be defined on manifolds and lay down the theoretical foundation for many important applications in geometric modeling.

REFERENCES

• 1: Benzècri, J. P. 1959. Varits localement affines. Sem. Topologie et Gom. Diff., Ch. Ehresmann 7, 229--332.
• 2: Bobenko, A., and Schroder, P. 2005. Discrete willmore flow. In Eurographics Symposium on Geometry Processing.
• 3: Bobenko, A. I., and Springborn, B. A. 2004. Variational principles for circle patterns and koebe's theorem. Transactions of the American Mathematical Society 356, 659.
• 4: Carner, C., Jin, M., Gu, X., and Qin, H. 2005. Topology-driven surface mappings with robust feature alignment. In IEEE Visualization, 543--550.
• 5: Chow, B., and Luo, F. 2003. Combinatorial ricci flows on surfaces. Journal Differential Geometry 63, 1, 97--129.
• 6: Éric Colin de Verdière , Francis Lazarus, Optimal System of Loops on an Orientable Surface, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.627-636, November 16-19, 2002
• 7: Dai, J., Luo, W., Yau, S.-T., and GU, X. 2006. Geometric accuracy analysis for discrete surface approximation. In Geometric Modeling and Processing. submitted.
• 8: De Verdiére, C. 1991. Yves un principe variationnel pour les empilements de cercles. (french) "a variational principle for circle packings". Invent. Math. 104 3, 655--669.
• 9: Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Helaman Ferguson , Alyn Rockwood , Jordan Cox, Topological design of sculptured surfaces, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.149-156, July 1992
• 11: Ron Goldman, Computer Graphics in its Fifth Decade: Ferment at the Foundations, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.4, October 08-10, 2003
• 12: Craig Gotsman , Xianfeng Gu , Alla Sheffer, Fundamentals of spherical parameterization for 3D meshes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 13: Grimm, C., and Hughes, J. F. 2003. Parameterizing n-holed tori. In IMA Conference on the Mathematics of Surfaces, 14--29.
• 14: 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
• 15: 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.
• 16: Xianfeng Gu , Ying He , Hong Qin, Manifold splines, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.27-38, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060249]
• 17: Steven Haker , Sigurd Angenent , Allen Tannenbaum , Ron Kikinis , Guillermo Sapiro , Michael Halle, Conformal Surface Parameterization for Texture Mapping, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.181-189, April 2000 [doi>10.1109/2945.856998 ]
• 18: Hamilton, R. S. 1988. The ricci flow on surfaces. Mathematics and general relativity 71, 237--262.
• 19: 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]
• 20: J. W. Milnor. 1958. On the existence of a connection with curvature zero. Comm. Math. Helv. 32, 215--223.
• 21: Kharevych, L., Springborn, B., and Schroder, P. 2005. Discrete conformal mappings via circle patterns.
• 22: Luo, W., and Gu, X. 2006. Discrete curvature flow and derivative cosine law. In preprint.
• 23: Luo, W. 2006. Error estimates for discrete harmonic 1-forms over riemann surfaces. In Communications in Analysis and Geometry. submitted.
• 24: Munkres, J. 1984. Elements of Algebraic Topology. Addison-Wesley Co.
• 25: Petersen, P. 1997. Riemannian Geometry. Springer Verlag.
• 26: Emil Praun , Hugues Hoppe, Spherical parametrization and remeshing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 27: Ratcliffe, J. G. 1994. Foundations of Hyperbolic Manifolds. Springer Verlag.
• 28: Rodin, B., and Sullivan, D. 1987. The convergence of circle packings to the riemann mapping. Journal of Differential Geometry 26, 2, 349--360.
• 29: Sovakar, A., and Kobbelt, L. 2004. Api design for adaptive subdivision schemes. Computers & Graphics 28, 1, 67--72.
• 30: Stephenson, K. 2005. Introduction To Circle Packing. Cambridge University Press.
• 31: Thurston, W. 1976. Geometry and Topology of 3-manifolds. Princeton lecture notes.
• 32: Thurston, W. P. 1997. Three-Dimensional Geometry and Topology. Princeton University Presss.
• 33: Wallner, J., and Pottmann, H. 1997. Spline orbifolds. Curves and Surfaces with Applications in CAGD, 445--464.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Keywords:
affine geometry, geometric structures, hyperbolic geometry, hyperbolic structure, real projective geometry, real projective structure, ricci flow, riemann uniformization