“Skipping steps in deformable simulation with online model reduction”
Conference:
Type(s):
Title:
- Skipping steps in deformable simulation with online model reduction
Session/Category Title: Physically based animation
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Finite element simulations of nonlinear deformable models are computationally costly, routinely taking hours or days to compute the motion of detailed meshes. Dimensional model reduction can make simulations orders of magnitude faster, but is unsuitable for general deformable body simulations because it requires expensive precomputations, and it can suppress motion that lies outside the span of a pre-specified low-rank basis. We present an online model reduction method that does not have these limitations. In lieu of precomputation, we analyze the motion of the full model as the simulation progresses, incrementally building a reduced-order nonlinear model, and detecting when our reduced model is capable of performing the next timestep. For these subspace steps, full-model computation is “skipped” and replaced with a very fast (on the order of milliseconds) reduced order step. We present algorithms for both dynamic and quasistatic simulations, and a “throttle” parameter that allows a user to trade off between faster, approximate previews and slower, more conservative results. For detailed meshes undergoing low-rank motion, we have observed speedups of over an order of magnitude with our method.
References:
1. An, S. S., Kim, T., and James, D. L. 2008. Optimizing Cubature for Efficient Integration of Subspace Deformations. ACM Trans. on Graphics 27, 5 (Dec.), 165. Google ScholarDigital Library
2. Balay, S., Buschelman, K., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H., 2001. PETSc Web page. http://www.mcs.anl.gov/petsc.Google Scholar
3. Baraff, D., and Witkin, A. P. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH 1998, Computer Graphics Proceedings, Annual Conference Series, 43–54. Google ScholarDigital Library
4. Barbič, J., and James, D. L. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. on Graphics 24, 3 (Aug.), 982–990. Google ScholarDigital Library
5. Barbič, J., and James, D. L. 2007. Time-critical distributed contact for 6-dof haptic rendering of adaptively sampled reduced deformable models. In ACM SIGGRAPH Symposium on Computer Animation, San Diego, CA. Google ScholarDigital Library
6. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics, 594–603. Google ScholarDigital Library
7. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. A Multiresolution Framework for Dynamic Deformations. In ACM SIGGRAPH Symposium on Computer Animation, 41–48. Google ScholarDigital Library
8. 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
9. Gibson, S. F., and Mirtich, B. 1997. A Survey of Deformable Models in Computer Graphics. Tech. Rep. TR-97-19, Mitsubishi Electric Research Laboratories, Cambridge, MA, November.Google Scholar
10. Golub, G., and Van Loan, C. 1996. Matrix Computations, third ed. The Johns Hopkins University Press, Baltimore. Google ScholarDigital Library
11. Grinspun, E., Krysl, P., and Schröder, P. 2002. CHARMS: A Simple Framework for Adaptive Simulation. ACM Trans. on Graphics 21, 3 (July), 281–290. Google ScholarDigital Library
12. Homescu, C., Petzold, L., and Serban, R. 2006. Error estimation for reduced-order models of dynamical systems. SIAM Journal of Numerical Analysis 43, 4, 1693–1714. Google ScholarDigital Library
13. Huang, J., Liu, X., Bao, H., Guo, B., and Shum, H.-Y. 2006. An efficient large deformation method using domain decomposition. Computers and Graphics 30, 927–935. Google ScholarDigital Library
14. Idelsohn, S., 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
15. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In ACM SIGGRAPH Symposium on Computer Animation, 131–140. Google ScholarDigital Library
16. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics 23, 3 (Aug.), 393–398. Google ScholarDigital Library
17. James, D. L., and Twigg, C. D. 2005. Skinning mesh animations. ACM Transactions on Graphics 24, 3 (Aug.), 399–407. Google ScholarDigital Library
18. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. ACM Trans. on Graphics 27, 5 (Dec.), 164:1–164:11. Google ScholarDigital Library
19. Kry, P. G., James, D. L., and Pai, D. K. 2002. EigenSkin: Real Time Large Deformation Character Skinning in Hardware. In ACM SIGGRAPH Symposium on Computer Animation, 153–160. Google ScholarDigital Library
20. Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. International Journal for Numerical Methods in Engineering 51, 479–504.Google ScholarCross Ref
21. Labelle, F., and Shewchuk, J. R. 2007. Isosurface stuffing: Fast tetrahedral meshes with good dihedral angles. ACM Transactions on Graphics 26, 3 (Aug.), 57. Google ScholarDigital Library
22. 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, 165–172. Google ScholarDigital Library
23. Magnenat-Thalmann, N., Laperrière, R., and Thalmann, D. 1988. Joint-dependent local deformations for hand animation and object grasping. In Proceedings on Graphics interface, 26–33. Google ScholarDigital Library
24. Meyer, M., and Anderson, J. 2007. Key Point Subspace Acceleration and Soft Caching. ACM Transactions on Graphics 26, 3 (July), 74. Google ScholarDigital Library
25. Meyer, M., and Matthies, H. G. 2003. Efficient model reduction in non-linear dynamics using the Karhunen-Lóeve expansion and dual-weighted-residual methods. Computational Mechanics 31, 179–191.Google ScholarCross Ref
26. Molino, N., Bao, Z., and Fedkiw, R. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Trans. on Graphics 23, 3 (Aug.), 385–392. Google ScholarDigital Library
27. Nealen, A., Muller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Eurographics: State of the Art Report.Google Scholar
28. O’Brien, J., and Hodgins, J. 1999. Graphical modeling and animation of brittle fracture. ACM Trans. on Graphics, 137–146. Google ScholarDigital Library
29. Ogot, M., Liang, Y., and Cuitino, A. 1996. Hybrid simulation strategy for multiple planar collisions with changing topologies and local deformation. Finite Elements in Analysis&Design 23, 2–4, 225–239. Google ScholarDigital Library
30. Ryckelynck, D., Hermanns, L., Chinesta, F., and Alarcón, E. 2005. An efficient a priori model reduction for boundary element models. Engineering Analysis with Boundary Elements 29, 796–801.Google ScholarCross Ref
31. Ryckelynck, D. 2005. A priori hyperreduction method: an adaptive approach. Journal of Computational Physics 202, 1, 346–366. Google ScholarDigital Library
32. Ryckelynck, D. 2009. Hyper-reduction of mechanical models involving internal variables. International Journal for Numerical Methods in Engineering 77, 75–89.Google ScholarCross Ref
33. Shabana, A. A. 1990. Theory of Vibration, Volume II: Discrete and Continuous Systems. Springer–Verlag, New York, NY.Google Scholar
34. Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. In ACM SIGGRAPH Symposium on Computer Animation, 181–190. Google ScholarDigital Library
35. Terzopoulos, D., and Fleischer, K. 1988. Deformable models. The Visual Computer 4, 6 (Dec.), 306–331.Google ScholarCross Ref
36. Terzopoulos, D., and Witkin, A. 1988. Physically Based Models with Rigid and Deformable Components. IEEE Computer Graphics&Applications 8, 6 (Nov.), 41–51. Google ScholarDigital Library
37. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically Deformable Models. In Computer Graphics (Proceedings of SIGGRAPH 87), 205–214. Google ScholarDigital Library
38. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Transactions on Graphics 25, 3 (July), 826–834. Google ScholarDigital Library
39. Utku, S., Clemente, J., and Salama, M. 1985. Errors in reduction methods. Computers and Structures 21, 6, 1153–1157.Google ScholarCross Ref
40. Wang, X. C., and Phillips, C. 2002. Multi-Weight Enveloping: Least-Squares Approximation Techniques for Skin Animation. In ACM SIGGRAPH Symposium on Computer Animation, 129–138. Google ScholarDigital Library
41. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Trans. on Graphics 28, 3 (Aug.), 39. Google ScholarDigital Library
