← ArchivePaper2016
Vivace: A Practical Gauss-Seidel Method for Stable Soft Body Dynamics
Parallel randomized Gauss-Seidel via graph coloring for PBD and Projective Dynamics constraints, achieving millisecond per-frame cloth and soft-body solve on GPU.
Abstract
The solution of large sparse systems of linear constraints is at the base of most interactive solvers for physically-based animation of soft body dynamics. We focus on applications with hard and tight per-frame resource budgets, such as video games, where the solution of soft body dynamics needs to be computed in a few milliseconds. Linear iterative methods are preferred in these cases since they provide approximate solutions within a given error tolerance and in a short amount of time. We present a parallel randomized Gauss-Seidel method which can be effectively employed to enable the animation of 3D soft objects discretized as large and irregular triangular or tetrahedral meshes. At the beginning of each frame, we partition the set of equations governing the system using a randomized graph coloring algorithm. The unknowns in the equations belonging to the same partition are independent of each other. Then, all the equations belonging to the same partition are solved at the same time in parallel. Our algorithm runs completely on the GPU and can support changes in the constraints topology. We tested our method as a solver for soft body dynamics within the Projective Dynamics and Position Based Dynamics frameworks.
How to read this
- Category
- Method: a parallel GPU solver for soft-body dynamics constraints
- Contributions
- A parallel randomized Gauss-Seidel method for large sparse constraint systems in soft-body animation under tight per-frame budgets
- Per-frame partitioning of equations via a randomized graph-coloring algorithm so equations within a partition are independent and solvable in parallel
- A fully GPU-resident implementation that supports changes in constraint topology, used within Projective Dynamics and Position-Based solvers
- Context
- Builds on fast constraint-based simulation, in particular Projective Dynamics (Bouaziz et al.), accelerating its linear solve with a colored parallel Gauss-Seidel scheme.Builds on: Projective Dynamics: Fusing Constraint Projections for Fast Simulation
- Correctness
- Targeted at millisecond budgets (for example games) and validated on triangular and tetrahedral meshes; it is an iterative approximate solver within a tolerance, so accuracy trades against iteration count and coloring quality affects parallel efficiency.
- Clarity
- Approach is accessible if you know PBD/Projective Dynamics; a first pass conveys the coloring-then-parallel-solve idea, with convergence details in later passes.
- How to read it
- First pass for the graph-coloring partitioning and the GPU Gauss-Seidel scheme; second pass on convergence behavior and topology-change handling if you plan to implement or benchmark it.
Built upon by
Nothing yet.
Related work
- Clean Cloth Inputs: Removing Character Self-Intersections with Volume Simulation 2018 / SIGGRAPH
- Wrinkle Meshes 2010 / SCA
- GPU-Based Simulation of Cloth Wrinkles at Submillimeter Levels 2021 / SIGGRAPH
- Nonlinear Cloth Simulation with Isogeometric Analysis 2024 / CASA
Keywords
This page summarises the entry and links to its original source. The archive never hosts or redistributes the publication itself.Show it in the full archive list →