Patent Document ID: 20180174346
Application ID: 15387039
Patent Flag: 0

Claim One:
1. A method for interactive, real-time animation of soft body dynamics, comprising the steps of: providing a 3D model of a soft body, said model comprising a set of vertices connected by edges; providing a first iteration of the animation; defining a set of physical constraints between vertices in the 3D model, said set of constraints forming a system of linear equations, Yq=b, where q is a set of unknowns representing positions of the vertices, Y is a sparse matrix, and b is an energy function comprising effects of external forces; solving said system of linear equations by: applying a Brooks-Vizing node coloring algorithm to an undirected graph corresponding to the matrix Y, thereby partitioning the system of linear equations into a set of partitions each including an independent subset of unknowns, for each partition, applying a Gauss-Seidel based solver in parallel, thereby solving the system of linear equations to determine an approximation of the unknowns; using the determined approximation of the unknowns to update the 3D model; and providing a next iteration of the animation.