Boris Springborn
Skip Abstract Section
Skip Supplemental Material SectionAbstract
We present a new algorithm for conformal mesh parameterization. It is based on a precise notion of discrete conformal equivalence for triangle meshes which mimics the notion of conformal equivalence for smooth surfaces. The problem of finding a flat mesh that is discretely conformally equivalent to a given mesh can be solved efficiently by minimizing a convex energy function, whose Hessian turns out to be the well known cot-Laplace operator. This method can also be used to map a surface mesh to a parameter domain which is flat except for isolated cone singularities, and we show how these can be placed automatically in order to reduce the distortion of the parameterization. We present the salient features of the theory and elaborate the algorithms with a number of examples.
Supplemental Material
- Balay, S., Buschelman, K., Eijkhout, V., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2007. PETSc Users Manual. Tech. Rep. ANL-95/11 (Revision 2.3.3), Argonne National Laboratory. http://www.mcs.anl.gov/petsc/.Google Scholar
- Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. Comp. Graph. Forum 27 2, 449--458.Google ScholarCross Ref
- Benson, S., McInnes, L. C., Moré, J., Munson, T., and Sarich, J. 2007. TAO User Manual. Tech. Rep. ANL/MCS-TM-242 (Revision 1.9), Argonne National Laboratory. http://www.mcs.anl.gov/tao.Google Scholar
- Bobenko, A. I., and Springborn, B. A. 2004. Variational Principles for Circle Patterns and Koebe's Theorem. Trans. Amer. Math. Soc. 356, 2, 659--689.Google ScholarCross Ref
- Bobenko, A. I., and Suris, Y. B., 2005. Discrete Differential Geometry. Consistency as Integrability. Preprint arXiv:math/0504358v1. To appear in Graduate Studies in Mathematics of the AMS.Google Scholar
- Bowers, P. L., and Hurdal, M. K. 2003. Planar Conformal Mappings of Piecewise Flat Surfaces. In Vis. and Math. III. Springer, 3--34.Google Scholar
- Chow, B., and Luo, F. 2003. Combinatorial Ricci Flows on Surfaces. J. Diff. Geom. 63, 1, 97--129.Google ScholarCross Ref
- Colin de Verdière, Y. 1991. Un Principe Variationnel pour les Empilements de Cercles. Invent. Math. 104, 655--669.Google ScholarCross Ref
- Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic Parameterizations of Surface Meshes. Comp. Graph. Forum 21, 3, 209--218.Google ScholarCross Ref
- Duffin, R. J. 1956. Basic Properties of Discrete Analytic Functions. Duke Math. J. 23, 335--363.Google ScholarCross Ref
- Duffin, R. 1959. Distributed and Lumped Networks. J. Math. Mech. {continued as Indiana Univ. Math. J.} 8, 793--826.Google ScholarCross Ref
- Erickson, J., and Whittlesey, K. 2005. Greedy Optimal Homotopy and Homology Generators. In Proc. ACM/SIAM Symp. on Disc. Alg., SIAM, 1038--1046. Google ScholarDigital Library
- Floater, M. S., and Hormann, K. 2005. Surface Parameterization: a Tutorial and Survey. In Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization. Springer, 157--186.Google Scholar
- Gu, X., and Yau, S.-T. 2003. Global Conformal Surface Parameterization. In Proc. Symp. Geom. Proc., Eurographics, 127--137. Google ScholarDigital Library
- Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry Images. ACM Trans. Graph. 21, 3, 355--361. Google ScholarDigital Library
- Jin, M., Kim, J., and Gu, X. D. 2007. Discrete Surface Ricci Flow: Theory and Applications. In Mathematics of Surfaces 2007, R. Martin, M. Sabin, and J. Winkler, Eds., Vol. 4647 of Lecture Notes in Computer Science. Springer, 209--232. Google ScholarDigital Library
- Kälberer, F., Nieser, M., and Polthier, K. 2007. QuadCover---Surface Parameterization using Branched Coverings. Comp. Graph. Forum 26, 3, 375--384.Google ScholarCross Ref
- Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete Conformal Mappings via Circle Patterns. ACM Trans. Graph. 25, 2, 412--438. Google ScholarDigital Library
- Leibon, G. 2002. Characterizing the Delaunay Decompositions of Compact Hyperbolic Surfaces. Geom. Topol. 6, 361--391.Google ScholarCross Ref
- Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21, 3, 362--371. Google ScholarDigital Library
- Lewin, L. 1981. Polylogarithms and Associated Functions. North Holland.Google Scholar
- Luo, F. 2004. Combinatorial Yamabe Flow on Surfaces. Commun. Contemp. Math. 6, 765--780.Google ScholarCross Ref
- Macleod, A. J. 1996. Algorithm 757: MISCFUN, a Software Package to Compute Uncommon Special Functions. ACM Trans. Math. Softw. 22, 3, 288--301. Google ScholarDigital Library
- Mercat, C. 2001. Discrete Riemann Surfaces and the Ising Model. Comm. in Math. Physics 218, 1, 177--216.Google ScholarCross Ref
- Milnor, J. 1982. Hyperbolic Geometry: The First 150 Years. Bul. Amer. Math. Soc. 6, 1, 9--24.Google ScholarCross Ref
- Pinkall, U., and Polthier, K. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experiment. Math. 2, 1, 15--36.Google ScholarCross Ref
- Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4, 1460--1485. Google ScholarDigital Library
- Rivin, I. 1994. Euclidean Structures on Simplicial Surfaces and Hyperbolic Volume. Ann. of Math. (2) 139, 553--580.Google Scholar
- Sheffer, A., and Hart, J. C. 2002. Seamster: Inconspicuous Low-Distortion Texture Seam Layout. In Proc. IEEE Vis., IEEE Comp. Soc., 291--298. Google ScholarDigital Library
- Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. ABF++: Fast and Robust Angle Based Flattening. ACM Trans. Graph. 24, 2, 311--330. Google ScholarDigital Library
- Sheffer, A., Praun, E., and Rose, K. 2006. Mesh Parameterization Methods and their Applications. Found. Trends Comput. Graph. Vis. 2, 2, 105--171. Google ScholarDigital Library
- Springborn, B. 2005. A Unique Representation of Polyhedral Types. Centering via Möbius Transformations. Math. Z. 249, 513--517.Google ScholarCross Ref
- Steihaug, T. 1983. The Conjugate Gradient Method and Trust Regions in Large Scale Optimization. SIAM J. Numer. Anal. 20, 3, 626--637.Google ScholarDigital Library
- Stephenson, K. 2003. Circle Packing: A Mathematical Tale. Notices Amer. Math. Soc. 50, 11, 1376--1388.Google Scholar
- Stephenson, K. 2005. Introduction to Circle Packing. Cambridge University Press.Google Scholar
- Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2007. Designing Quadrangulations with Discrete Harmonic Forms. In Proc. Symp. Geom. Proc., Eurographics, 201--210. Google ScholarDigital Library
- Troyanov, M. 1986. Les Surfaces Euclidiennes à Singularités Coniques. Enseign. Math. (2) 32, 79--94.Google Scholar
- Yang, Y., Kim, J., Luo, F., Hu, S., and Gu, D. 2008. Optimal Surface Parameterization Using Inverse Curvature Map. IEEE Trans. Vis. Comp. Graph. (to appear). Google ScholarDigital Library
- Zayer, R., Lévy, B., and Seidel, H.-P. 2007. Linear Angle Based Parameterization. In Proc. Symp. Geom. Proc., Eurographics, 135--141. Google ScholarDigital Library
Index Terms
- Conformal equivalence of triangle meshes
Recommendations
Discrete conformal equivalence of polyhedral surfaces
This paper describes a numerical method for surface parameterization, yielding maps that are locally injective and discretely conformal in an exact sense. Unlike previous methods for discrete conformal parameterization, the method is guaranteed to work ...
Discrete conformal mappings via circle patterns
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 ...
Developability of triangle meshes
Developable surfaces are those that can be made by smoothly bending flat pieces without stretching or shearing. We introduce a definition of developability for triangle meshes which exactly captures two key properties of smooth developable surfaces, ...
Comments