“Locally injective parametrization with arbitrary fixed boundaries” by Weber and Zorin
Conference:
Type(s):
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