Trading Spaces: Adaptive Subspace Time Integration for Contacting Elastodynamics
Article No.: 227, Pages 1 - 16
Abstract
We construct a subspace simulator that adaptively balances solution improvement against system size. The core components of our simulator are an adaptive subspace oracle, model, and parallel time-step solver algorithm. Our in-time-step adaptivity oracle continually assesses subspace solution quality and candidate update proposals while accounting for temporal variations in deformation and spatial variations in material. In turn our adaptivity model is subspace agnostic. It allows application across subspace representations and expresses unrestricted deformations independent of subspace choice. We couple our oracle and model with a custom-constructed parallel time-step solver for our enriched systems that exposes a pair of user tolerances which provide controllable simulation quality. As tolerances are tightened our model converges to full-space solutions (with expected cost increases). On the other hand, as tolerances are relaxed we obtain output-bound simulation costs. We demonstrate the efficacy of our approach across a wide range of challenging nonlinear materials models, material stiffnesses, heterogeneities, dynamic behaviors, and frictionally contacting conditions, obtaining scalable and efficient simulations of complex elastodynamic scenarios.
References
[1]
David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In SIGGRAPH'98 Proceedings. 43--54.
[2]
Jernej Barbič and Doug L. James. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. Graph. 24, 3 (jul 2005), 982--990.
[3]
Adam W Bargteil, Chris Wojtan, Jessica K Hodgins, and Greg Turk. 2007. A finite element method for animating large viscoplastic flow. ACM transactions on graphics (TOG) 26, 3 (2007), 16--es.
[4]
Otman Benchekroun, Jiayi Eris Zhang, Siddartha Chaudhuri, Eitan Grinspun, Yi Zhou, and Alec Jacobson. 2023. Fast Complementary Dynamics via Skinning Eigenmodes. ACM Transactions on Graphics (TOG) 42, 4 (2023), 1--21.
[5]
S. Bouaziz, S. Martin, T. Liu, L. Kavan, and M. Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans Graph 33, 4 (2014).
[6]
Charles George Broyden. 1970. The convergence of a class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics 6, 1 (1970), 76--90.
[7]
Yue Chang, Peter Yichen Chen, Zhecheng Wang, Maurizio M Chiaramonte, Kevin Carlberg, and Eitan Grinspun. 2023. LiCROM: Linear-Subspace Continuous Reduced Order Modeling with Neural Fields. In SIGGRAPH Asia 2023 Conference Papers. 1--12.
[8]
Anka He Chen, Ziheng Liu, Yang Yin, and Cem Yuksel. 2024. Vertex Block Descent. ACM Transactions on Graphics (TOG) 116 (2024).
[9]
Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Transactions on Mathematical Software (TOMS) 35, 3 (2008), 1--14.
[10]
Leonardo Dagum and Ramesh Menon. 1998. OpenMP: an industry standard API for shared-memory programming. IEEE computational science and engineering 5, 1 (1998), 46--55.
[11]
Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, and Alan H Barr. 2001. Dynamic real-time deformations using space & time adaptive sampling. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. 31--36.
[12]
Denis Demidov. 2020. AMGCL---A C++ library for efficient solution of large sparse linear systems. Software Impacts 6 (2020), 100037.
[13]
Marion Dunyach, David Vanderhaeghe, Loïc Barthe, and Mario Botsch. 2013. Adaptive remeshing for real-time mesh deformation. In Eurographics 2013. The Eurographics Association.
[14]
François Faure, Benjamin Gilles, Guillaume Bousquet, and Dinesh K. Pai. 2011. Sparse Meshless Models of Complex Deformable Solids. ACM Trans. Graph. 30, 4, Article 73 (July 2011), 10 pages.
[15]
Zachary Ferguson, Teseo Schneider, Danny Kaufman, and Daniele Panozzo. 2023. In-Timestep Remeshing for Contacting Elastodynamics. ACM Transactions on Graphics (TOG) 42, 4 (2023), 1--15.
[16]
Roger Fletcher. 1970. A new approach to variable metric algorithms. The computer journal 13, 3 (1970), 317--322.
[17]
Lawson Fulton, Vismay Modi, David Duvenaud, David I. W. Levin, and Alec Jacobson. 2019. Latent-space Dynamics for Reduced Deformable Simulation. Computer Graphics Forum 38, 2 (2019), 379--391. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.13645
[18]
T. Gast, C. Schroeder, A. Stomakhin, C. Jiang, and J. M Teran. 2015. Optimization integrator for large time steps. IEEE Trans Vis Comp Graph 21, 10 (2015).
[19]
Donald Goldfarb. 1970. A family of variable-metric methods derived by variational means. Mathematics of computation 24, 109 (1970), 23--26.
[20]
Gaël Guennebaud et al. 2010. Eigen.
[21]
Ernst Hairer and Christian Lubich. 2014. Energy-diminishing integration of gradient systems. IMA J. Numer. Anal. 34, 2 (2014), 452--461.
[22]
David Harmon and Denis Zorin. 2013. Subspace Integration with Local Deformations. ACM Trans. Graph. 32, 4, Article 107 (jul 2013), 10 pages.
[23]
Kemeng Huang, Floyd M. Chitalu, Huancheng Lin, and Taku Komura. 2024. GIPC: Fast and Stable Gauss-Newton Optimization of IPC Barrier Energy. ACM Trans. Graph. 43, 2, Article 23 (mar 2024), 18 pages.
[24]
Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded Biharmonic Weights for Real-Time Deformation. ACM Trans. Graph. 30, 4, Article 78 (jul 2011), 8 pages.
[25]
Couro Kane, Jerrold E Marsden, Michael Ortiz, and Matthew West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. International Journal for numerical methods in engineering 49, 10 (2000), 1295--1325.
[26]
George Karypis and Vipin Kumar. 1997. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. (1997).
[27]
Theodore Kim and Doug L. James. 2009. Skipping Steps in Deformable Simulation with Online Model Reduction. ACM Trans. Graph. 28, 5 (dec 2009), 1--9.
[28]
Lei Lan, Minchen Li, Chenfanfu Jiang, Huamin Wang, and Yin Yang. 2023. Second-Order Stencil Descent for Interior-Point Hyperelasticity. ACM Trans. Graph. 42, 4, Article 108 (jul 2023), 16 pages.
[29]
Lei Lan, Guanqun Ma, Yin Yang, Changxi Zheng, Minchen Li, and Chenfanfu Jiang. 2022. Penetration-Free Projective Dynamics on the GPU. ACM Trans. Graph. 41, 4, Article 69 (jul 2022), 16 pages.
[30]
Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection- and Inversion-free Large Deformation Dynamics. ACM Trans. Graph. (SIGGRAPH) 39, 4, Article 49 (2020).
[31]
Minchen Li, Ming Gao, Timothy Langlois, Chenfanfu Jiang, and Danny M. Kaufman. 2019. Decomposed Optimization Time Integrator for Large-Step Elastodynamics. ACM Trans. on Graph. 38, 4 (2019).
[32]
Minchen Li, Danny M. Kaufman, and Chenfanfu Jiang. 2021. Codimensional Incremental Potential Contact. ACM Trans. Graph. (SIGGRAPH) 40, 4, Article 170 (2021).
[33]
Xuan Li, Yu Fang, Lei Lan, Huamin Wang, Yin Yang, Minchen Li, and Chenfanfu Jiang. 2023. Subspace-Preconditioned GPU Projective Dynamics with Contact for Cloth Simulation. In SIGGRAPH Asia 2023 Conference Papers. 1--12.
[34]
Dong C Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical programming 45, 1 (1989), 503--528.
[35]
H. Liu, N. Mitchell, M. Aanjaneya, and E. Sifakis. 2016. A scalable schur-complement fluids solver for heterogeneous compute platforms. ACM Trans Graph 35, 6 (2016).
[36]
T. Liu, S. Bouaziz, and L. Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans Graph 36, 4 (2017).
[37]
Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: Position-Based Simulation of Compliant Constrained Dynamics (MIG '16). Association for Computing Machinery, New York, NY, USA, 49--54.
[38]
P-L Manteaux, Christopher Wojtan, Rahul Narain, Stéphane Redon, François Faure, and M-P Cani. 2017. Adaptive physically based models in computer graphics. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 312--337.
[39]
Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-Based Elastic Materials. SIGGRAPH Comput. Graph. (2011), 1--8.
[40]
Alexandre Mercier-Aubin, Paul G. Kry, Alexandre Winter, and David I. W. Levin. 2022. Adaptive Rigidification of Elastic Solids. ACM Trans. Graph. 41, 4, Article 71 (jul 2022), 11 pages.
[41]
Vismay Modi, Nicholas Sharp, Or Perel, Shinjiro Sueda, and David I. W. Levin. 2024. Simplicits: Mesh-Free, Geometry-Agnostic Elastic Simulation. ACM Trans. Graph. 43, 4, Article 117 (jul 2024), 11 pages.
[42]
Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. J Vis Commun Image R 18, 2 (2007), 109--118.
[43]
Rahul Narain, Tobias Pfaff, and James F O'Brien. 2013. Folding and crumpling adaptive sheets. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1--8.
[44]
Rahul Narain, Armin Samii, and James F O'brien. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM transactions on graphics (TOG) 31, 6 (2012), 1--10.
[45]
Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer Science & Business Media.
[46]
M. Overby, G. E Brown, J. Li, and R. Narain. 2017. ADMM ⊇ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. IEEE Trans Vis Comp Graph 23, 10 (2017).
[47]
A. Pentland and J. Williams. 1989. Good Vibrations: Modal Dynamics for Graphics and Animation. SIGGRAPH Comput. Graph. 23, 3 (jul 1989), 207--214.
[48]
Chuck Pheatt. 2008. Intel® threading building blocks. Journal of Computing Sciences in Colleges 23, 4 (2008), 298--298.
[49]
Cristian Romero, Dan Casas, Maurizio M. Chiaramonte, and Miguel A. Otaduy. 2022. Contact-Centric Deformation Learning. ACM Trans. Graph. 41, 4, Article 70 (jul 2022), 11 pages.
[50]
Olaf Schenk, Klaus Gärtner, Wolfgang Fichtner, and Andreas Stricker. 2001. PARDISO: a high-performance serial and parallel sparse linear solver in semiconductor device simulation. Future Generation Computer Systems 18, 1 (2001), 69--78.
[51]
Silvia Sellán, Jack Luong, Leticia Mattos Da Silva, Aravind Ramakrishnan, Yuchuan Yang, and Alec Jacobson. 2022. Breaking Good: Fracture Modes for Realtime Destruction. arXiv:2111.05249 [cs.GR] https://arxiv.org/abs/2111.05249
[52]
David F Shanno. 1970. Conditioning of quasi-Newton methods for function minimization. Mathematics of computation 24, 111 (1970), 647--656.
[53]
Nicholas Sharp, Cristian Romero, Alec Jacobson, Etienne Vouga, Paul G Kry, David IW Levin, and Justin Solomon. 2023. Data-Free Learning of Reduced-Order Kinematics. (2023).
[54]
Siyuan Shen, Yin Yang, Tianjia Shao, He Wang, Chenfanfu Jiang, Lei Lan, and Kun Zhou. 2021. High-Order Differentiable Autoencoder for Nonlinear Model Reduction. ACM Trans. Graph. 40, 4, Article 68 (jul 2021), 15 pages.
[55]
Xing Shen, Runyuan Cai, Mengxiao Bi, and Tangjie Lv. 2024. Preconditioned Nonlinear Conjugate Gradient Method for Real-time Interior-point Hyperelasticity. arXiv preprint arXiv:2405.08001 (2024).
[56]
Timothy JR Simnett, Stephen D Laycock, and Andy M Day. 2009. An Edge-based Approach to Adaptively Refining a Mesh for Cloth Deformation. In TPCG. 77--84.
[57]
Lawrence Sirovich and Michael Kirby. 1987. Low-dimensional procedure for the characterization of human faces. Josa a 4, 3 (1987), 519--524.
[58]
Breannan Smith, Fernando De Goes, and Theodore Kim. 2018. Stable neo-hookean flesh simulation. ACM Transactions on Graphics (TOG) 37, 2 (2018), 1--15.
[59]
Jonas Spillmann and Matthias Teschner. 2008. An adaptive contact model for the robust simulation of knots. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 497--506.
[60]
Yun Teng, Mark Meyer, Tony DeRose, and Theodore Kim. 2015. Subspace Condensation: Full Space Adaptivity for Subspace Deformations. ACM Trans. Graph. 34, 4, Article 76 (jul 2015), 9 pages.
[61]
Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2015. Linear Subspace Design for Real-Time Shape Deformation. ACM Trans. Graph. 34, 4, Article 57 (jul 2015), 11 pages.
[62]
Ofir Weber, Roi Poranne, and Craig Gotsman. 2012. Biharmonic coordinates. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 2409--2422.
[63]
Martin Wicke, Daniel Ritchie, Bryan M Klingner, Sebastian Burke, Jonathan R Shewchuk, and James F O'Brien. 2010. Dynamic local remeshing for elastoplastic simulation. ACM Transactions on graphics (TOG) 29, 4 (2010), 1--11.
[64]
Yufeng Zhu, Robert Bridson, and Danny M Kaufman. 2018. Blended cured quasi-newton for distortion optimization. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1--14.
Index Terms
- Trading Spaces: Adaptive Subspace Time Integration for Contacting Elastodynamics
Recommendations
Discriminant Subspace Analysis: A Fukunaga-Koontz Approach
The Fisher Linear Discriminant (FLD) is commonly used in pattern recognition. It finds a linear subspace that maximally separates class patterns according to the Fisher Criterion. Several methods of computing the FLD have been proposed in the literature,...
Maximum Margin Subspace Projections for Face Recognition
CICC-ITOE '10: Proceedings of the 2010 International Conference on Innovative Computing and Communication and 2010 Asia-Pacific Conference on Information Technology and Ocean EngineeringTraditional dimensionality reduction algorithms such as Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA) and Locality Preserving Projections (LPP) have been employed in many fields such as biometrics patter recognition. But those ...
Subspace-based subspace sum graph on vector spaces
AbstractSuppose that is a n-dimensional vector space and is its fixed k-dimensional subspace such that In the present article, we initiate the study of a new graph structure “subspace-based subspace sum graph” where the vertex set
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 November 2024
Published in TOG Volume 43, Issue 6
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSERC Discovery
- Connaught Fund
- CFI-JELF Fund
- Canada Research Chairs
- Ontario Early Researchers
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 58Total Downloads
- Downloads (Last 12 months)58
- Downloads (Last 6 weeks)58
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in