“Fast Simulation of Skeleton-Driven Deformable Body Characters” by Kim and Pollard

We propose a fast physically-based simulation system for skeleton-driven deformable body characters. Our system can generate realistic motions of self-propelled deformable body characters by considering the two-way interactions among the skeleton, the deformable body, and the environment in the dynamic simulation. It can also compute the passive jiggling behavior of a deformable body driven by a kinematic skeletal motion. We show that a well-coordinated combination of: (1) a reduced deformable body model with nonlinear finite elements, (2) a linear-time algorithm for skeleton dynamics, and (3) explicit integration can boost simulation speed to orders of magnitude faster than existing methods, while preserving modeling accuracy as much as possible. Parallel computation on the GPU has also been implemented to obtain an additional speedup for complicated characters. Detailed discussions of our engineering decisions for speed and accuracy of the simulation system are presented in the article. We tested our approach with a variety of skeleton-driven deformable body characters, and the tested characters were simulated in real time or near real time.

Albro, J. V., Sohl, G. A., Bobrow, J. E., and Park, F. C. 2000. On the computation of optimal high-dives. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, 3958–3963.Google Scholar
Baraff, D. 1996. Linear-time dynamics using lagrange multipliers. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’96). ACM, New York, 137–146. Google ScholarDigital Library
Baraff, D. and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’98). ACM, New York, 43–54. Google ScholarDigital Library
Barbič, J. and James, D. L. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. Graph 24, 3, 982–990. Google ScholarDigital Library
Bargteil, A. W., Wojtan, C., Hodgins, J. K., and Turk, G. 2007. A finite element method for animating large viscoplastic flow. ACM Trans. Graphics. 26, 3. Google ScholarDigital Library
Basar, Y. and Weichert, D. 2000. Nonlinear Continuum Mechanics of Solids. Springer.Google Scholar
Bonet, J. and Wood, R. D. 1997. Nonlinear Continuum Mechanics for Finite Element Analysis. Cambridge University Press.Google Scholar
Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graphics. 21, 3. Google ScholarDigital Library
Bro-nielsen, M. and Cotin, S. 1996. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Comput. Graph. Forum. 57–66.Google Scholar
Capell, S., Burkhart, M., Curless, B., Duchamp, T., and Popović, Z. 2005. Physically based rigging for deformable characters. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’05). ACM, New York, 301–310. Google ScholarDigital Library
Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002a. Interactive skeleton-driven dynamic deformations. ACM Trans. Graph. 21, 3. Google ScholarDigital Library
Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002b. A multiresolution framework for dynamic deformations. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’02). ACM, New York, 41–47. Google ScholarDigital Library
Choi, K.-J. and Ko, H.-S. 2002. Stable but responsive cloth. ACM Trans. Graph. 21, 3. Google ScholarDigital Library
Choi, M. G. and Ko, H.-S. 2005. Modal warping: real-time simulation of large rotational deformation and manipulation. IEEE Trans. Visual. Comput. Graph. 11, 91–101. Google ScholarDigital Library
Comas, O., Taylor, Z. A., Allard, J., Ourselin, S., Cotin, S., and Passenger, J. 2008. Efficient nonlinear fem for soft tissue modelling and its gpu implementation within the open source framework sofa. In Proceedings of the 4th International Symposium on Biomedical Simulation (ISBMS’08). Springer-Verlag, Berlin, 28–39. Google ScholarDigital Library
de Farias, T. S. M., Almeida, M. W. S., Teixeira, J. M. X., Teichrieb, V., and Kelner, J. 2008. A high performance massively parallel approach for real time deformable body physics simulation. In Proceedings of the 20th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD’08). 45–52. Google ScholarDigital Library
Faloutsos, P., van de Panne, M., and Terzopoulos, D. 1997. Dynamic free-form deformations for animation synthesis. IEEE Trans. Visual. Comput. Graph. 3, 3, 201–214. Google ScholarDigital Library
Featherstone, R. 1983. The calculation of robot dynamics using articulated-body inertias. Int. J. Robotics Res. 2, 1, 13–30.Google ScholarCross Ref
Featherstone, R. 1987. Robot Dynamics Algorithms. Kluwer. Google ScholarDigital Library
Galoppo, N., Otaduy, M. A., Mecklenburg, P., Gross, M., and Lin, M. C. 2006. Fast simulation of deformable models in contact using dynamic deformation textures. In ACM SIGGRAPH /Eurographics Symposium on Computer Animation, M.-P. Cani and J. O’Brien, Eds., Eurographics Association, 73–82. Google ScholarDigital Library
Galoppo, N., Otaduy, M. A., Tekin, S., Gross, M., and Lin, M. C. 2007. Soft articulated characters with fast contact handling. Comput. Graph. Forum 26, 3.Google ScholarCross Ref
Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations 3rd Ed. The Johns Hopkins University Press. Google ScholarDigital Library
Govindaraju, N. K., Redon, S., Lin, M. C., and Manocha, D. 2003. Cullide: interactive collision detection between complex models in large environments using graphics hardware. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics hardware (HWWS’03). Eurographics Association, 25–32. Google ScholarDigital Library
Grossman, R. L., Nerode, A., Ravn, A. P., and Rischel, H., Eds. 1993. Hybrid Systems. Lecture Notes in Computer Science, vol. 736, Springer. Google ScholarDigital Library
Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Proceedings of the Graphics Interface Conference. Canadian Human-Computer Commnication Society, 247–256.Google Scholar
Huang, J., Chen, L., Liu, X., and Bao, H. 2008. Efficient mesh deformation using tetrahedron control mesh. In Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling (SPM’08). ACM, New York, 241–247. Google ScholarDigital Library
Irving, G., Schroeder, C., and Fedkiw, R. 2007. Volume conserving finite element simulations of deformable models. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’04). Eurographics Association, 131–140. Google ScholarDigital Library
James, D. L. and Pai, D. K. 1999. ArtDefo-accurate real time deformable objects. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’99), A. Rockwood, Ed., ACM Press, N.Y., 65–72. Google ScholarDigital Library
James, D. L. and Pai, D. K. 2002. Dyrt: dynamic response textures for real time deformation simulation with graphics hardware. ACM Trans. Graph. 21, 3. Google ScholarDigital Library
Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
Kharevych, L., Mullen, P., Owhadi, H., and Desbrun, M. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
Kim, J. and Pollard, N. S. 2011. Direct control of simulated non-human characters. IEEE Comput. Graph. Appl. 31, 4. Google ScholarDigital Library
Kim, T. and James, D. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28, 5. Google ScholarDigital Library
Lee, S.-H., Sifakis, E., and Terzopoulos, D. 2009. Comprehensive biomechanical modeling and simulation of the upper body. ACM Trans. Graph. 28, 4, 1–17. Google ScholarDigital Library
Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’02). ACM, New York, 49–54. Google ScholarDigital Library
Müller, M. and Gross, M. 2004. Interactive virtual materials. In Proceedings of Graphics Interface (GI’04). Canadian Human-Computer Communications Society, 239–246. Google ScholarDigital Library
Murray, R. M., Li, Z., and Sastry, S. S. 1994. A Mathematical Introduction to Robotic Manipulation. CRC Press. Google ScholarDigital Library
Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809–836.Google ScholarCross Ref
Nesme, M., Kry, P. G., Jeřábková, L., and Faure, F. 2009. Preserving topology and elasticity for embedded deformable models. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
Nesme, M., Payan, Y., and Faure, F. 2006. Animating shapes at arbitrary resolution with non-uniform stiffness. In Proceedings of the Eurographics Workshop in Virtual Reality Interaction and Physical Simulation (VRIPHYS). Eurographics.Google Scholar
O’Brien, J. F., Bargteil, A. W., and Hodgins, J. K. 2002. Graphical modeling and animation of ductile fracture. ACM Trans. Graph. 21, 3. Google ScholarDigital Library
O’Brien, J. F. and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’99). 137–146. Google ScholarDigital Library
Park, F. C., Bobrow, J. E., and Ploen, S. R. 1995. A lie group formulation of robot dynamics. Int. J. Robotics Res. 14, 6, 609–618. Google ScholarDigital Library
Pentland, A. and Williams, J. 1989. Good vibrations: modal dynamics for graphics and animation. In Proceedings of the 16th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’89). ACM, New York, 215–222. Google ScholarDigital Library
Rathod, H. T., Venkatesudu, B., and Nagaraja, K. V. 2005. Gauss legendre quadrature formulas over a tetrahedron. Numer. Math. Part. Diff. Eqs. 22, 1, 197–219.Google ScholarCross Ref
Rocchini, C. and Cignoni, P. 2000. Generating random points in a tetrahedron. J. Graph. Tools 5, 4, 9–12. Google ScholarDigital Library
Schöberl, J. 1997. NETGEN: An advancing front 2D/3D-mesh generator based on abstract rules. Comput. Visual Sci. 1, 41–52.Google ScholarCross Ref
Sederberg, T. W. and Parry, S. R. 1986. Free-form deformation of solid geometric models. SIGGRAPH Comput. Graph. 20, 4, 151–160. Google ScholarDigital Library
Shi, X., Zhou, K., Tong, Y., Desbrun, M., Bao, H., and Guo, B. 2008. Example-based dynamic skinning in real time. ACM Trans. Graph. 27, 3. Google ScholarDigital Library
Shinar, T., Schroeder, C., and Fedkiw, R. 2008. Two-way coupling of rigid and deformable bodies. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’08). ACM. Google ScholarDigital Library
Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2007. Hybrid simulation of deformable solids. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’07), M. Gleicher and D. Thalmann, Eds., Eurographics Association, 81–90. Google ScholarDigital Library
Smith, O. K. 1961. Eigenvalues of a symmetric 3 × 3 matrix. Commu. ACM 4, 4, 168. Google ScholarDigital Library
Stern, A. and Desbrun, M. 2006. Discrete geometric mechanics for variational time integrators. In ACM SIGGRAPH Courses. ACM, New York, 75–80. Google ScholarDigital Library
Sulejmanpašić, A. and Popović, J. 2005. Adaptation of performed ballistic motion. ACM Trans. Graph. 24, 1, 165–179. Google ScholarDigital Library
Teran, J., Blemker, S., Hing, V. N. T., and Fedkiw, R. 2003. Finite volume methods for the simulation of skeletal muscle. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’03). Eurographics Association, 68–74. Google ScholarDigital Library
Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’05). ACM Press, New York, 181–190. Google ScholarDigital Library
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 (SIGGRAPH’87). ACM, New York, 205–214. Google ScholarDigital Library
Terzopoulos, D. and Witkin, A. 1988. Physically based models with rigid and deformable components. IEEE Comput. Graphi. Appli. 8, 6, 41–51. Google ScholarDigital Library
Turner, R. and Thalmann, D. 1993. The elastic surface layer model for animated character construction. In Proceedings of Computer Graphics International Conference. Springer-Verlag, 399–412.Google Scholar
van de Panne, M. and Lamouret, A. 1995. Guided optimization for balanced locomotion. In Proceedings of the Computer Animation and Simulation. D. Terzopoulos and D. Thalmann, Eds., Springer-Verlag, 165–177.Google Scholar
Wojtan, C. and Turk, G. 2008. Fast viscoelastic behavior with thin features. ACM Trans. Graph. 27, 3. Google ScholarDigital Library
Zhang, X. and Kim, Y. J. 2007. Interactive collision detection for deformable models using streaming AABBs. IEEE Trans. Visual. Comput. Graph. 13, 2, 318–329. Google ScholarDigital Library
Zordan, V. B. and Hodgins, J. K. 2002. Motion capture-driven simulations that hit and react. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’02). ACM, New York, 89–96. Google ScholarDigital Library