Parallel block Neo-Hookean XPBD using graph clustering. (February 2023)

• Record Type: Journal Article
• Authors: Ton-That, Quoc-Minh; Kry, Paul G.; Andrews, Sheldon
• Is Part Of: Computers & graphics. Volume 110(2023)
• Page Start: 1
• Page End: 10
• Publication Date: 2023-02
• Subjects: Finite element method -- Physics-based animation -- Soft body simulation -- Elasticity -- Real-time physics; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2022.10.009
• Languages: English
• ISSNs: 0097-8493

Abstract

Abstract: The eXtended Position Based Dynamics algorithm (XPBD) enables unified simulation of various materials from fluids to both elastic solids and stiff solids. In particular, finite element based neo-Hookean models can simulate near incompressible materials by means of a decoupled compliant constraint formulation. Due to XPBD's reliance on local constraint projections in the solver loop, its computational nature lends itself to parallelization by means of graph coloring algorithms used to determine partitions of independent constraints which can be solved simultaneously. However, minimal graph coloring is bounded from below by the maximum valence of the finite element mesh, thus hindering parallelization opportunities. In this paper, we propose a novel graph clustering approach on the constraint graph which groups highly dependent constraints into supernodes. By applying graph coloring on the supernodal constraint graph, we are able to significantly reduce the number of partitions, thus enhancing parallelization of the solver. Furthermore, we accelerate convergence of the neo-Hookean XPBD solver by a coupled constraint formulation, resulting in enhanced stability and efficiency compared to previous approaches. Highlights: Constraint graph clustering improves partitioning based parallelism for soft body solvers. Blocked constraint projection accelerates convergence. Order of magnitude speedup compared to baseline simulation techniques.