“Bounded biharmonic weights for real-time deformation” by Jacobson, Baran, Popović and Sorkine-Hornung

Object deformation with linear blending dominates practical use as the fastest approach for transforming raster images, vector graphics, geometric models and animated characters. Unfortunately, linear blending schemes for skeletons or cages are not always easy to use because they may require manual weight painting or modeling closed polyhedral envelopes around objects. Our goal is to make the design and control of deformations simpler by allowing the user to work freely with the most convenient combination of handle types. We develop linear blending weights that produce smooth and intuitive deformations for points, bones and cages of arbitrary topology. Our weights, called bounded biharmonic weights, minimize the Laplacian energy subject to bound constraints. Doing so spreads the influences of the controls in a shape-aware and localized manner, even for objects with complex and concave boundaries. The variational weight optimization also makes it possible to customize the weights so that they preserve the shape of specified essential object features. We demonstrate successful use of our blending weights for real-time deformation of 2D and 3D shapes.

1. Andersen, E. D., and Andersen, K. D. 2000. The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In High Performance Optimization. Kluwer Academic Publishers, 197–232.Google Scholar
2. Au, O. K.-C., Fu, H., Tai, C.-L., and Cohen-Or, D. 2007. Handle-aware isolines for scalable shape editing. ACM Trans. Graph. 26, 3, 83. Google ScholarDigital Library
3. Baran, I., and Popović, J. 2007. Automatic rigging and animation of 3D characters. ACM Trans. Graph. 26, 3, 72:1–72:8. Google ScholarDigital Library
4. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. ACM Trans. Graph. 28, 3, 34:1–34:11. Google ScholarDigital Library
5. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform modeling. ACM Trans. Graph. 23, 3, 630–634. Google ScholarDigital Library
6. Botsch, M., and Sorkine, O. 2008. On linear variational surface deformation methods. IEEE TVCG 14, 1, 213–230. Google Scholar
7. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. PriMo: Coupled prisms for intuitive surface modeling. In Proc. SGP, 11–20. Google ScholarDigital Library
8. Botsch, M., Pauly, M., Wicke, M., and Gross, M. 2007. Adaptive space deformations based on rigid cells. Comput. Graph. Forum 26, 3, 339–347.Google ScholarCross Ref
9. Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., and Lévy, B. 2010. Polygon Mesh Processing. AK Peters.Google Scholar
10. Der, K. G., Sumner, R. W., and Popović, J. 2006. Inverse kinematics for reduced deformable models. ACM Trans. Graph. 25, 3, 1174–1179. Google ScholarDigital Library
11. Floater, M. S. 2003. Mean value coordinates. Computer-Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
12. Hormann, K., and Sukumar, N. 2008. Maximum entropy coordinates for arbitrary polytopes. Comput. Graph. Forum 27, 5, 1513–1520. Google ScholarDigital Library
13. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3, 1134–1141. Google ScholarDigital Library
14. Jacobson, A., Tosun, E., Sorkine, O., and Zorin, D. 2010. Mixed finite elements for variational surface modeling. Comput. Graph. Forum (Proc. SGP) 29, 5, 1565–1574.Google ScholarCross Ref
15. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3, 71:1–71:9. Google ScholarDigital Library
16. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566. Google ScholarDigital Library
17. Kavan, L., Collins, S., Zara, J., and O’Sullivan, C. 2008. Geometric skinning with approximate dual quaternion blending. ACM Trans. Graph. 27, 4, 105:1–105:23. Google ScholarDigital Library
18. Landreneau, E., and Schaefer, S. 2010. Poisson-based weight reduction of animated meshes. Comput. Graph. Forum 29, 6, 1945–1954.Google ScholarCross Ref
19. Langer, T., and Seidel, H.-P. 2008. Higher order barycentric coordinates. Comput. Graph. Forum 27, 2, 459–466.Google ScholarCross Ref
20. Lipman, Y., Kopf, J., Cohen-Or, D., and Levin, D. 2007. GPU-assisted positive mean value coordinates for mesh deformations. In Proc. SGP, 117–124. Google ScholarDigital Library
21. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3, 78:1–78:10. Google ScholarDigital Library
22. Magnenat-Thalmann, N., Laperrière, R., and Thalmann, D. 1988. Joint-dependent local deformations for hand animation and object grasping. In Graphics Interface, 26–33. Google Scholar
23. Schaefer, S., McPhail, T., and Warren, J. 2006. Image deformation using moving least squares. ACM Trans. Graph. 25, 3, 533–540. Google ScholarDigital Library
24. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 1968 23rd ACM national conference, ACM, 517–524. Google Scholar
25. Shewchuk, J. R. 1996. Triangle: Engineering a 2D quality mesh generator and delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, 203–222. Google ScholarDigital Library
26. Shi, X., Zhou, K., Tong, Y., Desbrun, M., Bao, H., and Guo, B. 2007. Mesh puppetry: cascading optimization of mesh deformation with inverse kinematics. ACM Trans. Graph. 26, 3, 81:1–81:10. Google ScholarDigital Library
27. Si, H., 2003. TetGen: A 3D delaunay tetrahedral mesh generator. http://tetgen.berlios.de.Google Scholar
28. Sibson, R. 1981. Interpolating multivariate data. John Wiley & Sons, ch. A brief description of natural neighbor interpolation, 21–36.Google Scholar
29. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. SGP, 109–116. Google ScholarDigital Library
30. Sumner, R. W., Schmid, J., and Pauly, M. 2007. Embedded deformation for shape manipulation. ACM Trans. Graph. 26, 3, 80:1–80:7. Google ScholarDigital Library
31. Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Trans. Graph. 29, 4, 78:1–78:11. Google ScholarDigital Library
32. Weber, O., Sorkine, O., Lipman, Y., and Gotsman, C. 2007. Context-aware skeletal shape deformation. Comput. Graph. Forum 26, 3, 265–274.Google ScholarCross Ref
33. Weber, O., Ben-Chen, M., and Gotsman, C. 2009. Complex barycentric coordinates with applications to planar shape deformation. Comput. Graph. Forum 28, 2, 587–597.Google ScholarCross Ref