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

  • ©Junggon Kim and Nancy S. Pollard

Conference:


Type:


Title:

    Fast Simulation of Skeleton-Driven Deformable Body Characters

Presenter(s)/Author(s):



Abstract:


    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.

References:


    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


ACM Digital Library Publication: