Hierarchical Parallelization of Rigid Body Simulation with Soft Blocking Method on GPU

This paper proposes and implements a method to efficiently parallelize constraint solving in rigid body simulation using GPUs. Rigid body simulation is widely used in robot development, computer games, movies, and other fields, and there is a growing need for faster computation. As current computers are reaching their limits in terms of scale-up, such as clock frequency improvements, performance improvements are being sought through scale-out, which increases parallelism. However, rigid body simulation is difficult to parallelize efficiently due to its characteristics. This is because, unlike fluid or molecular physics simulations, where each particle or lattice can be independently extracted and processed, rigid bodies can interact with a large number of distant objects depending on the instance. This characteristic causes significant load imbalance, making it difficult to evenly distribute computational resources using simple methods such as spatial partitioning. Therefore, this paper proposes and implements a computational method that enables high-speed computation of large-scale scenes by hierarchically clustering rigid bodies based on their number and associating the hierarchy with the hardware structure of GPUs. In addition, to effectively utilize parallel computing resources, we considered a more relaxed parallelization condition for the conventional Gauss–Seidel block parallelization method and demonstrated that convergence is guaranteed. We investigated how speed and convergence performance change depending on how much computational cost is allocated to each hierarchy and discussed the desirable parameter settings. By conducting experiments comparing our method with several widely used software packages, we demonstrated that our approach enables calculations at speeds previously unattainable with existing techniques, while leveraging GPU computational resources to handle multiple rigid bodies simultaneously without significantly compromising accuracy.