“Real-Time subspace integration for St. Venant-Kirchhoff deformable models” by Barbic and James

In this paper, we present an approach for fast subspace integration of reduced-coordinate nonlinear deformable models that is suitable for interactive applications in computer graphics and haptics. Our approach exploits dimensional model reduction to build reduced-coordinate deformable models for objects with complex geometry. We exploit the fact that model reduction on large deformation models with linear materials (as commonly used in graphics) result in internal force models that are simply cubic polynomials in reduced coordinates. Coefficients of these polynomials can be precomputed, for efficient runtime evaluation. This allows simulation of nonlinear dynamics using fast implicit Newmark subspace integrators, with subspace integration costs independent of geometric complexity. We present two useful approaches for generating low-dimensional subspace bases: modal derivatives and an interactive sketching technique. Mass-scaled principal component analysis (mass-PCA) is suggested for dimensionality reduction. Finally, several examples are given from computer animation to illustrate high performance, including force-feedback haptic rendering of a complicated object undergoing large deformations.

1. Almroth. B. O., Stern, P., and Brogan. F. A. 1978. Automatic Choice of Global Shape Functions in Structural Analysis. AIAA Journal 16, 5, 525–528.Google ScholarCross Ref
2. Baraff, D., and Witkin, A. 1992. Dynamic Simulation of Non-penetrating Flexible Bodies. Computer Graphics (Proc. of ACM SIGGRAPH 92) 26(2), 303–308. Google ScholarDigital Library
3. Baraff, D., and Witkin, A. 1998. Large Steps in Cloth Simulation. In Proc. of ACM SIGGRAPH 98, 43–54. Google ScholarDigital Library
4. Basdogan, C. 2001. Real-time Simulation of Dynamically Deformable Finite Element Models Using Modal Analysis and Spectral Lanczos Decomposition Methods. In Medicine Meets Virtual Reality (MMVR’2001), 46–52.Google Scholar
5. Belytschko, T. 2001. Nonlinear Finite Elements for Continua and Structures. Wiley.Google Scholar
6. Bonet, J., and Wood. R. D. 1997. Nonlinear Continuum Mechanics for Finite Element Analysis. Cambridge University Press.Google Scholar
7. Bridson. R., Fedkiw, R. P. and Anderson, J. 2002. Robust Treatment of Collisions. Contact, and Friction for Cloth Animation. ACM Trans. on Graphics 21, 3, 594–603. Google ScholarDigital Library
8. Bro-Nielsen, M., and Cotin, S. 1996. Real-time Volumetric Deformable Models for Surgery Simulation using Finite Elements and Condensation. Comp. Graphics Forum 15, 3, 57–66.Google ScholarCross Ref
9. Capell, S., Green. S., Curless. B., Duchamp, T., and Popović, Z. 2002. A Multiresolution Framework for Dynamic Deformations. In Proc. of the Symp. on Comp. Animation 2002, 41–48. Google ScholarDigital Library
10. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. Interactive Skeleton-Driven Dynamic Deformations. ACM Trans. on Graphics 21, 3 (July), 586–593. Google ScholarDigital Library
11. Choi, M. G., and Ko. H.-S. 2005. Modal Warping: Real-Time Simulation of Large Rotational Deformation and Manipulation. In IEEE Trans. on Vis. and Comp. Graphics, vol. 11, 91–101. Google ScholarDigital Library
12. Cotin, S., Delingette, H., and Ayache, N. 1999. Realtime Elastic Deformations of Soft Tissues for Surgery Simulation. IEEE Trans. on Vis. and Comp. Graphics 5, 1, 62–73. Google ScholarDigital Library
13. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic Real-Time Deformations Using Space & Time Adaptive Sampling. In Proc. of ACM SIGGRAPH 2001, 31–36. Google ScholarDigital Library
14. Faloutsos, P., Van De Panne, M., and Terzopoulos, D. 1997. Dynamic Free-Form Deformations for Animation Synthesis. IEEE Trans. on Vis. and Comp. Graphics 3, 3, 201–214. Google ScholarDigital Library
15. Fung, Y. 1977. A First Course in Continuum Mechanics. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
16. Grinspun, E., Krysl, P., and Schröder, P. 2002. CHARMS: A Simple Frame-work for Adaptive Simulation. ACM Trans. on Graphics 21, 3 (July), 281–290. Google ScholarDigital Library
17. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive Deformation Using Modal Analysis with Constraints. In Proc. of Graphics Interface.Google Scholar
18. Holzapfel, G. A. 2000. Nonlinear Solid Mechanics. Wiley.Google Scholar
19. Idelsohn, S. R., and Cardona. A. 1985. A Load-dependent Basis for Reduced Nonlinear Structural Dynamics. Computers and Structures 20, 1–3, 203–210.Google ScholarCross Ref
20. Idelsohn, S. R., and Cardona, A. 1985. A Reduction Method for Nonlinear Structural Dynamic Analysis. Computer Methods in Applied Mechanics and Engineering 49, 253–279.Google ScholarCross Ref
21. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible Finite Elements for Robust Simulation of Large Deformation. In Proc. of the Symp. on Comp. Animation 2004, 131–140. Google ScholarDigital Library
22. James, D., and Fatahalian. K. 2003. Precomputing Interactive Dynamic Deformable Scenes. In Proc. of ACM SIGGRAPH 2003, ACM, 879–887. Google ScholarDigital Library
23. James, D. L., and Pai, D. K. 1999. Artdefo: Accurate Real Time Deformable Objects. In Proc. of ACM SIGGRAPH 99, vol. 33, 65–72. Google ScholarDigital Library
24. James, D. L., and Pai. D. K. 2002. DyRT: Dynamic Response Textures for Real Time Deformation Simulation with Graphics Hardware. In Proc. of ACM SIGGRAPH 2002. Google ScholarDigital Library
25. James, D. L., and Pai. D. K. 2004. BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models. ACM Trans. on Graphics 23, 3 (Aug.), 393–398. Google ScholarDigital Library
26. James, D. L., Barbič, J., and Twigg, C. D. 2004. Squashing Cubes: Automating Deformable Model Construction for Graphics. In Proc. of ACM SIGGRAPH Sketches and Applications. Google ScholarDigital Library
27. Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. Int. J. for Numerical Methods in Engineering 51, 479–504.Google ScholarCross Ref
28. Lumley, J. L. 1967. The structure of inhomogeneous turbulence. In Atmospheric turbulence and wave propagation, 166–178.Google Scholar
29. Metaxas, D., and Terzopoulos, D. 1992. Dynamic Deformation of Solid Primitives with Constraints. Computer Graphics (Proc. of ACM SIGGRAPH 92) 26(2), 309–312. Google ScholarDigital Library
30. Müller, M., and Gross. M. 2004. Interactive Virtual Materials. In Proc. of Graphics Interface 2004, 239–246. Google ScholarDigital Library
31. Müller, M., Dorsey. J., McMillian, L., Jagnow, R., and Cutler, B. 2002. Stable Real-Time Deformations. In Proc. of the Symp. on Comp. Animation 2002, 49–54. Google ScholarDigital Library
32. Müller, M., Teschner, M., and Gross, M. 2004. Physically-Based Simulation of Objects Represented by Surface Meshes. In Proc. of Comp. Graphics Int. (CGI), 26–33. Google ScholarDigital Library
33. Nickell, R. E. 1976. Nonlinear Dynamics by Mode Superposition. Computer Methods in Applied Mechanics and Engineering 7, 107–129.Google ScholarCross Ref
34. O’BRIEN, J., AND HODGINS. J. 1999. Graphical Modeling and Animation of Brittle Fracture. In Proc. of ACM SIGGRAPH 99, 111–120. Google ScholarDigital Library
35. Pai, D. 2002. Strands: Interactive simulation of thin solids using Cosserat models. Computer Graphics Forum 21, 3, 347–352.Google ScholarCross Ref
36. Pentland, A., and Williams, J. July 1989. Good vibrations: Modal dynamics for graphics and animation. Computer Graphics (Proc. of ACM SIGGRAPH 89) 23, 3, 215–222. Google ScholarDigital Library
37. Picinbono, G., Delingette, H., and Ayache, N. 2001. Non-linear and anisotropic elastic soft tissue models for medical simulation. In IEEE Int. Conf. on Robotics and Automation 2001.Google Scholar
38. Shabana, A. A. 1990. Theory of Vibration, Volume II: Discrete and Continuous Systems. Springer–Verlag, New York, NY.Google Scholar
39. Shinya, M., and Fournier, A. 1992. Stochastic motion – Motion under the influence of wind. Comp. Graphics Forum, 119–128.Google Scholar
40. Stam, J. 1997. Stochastic Dynamics: Simulating the Effects of Turbulence on Flexible Structures. Comp. Graphics Forum 16(3).Google Scholar
41. Terzopoulos, D., and Witkin, A. 1988. Physically Based Models with Rigid and Deformable Components. IEEE Comp. Graphics & Applications 8, 6, 41–51. Google ScholarDigital Library
42. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically Deformable Models. Computer Graphics (Proc. of ACM SIGGRAPH 87) 21(4), 205–214. Google ScholarDigital Library
43. Wriggers, P. 2002. Computational Contact Mechanics. John Wiley & Sons, Ltd.Google Scholar
44. Zhuang, Y., and Canny, J. 2000. Haptic Interaction with Global Deformations. In Proc. of the IEEE Int. Conf. on Robotics and Automation.Google Scholar