“Hyper-reduced projective dynamics” by Brandt, Eisemann and Hildebrandt
Conference:
Type(s):
Entry Number: 80
Title:
- Hyper-reduced projective dynamics
Session/Category Title: That's Elastic
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present a method for the real-time simulation of deformable objects that combines the robustness, generality, and high performance of Projective Dynamics with the efficiency and scalability offered by model reduction techniques. The method decouples the cost for time integration from the mesh resolution and can simulate large meshes in real-time. The proposed hyper-reduction of Projective Dynamics combines a novel fast approximation method for constraint projections and a scalable construction of sparse subspace bases. The resulting system achieves real-time rates for large sub-spaces enabling rich dynamics and can resolve general user interactions, collision constraints, external forces and changes to the materials. The construction of the hyper-reduced system does not require user-interaction and refrains from using training data or modal analysis, which results in a fast preprocessing stage.
References:
1. Steven S. An, Theodore Kim, and Doug L. James. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Trans. Graph. 27, 5 (2008), 1–10. Google ScholarDigital Library
2. Jernej Barbič and Doug L. James. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. Graph. 24, 3 (2005), 982–990. Google ScholarDigital Library
3. Jernej Barbič and Doug L. James. 2010. Subspace Self-collision Culling. ACM Trans. Graph. 29, 4 (2010), 81:1–81:9. Google ScholarDigital Library
4. Jernej Barbič, Funshing Sin, and Eitan Grinspun. 2012. Interactive Editing of Deformable Simulations. ACM Trans. Graph. 31, 4 (2012), 70:1–70:8. Google ScholarDigital Library
5. Maxime Barrault, Yvon Maday, Ngoc Cuong Nguyen, and Anthony T. Patera. 2004. An ’empirical interpolation’ method: application to efficient reduced-basis discretization of partial differential equations. Comptes Rendus Mathematique 339, 9 (2004), 667–672.Google ScholarCross Ref
6. Jan Bender, Dan Koschier, Patrick Charrier, and Daniel Weber. 2014. Position-based simulation of continuous materials. Computers & Graphics 44 (2014), 1 — 10. Google ScholarDigital Library
7. Jan Bender, Matthias Müller, and Miles Macklin. 2017. Position-Based Simulation Methods in Computer Graphics. In EUROGRAPHICS 2017 Tutorials.Google Scholar
8. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans. Graph. 33, 4 (2014), 154:1–154:11. Google ScholarDigital Library
9. Christopher Brandt and Klaus Hildebrandt. 2017. Compressed Vibration Modes of Deformable Bodies. Computer Aided Geometric Design 52–53 (2017), 297–312.Google Scholar
10. Christopher Brandt, Christoph von Tycowicz, and Klaus Hildebrandt. 2016. Geometric Flows of Curves in Shape Space for Processing Motion of Deformable Objects. Computer Graphics Forum 35, 2 (2016).Google Scholar
11. Marcel Campen, Martin Heistermann, and Leif Kobbelt. 2013. Practical Anisotropic Geodesy. Computer Graphics Forum 32, 5 (2013), 63–71. Google ScholarDigital Library
12. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popovič. 2002. A Multiresolution Framework for Dynamic Deformations. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 41–47. Google ScholarDigital Library
13. Jeffrey N. Chadwick, Steven S. An, and Doug L. James. 2009. Harmonic shells: a practical nonlinear sound model for near-rigid thin shells. ACM Trans. Graph. 28, 5 (2009), 119:1–119:10. Google ScholarDigital Library
14. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29 (2010), 38:1–38:6. Google ScholarDigital Library
15. Saifon Chaturantabut and Danny C Sorensen. 2010. Nonlinear model reduction via discrete empirical interpolation. SIAM Journal on Scientific Computing 32, 5 (2010), 2737–2764. Google ScholarDigital Library
16. Xiang Chen, Changxi Zheng, and Kun Zhou. 2017. Example-Based Subspace Stress Analysis for Interactive Shape Design. IEEE Trans. Vis. and Comp. Graph. 23, 10 (2017), 2314–2327.Google ScholarDigital Library
17. Min Gyu Choi and Hyeong-Seok Ko. 2005. Modal Warping: Real-Time Simulation of Large Rotational Deformation and Manipulation. IEEE Trans. Vis. Comput. Graphics 11, 1 (2005), 91–101. Google ScholarDigital Library
18. Leonardo Dagum and Ramesh Menon. 1998. OpenMP: An Industry-Standard API for Shared-Memory Programming. IEEE Comput. Sci. Eng. 5, 1 (1998), 46–55. Google ScholarDigital Library
19. Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, and Alan H. Barr. 2001. Dynamic Real-time Deformations Using Space & Time Adaptive Sampling. In Proc. ACM SIGGRAPH. 31–36. Google ScholarDigital Library
20. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K. Pai. 2011. Frame-based Elastic Models. ACM Trans. Graph. 30, 2 (2011), 15:1–15:12. Google ScholarDigital Library
21. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org. (2010).Google Scholar
22. Fabian Hahn, Bernhard Thomaszewski, Stelian Coros, Robert W Sumner, Forrester Cole, Mark Meyer, Tony DeRose, and Markus H. Gross. 2014. Subspace clothing simulation using adaptive bases. ACM Trans. Graph. 33, 4 (2014), 105:1–105:9. Google ScholarDigital Library
23. David Harmon and Denis Zorin. 2013. Subspace integration with local deformations. ACM Trans. Graph. 32, 4 (2013), 107:1–107:10. Google ScholarDigital Library
24. Klaus Hildebrandt, Christian Schulz, Christoph von Tycowicz, and Konrad Polthier. 2011. Interactive surface modeling using modal analysis. ACM Trans. Graph. 30, 5 (2011), 119:1–119:11. Google ScholarDigital Library
25. Klaus Hildebrandt, Christian Schulz, Christoph von Tycowicz, and Konrad Polthier. 2012. Interactive spacetime control of deformable objects. ACM Trans. Graph. 31, 4 (2012), 71:1–71:8. Google ScholarDigital Library
26. Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-Yi Wei, Shang-Hua Teng, Hujun Bao, Baining Guo, and Heung-Yeung Shum. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3 (2006). Google ScholarDigital Library
27. Jin Huang, Yiying Tong, Kun Zhou, Hujun Bao, and Mathieu Desbrun. 2011. Interactive Shape Interpolation through Controllable Dynamic Deformation. IEEE Trans. Vis. Comput. Graph. 17, 7 (2011), 983–992. Google ScholarDigital Library
28. Alec Jacobson, Ilya Baran, Ladislav Kavan, Jovan Popović, and Olga Sorkine. 2012. Fast Automatic Skinning Transformations. ACM Trans. Graph. 31, 4 (2012), 77:1–77:10. Google ScholarDigital Library
29. Alec Jacobson, Ilya Baran, Jovan Popovic, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4 (2011), 78:1–78:8. Google ScholarDigital Library
30. Lily Kharevych, Patrick Mullen, Houman Owhadi, and Mathieu Desbrun. 2009. Numerical Coarsening of Inhomogeneous Elastic Materials. ACM Trans. Graph. 28, 3 (2009), 51:1–51:8. Google ScholarDigital Library
31. Theodore Kim and John Delaney. 2013. Subspace Fluid Re-simulation. ACM Trans. Graph. 32, 4 (2013), 62:1–62:9. Google ScholarDigital Library
32. Tae-Yong Kim, Nuttapong Chentanez, and Matthias Müller-Fischer. 2012. Long Range Attachments – a Method to Simulate Inextensible Clothing in Computer Games. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 305–310. Google ScholarDigital Library
33. Petr Krysl, Sanjay Lall, and Jerrold E. Marsden. 2001. Dimensional Model Reduction in Non-linear Finite Element Dynamics of Solids and Structures. Int. J. Numer. Meth. Eng 51 (2001), 479–504.Google ScholarCross Ref
34. Siwang Li, Jin Huang, Fernando de Goes, Xiaogang Jin, Hujun Bao, and Mathieu Desbrun. 2014. Space-time Editing of Elastic Motion Through Material Optimization and Reduction. ACM Trans. Graph. 33, 4 (2014), 108:1–108:10. Google ScholarDigital Library
35. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast Simulation of Mass-spring Systems. ACM Trans. Graph. 32, 6 (2013), 214:1–214:7. Google ScholarDigital Library
36. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans. Graph. 36, 3 (2017), 23:1–23:16. Google ScholarDigital Library
37. Miles Macklin and Matthias Müller. 2013. Position Based Fluids. ACM Trans. Graph. 32, 4 (2013), 104:1–104:12. Google ScholarDigital Library
38. Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: Position-based Simulation of Compliant Constrained Dynamics. In Proc. ACM Motion in Games. 49–54. Google ScholarDigital Library
39. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based Elastic Materials. ACM Trans. Graph. 30, 4 (2011), 72:1–72:8. Google ScholarDigital Library
40. Matthias Müller. 2008. Hierarchical Position Based Dynamics. In Proc. Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS).Google Scholar
41. Matthias Müller and Nuttapong Chentanez. 2011. Solid Simulation with Oriented Particles. ACM Trans. Graph. 30, 4 (2011), 92:1–92:10. Google ScholarDigital Library
42. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2014. Strain Based Dynamics. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 149–157. Google ScholarDigital Library
43. Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position Based Dynamics. J. Vis. Comun. Image Represent. 18, 2 (2007), 109–118.Google ScholarDigital Library
44. Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless Deformations Based on Shape Matching. In Proc. ACM SIGGRAPH. 471–478. Google ScholarDigital Library
45. Przemyslaw Musialski, Thomas Auzinger, Michael Birsak, Michael Wimmer, and Leif Kobbelt. 2015. Reduced-order Shape Optimization Using Offset Surfaces. ACM Trans. Graph. 34, 4 (2015), 102:1–102:9. Google ScholarDigital Library
46. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM ⊇ Projective Dynamics: Fast Simulation of General Constitutive Models. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 21–28. Google ScholarDigital Library
47. Matthieu Nesme, Paul G. Kry, Lenka Jeřábková, and François Faure. 2009. Preserving Topology and Elasticity for Embedded Deformable Models. ACM Trans. Graph. 28, 3 (2009), 52:1–52:9. Google ScholarDigital Library
48. Thomas Neumann, Kiran Varanasi, Stephan Wenger, Markus Wacker, Marcus Magnor, and Christian Theobalt. 2013. Sparse Localized Deformation Components. ACM Trans. Graph. 32, 6 (2013), 179:1–179:10. Google ScholarDigital Library
49. John Nickolls, Ian Buck, Michael Garland, and Kevin Skadron. 2008. Scalable Parallel Programming with CUDA. Queue 6, 2 (2008), 40–53. Google ScholarDigital Library
50. Matthew Overby, George E. Brown, Jie Li, and Rahul Narain. 2017. ADMM ⊇ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. IEEE Trans. Vis. and Comp. Graph. 23, 10 (2017), 2222–2234.Google ScholarDigital Library
51. Zherong Pan, Hujun Bao, and Jin Huang. 2015. Subspace Dynamic Simulation Using Rotation-strain Coordinates. ACM Trans. Graph. 34, 6 (2015), 242:1–242:12. Google ScholarDigital Library
52. Alex Pentland and John Williams. 1989. Good vibrations: modal dynamics for graphics and animation. In Proc. of ACM SIGGRAPH. 215–222. Google ScholarDigital Library
53. Olivier Rémillard and Paul G. Kry. 2013. Embedded Thin Shells for Wrinkle Simulation. ACM Trans. Graph. 32, 4 (2013), 50:1–50:8. Google ScholarDigital Library
54. Alec R. Rivers and Doug L. James. 2007. FastLSM: Fast Lattice Shape Matching for Robust Real-time Deformation. ACM Trans. Graph. 26, 3 (2007). Google ScholarDigital Library
55. Christian Schulz, Christoph von Tycowicz, Hans-Peter Seidel, and Klaus Hildebrandt. 2014. Animating Deformable Objects using Sparse Spacetime Constraints. ACM Trans. Graph. 33, 4 (2014), 109:1–109:10. Google ScholarDigital Library
56. Sara C. Schvartzman, Jorge Gascón, and Miguel A. Otaduy. 2009. Bounded Normal Trees for Reduced Deformations of Triangulated Surfaces. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 75–82. Google ScholarDigital Library
57. Jos Stam. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In Proc. IEEE International Conference on Computer-Aided Design and Computer Graphics. 1–11.Google ScholarCross Ref
58. Yun Teng, Miguel A. Otaduy, and Theodore Kim. 2014. Simulating Articulated Subspace Self-contact. ACM Trans. Graph. 33, 4 (2014), 106:1–106:9. Google ScholarDigital Library
59. Philipp von Radziewsky, Elmar Eisemann, Hans-Peter Seidel, and Klaus Hildebrandt. 2016. Optimized subspaces for deformation-based modeling and shape interpolation. Computers & Graphics 58 (2016), 128 — 138. Google ScholarDigital Library
60. Christoph von Tycowicz, Christian Schulz, Hans-Peter Seidel, and Klaus Hildebrandt. 2013. An Efficient Construction of Reduced Deformable Objects. ACM Trans. Graph. 32, 6 (2013), 213:1–213:10. Google ScholarDigital Library
61. Christoph von Tycowicz, Christian Schulz, Hans-Peter Seidel, and Klaus Hildebrandt. 2015. Real-time Nonlinear Shape Interpolation. ACM Trans. Graph. 34, 3 (2015), 34:1–34:10. Google ScholarDigital Library
62. Huamin Wang. 2015. A Chebyshev Semi-iterative Approach for Accelerating Projective and Position-based Dynamics. ACM Trans. Graph. 34, 6 (2015), 246:1–246:9. Google ScholarDigital Library
63. Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2015. Linear Subspace Design for Real-time Shape Deformation. ACM Trans. Graph. 34, 4 (2015), 57:1–57:11. Google ScholarDigital Library
64. Marcel Weiler, Dan Koschier, and Jan Bender. 2016. Projective Fluids. In Proc. ACM Motion in Games. 79–84. Google ScholarDigital Library
65. Chris Wojtan and Greg Turk. 2008. Fast Viscoelastic Behavior with Thin Features. ACM Trans. Graph. 27, 3 (2008), 47:1–47:8. Google ScholarDigital Library
66. Xiaofeng Wu, Rajaditya Mukherjee, and Huamin Wang. 2015. A Unified Approach for Subspace Simulation of Deformable Bodies in Multiple Domains. ACM Trans. Graph. 34, 6 (2015), 241:1–241:9. Google ScholarDigital Library
67. Hongyi Xu, Yijing Li, Yong Chen, and Jernej Barbic. 2015. Interactive Material Design Using Model Reduction. ACM Trans. Graph. 34, 2 (2015), 18:1–18:14. Google ScholarDigital Library
68. Yin Yang, Dingzeyu Li, Weiwei Xu, Yuan Tian, and Changxi Zheng. 2015. Expediting Precomputation for Reduced Deformable Simulation. ACM Trans. Graph. 34, 6 (2015), 243:1–243:13. Google ScholarDigital Library
69. Y. Yang, W. Xu, X. Guo, K. Zhou, and B. Guo. 2013. Boundary-Aware Multidomain Subspace Deformation. IEEE Trans. Vis. and Comp. Graph. 19, 10 (2013), 1633–1645.Google ScholarCross Ref
