“Provably good planar mappings” by Poranne and Lipman

  • ©Roi Poranne and Yaron Lipman

Conference:


Type:


Title:

    Provably good planar mappings

Presenter(s)/Author(s):


Session Title: Surfaces, Deformation, and Correspondence

Moderator(s):


Abstract:


    The problem of planar mapping and deformation is central in computer graphics. This paper presents a framework for adapting general, smooth, function bases for building provably good planar mappings. The term “good” in this context means the map has no fold-overs (injective), is smooth, and has low isometric or conformal distortion.Existing methods that use mesh-based schemes are able to achieve injectivity and/or control distortion, but fail to create smooth mappings, unless they use a prohibitively large number of elements, which slows them down. Meshless methods are usually smooth by construction, yet they are not able to avoid fold-overs and/or control distortion.Our approach constrains the linear deformation spaces induced by popular smooth basis functions, such as B-Splines, Gaussian and Thin-Plate Splines, at a set of collocation points, using specially tailored convex constraints that prevent fold-overs and high distortion at these points. Our analysis then provides the required density of collocation points and/or constraint type, which guarantees that the map is injective and meets the distortion constraints over the entire domain of interest.We demonstrate that our method is interactive at reasonably complicated settings and compares favorably to other state-of-the-art mesh and meshless planar deformation methods.

References:


    1. Adams, B., Ovsjanikov, M., Wand, M., Seidel, H.-P., and Guibas, L. J. 2008. Meshless modeling of deformable shapes and their motion. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’08, 77–86. Google ScholarDigital Library
    2. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, SIGGRAPH ’00, 157–164. Google ScholarDigital Library
    3. 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
    4. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. In ACM SIGGRAPH 2009 Papers, ACM, New York, NY, USA, SIGGRAPH ’09, 34:1–34:11. Google ScholarDigital Library
    5. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., and Kobbelt, L. 2013. Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32, 4 (July), 98:1–98:12. Google ScholarDigital Library
    6. Bookstein, F. L. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11, 6 (June), 567–585. Google ScholarDigital Library
    7. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4 (July), 38:1–38:6. Google ScholarDigital Library
    8. Chen, R., Weber, O., Keren, D., and Ben-Chen, M. 2013. Planar shape interpolation with bounded distortion. ACM Trans. Graph. 32, 4 (July), 108:1–108:12. Google ScholarDigital Library
    9. Floater, M., and Kosinka, J. 2010. On the injectivity of wachspress and mean value mappings between convex polygons. Advances in Computational Mathematics 32, 2, 163–174.Google ScholarCross Ref
    10. Floater, M. S. 2003. Mean value coordinates. Comput. Aided Geom. Des. 20, 1 (Mar.), 19–27. Google ScholarDigital Library
    11. Fries T.-P., M. H. G. 2003. Classification and overview of mesh-free methods. Tech. Rep. 2003-03, TU Brunswick, Germany.Google Scholar
    12. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3 (July), 1134–1141. Google ScholarDigital Library
    13. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3 (July). Google ScholarDigital Library
    14. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3 (July), 561–566. Google ScholarDigital Library
    15. Kosinka, J., and Barton, M. 2010. Injective shape deformations using cube-like cages. Computer-Aided Design and Applications 7, 3, 309–318.Google ScholarCross Ref
    16. Lehto, O., and Virtanen, K. 1973. Quasiconformal mappings in the plane. Grundlehren der mathematischen Wissenschaften. Springer.Google Scholar
    17. Levi, Z., and Levin, D. 2013. Shape deformation via interior rbf. IEEE Transactions on Visualization and Computer Graphics 99, PrePrints, 1.Google Scholar
    18. Li, X.-Y., Ju, T., and Hu, S.-M. 2013. Cubic mean value coordinates. ACM Transactions on Graphics 32, 4, 126:1–10. Google ScholarDigital Library
    19. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3 (Aug.), 78:1–78:10. Google ScholarDigital Library
    20. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4 (July), 108:1–108:13. Google ScholarDigital Library
    21. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. In Proceedings of the Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP ’08, 1495–1504. Google ScholarDigital Library
    22. Peters, J., and Reif, U. 1998. Analysis of algorithms generalizing b-spline subdivision. SIAM J. Numer. Anal. 35, 2 (Apr.), 728–748. Google ScholarDigital Library
    23. Reif, U. 1995. A unified approach to subdivision algorithms near extraordinary vertices. Computer Aided Geometric Design 12, 2, 153–174. Google ScholarDigital Library
    24. Schneider, T., Hormann, K., and Floater, M. S. 2013. Bijective composite mean value mappings. Computer Graphics Forum 32, 5 (July), 137–146. Proceedings of SGP. Google ScholarDigital Library
    25. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. Computer Graphics Forum (proceedings of EUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing) 32, 5, 125–135. Google ScholarDigital Library
    26. Sederberg, T. W., and Parry, S. R. 1986. Free-form deformation of solid geometric models. In Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’86, 151–160. Google ScholarDigital Library
    27. Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In Proceedings of the 3D Data Processing, Visualization, and Transmission, 2Nd International Symposium, IEEE Computer Society, Washington, DC, USA, 3DPVT ’04, 68–75. Google ScholarDigital Library
    28. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proceedings of EUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing, 109–116. Google ScholarDigital Library
    29. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, ACM, 175–184. Google ScholarDigital Library
    30. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’87, 205–214. Google ScholarDigital Library
    31. Warren, J. 1996. Barycentric coordinates for convex polytopes. In Advances in Computational Mathematics 6, 97–108.Google ScholarCross Ref
    32. Weber, O., Poranne, R., and Gotsman, C. 2012. Biharmonic coordinates. Comput. Graph. Forum 31, 8, 2409–2422. Google ScholarDigital Library
    33. Wendland, H. 2004. Scattered Data Approximation. Cambridge University Press.Google Scholar
    34. Xu, D., Zhang, H., Wang, Q., and Bao, H. 2005. Poisson shape interpolation. In Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling, ACM, New York, NY, USA, SPM ’05, 267–274. Google ScholarDigital Library
    35. Zorin, D. 1998. A Method for Analysis of C1-continuity of Subdivision Surfaces. Technical report (Stanford University. Computer Systems Laboratory). Computer Systems Laboratory, Stanford University. Google ScholarDigital Library

ACM Digital Library Publication: