“Bijective maps from simplicial foliations”
Conference:
Type(s):
Title:
- Bijective maps from simplicial foliations
Session/Category Title: CORRESPONDENCE & MAPPING
Presenter(s)/Author(s):
Moderator(s):
Abstract:
This paper presents a method for bijective parametrization of 2D and 3D objects over canonical domains. While a range of solutions for the two-dimensional case are well-known, our method guarantees bijectivity of mappings also for a large, combinatorially-defined class of tetrahedral meshes (shellable meshes). The key concept in our method is the piecewise-linear (PL) foliation, decomposing the mesh into one-dimensional submanifolds and reducing the mapping problem to parametrization of a lower-dimensional manifold (a foliation section). The maps resulting from these foliations are proved to be bijective and continuous, and shown to have provably bijective PL approximations. We describe exact, numerically robust evaluation methods and demonstrate our implementation’s capabilities on a large variety of meshes.
References:
1. Adiprasito, K. A., and Benedetti, B. 2012. Subdivisions, shellability, and collapsibility of products. arXiv:1202.6606.Google Scholar
2. Adiprasito, K. A., and Izmestiev, I. 2015. Derived subdivisions make every PL sphere polytopal. Israel Journal of Mathematics 208, 1, 443–450.Google ScholarCross Ref
3. Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3D. ACM Trans. Graph. 32, 4, 106:1–106:14. Google ScholarDigital Library
4. Aigerman, N., and Lipman, Y. 2015. Orbifold tutte embeddings. ACM Trans. Graph. 34, 6, 190:1–190:12. Google ScholarDigital Library
5. Aigerman, N., Poranne, R., and Lipman, Y. 2015. Seamless surface mappings. ACM Trans. Graph. 34, 4, 72:1–72:13. Google ScholarDigital Library
6. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proc. SIGGRAPH ’00, 157–164. Google ScholarDigital Library
7. Alexander, J. W. 1924. On the subdivision of 3-space by a polyhedron. Proc. Nat. Acad. Sci. of the USA 10, 1, 6.Google ScholarCross Ref
8. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., and Kobbelt, L. 2013. Integer-grid maps for reliable quad meshing. In Proc. SIGGRAPH 2013, 98:1–98:12.Google Scholar
9. Choquet, G. 1945. Sur un type de transformation analytique généralisant la représentation conforme et défini au moyen de fonctions harmoniques. Bulletin des Sciences Mathématiques 69, 156–165.Google Scholar
10. Colin de Verdière, E., Pocchiola, M., and Vegter, G. 2003. Tutte’s barycenter method applied to isotopies. Computational Geometry 26, 1, 81–97. Google ScholarDigital Library
11. de Fraysseix, H., de Mendez, P. O., and Rosenstiehl, P. 1995. Bipolar orientations revisited. Discrete Applied Mathematics 56, 2-3, 157–179. Google ScholarDigital Library
12. Degener, P., Meseth, J., and Klein, R. 2003. An adaptable surface parameterization method. Int. Meshing Roundtable 3, 201–213.Google Scholar
13. Dey, T. K., Edelsbrunner, H., and Guha, S. 1999. Computational topology. In Advances in Discrete and Computational Geometry, 109–143.Google Scholar
14. Fiedler, M. 1975. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal 25, 4, 619–633.Google ScholarCross Ref
15. Filippov, A. F. 1988. Differential equations with discontinuous righthand sides. Mathematics and its Applications. Kluwer Academic Publ, Dordrecht.Google Scholar
16. Floater, M. S., and Pham-Trong, V. 2006. Convex combination maps over triangulations, tilings, and tetrahedral meshes. Advances in Computational Mathematics 25, 4, 347–356.Google ScholarCross Ref
17. Floater, M. S. 1997. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 14, 3, 231–250. Google ScholarDigital Library
18. Floater, M. S. 2003. One-to-one piecewise linear mappings over triangulations. Math. Comput. 72, 242, 685–696. Google ScholarDigital Library
19. Fu, X.-M., Liu, Y., and Guo, B. 2015. Computing locally injective mappings by advanced MIPS. ACM Trans. Graph. 34, 20 4, 71:1–71:12. Google ScholarDigital Library
20. Furch, R. 1924. Zur Grundlegung der kombinatorischen Topologie. In Abhandlungen aus dem mathematischen Seminar der Universität Hamburg, vol. 3, Springer, 69–88.Google Scholar
21. Gergen, J. J. 1930. Mapping of a general type of three dimensional region on a sphere. American Journal of Mathematics 52, 2, 197–224.Google ScholarCross Ref
22. Gergen, J. J. 1931. Note on the green function of a star-shaped three dimensional region. American Journal of Mathematics 53, 4, 746–752.Google ScholarCross Ref
23. Goodrick, R. E. 1968. Non-simplicially collapsible triangulations of In. In Mathematical Proceedings of the Cambridge Philosophical Society, vol. 64, Cambridge Univ Press, 31–36.Google Scholar
24. Gotsman, C., Gu, X., and Sheffer, A. 2003. Fundamentals of spherical parameterization for 3D meshes. In Proc. SIGGRAPH 2003, 358–363. Google ScholarDigital Library
25. Granlund, T., et al. 2015. GNU MP: The GNU Multiple Precision Arithmetic Library, 6.1.0 ed. http://gmplib.org/. Google ScholarDigital Library
26. Groff, R. E. 2003. Piecewise linear homeomorphisms for approximation of invertible maps. PhD thesis, The University of Michigan.Google Scholar
27. Hormann, K., and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design 1999, Innovations in Applied Mathematics. 153–162.Google Scholar
28. Huynh, L., and Gingold, Y. I. 2015. Bijective deformations in Rn via integral curve coordinates. CoRR abs/1505.00073.Google Scholar
29. Jin, Y., Huang, J., and Tong, R. 2014. Remeshing-assisted optimization for locally injective mappings. Computer Graphics Forum 33, 5, 269–279.Google ScholarDigital Library
30. Jin, Y., Qian, G.-P., Zhao, J.-Y., Chang, J., Tong, R.-F., and Zhang, J. 2015. Stretch-minimizing volumetric parameterization. J. Comp. Sci. and Tech. 30, 3, 553–564.Google ScholarCross Ref
31. King, S. 2004. How to make a triangulation of S3 polytopal. Trans. Am. Math. Soc. 356, 11, 4519–4542.Google ScholarCross Ref
32. Kneser, H. 1926. Lösung der Aufgabe 41. Jahresbericht der Deutschen Mathematiker-Vereinigung 35, 123–124.Google Scholar
33. Kovalsky, S. Z., Aigerman, N., Basri, R., and Lipman, Y. 2014. Controlling singular values with semidefinite programming. ACM Transactions on Graphics 33, 4. Google ScholarDigital Library
34. Laugesen, R. S. 1996. Injectivity can fail for higher-dimensional harmonic extensions. Complex Variables Theory Appl. 28, 4, 357–369.Google ScholarCross Ref
35. Lempel, A., Even, S., and Cederbaum, I. 1967. An algorithm for planarity testing of graphs. In Theory of Graphs. Gordon and Breach, 215–232.Google Scholar
36. Li, X., Guo, X., Wang, H., He, Y., Gu, X., and Qin, H. 2007. Harmonic volumetric mapping for solid modeling applications. In Proc. SPM ’07, 109–120. Google ScholarDigital Library
37. Lin, J., Xia, J., Gao, X., Liao, M., He, Y., and Gu, X. 2015. Interior structure transfer via harmonic 1-forms. Multimedia Tools and Applications 74, 1, 139–158. Google ScholarDigital Library
38. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4, 108:1–108:13. Google ScholarDigital Library
39. Liu, H., and Liao, G. 1996. A note on harmonic maps. Applied Mathematics Letters 9, 4, 95–97.Google ScholarCross Ref
40. Mani, P., and Bruggesser, H. 1971. Shellable decompositions of cells and spheres. Mathematica Scandinavica 29, 197–205.Google ScholarCross Ref
41. Moerdijk, I., and Mrčun, J. 2003. Introduction to Foliations and Lie Groupoids. Cambridge Studies in Advanced Mathematics. Cambridge University Press.Google Scholar
42. Moise, E. E. 1952. Affine structures in 3-manifolds: V. The triangulation theorem and Hauptvermutung. Annals of Mathematics, 96–114.Google ScholarCross Ref
43. Myles, A., Pietroni, N., and Zorin, D. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. 33, 4. Google ScholarDigital Library
44. Nguyen, T., and Jüttler, B. 2010. Parameterization of contractible domains using sequences of harmonic maps. In Curves and Surfaces, vol. 6920 of LNCS, 501–514. Google ScholarDigital Library
45. Pachner, U. 1991. PL homeomorphic manifolds are equivalent by elementary shellings. Europ. J. Comb. 12, 2, 129–145. Google ScholarDigital Library
46. Ray, N., and Sokolov, D. 2014. Robust polylines tracing for n-symmetry direction field on triangulated surfaces. ACM Trans. Graph. 33, 3. Google ScholarDigital Library
47. Rudin, M. E. 1958. An unshellable triangulation of a tetrahedron. Bulletin of the American Mathematical Society 64, 3, 90–91.Google ScholarCross Ref
48. Saba, S., Yavneh, I., Gotsman, C., and Sheffer, A. 2005. Practical spherical embedding of manifold triangle meshes. Int. Conf. on Shape Modeling and Applications, 258–267. Google ScholarDigital Library
49. Schneider, T., and Hormann, K. 2015. Smooth bijective maps between arbitrary planar polygons. Computer Aided Geometric Design 35, 243–254. Google ScholarDigital Library
50. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. In Proc. SGP ’13, 125–135. Google ScholarDigital Library
51. Smith, J., and Schaefer, S. 2015. Bijective parameterization with free boundaries. ACM Trans. Graph. 34, 4, 70:1–70:9. Google ScholarDigital Library
52. Stoddart, A., et al. 1964. The shape of level surfaces of harmonic functions in three dimensions. The Michigan Mathematical Journal 11, 3, 225–229.Google ScholarCross Ref
53. Tutte, W. T. 1963. How to draw a graph. Proc. Lond. Math. Soc. 13, 743–767.Google ScholarCross Ref
54. Wang, Y., Gu, X., and Yau, S.-T. 2004. Volumetric harmonic map. Communications in Information & Systems 3, 3, 191–202.Google Scholar
55. Weber, O., and Zorin, D. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Trans. Graph. 33, 4, 75:1–75:12. Google ScholarDigital Library
56. Weinkauf, T., Theisel, H., Hege, H.-C., and Seidel, H.-P. 2004. Topological construction and visualization of higher order 3D vector fields. Computer Graphics Forum 23, 3, 469–478.Google ScholarCross Ref
57. Wu, J., Song, J., and Zhang, W. 2014. An efficient and accurate method to compute the Fiedler vector based on Householder deflation and inverse power iteration. J. Computational Applied Mathematics 269, 101–108.Google ScholarCross Ref
58. Xia, J., He, Y., Han, S., Fu, C.-W., Luo, F., and Gu, X. 2010. Parameterization of star-shaped volumes using Green’s functions. In Advances in Geometric Modeling and Processing, vol. 6130 of LNCS. 219–235. Google ScholarDigital Library
59. Xia, J., He, Y., Yin, X., Han, S., and Gu, X. 2010. Direct-product volumetric parameterization of handlebodies via harmonic fields. In Proc. SMI 2010, 3–12. Google ScholarDigital Library
60. Yap, C. K. 1997. Robust geometric computation. In Handbook of Discrete and Computational Geometry, chapter 35. CRC Press LLC, Boca Raton, FL, 653–668. Google ScholarDigital Library
61. Zeng, W., Li, X., Yau, S.-T., and Gu, X. 2007. Conformal spherical parametrization for high genus surfaces. Communications in Information & Systems 7, 3, 273–286.Google ScholarCross Ref
62. Zhang, E., Mischaikow, K., and Turk, G. 2006. Vector field design on surfaces. ACM Trans. Graph. 25, 4, 1294–1326. Google ScholarDigital Library
63. Ziegler, G. M. 1998. Shelling polyhedral 3-balls and 4-polytopes. Discrete & Computational Geometry 19, 2, 159–174.Google ScholarCross Ref
