Scalable Partitioning for Parallel Position Based Dynamics

Figure 1: Interactive animation of deformable bodies, modeled using Position Based Dynamics [MHHR07] and composed of hundreds of thousands of constraints. We alter the constraints ’ topology for reducing the number of GPU kernel calls required for the computation, leading to significant speed-ups with negligible visual effects on the actual motion. Color key: Red, our approach. Green, parallel Gauss-Seidel. Blue, averaged Jacobi. We introduce a practical partitioning technique designed for parallelizing Position Based Dynamics, and exploit-ing the ubiquitous multi-core processors present in current commodity GPUs. The input is a set of particles whose dynamics is influenced by spatial constraints. In the initialization phase, we build a graph in which each node corresponds to a constraint and two constraints are connected by an edge if they influence at least one com-mon particle. We introduce a novel greedy algorithm for inserting additional constraints (phantoms) in the graph such that the resulting topology is q̂-colourable, where q ̂ ≥ 2 is an arbitrary number. We color the graph, and the constraints with the same color are assigned to the same partition. Then, the set of constraints belonging to each partition is solved in parallel during the animation phase. We demonstrate this by using our partitioning technique; the performance hit caused by the GPU kernel calls is significantly decreased, leaving unaffected the visual quality, robustness and speed of serial position based dynamics