“Expediting precomputation for reduced deformable simulation” by Yang, Li, Xu, Tian and Zheng
Conference:
Type(s):
Title:
- Expediting precomputation for reduced deformable simulation
Session/Category Title: Simulation in Subspaces
Presenter(s)/Author(s):
Abstract:
Model reduction has popularized itself for simulating elastic deformation for graphics applications. While these techniques enjoy orders-of-magnitude speedups at runtime simulation, the efficiency of precomputing reduced subspaces remains largely over-looked. We present a complete system of precomputation pipeline as a faster alternative to the classic linear and nonlinear modal analysis. We identify three bottlenecks in the traditional model reduction precomputation, namely modal matrix construction, cubature training, and training dataset generation, and accelerate each of them. Even with complex deformable models, our method has achieved orders-of-magnitude speedups over the traditional precomputation steps, while retaining comparable runtime simulation quality.
References:
1. Achlioptas, D. 2001. Database-friendly random projections. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, ACM, 274–281.
2. An, S. S., Kim, T., and James, D. L. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Trans. Graph. 27, 5 (Dec.), 165:1–165:10.
3. Atkinson, K. 1989. An Introduction to Numerical Analysis, 2 edition ed. Wiley, New York, Jan.
4. Baraff, D., and Witkin, A. 1992. Dynamic simulation of non-penetrating flexible bodies. SIGGRAPH Comput. Graph. 26, 2 (July), 303–308.
5. Barbič, J., and James, D. L. 2005. Real-time subspace integration for st. venant-kirchhoff deformable models. In ACM Trans. Graph., vol. 24, ACM, 982–990.
6. Barbič, J., and James, D. L. 2010. Subspace self-collision culling. In ACM Trans. Graph., vol. 29, ACM, 81.
7. Barbič, J., and Popović, J. 2008. Real-time control of physically based simulations using gentle forces. In ACM Trans. Graph., vol. 27, ACM, 163.
8. Barbič, J., and Zhao, Y. 2011. Real-time large-deformation substructuring. In ACM Trans. Graph., vol. 30, ACM, 91.
9. Barbič, J., Sin, F., and Grinspun, E. 2012. Interactive editing of deformable simulations. ACM Trans. Graph. 31, 4, 70.
10. Barbič, J., da Silva, M., and Popović, J. 2009. Deformable object animation using reduced optimal control. ACM Trans. Graph. 28, 3, 53:1–53:9.
11. Berrut, J.-P., and Trefethen, L. N. 2004. Barycentric lagrange interpolation. SIAM Review 46, 3, 501–517.
12. Bingham, E., and Mannila, H. 2001. Random projection in dimensionality reduction: Applications to image and text data. KDD ’01, 245–250.
13. Bonet, D. J., and Wood, D. R. D. 2008. Nonlinear Continuum Mechanics for Finite Element Analysis. Cambridge University Press.
14. Brown, P., and Saad, Y. 1990. Hybrid krylov methods for nonlinear systems of equations. SIAM Journal on Scientific and Statistical Computing 11, 3, 450–481.
15. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. Interactive skeleton-driven dynamic deformations. SIGGRAPH ’02, 586–593.
16. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. A multiresolution framework for dynamic deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’02, 41–47.
17. Chan, T., and Jackson, K. 1984. Nonlinearly preconditioned krylov subspace methods for discrete newton algorithms. SIAM Journal on Scientific and Statistical Computing 5, 3, 533–542.
18. Choi, M. G., and Ko, H.-S. 2005. Modal warping: Real-time simulation of large rotational deformation and manipulation. IEEE Transactions on Visualization and Computer Graphics 11, 1 (Jan.), 91–101.
19. Craig, R. R., and Hale, A. L. 1988. Block-Krylov component synthesis method for structural model reduction. Journal of Guidance, Control, and Dynamics 11, 6, 562–570. 00055.
20. Craig, R. J. 2000. Coupling of substructures for dynamic analyses – An overview. In 41st Structures, Structural Dynamics, and Materials Conference and Exhibit, Structures, Structural Dynamics, and Materials and Co-located Conferences. American Institute of Aeronautics and Astronautics, Apr.
21. Dasgupta, S. 2000. Experiments with random projection. In Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, UAI ’00, 143–151.
22. García, F. G., Paradinas, T., Coll, N., and Patow, G. 2013. *cages:: A multilevel, multi-cage-based system for mesh deformation. ACM Trans. Graph. 32, 3 (July), 24:1–24:13.
23. Golub, G. H., and van Van Loan, C. F. 1996. Matrix Computations (Johns Hopkins Studies in Mathematical Sciences)(3rd Edition). Johns Hopkins University Press.
24. Grinspun, E., Krysl, P., and Schröder, P. 2002. Charms: A simple framework for adaptive simulation. SIGGRAPH ’02, 281–290.
25. Hahn, F., Thomaszewski, B., Coros, S., Sumner, R. W., Cole, F., Meyer, M., Derose, T., and Gross, M. 2014. Subspace clothing simulation using adaptive bases. ACM Trans. Graph. 33, 4 (July), 105:1–105:9.
26. Halko, N., Martinsson, P. G., and Tropp, J. A. 2011. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53, 2 (May), 217–288.
27. Harmon, D., and Zorin, D. 2013. Subspace integration with local deformations. ACM Trans. Graph. 32, 4 (July), 107:1–107:10.
28. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Graphics Interface, CIPS, Canadian Human-Computer Commnication Society, 247–256.
29. Hecht, F., Lee, Y. J., Shewchuk, J. R., and O’Brien, J. F. 2012. Updated sparse cholesky factors for corotational elastodynamics. ACM Trans. Graph. 31, 5 (Sept.), 123:1–123:13.
30. Huang, J., Tong, Y., Zhou, K., Bao, H., and Desbrun, M. 2011. Interactive shape interpolation through controllable dynamic deformation. Visualization and Computer Graphics, IEEE Transactions on 17, 7 (July), 983–992.
31. Hughes, T. J. R. 2000. The Finite Element Method: Linear Static and Dynamic Finite Element Analysis (Dover Civil and Mechanical Engineering). Dover Publications.
32. James, D. L., and Pai, D. K. 2004. Bd-tree: Output-sensitive collision detection for reduced deformable models. SIGGRAPH ’04, 393–398.
33. Johnstone, I. M., and Lu, A. Y. 2009. Sparse Principal Components Analysis. arXiv:0901.4392 {math, stat} (Jan.).
34. Kharevych, L., Mullen, P., Owhadi, H., and Desbrun, M. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Trans. Graph. 28, 3 (July), 51:1–51:8.
35. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28, 5 (Dec.), 123:1–123:9.
36. Kim, T., and James, D. L. 2011. Physics-based character skinning using multi-domain subspace deformations. SCA ’11, 63–72.
37. Kry, P. G., James, D. L., and Pai, D. K. 2002. Eigenskin: Real time large deformation character skinning in hardware. SCA ’02, 153–159.
38. Meyer, M., and Anderson, J. 2007. Key point subspace acceleration and soft caching. ACM Trans. Graph. 26, 3, 74.
39. Miller, K. S. 1981. On the inverse of the sum of matrices. Mathematics Magazine 54, 2, pp. 67–72.
40. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. SCA ’02, 49–54.
41. Nealen, A., Mãčâijller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Computer Graphics Forum 25, 4, 809–836.
42. Nesme, M., Kry, P. G., Jeřábková, L., axnd Faure, F. 2009. Preserving topology and elasticity for embedded deformable models. ACM Trans. Graph. 28, 3, 52.
43. O’Brien, J. F., Cook, P. R., and Essl, G. 2001. Synthesizing sounds from physically based motion. In Proceedings of ACM SIGGRAPH 2001, 529–536.
44. Parlett, B. N. 1987. The Symmetric Eigenvalue Problem (Classics in Applied Mathematics). Society for Industrial and Applied Mathematics.
45. Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. SIGGRAPH ’89, 215–222.
46. Pernice, M., and Walker, H. 1998. Nitsol: A newton iterative solver for nonlinear systems. SIAM Journal on Scientific Computing 19, 1, 302–318.
47. R., H.-N. 1994. Context vectors: general purpose approximate meaning representations self-organized from raw data. Computational Intelligence: Imitating Life, IEEE Press, 43–56.
48. Saad, Y. 1981. Krylov subspace methods for solving large unsymmetric linear systems. Mathematics of Computation 37, 155.
49. Saad, Y. 2011. Numerical Methods for Large Eigenvalue Problems, Revised Edition (Classics in Applied Mathematics). SIAM – Society for Industrial & Applied Mathematics.
50. Shabana, A. A. 2005. Dynamics of Multibody Systems, third ed. Cambridge University Press. Cambridge Books Online.
51. Shewchuk, J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Tech. rep., CMU.
52. Teng, Y., Otaduy, M. A., and Kim, T. 2014. Simulating articulated subspace self-contact. ACM Trans. Graph. 33, 4.
53. Terzopoulos, D., and Fleischer, K. 1988. Deformable models. The Visual Computer 4, 6, 306–331.
54. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. SIGGRAPH Comput. Graph. 21, 4 (Aug.), 205–214.
55. von Tycowicz, C., Schulz, C., Seidel, H.-P., and Hildebrandt, K. 2013. An efficient construction of reduced deformable objects. ACM Trans. Graph. 32, 6 (Nov.), 213:1–213:10.
56. Wang, Y., Jacobson, A., Barbič, J., and Kavan, L. 2015. Linear subspace design for real-time shape deformation. ACM Trans. Graph. 34, 4 (July), 57:1–57:11.
57. Wu, X., Downes, M. S., Goktekin, T., and Tendick, F. 2001. Adaptive nonlinear finite elements for deformable body simulation using dynamic progressive meshes. Computer Graphics Forum 20, 3, 349–358.
58. Xu, H., Li, Y., Chen, Y., and Barbivč, J. 2015. Interactive material design using model reduction. ACM Trans. Graph. 34, 2, 18.
59. Yang, Y., Xu, W., Guo, X., Zhou, K., and Guo, B. 2013. Boundary-aware multidomain subspace deformation. IEEE Transactions on Visualization and Computer Graphics 19, 10, 1633–1645.
60. Zheng, C., and James, D. L. 2011. Toward high-quality modal contact sound. ACM Trans. Graph. 30, 4, 38.
