A Multi-Layer Solver for XPBD
Pages 1 - 11
Abstract
We present a novel multi-layer method for extended position-based dynamics that exploits a sequence of reduced models consisting of rigid and elastic parts to speed up convergence. Taking inspiration from concepts like adaptive rigidification and long-range constraints, we automatically generate different rigid bodies at each layer based on the current strain rate. During the solve, the rigid bodies provide coupling between progressively less distant vertices during layer iterations, and therefore the fully elastic iterations at the final layer start from a lower residual error. Our layered approach likewise helps with the treatment of contact, where the mixed solves of both rigid and elastic in the layers permit fast propagation of impacts. We show several experiments that guide the selection of parameters of the solver, including the number of layers, the iterations per layers, as well as the choice of rigid patterns. Overall, our results show lower compute times for achieving a desired residual reduction across a variety of simulation models and scenarios.
References
[1]
[AD99] Adams, M. and Demmel, J. "Parallel Multigrid Solver for 3D Unstructured Finite Element Problems". SC '99: Proceedings of the 1999 ACM/IEEE Conference on Supercomputing. 1999, 27--27. 3.
[2]
[BKCW14] Bender, Jan, Koschier, Dan, Charrier, Patrick, and Weber, Daniel. "Position-based simulation of continuous materials". Computers & Graphics 44 (2014), 1--10. issn: 0097-8493. 2.
[3]
[BML*14] Bouaziz, Sofien, Martin, Sebastian, Liu, Tiantian, et al. "Projective Dynamics: Fusing Constraint Projections for Fast Simulation". ACM Trans. Graph. 33.4 (July 2014). issn: 0730-0301. 6 2.
[4]
[BRL15] Barbié, L., Ramière, I., and Lebon, F. "An automatic multilevel refinement technique based on nested local meshes for nonlinear mechanics". Computers & Structures 147 (2015). CIVIL-COMP, 14--25. issn: 0045-7949. 3.
[5]
[BYM05] Bell, Nathan, Yu, Yizhou, and Mucha, Peter J. "Particle-based simulation of granular materials". Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. SCA '05. Los Angeles, California: Association for Computing Machinery, 2005, 77--86. isbn: 1595931988. 4.
[6]
[Cet23] Cetinaslan, Ozan. "ESBD: Exponential Strain-based Dynamics using XPBD algorithm". Computers & Graphics 116 (2023), 500--512. issn: 0097-8493. 3.
[7]
[CNS*18] Chen, Jun, Nonaka, Keisuke, Sankoh, Hiroshi, et al. "Efficient Parallel Connected Component Labeling With a Coarse-to-Fine Strategy". IEEE Access 6 (2018), 55731--55740. 10.
[8]
[FP15] Fratarcangeli, M. and Pellacini, F. "Scalable Partitioning for Parallel Position Based Dynamics". Computer Graphics Forum 34.2 (2015), 405--413. 4.
[9]
[GPP*14] Gupta, Siddharth, Palsetia, Diana, Patwary, Md. Mostofa Ali, et al. "A New Parallel Algorithm for Two-Pass Connected Component Labeling". 2014 IEEE International Parallel & Distributed Processing Symposium Workshops. 2014, 1355--1362. 10.
[10]
[Gui93] Guillard, Hervé. Node-nested multi-grid method with Delaunay coarsening. Research Report RR-1898. INRIA, 1993 3.
[11]
[KCM12] Kim, Tae-Yong, Chentanez, Nuttapong, and Müller-Fischer, Matthias. "Long range attachments - a method to simulate inextensible clothing in computer games". Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. SCA '12. 2012, 305--310. 2.
[12]
[LZBJ21] Liu, Hsueh-Ti Derek, Zhang, Jiayi Eris, Ben-Chen, Mirela, and Jacobson, Alec. "Surface Multigrid via Intrinsic Prolongation". ACM Trans. Graph. 40.4 (2021) 2.
[13]
[MCMJ17] Müller, Matthias, Chentanez, Nuttapong, Macklin, Miles, and Jeschke, Stefan. "Long Range Constraints for Rigid Body Simulations". Proceedings of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation. SCA '17. 2017. isbn: 9781450350914. 2.
[14]
[MEM*20] Macklin, M., Erleben, K., Müller, M., et al. "Primal/Dual Descent Methods for Dynamics". Computer Graphics Forum 39.8 (2020), 89--100. 2.
[15]
[MHHR07] Müller, Matthias, Heidelberger, Bruno, Hennix, Marcus, and Ratcliff, John. "Position based dynamics". Journal of Visual Communication and Image Representation 18.2 (2007), 109--118. issn: 1047-3203. 2.
[16]
[MK23] Mercier-Aubin, Alexandre and Kry, Paul G. "Adaptive Rigidification of Discrete Shells". Proc. ACM Comput. Graph. Interact. Tech. 6.3 (Aug. 2023). 3, 10.
[17]
[MKWL22] Mercier-Aubin, Alexandre, Kry, Paul G., Winter, Alexandre, and Levin, David I. W. "Adaptive Rigidification of Elastic Solids". ACM Trans. Graph. 41.4 (July 2022). issn: 0730-0301. 2--4.
[18]
[MM21] Macklin, Miles and Muller, Matthias. "A Constraint-based Formulation of Stable Neo-Hookean Materials". Proceedings of the 14th ACM SIGGRAPH Conference on Motion, Interaction and Games. MIG '21. Virtual Event, Switzerland: Association for Computing Machinery, 2021. isbn: 9781450391313. 10.
[19]
[MMC*20] Müller, Matthias, Macklin, Miles, Chentanez, Nuttapong, et al. "Detailed Rigid Body Simulation with Extended Position Based Dynamics". Computer Graphics Forum 39.8 (2020), 101--112. 2--4, 6.
[20]
[MMC16] Macklin, Miles, Müller, Matthias, and Chentanez, Nuttapong. "XPBD: Position-Based Simulation of Compliant Constrained Dynamics". Proceedings of the 9th International Conference on Motion in Games. MIG '16. 2016, 49--54. isbn: 9781450345927. 2, 3.
[21]
[MMCK14] Macklin, Miles, Müller, Matthias, Chentanez, Nuttapong, and Kim, Tae-Yong. "Unified particle physics for real-time applications". ACM Trans. Graph. 33.4 (July 2014). issn: 0730-0301. 4.
[22]
[MSZ94] Murray, Richard M., Sastry, S. Shankar, and Zexiang, Li. A Mathematical Introduction to Robotic Manipulation. 1st. USA: CRC Press, Inc., 1994. isbn: 0849379814 3.
[23]
[Mül08] Müller, Matthias. "Hierarchical Position Based Dynamics." Vol. 8. Jan. 2008, 1--10. 2, 3.
[24]
[MYB*01] Marins, J.L., Yun, Xiaoping, Bachmann, E.R., et al. "An extended Kalman filter for quaternion-based orientation estimation using MARG sensors". Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180). Vol. 4. 2001, 2003--2011 vol.4. 4.
[25]
[MZS*11] McAdams, Aleka, Zhu, Yongning, Selle, Andrew, et al. "Efficient elasticity for character skinning with contact and collisions". ACM Trans. Graph. 30.4 (July 2011). issn: 0730-0301. 3.
[26]
[SLM06] Servin, Martin, Lacoursière, Claude, and Melin, Niklas. "Interactive Simulation of Elastic Deformable Materials". Proceedings of SIGRAD. Jan. 2006, 22--32. isbn: 91-85643-17-3 3.
[27]
[SVJ15] Sacht, Leonardo, Vouga, Etienne, and Jacobson, Alec. "Nested cages". ACM Trans. Graph. 34.6 (Nov. 2015). issn: 0730-0301. 3.
[28]
[TBV12] Tonge, Richard, Benevolenski, Feodor, and Voroshilov, Andrey. "Mass Splitting for Jitter-Free Parallel Rigid Body Simulation". ACM Trans. Graph. 31.4 (July 2012). issn: 0730-0301. 4.
[29]
[TKA23] Ton-That, Quoc-Minh, Kry, Paul G., and Andrews, Sheldon. "Parallel block Neo-Hookean XPBD using graph clustering". Computers & Graphics 110 (2023), 1--10. issn: 0097-8493. 2.
[30]
[TvL84] Tarjan, Robert E. and van Leeuwen, Jan. "Worst-Case Analysis of Set Union Algorithms". J. ACM 31.2 (Mar. 1984), 245--281. issn: 0004-5411. 5.
[31]
[XTL19] Xian, Zangyueyang, Tong, Xin, and Liu, Tiantian. "A Scalable Galerkin Multigrid Method for Real-Time Simulation of Deformable Objects". ACM Trans. Graph. 38.6 (Nov. 2019). issn: 0730-0301. 2.
Index Terms
- A Multi-Layer Solver for XPBD
Recommendations
Fast frictional dynamics for rigid bodies
SIGGRAPH '05: ACM SIGGRAPH 2005 PapersWe describe an efficient algorithm for the simulation of large sets of non-convex rigid bodies. The algorithm finds a simultaneous solution for a multi-body system that is linear in the total number of contacts detected in each iteration. We employ a ...
Fast frictional dynamics for rigid bodies
We describe an efficient algorithm for the simulation of large sets of non-convex rigid bodies. The algorithm finds a simultaneous solution for a multi-body system that is linear in the total number of contacts detected in each iteration. We employ a ...
Nonconvex rigid bodies with stacking
We consider the simulation of nonconvex rigid bodies focusing on interactions such as collision, contact, friction (kinetic, static, rolling and spinning) and stacking. We advocate representing the geometry with both a triangulated surface and a signed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
276 pages
- Conference Co-chairs:
- Paul Kry,
- Marie-Paule Cani,
- Program Co-chairs:
- Melina Skouras,
- He Wang
Sponsors
In-Cooperation
- EUROGRAPHICS: The European Association for Computer Graphics
Publisher
Eurographics Association
Goslar, Germany
Publication History
Published: 18 September 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SCA '24
Sponsor:
SCA '24: ACM SIGGRAPH/Eurographics Symposium on Computer Animation
August 21 - 23, 2024
Quebec, Montreal, Canada
Acceptance Rates
Overall Acceptance Rate 183 of 487 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 23Total Downloads
- Downloads (Last 12 months)23
- Downloads (Last 6 weeks)2
Reflects downloads up to 04 Jan 2025
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