“Cubic mean value coordinates” by Li, Ju and Hu

  • ©Xianying Li, Tao Ju, and Shi-Min Hu




    Cubic mean value coordinates

Session/Category Title: Skinning & Deformation




    We present a new method for interpolating both boundary values and gradients over a 2D polygonal domain. Despite various previous efforts, it remains challenging to define a closed-form interpolant that produces natural-looking functions while allowing flexible control of boundary constraints. Our method builds on an existing transfinite interpolant over a continuous domain, which in turn extends the classical mean value interpolant. We re-derive the interpolant from the mean value property of biharmonic functions, and prove that the interpolant indeed matches the gradient constraints when the boundary is piece-wise linear. We then give closed-form formula (as generalized barycentric coordinates) for boundary constraints represented as polynomials up to degree 3 (for values) and 1 (for normal derivatives) over each polygon edge. We demonstrate the flexibility and efficiency of our coordinates in two novel applications, smooth image deformation using curved cage networks and adaptive simplification of gradient meshes.


    1. Baran, I., and Popović, J. 2007. Automatic rigging and animation of 3d characters. ACM Transactions on Graphics 26, 3, 72:1–8. Google ScholarDigital Library
    2. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform modeling. ACM Transactions on Graphics 23, 3, 630–634. Google ScholarDigital Library
    3. Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., and Lévy, B. 2010. Polygon Mesh Processing. A. K. Peters, Natick.Google Scholar
    4. Dyken, C., and Floater, M. S. 2009. Transfinite mean value interpolation. Computer Aided Geometric Design (CAGD) 26, 1, 117–134. Google ScholarDigital Library
    5. Farbman, Z., Hoffer, G., Lipman, Y., Cohen-Or, D., and Lischinski, D. 2009. Coordinates for instant image cloning. ACM Transactions on Graphics 28, 3, 67:1–9. Google ScholarDigital Library
    6. Ferguson, J. 1964. Multivariable curve interpolation. Journal of the ACM 11, 2, 221–228. Google ScholarDigital Library
    7. Floater, M. S., and Schulz, C. 2008. Pointwise radial minimization: Hermite interpolation on arbitrary domains. Computer Graphics Forum 27, 5, 1505–1512. Google ScholarDigital Library
    8. Floater, M. S., Hormann, K., and Kós, G. 2006. A general construction of barycentric coordinates over convex polygons. Advances in Computational Mathematics 24, 3, 311–331.Google ScholarCross Ref
    9. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design (CAGD) 20, 1, 19–27. Google ScholarDigital Library
    10. Goyal, S., and Goyal, V. B. 2012. Mean value results for second and higher order partial differential equations. Applied Mathematical Sciences 6, 77-80, 3941–3957.Google Scholar
    11. Hormann, K., and Floater, M. S. 2006. Mean value coordinates for arbitrary planar polygons. ACM Transactions on Graphics 25, 4, 1424–1441. Google ScholarDigital Library
    12. Hormann, K., and Sukumar, N. 2008. Maximum entropy coordinates for arbitrary polytopes. Computer Graphics Forum 27, 5, 1513–1520. Google ScholarDigital Library
    13. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics 30, 4, 78:1–8. Google ScholarDigital Library
    14. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Transactions on Graphics 26, 3, 71:1–9. Google ScholarDigital Library
    15. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Transactions on Graphics 24, 3, 561–566. Google ScholarDigital Library
    16. Lai, Y.-K., Hu, S.-M., and Martin, R. R. 2009. Automatic and topology-preserving gradient mesh generation for image vectorization. ACM Transactions on Graphics 28, 3, 85:1–8. Google ScholarDigital Library
    17. Langer, T., and Seidel, H.-P. 2008. Higher order barycentric coordinates. Computer Graphics Forum 27, 2, 459–466.Google ScholarCross Ref
    18. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Transactions on Graphics 27, 3, 78:1–10. Google ScholarDigital Library
    19. Manson, J., and Schaefer, S. 2010. Moving least squares coordinates. Computer Graphics Forum 29, 5, 1517–1524.Google ScholarCross Ref
    20. Manson, J., Li, K., and Schaefer, S. 2011. Positive Gordon-Wixom coordinates. Computer Aided Design 43, 11, 1422–1426. Google ScholarDigital Library
    21. Meyer, M., Lee, H., Barr, A., and Desbrun, M. 2002. Generalized barycentric coordinates on irregular polygons. Journal of Graphics Tools 7, 1, 13–22. Google ScholarDigital Library
    22. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: a vector representation for smooth-shaded images. ACM Transactions on Graphics 27, 3, 92:1–8. Google ScholarDigital Library
    23. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1, 15–36.Google ScholarCross Ref
    24. Polyanin, A. D. 2002. Handbook of linear partial differential equations for engineers and scientists. Chapman & Hall/CRC, London.Google Scholar
    25. Sun, J., Liang, L., Wen, F., and Shum, H.-Y. 2007. Image vectorization using optimized gradient meshes. ACM Transactions on Graphics 26, 3, 11:1–7. Google ScholarDigital Library
    26. Wachspress, E. 1975. A Rational Finite Element Basis. London: Academic Press.Google Scholar
    27. Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Transactions on Graphics 29, 4, 78:1–11. Google ScholarDigital Library
    28. Weber, O., Ben-Chen, M., and Gotsman, C. 2009. Complex barycentric coordinates with applications to planar shape deformation. Computer Graphics Forum 28, 2, 587–597.Google ScholarCross Ref
    29. Weber, O., Ben-Chen, M., Gotsman, C., and Hormann, K. 2011. A complex view of barycentric mappings. Computer Graphics Forum 30, 5, 1533–1542.Google ScholarCross Ref
    30. Weber, O., Poranne, R., and Gotsman, C. 2012. Biharmonic coordinates. Computer Graphics Forum 31, 8, 2409–2422. Google ScholarDigital Library
    31. Xia, T., Liao, B., and Yu, Y. 2009. Patch-based image vectorization with automatic curvilinear feature alignment. ACM Transactions on Graphics 28, 5, 115:1–10. Google ScholarDigital Library

ACM Digital Library Publication: