{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T15:20:56Z","timestamp":1762183256723,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T00:00:00Z","timestamp":1762041600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>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\u2013Seidel 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.<\/jats:p>","DOI":"10.3390\/computation13110250","type":"journal-article","created":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T13:55:22Z","timestamp":1762178122000},"page":"250","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hierarchical Parallelization of Rigid Body Simulation with Soft Blocking Method on GPU"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3470-2179","authenticated-orcid":false,"given":"Rikuya","family":"Tomii","sequence":"first","affiliation":[{"name":"Department of Information and Network Engineering, The University of Electro-Communications, Tokyo 1828585, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3907-0708","authenticated-orcid":false,"given":"Tetsu","family":"Narumi","sequence":"additional","affiliation":[{"name":"Department of Information and Network Engineering, The University of Electro-Communications, Tokyo 1828585, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2025,11,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0148-9062(88)92293-0","article-title":"Formulation of a three-dimensional distinct element model-Part I. A scheme to detect and represent contacts in a system composed of many polyhedral blocks","volume":"25","author":"Cundall","year":"1988","journal-title":"Int. J. Rock Mech. Min. Sci. Geomech. Abstr."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Mirtich, B., and Canny, J. (1995, January 9\u201312). Impulse-based simulation of rigid bodies. Proceedings of the 1995 Symposium on Interactive 3D Graphics (I3D \u201995), Monterey, CA, USA.","DOI":"10.1145\/199404.199436"},{"key":"ref_3","unstructured":"Baraff, D. (1993). Non-penetrating rigid body simulation. State of the Art Reports, Eurographics Association."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0045-7825(97)00137-0","article-title":"A Gauss-Seidel like algorithm to solve frictional contact problems","volume":"155","author":"Jourdan","year":"1998","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1023\/A:1008292328909","article-title":"Formulating Dynamic Multi-Rigid-Body Contact Problems with Friction as Solvable Linear Complementarity Problems","volume":"14","author":"Anitescu","year":"1997","journal-title":"Nonlinear Dyn."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Sauer, J., and Sch\u00f6mer, E. (1998, January 2\u20135). A constraint-based approach to rigid body dynamics for virtual reality applications. Proceedings of the ACM Symposium on Virtual Reality Software and Technology (VRST \u201998), Taipei, Taiwan.","DOI":"10.1145\/293701.293721"},{"key":"ref_7","unstructured":"NVidia (2025, August 02). NVidia PhysX System Software. Available online: https:\/\/www.nvidia.com\/ja-jp\/drivers\/physx\/physx-9-19-0218-driver\/."},{"key":"ref_8","unstructured":"Coumans, E., and Bai, Y. (2025, August 02). Pybullet, a Python Module for Physics Simulation for Games, Robotics and Machine Learning. Available online: http:\/\/pybullet.org\/."},{"key":"ref_9","unstructured":"Smith, R. (2025, August 02). Open Dynamics Engine. Available online: https:\/\/ode.org\/ode-latest-userguide.pdf."},{"key":"ref_10","unstructured":"Freeman, C.D., Frey, E., Raichuk, A., Girgin, S., Mordatch, I., and Bachem, O. (2021). Brax\u2014A Differentiable Physics Engine for Large Scale Rigid Body Simulation. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Iglberger, K., and R\u00fcde, U. (2009, January 25\u201328). A Parallel Rigid Body Dynamics Algorithm. Proceedings of the 15th International Euro-Par Conference on Parallel Processing (Euro-Par \u201909), Delft, The Netherlands.","DOI":"10.1007\/978-3-642-03869-3_71"},{"key":"ref_12","unstructured":"Sundberg, J. (2014). Parallel Projected Gauss-Seidel Solver for Large-Scale Granular Matter: Examining the Physics of the Parallel Solver and Development of a Multigrid Solver. [Master\u2019s Thesis, Ume\u00e5 University, Department of Physics]."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1452","DOI":"10.1109\/TPDS.2021.3052091","article-title":"A Parallel Jacobi-Embedded Gauss-Seidel Method","volume":"32","author":"Ahmadi","year":"2021","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_14","first-page":"99","article-title":"Hierarchical Domain Decomposition Method for Devices including Moving Bodies","volume":"4","author":"Sugimoto","year":"2018","journal-title":"J. Adv. Simul. Sci. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Jia, P.H., Hu, J., Chen, Y., and Liu, Q.H. (2019, January 20\u201322). Hierarchical Domain Decomposition Method for the Analysis of Multiscale Composite Structures. Proceedings of the 2019 IEEE International Conference on Computational Electromagnetics (ICCEM), Shanghai, China.","DOI":"10.1109\/COMPEM.2019.8779157"},{"key":"ref_16","unstructured":"Daviet, G. (2023, January 6\u201310). Interactive Hair Simulation on the GPU using ADMM. Proceedings of the ACM SIGGRAPH 2023 Conference Proceedings (SIGGRAPH \u201923), Los Angeles, CA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3731183","article-title":"JGS2: Near Second-order Converging Jacobi\/Gauss-Seidel for GPU Elastodynamics","volume":"44","author":"Lan","year":"2025","journal-title":"ACM Trans. Graph."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0021-9991(82)90061-4","article-title":"Application of multigrid methods for integral equations to two problems from fluid dynamics","volume":"48","author":"Schippers","year":"1982","journal-title":"J. Comput. Phys."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Xu, J., and Zikatanov, L.T. (2016). Algebraic Multigrid Methods. arXiv.","DOI":"10.1017\/S0962492917000083"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2021","DOI":"10.1007\/s00366-025-02144-w","article-title":"Hierarchical matrices for 3D Helmholtz problems in the multi-patch IgA-BEM setting","volume":"41","author":"Desiderio","year":"2025","journal-title":"Eng. Comput."},{"key":"ref_21","first-page":"13","article-title":"An LCP-approach for multibody systems with planar friction","volume":"92","author":"Glocker","year":"1992","journal-title":"Proc. CMIS"},{"key":"ref_22","unstructured":"Richard, P., and Braz, J. (2010, January 17\u201321). Interactive Rigid Body Dynamics Using a Projected Gauss\u2013Seidel Subspace Minimization Method. Proceedings of the Computer Vision, Imaging and Computer Graphics. Theory and Applications, Angers, France."},{"key":"ref_23","unstructured":"Poulsen, M.L., Niebe, S., and Erleben, K. (2010, January 1\u20134). Heuristic Convergence Rate Improvements of the Projected Gauss\u2013Seidel Method for Frictional Contact Problems. Proceedings of the 18th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision in Co-Operation with EUROGRAPHICS, Pilsen, Czech Republic."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1023\/A:1017501703105","article-title":"Convergence of a block coordinate descent method for nondifferentiable minimization","volume":"109","author":"Tseng","year":"2001","journal-title":"J. Optim. Theory Appl."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Koester, D., Ranka, S., and Fox, G. (1994, January 14\u201318). A parallel Gauss-Seidel algorithm for sparse power system matrices. Proceedings of the 1994 ACM\/IEEE Conference on Supercomputing, Washington, DC, USA.","DOI":"10.1145\/602805.602806"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"012030","DOI":"10.1088\/1742-6596\/1232\/1\/012030","article-title":"Vertices Coloring Technique Using Graph Methods For Determining Minimal Map Colors","volume":"1232","author":"Azizah","year":"2019","journal-title":"J. Phys. Conf. Ser."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/11\/250\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T14:27:29Z","timestamp":1762180049000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/11\/250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,2]]},"references-count":26,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2025,11]]}},"alternative-id":["computation13110250"],"URL":"https:\/\/doi.org\/10.3390\/computation13110250","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2025,11,2]]}}}