“Lifted bijections for low distortion surface mappings” by Aigerman, Poranne and Lipman

  • ©Noam Aigerman, Roi Poranne, and Yaron Lipman



Session Title:

    Geometry Processing


    Lifted bijections for low distortion surface mappings




    This paper introduces an algorithm for computing low-distortion, bijective mappings between surface meshes. The algorithm recieves as input a coarse set of corresponding pairs of points on the two surfaces, and follows three steps: (i) cutting the two meshes to disks in a consistent manner; (ii) jointly flattening the two disks via a novel formulation for minimizing isometric distortion while guaranteeing local injectivity (the flattenings can overlap, however); and (iii) computing a unique continuous bijection that is consistent with the flattenings.The construction of the algorithm stems from two novel observations: first, bijections between disk-type surfaces can be uniquely and efficiently represented via consistent locally injective flattenings that are allowed to be globally overlapping. This observation reduces the problem of computing bijective surface mappings to the task of computing locally injective flattenings, which is shown to be easier. Second, locally injective flattenings that minimize isometric distortion can be efficiently characterized and optimized in a convex framework.Experiments that map a wide baseline of pairs of surface meshes using the algorithm are provided. They demonstrate the ability of the algorithm to produce high-quality continuous bijective mappings between pairs of surfaces of varying isometric distortion levels.


    1. Allen, B., Curless, B., and Popović, Z. 2003. The space of all body shapes: reconstruction and parameterization from range scans. ACM Transactions on Graphics (proc. SIGGRAPH). Google ScholarDigital Library
    2. Andersen, E. D., and Andersen, K. D. 1999. The MOSEK interior point optimization for linear programming: an implementation of the homogeneous algorithm. Kluwer Academic Publishers, 197–232.Google Scholar
    3. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Pang, H., and Davis, J. 2004. The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces. Proc. of the Neural Information Processing Systems.Google Scholar
    4. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. Scape: Shape completion and animation of people. ACM Trans. Graph. 24, 3 (July), 408–416. Google ScholarDigital Library
    5. Besl, P., and McKay, N. 1992. A method for registration of 3-d shapes. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI). Google ScholarDigital Library
    6. Boyd, S. P., and Vandenberghe, L. 2004. Convex optimization. Cambridge university press. Google ScholarDigital Library
    7. Bradley, D., Popa, T., Sheffer, A., Heidrich, W., and Boubekeur, T. 2008. Markerless garment capture. ACM Trans. Graph. 27, 3 (Aug.), 99:1–99:9. Google ScholarDigital Library
    8. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proc. National Academy of Sciences (PNAS).Google Scholar
    9. Brown, B. J., and Rusinkiewicz, S. 2007. Global non-rigid alignment of 3-d scans. ACM Trans. Graph. 26, 3 (July). Google ScholarDigital Library
    10. Chui, H., and Rangarajan, A. 2003. A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding 89, 2–3, 114–141. Google ScholarDigital Library
    11. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in multiresolution for geometric modelling. Springer, 157–186.Google Scholar
    12. Floater, M. 2003. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation 72, 242, 685–696. Google ScholarDigital Library
    13. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
    14. Giorgi, D., Biasotti, S., and Paraboschi, L. 2007. SHREC: SHape REtrieval Contest: Watertight models track. http://watertight.ge.imati.cnr.it/.Google Scholar
    15. Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry images. ACM Trans. Graph. 21, 3 (July), 355–361. Google ScholarDigital Library
    16. Gu, X., Wang, Y., Chan, T. F., Thompson, P. M., and Yau, S.-T. 2004. Genus zero surface conformal mapping and its application to brain surface mapping. Medical Imaging, IEEE Transactions on 23, 8, 949–958.Google ScholarCross Ref
    17. Hormann, K., and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999, P.-J. Laurent, P. Sablonnière, and L. L. Schumaker, Eds., Innovations in Applied Mathematics. Vanderbilt University Press, Nashville, TN, 153–162.Google Scholar
    18. Hormann, K., Lévy, B., and Sheffer, A. 2007. Mesh parameterization: Theory and practice video files associated with this course are available from the citation page. In ACM SIGGRAPH 2007 Courses, ACM, New York, NY, USA, SIGGRAPH ’07. Google ScholarDigital Library
    19. Huang, Q., Adams, B., Wicke, M., and Guibas, L. J. 2008. Non-rigid registration under isometric deformations. Computer Graphics Forum (Proc. SGP 2008). Google ScholarDigital Library
    20. Jain, V., Zhang, H., and van Kaick, O. 2007. Non-rigid spectral correspondence of triangle meshes. International Journal on Shape Modeling 13, 1, 101–124.Google ScholarCross Ref
    21. Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. ACM Trans. Graph. 30, 4 (July), 79:1–79:12. Google ScholarDigital Library
    22. Kraevoy, V., and Sheffer, A. 2004. Cross-parameterization and compatible remeshing of 3d models. ACM Trans. Graph. 23, 3 (Aug.), 861–869. Google ScholarDigital Library
    23. Lee, A. W. F., Dobkin, D., Sweldens, W., and Schröder, P. 1999. Multiresolution mesh morphing. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, SIGGRAPH ’99, 343–350. Google ScholarDigital Library
    24. Li, H., Sumner, R. W., and Pauly, M. 2008. Global correspondence optimization for non-rigid registration of depth scans. Computer Graphics Forum 27, 5, 1421–1430. Google ScholarDigital Library
    25. Lin, J. L., Chuang, J. H., Lin, C. C., and Chen, C. C. 2003. Consistent parametrization by quinary subdivision for remeshing and mesh metamorphosis. In Proceedings of the 1st International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia, ACM, New York, NY, USA, GRAPHITE ’03, 151–158. Google ScholarDigital Library
    26. Lipman, Y., and Funkhouser, T. 2009. Mobius voting for surface correspondence. ACM Trans. Graph. 28, 3 (July), 72:1–72:12. Google ScholarDigital Library
    27. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4 (July), 108:1–108:13. Google ScholarDigital Library
    28. Löfberg, J. 2004. Yalmip: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference.Google ScholarCross Ref
    29. Marx, M. L. 1974. Extensions of normal immersions of S1 into R2. Transactions of the American Mathematical Society 187, 309–326.Google Scholar
    30. Mémoli, F., and Sapiro, G. 2005. A theoretical and computational framework for isometry invariant recognition of point cloud data. Foundations of Computational Mathematics 5, 3, 313–347. Google ScholarDigital Library
    31. Michikawa, T., Kanai, T., Fujita, M., and Chiyokura, H. 2001. Multiresolution interpolation meshes. In Computer Graphics and Applications, 2001. Proceedings. Ninth Pacific Conference on, 60–69. Google ScholarDigital Library
    32. Ovsjanikov, M., Mérigot, Q., Mémoli, F., and Guibas, L. 2010. One point isometric matching with the heat kernel. In Computer Graphics Forum (Proc. of SGP).Google Scholar
    33. Ovsjanikov, M., Ben-Chen, M., Solomon, J., Butscher, A., and Guibas, L. 2012. Functional maps: A flexible representation of maps between shapes. ACM Trans. Graph. 31, 4 (July), 30:1–30:11. Google ScholarDigital Library
    34. Ovsjanikov, M., Ben-Chen, M., Chazal, F., and Guibas, L. J. 2013. Analysis and visualization of maps between shapes. Comput. Graph. Forum 32, 6, 135–145. Google ScholarDigital Library
    35. Panozzo, D., Baran, I., Diamanti, O., and Sorkine-Hornung, O. 2013. Weighted averages on surfaces. ACM Trans. Graph. 32, 4 (July), 60:1–60:12. Google ScholarDigital Library
    36. Pauly, M., Mitra, N. J., Giesen, J., Gross, M., and Guibas, L. 2005. Example-based 3d scan completion. In Symposium on Geometry Processing, 23–32. Google ScholarDigital Library
    37. Praun, E., Sweldens, W., and Schröder, P. 2001. Consistent mesh parameterizations. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM, 179–184. Google ScholarDigital Library
    38. Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’01, 409–416. Google ScholarDigital Library
    39. Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. ACM Trans. Graph. 23, 3 (Aug.), 870–877. Google ScholarDigital Library
    40. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Found. Trends. Comput. Graph. Vis. 2, 2 (Jan.), 105–171. Google ScholarDigital Library
    41. Solomon, J., Nguyen, A., Butscher, A., Ben-Chen, M., and Guibas, L. 2012. Soft maps between surfaces. Comp. Graph. Forum 31, 5 (Aug.), 1617–1626. Google ScholarDigital Library
    42. Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of the Conference on Visualization ’02, IEEE Computer Society, Washington, DC, USA, VIS ’02, 355–362. Google ScholarDigital Library
    43. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3 (July), 553–560. Google ScholarDigital Library
    44. Tevs, A., Bokeloh, M., M. Wand, Schilling, A., and Seidel, H.-P. 2009. Isometric registration of ambiguous and partial data. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition.Google Scholar
    45. van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. 2011. A survey on shape correspondence. Computer Graphics Forum 30, 6, 1681–1707.Google ScholarCross Ref
    46. Zeng, W., Luo, F., Yau, S.-T., and Gu, X. D. 2009. Surface quasi-conformal mapping by solving beltrami equations. In Mathematics of Surfaces XIII. Springer Berlin Heidelberg, 391–408. Google ScholarDigital Library

ACM Digital Library Publication: