Vivace: a Practical Gauss-Seidel Method for Stable Soft Body Dynamics

摘要

The solution of large sparse systems of linear constraints is at thernbase of most interactive solvers for physically-based animation ofrnsoft body dynamics. We focus on applications with hard and tightrnper-frame resource budgets, such as video games, where the solutionrnof soft body dynamics needs to be computed in a few milliseconds.rnLinear iterative methods are preferred in these cases sincernthey provide approximate solutions within a given error tolerancernand in a short amount of time. We present a parallel randomizedrnGauss-Seidel method which can be effectively employed tornenable the animation of 3D soft objects discretized as large and irregularrntriangular or tetrahedral meshes. At the beginning of eachrnframe, we partition the set of equations governing the system usingrna randomized graph coloring algorithm. The unknowns in thernequations belonging to the same partition are independent of eachrnother. Then, all the equations belonging to the same partition arernsolved at the same time in parallel. Our algorithm runs completelyrnon the GPU and can support changes in the constraints topology.rnWe tested our method as a solver for soft body dynamics within thernProjective Dynamics and Position Based Dynamics frameworks.rnWe show how the algorithmic simplicity of this iterative strategyrnenables great numerical stability and fast convergence speed, whichrnare essential features for physically based animations with fixed andrnsmall hard time budgets. Compared to the state of the art, we foundrnour method to be faster and scale better while providing stabler solutionsrnfor very small time budgets.