The Red-Black Physics Engine: A Parallel Framework for Interactive Soft Body Dynamics

Abstract

The simulation of soft bodies has been an ongoing research problem for over 30 years. The desiderata for real-time applications are believable results, while maintaining interactivity. The most popular approach to achieve this has been to use iterative methods, that find an approximate solution to the underlying equation system rapidly. In recent years, efforts have been made to improve the performance of these methods by exploiting the computational capabilities of modern hardware architectures, such as the graphics processing unit. This thesis introduces a parallel iterative solver that utilizes a Red-Black Gauss- Seidel technique. The solver is implemented within the Projective Dynamics framework, using a quadrangular network of particles and constraints, to simulate soft bodies in real-time. The results show that in this particular case, the Red-Black Gauss-Seidel method outperforms other traditional iterative solvers in terms of convergence speed. The results were achieved by creating a physics engine prototype, using a Verlet numerical integration scheme, parallel collision handling and three different types of iterative solvers; sequential Gauss-Seidel, parallel Jacobi and parallel Red-Black Gauss-Seidel. These solvers were then compared to each other. The physics engine as a whole was also compared to other contributions in the field. The quadrangular structure of the soft bodies resulted in real-time performance, at the cost of a moderate loss in precision.