Visibility-Based Fast Collision Detection of a Large Number of Moving Objects on GPU

Abstract

This paper proposes a simple and efficient collision detection algorithm for a large number of moving objects. The basic idea is to minimise the number of moving objects that go through the complicated the collision checking process, which can improve the overall performance. To this end, we propose a visibility-based culling technique that identifies substantially small or hidden objects that do not cause any visual artifact even if we ignore them. This paper also develops a variable-size Morton codes to speed up the construction time of the Linear Bounding Volume Hierarchy (LBVH), which is used to efficiently check the proximity between objects efficiently. The visibility-based culling technique is based on the so called visibility map on the top of the g-Buffer technique. This map is a texture that contains the ID of the moving object in the screen space. The number of fragments of each object on the map is then counted in parallel manner on the GPU. If the number of fragments is less than a predefined threshold value, the algorithm does not include the object in the LBVH constructions step. Although the performance depends on the camera view point, we have verified through several experiments that the proposed algorithm improves the overall performance at least 70% even when the number of moving objects is more than 10,000.

Keywords

• Collision detection
• linear bounding volume hierarchy
• visibility