“Locally injective parametrization with arbitrary fixed boundaries” by Weber and Zorin

  • ©Ofir Weber and Denis Zorin

Conference:


Type:


Title:

    Locally injective parametrization with arbitrary fixed boundaries

Session/Category Title: Surfaces, Deformation, and Correspondence

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We present an algorithm for mapping a triangle mesh, which is homeomorphic to a disk, to a planar domain with arbitrary fixed boundaries. The algorithm is guaranteed to produce a globally bijective map when the boundary is fixed to a shape that does not self-intersect. Obtaining a one-to-one map is of paramount importance for many graphics applications such as texture mapping. However, for other applications, such as quadrangulation, remeshing, and planar deformations, global bijectively may be unnecessarily constraining and requires significant increase on map distortion. For that reason, our algorithm allows the fixed boundary to intersect itself, and is guaranteed to produce a map that is injective locally (if such a map exists). We also extend the basic ideas of the algorithm to support the computation of discrete approximation for extremal quasiconformal maps. The algorithm is conceptually simple and fast. We demonstrate the superior robustness of our algorithm in various settings and configurations in which state-of-the-art algorithms fail to produce injective maps.

References:


    1. Ahlfors, L. 1966. Lectures on quasiconformal mappings, vol. 38. Amer. Mathematical Society.Google Scholar
    2. Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. In Computer Graphics Forum, vol. 27, Blackwell Synergy, 449–458.Google Scholar
    3. Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, 77. Google ScholarDigital Library
    4. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., Kobbelt, L., et al. 2013. Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
    5. Duren, P. L., Bollobas, B., Fulton, W., Katok, A., Kirwan, F., and Sarnak, P. 2004. Harmonic mappings in the plane, vol. 156. Cambridge University Press Cambridge.Google Scholar
    6. Eberly, D. 1998. Triangulation by ear clipping. Geometric Tools, LLC. http://www.geometrictools.com.Google Scholar
    7. Floater, M. 1997. Parametrization and smooth approximation of surface triangulations* 1. Computer Aided Geometric Design 14, 3, 231–250. Google ScholarDigital Library
    8. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
    9. Gardiner, F., and Lakic, N. 2000. Quasiconformal Teichmüller theory, vol. 76 of Mathematical Surveys and Monographs. American Mathematical Society.Google Scholar
    10. Hormann, K., and Greiner, G. 2000. Mips: An efficient global parametrization method. Curve and Surface Design: Saint-Malo 99, 153.Google Scholar
    11. Hormann, K., Lévy, B., and Sheffer, A. 2007. Mesh parameterization: Theory and practice. SIGGRAPH Course Notes. Google ScholarDigital Library
    12. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-Cover: Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3, 375–384.Google ScholarCross Ref
    13. Kanai, T., Suzuki, H., and Kimura, F. 1997. 3d geometric metamorphosis based on harmonic map. pg, 97. Google ScholarDigital Library
    14. 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
    15. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. In ACM Transactions on Graphics (TOG), vol. 21, ACM, 362–371. Google ScholarDigital Library
    16. Lipman, Y., and Funkhouser, T. 2009. Möbius voting for surface correspondence. In ACM Transactions on Graphics (TOG), vol. 28, ACM, 72. Google ScholarDigital Library
    17. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics (TOG) 31, 4, 108. Google ScholarDigital Library
    18. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. 2008. A local/global approach to mesh parameterization. In Computer Graphics Forum, vol. 27, Wiley Online Library, 1495–1504. Google ScholarDigital Library
    19. Marx, M. 1974. Extensions of normal immersions of s 1 into r 2. Transactions of the American Mathematical Society 187, 309–326.Google Scholar
    20. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental mathematics 2, 1, 15–36.Google Scholar
    21. Schneider, T., Hormann, K., and Floater, M. S. 2013. Bijective composite mean value mappings. In Computer Graphics Forum, vol. 32, Wiley Online Library, 137–146. Google ScholarDigital Library
    22. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. In Computer Graphics Forum, vol. 32, Wiley Online Library, 125–135. Google ScholarDigital Library
    23. Sheffer, A., and de Sturler, E. 2001. Parameterization of Faceted Surfaces for Meshing using Angle-Based Flattening. Engineering with Computers 17, 3, 326–337.Google ScholarCross Ref
    24. 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
    25. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Foundations and Trends® in Computer Graphics and Vision 2, 2, 171. Google ScholarDigital Library
    26. Shewchuk, J. 1996. Robust adaptive floating-point geometric predicates. In Proceedings of the twelfth annual symposium on Computational geometry, ACM, 141–150. Google ScholarDigital Library
    27. Shewchuk, J. R. 2005. Triangle: A two-dimensional quality mesh generator and delaunay triangulator. Computer Science Division, University of California at Berkeley, Berkeley, California, 94720–1776.Google Scholar
    28. Shor, P., and Van Wyk, C. 1992. Detecting and decomposing self-overlapping curves. Computational Geometry 2, 1, 31–50. Google ScholarDigital Library
    29. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes.Google Scholar
    30. Tutte, W. 1963. How to draw a graph. Proc. London Math. Soc 13, 3, 743–768.Google ScholarCross Ref
    31. Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. In Computer Graphics Forum, vol. 31, Wiley Online Library, 1679–1689. Google ScholarDigital Library
    32. Wein, R., Berberich, E., Fogel, E., Halperin, D., Hemmer, M., Salzman, O., and Zukerman, B. 2013. 2D arrangements. In CGAL User and Reference Manual, 4.3 ed. CGAL Editorial Board.Google Scholar
    33. Whitney, H. 1937. On regular closed curves in the plane. Compositio Math 4, 276–284.Google Scholar
    34. Xu, Y., Chen, R., Gotsman, C., and Liu, L. 2011. Embedding a triangular graph within a given boundary. Computer Aided Geometric Design 28, 6, 349–356. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page: