“Bijective maps from simplicial foliations”

  • ©Marcel Campen, Claudio T. Silva, and Denis Zorin

Conference:


Type:


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

ACM Digital Library Publication:


Overview Page: