“Mesh-based inverse kinematics”

The ability to position a small subset of mesh vertices and produce a meaningful overall deformation of the entire mesh is a fundamental task in mesh editing and animation. However, the class of meaningful deformations varies from mesh to mesh and depends on mesh kinematics, which prescribes valid mesh configurations, and a selection mechanism for choosing among them. Drawing an analogy to the traditional use of skeleton-based inverse kinematics for posing skeletons. we define mesh-based inverse kinematics as the problem of finding meaningful mesh deformations that meet specified vertex constraints.Our solution relies on example meshes to indicate the class of meaningful deformations. Each example is represented with a feature vector of deformation gradients that capture the affine transformations which individual triangles undergo relative to a reference pose. To pose a mesh, our algorithm efficiently searches among all meshes with specified vertex positions to find the one that is closest to some pose in a nonlinear span of the example feature vectors. Since the search is not restricted to the span of example shapes, this produces compelling deformations even when the constraints require poses that are different from those observed in the examples. Furthermore, because the span is formed by a nonlinear blend of the example feature vectors, the blending component of our system may also be used independently to pose meshes by specifying blending weights or to compute multi-way morph sequences.

1. Alexa, M., and Müller, W. 2000. Representing animations by principal components. Computer Graphics Forum 19, 3, 411–418.Google ScholarCross Ref
2. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, 157–164. Google ScholarDigital Library
3. Alexa, M. 2002. Linear combination of transformations. ACM Transactions on Graphics 21, 3 (July), 380–387. Google ScholarDigital Library
4. Alexa, M. 2003. Differential coordinates for mesh morphing and deformation. The Visual Computer 19, 2, 105–114.Google ScholarCross Ref
5. Barr, A. H. 1984. Global and local deformations of solid primitives. In Computer Graphics (Proceedings of ACM SIGGRAPH 84), vol. 18, 21–30. Google ScholarDigital Library
6. Blanz, V., and Vetter, T. 1999. A morphable model for the synthesis of 3d faces. In Proceedings of ACM SIGGRAPH 99, Computer Graphics Proceedings, Annual Conference Series, 187–194. Google ScholarDigital Library
7. Bregler, C., Loeb, L., Chuang, E., and Deshpande, H. 2002. Turning to the masters: Motion capturing cartoons. ACM Transactions on Graphics 21, 3 (July), 399–407. Google ScholarDigital Library
8. Gill, P. E., Murray, W., and Wright, M. H. 1989. Practical Optimization. Academic Press, London.Google Scholar
9. Golub, G. H., and Loan, C. F. V. 1996. Matrix Computations, third ed. Johns Hopkins University Press, Baltimore, Maryland. Google ScholarDigital Library
10. Grochow, K., Martin, S. L., Hertzmann, A., and Popović, Z. 2004. Style-based inverse kinematics. ACM Transactions on Graphics 23, 3 (Aug.), 522–531. Google ScholarDigital Library
11. Guskov, I., Sweldens, W., and Schröder, P. 1999. Multiresolution signal processing for meshes. In Proceedings of ACM SIGGRAPH 99, Computer Graphics Proceedings, Annual Conference Series, 325–334. Google ScholarDigital Library
12. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Proceedings of Graphics Interface 2003, 247–256.Google Scholar
13. James, D. L., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM Transactions on Graphics 22, 3 (July), 879–887. Google ScholarDigital Library
14. Karypis, G., and Kumar, V. 1999, A fast and highly quality multi-level scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 1. http://www.cs.umn.edu/~metis. Google ScholarDigital Library
15. Kobbelt, L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proceedings of ACM SIGGRAPH 98, Computer Graphics Proceedings, Annual Conference Series, 105–114. Google ScholarDigital Library
16. Kobbelt, L. P., Bareuther, T., and Seidel, H.-P. 2000. Multiresolution shape deformations for meshes with dynamic vertex connectivity. Computer Graphics Forum 19, 3 (Aug.), 249–260.Google ScholarCross Ref
17. Lewis, J. P., Cordner, M., and Fong, N. 2000. Pose space deformations: A unified approach to shape interpolation and skeleton-driven deformation. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, 165–172. Google ScholarDigital Library
18. Lipman, Y., Sorkine, O., Cohen-Or, D., Levin, D., Rössl, C., and Seidel, H.-P. 2004. Differential coordinates for interactive mesh editing. In Proceedings of Shape Modeling International, 181–190. Google ScholarDigital Library
19. Madsen, K., Nielsen, H., and Tingleff, O. 2004. Methods for non-linear least squares problems. Tech. rep., Informatics and Mathematical Modelling, Technical University of Denmark.Google Scholar
20. Murray, R. M., Li, Z., and Sastry, S. S. 1994. A mathematical introduction to robotic manipulation. CRC Press. Google ScholarDigital Library
21. Ngo, T., Cutrell, D., Dana, J., Donald, B., Loeb, L., and Zhu, S. 2000. Accessible animation and customizable graphics via simplicial configuration modeling. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, 403–410. Google ScholarDigital Library
22. Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. In Computer Graphics (Proceedings of ACM SIGGRAPH 89), vol. 23, 215–222. Google ScholarDigital Library
23. Rose, C. F., Sloan, P.-P. J., and Cohen, M. F. 2001. Artist-directed inverse-kinematics using radial basis function interpolation. Computer Graphics Forum 20, 3, 239–250.Google ScholarCross Ref
24. Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In Proceedings of the 2nd Symposium on 3D Processing. Visualization and Transmission, 68–75. Google ScholarDigital Library
25. Shoemake, K., and Duff, T. 1992. Matrix animation and polar decomposition. In Proceedings of Graphics Interface 92, 259–264. Google ScholarDigital Library
26. Sloan, P.-P. J., III, C. F. R., and Cohen, M. F. 2001. Shape by example. In 2001 ACM Symposium on Interactive 3D Graphics, 135–144. Google ScholarDigital Library
27. Sorkine, O., Lipman, Y., Cohen-Or, D., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, 179–188. Google ScholarDigital Library
28. Sumner, R. W., and Popović, J. 2004. Deformation transfer for triangle meshes. ACM Transactions on Graphics 23, 3 (Aug.), 399–405. Google ScholarDigital Library
29. Tipping, M. E., and Bishop, C. M. 1999. Probabilistic principal component analysis. Journal of the Royal Statistical Society, Series B 61, 3, 611–622. Google ScholarDigital Library
30. Toledo, S., 2003. TAUCS: A library of sparse linear solvers, version 2.2. http://www.tau.ac.il/~stoledo/taucs.Google Scholar
31. Xu, D., Zhang, H., Wang, Q., and Bao, H. 2005. Poisson shape interpolation. In Proceedings of ACM Symposium on Solid and Physical Modeling. Google ScholarDigital Library
32. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with poisson-based gradient field manipulation. ACM Transactions on Graphics 23, 3 (Aug.), 644–651. Google ScholarDigital Library
33. Zhang, L., Snavely, N., Curless, B., and Seitz, S. M. 2004. Spacetime faces: high resolution capture for modeling and animation. ACM Transactions on Graphics 23, 3 (Aug.), 548–558. Google ScholarDigital Library
34. Zorin, D., Schröder, P., and Sweldens, W. 1997. Interactive multiresolution mesh editing. In Proceedings of ACM SIGGRAPH 97, Computer Graphics Proceedings, Annual Conference Series, 259–268. Google ScholarDigital Library