Bounded biharmonic weights for real-time deformation

Abstract

Changing an object's shape is a basic operation in computer graphics, necessary for transforming raster images, vector graphics, geometric models, and animated characters. The fastest approaches for such object deformation involve linearly blending a small number of given affine transformations, typically each associated with bones of an internal skeleton, vertices of an enclosing cage, or a collection of loose point handles. Unfortunately, linear blending schemes are not always easy to use because they may require manually painting influence weights or modeling closed polyhedral cages around the input object. 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 handles 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.

References

1. Andersen, E.D., Andersen, K.D. The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. High Performance Optimization. H. Frenk, C. Roos, T. Terlaky, and S. Zhang, eds. Kluwer Academic Publishers, 2000, 197--232.
2. Baran, I., Popović, J. Automatic rigging and animation of 3D characters. ACM Trans. Graph. 26, 3 (2007), 72:1--72:8.
3. Botsch, M., Kobbelt, L. An intuitive framework for real-time freeform modeling. ACM Trans. Graph. 23, 3 (2004), 630--634.
4. Botsch, M., Pauly, M., Gross, M., Kobbelt., L. PriMo: coupled prisms for intuitive surface modeling. In Proceedings of SGP (2006), 11--20.
5. Botsch, M., Pauly, M., Wicke, M., Gross, M. Adaptive space deformations based on rigid cells. Comput. Graph. Forum 26, 3 (2007), 339--347.
6. Botsch, M., Sorkine, O. On linear variational surface deformation methods. IEEE TVCG 14, 1 (2008), 213--230.
7. Der, K.G., Sumner, R.W., Popović, J. Inverse kinematics for reduced deformable models. ACM Trans. Graph. 25, 3 (2006), 1174--1179.
8. Floater, M.S. Mean value coordinates. Comput. Aided Geom. Design 20, 1 (2003), 19--27.
9. Igarashi, T., Moscovich, T., Hughes, J.F. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3 (2005), 1134--1141.
10. Jacobson, A., Tosun, E., Sorkine, O., Zorin, D. Mixed finite elements for variational surface modeling. In Proceedings of SGP (2010).
11. Jacobson, A., Weinkauf, T., Sorkine, O. Smooth shape-aware functions with controlled extrema. In Proceedings of SGP (2012).
12. Joshi, P., Meyer, M., DeRose, T., Green, B., Sanocki, T. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3 (2007).
13. Ju, T., Schaefer, S., Warren, J. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3 (2005), 561--566.
14. Kavan, L., Collins, S., Zara, J., O'Sullivan, C. Geometric skinning with approximate dual quaternion blending. ACM Trans. Graph. 27, 4 (2008).
15. Magnenat-Thalmann, N., Laperrière, R., Thalmann, D. Joint-dependent local deformations for hand animation and object grasping. In Graphics Interface (1988), 26--33.
16. Schaefer, S., McPhail, T., Warren, J. Image deformation using moving least squares. ACM Trans. Graph. 25, 3 (2006), 533--540.
17. Shepard, D. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of ACM National Conference (1968), 517--524.
18. Shewchuk, J.R. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In WACG (1996), 203--222.
19. Shi, X., Zhou, K., Tong, Y., Desbrun, M., Bao, H., Guo, B. Mesh puppetry: cascading optimization of mesh deformation with inverse kinematics. ACM Trans. Graph. 26, 3 (2007), 81:1--81:10.
20. Si, H. TETGEN: a 3D delaunay tetrahedral mesh generator, 2003. http://tetgen.org.
21. Sibson, R. A brief description of natural neighbor interpolation. Interpolating Multivariate Data. V. Barnett, ed. Volume 21, John Wiley & Sons, 1981, 21--36.
22. Sorkine, O., Alexa, M. As-rigid-as-possible surface modeling. In Proceedings of SGP (2007), 109--116.
23. Sumner, R.W., Schmid, J., Pauly, M. Embedded deformation for shape manipulation. ACM Trans. Graph. 26, 3 (2007), 80:1--80:7.
24. Weber, O., Ben-Chen, M., Gotsman, C., Hormann, K. A complex view of barycentric mappings. Comput. Graph. Forum 30, 5 (2011).
25. Weber, O., Sorkine, O., Lipman, Y., Gotsman, C. Context-aware skeletal shape deformation. Comput. Graph. Forum 26, 3 (2007), 265--274.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Image and video acquisition

        • 3D imaging

  • Computer graphics

    • Animation

    • Image manipulation

    • Rendering