DOI: 10.17587/prin.8.354-358

Spheres Collision Detection Algorithms on GPU

M. V. Mikhayluk, mix@niisi.ras.ru, D. Sc., Head of Department, A. M. Trushin, Researcher, Scientific Research Institute of System Analysis Russian Academy of Sciences, Moscow, 117218, Russian Federation

Corresponding author: Mikhayluk Mikhail V., Professor, D. Sc., Head of Department, Scientific Research Institute of System Analysis Russian Academy of Sciences, Moscow, 117218, Russian Federation, E-mail: mix@niisi.ras.ru

In the paper we consider the problem of pairwise collision detection of spheres and spheres with capsules in virtual object dynamics calculation systems. Performing this task in real-time on CPU (Central Processing Unit) for hundreds of thousands pairs of spheres and capsules is impossible. The algorithms to solve these tasks on GPU (Graphics Processing Unit) are proposed here. First, the technology and features of the CUDA (Compute Untied Device Architecture) architecture and features of work are described, in particular, memory organization, data transferring from CPU to GPU and back, the implementation of conditional statements, etc. Then, the algorithms of kernels to solve raised tasks are presented. In these algorithms conditional statements are replaced with simple expressions, involving condition flags. The proposed algorithms were tested on virtual scenes with different number of spheres and capsules (from several thousand to several million), and their working time on CPU was compared with the one computed with CUDA. It was shown that the tasks are solved on the GPU 50—100 times faster, starting from 17 thousand pairs for spheres and from 8,5 thousand sphere/capsule pairs. The developed software modules are implemented in the simulator for complex dynamic systems control, developed in Scientific Research Institute for System Analysis Russian Academy of Sciences. They can be used in multibody dynamics calculation systems, virtual environment systems, virtual laboratories, etc.

Keywords: virtual objects, collision detection, sphere, capsule, GPU, CUDA, parallel computing, virtual environment systems

pp. 354–358

For citation:
Mikhayluk M. V., Trushin A. M. Spheres Collision Detection Algorithms on GPU, Programmnaya Ingeneria, 2017, vol. 8, no. 7, pp. 354—358.

This work was supported by the Russian Foundation for Basic Research, project nos. 16-37-00218-мол_а.