“Computing locally injective mappings by advanced MIPS” by Aigerman, Poranne and Lipman

  • ©Xiao-Ming Fu, Yang Liu, and Baining Guo

Conference:


Type:


Title:

    Computing locally injective mappings by advanced MIPS

Session/Category Title: Parameterization & Mapping

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Computing locally injective mappings with low distortion in an efficient way is a fundamental task in computer graphics. By revisiting the well-known MIPS (Most-Isometric ParameterizationS) method, we introduce an advanced MIPS method that inherits the local injectivity of MIPS, achieves as low as possible distortions compared to the state-of-the-art locally injective mapping techniques, and performs one to two orders of magnitude faster in computing a mesh-based mapping. The success of our method relies on two key components. The first one is an enhanced MIPS energy function that penalizes the maximal distortion significantly and distributes the distortion evenly over the domain for both mesh-based and meshless mappings. The second is a use of the inexact block coordinate descent method in mesh-based mapping in a way that efficiently minimizes the distortion with the capability not to be trapped early by the local minimum. We demonstrate the capability and superiority of our method in various applications including mesh parameterization, mesh-based and meshless deformation, and mesh improvement.

References:


    1. Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3D. ACM Trans. Graph. (SIGGRAPH) 32, 4, 106:1–106:14. Google ScholarDigital Library
    2. Aigerman, N., Poranne, R., and Lipman, Y. 2014. Lifted bijections for low distortion surface mappings. ACM Trans. Graph. (SIGGRAPH) 33, 4, 69:1–69:12. Google ScholarDigital Library
    3. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In SIGGRAPH, 157–164. Google ScholarDigital Library
    4. Bonettini, S. 2011. Inexact block coordinate descent methods with application to non-negative matrix factorization. IMA J. Numer. Anal. 31, 4, 1431–1452.Google ScholarCross Ref
    5. Botsch, M., and Sorkine, O. 2008. On linear variational surface deformation methods. IEEE. T. Vis. Comput. Gr. 14, 1, 213–230. Google ScholarDigital Library
    6. Brewer, M., Diachin, L. F., Knupp, P., Leurent, T., and Melander, D. 2003. The mesquite mesh quality improvement toolkit. In Int. Meshing Roundtable, 239–250.Google Scholar
    7. Cassioli, A., Di Lorenzo, D., and Sciandrone, M. 2013. On the convergence of inexact block coordinate descent methods for constrained optimization. Eur. J. Oper. Res. 231, 2, 274C–281.Google ScholarCross Ref
    8. Degener, P., Meseth, J., and Klein, R. 2003. An adaptable surface parameterization method. In Int. Meshing Roundtable, 201–213.Google Scholar
    9. Eigensatz, M., and Pauly, M. 2009. Positional, Metric, and Curvature Control for Constraint-Based Surface Deformation. Comput. Graph. Forum (EUROGRAPHICS) 28, 2, 551–558.Google ScholarCross Ref
    10. Escobar, J., Rodríguez, E., Montenegro, R., Montero, G., and González-Yuste, J. 2003. Simultaneous untangling and smoothing of tetrahedral meshes. Comput. Methods Appl. Mech. Engrg. 192, 2775–2787.Google ScholarCross Ref
    11. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In In Advances in Multiresolution for Geometric Modelling, Springer, 157–186.Google Scholar
    12. Floater, M. S., and Pham-Trong, V. 2006. Convex combination maps over triangulations, tilings, and tetrahedral meshes. Adv. Comput. Math. 25, 4, 347–356.Google ScholarCross Ref
    13. Floater, M. S. 2003. Mean value coordinates. Comput. Aided Geom. Des. 20, 1, 19–27. Google ScholarDigital Library
    14. Floater, M. S. 2003. One-to-one piecewise linear mappings over triangulations. Math. Comput. 72, 685–696. Google ScholarDigital Library
    15. Freitag, L. A., and Knupp, P. M. 2002. Tetrahedral mesh improvement via optimization of the element condition number. Int. J. Numer. Meth. Eng. 53, 6, 1679–1689.Google ScholarCross Ref
    16. Freitag Diachin, L., Knupp, P., Munson, T., and Shontz, S. 2006. A comparison of two optimization methods for mesh quality improvement. Eng. with Comput. 22, 2, 61–74. Google ScholarDigital Library
    17. Fu, X.-M., Liu, Y., Snyder, J., and Guo, B. 2014. Anisotropic simplicial meshing using local convex functions. ACM Trans. Graph. (SIGGRAPH ASIA) 33, 6, 182:1–182:11. Google ScholarDigital Library
    18. Gregson, J., Sheffer, A., and Zhang, E. 2011. All-hex mesh generation via volumetric polycube deformation. Comput. Graph. Forum (SGP) 30, 1407–1416.Google ScholarCross Ref
    19. Hormann, K., and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153–162.Google Scholar
    20. Hormann, K. 2001. Theory and Applications of Parameterizing Triangulations. PhD thesis, Department of Computer Science, University of Erlangen.Google Scholar
    21. Huang, J., Jiang, T., Shi, Z., Tong, Y., Bao, H., and Desbrun, M. 2014. l1-based construction of polycube maps from complex shapes. ACM Trans. Graph. 33, 3, 25:1–25:11. Google ScholarDigital Library
    22. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. (SIGGRAPH) 24, 3, 1134–1141. Google ScholarDigital Library
    23. Jiao, X., Wang, D., and Zha, H. 2011. Simple and effective variational optimization of surface and volume triangulations. Eng. Comput. 27, 1, 315–332. Google ScholarDigital Library
    24. Jin, Y., Huang, J., and Tong, R. 2014. Remeshing-assisted optimization for locally injective mappings. Comput. Graph. Forum (SGP) 33, 5, 269–279. Google ScholarDigital Library
    25. 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
    26. Kovalsky, S. Z., Aigerman, N., Basri, R., and Lipman, Y. 2014. Controlling singular values with semidefinite programming. ACM Trans. Graph. (SIGGRAPH) 33, 4, 68:1–68:13. Google ScholarDigital Library
    27. Levi, Z., and Zorin, D. 2014. Strict minimizers for geometric optimization. ACM Trans. Graph. (SIGGRAPH) 33, 6, 185:1–185:14. Google ScholarDigital Library
    28. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. (SIGGRAPH) 21, 3, 362–371. Google ScholarDigital Library
    29. Li, Y., Liu, Y., Xu, W., Wang, W., and Guo, B. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. (SIGGRAPH ASIA) 31, 6, 177:1–177:11. Google ScholarDigital Library
    30. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. (SIGGRAPH) 31, 4, 108:1–108:13. Google ScholarDigital Library
    31. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. Comput. Graph. Forum (SGP) 27, 5, 1495–1504. Google ScholarDigital Library
    32. Poranne, R., and Lipman, Y. 2014. Provably good planar mappings. ACM Trans. Graph. (SIGGRAPH) 33, 4, 76:1–76:11. Google ScholarDigital Library
    33. Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. In SIGGRAPH ’01, 409–416. Google ScholarDigital Library
    34. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. Comput. Graph. Forum (SGP) 32, 5, 125–135. Google ScholarDigital Library
    35. 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
    36. 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
    37. Solomon, J., Ben-Chen, M., Butscher, A., and Guibas, L. 2011. As-killing-as-possible vector fields for planar deformation. Comput. Graph. Forum (SGP) 30, 5, 1543–1552.Google ScholarCross Ref
    38. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry Processing, 109–116. Google ScholarDigital Library
    39. Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of the Conference on Visualization ’02, 355–362. Google ScholarDigital Library
    40. Tappenden, R., Richtárik, P., and Gondzio, J. 2013. Inexact coordinate descent: complexity and preconditioning. arXiv:1304.5530v2 {math.OC}.Google Scholar
    41. Tutte, W. T. 1963. How to draw a graph. In Proceedings of the London Mathematical Society, vol. 13, 747–767.Google Scholar
    42. Weber, O., and Zorin, D. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Trans. Graph. (SIGGRAPH) 33, 4, 75:1–75:12. Google ScholarDigital Library
    43. Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. Comput. Graph. Forum 31, 5, 1679–1689. Google ScholarDigital Library
    44. Xu, Y., and Yin, W. 2013. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6, 3, 1758–1789.Google ScholarDigital Library
    45. Zayer, R., Lévy, B., and Seidel, H.-P. 2007. Linear angle based parameterization. In Symp. Geom. Proc., 135–141. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page: