Detecção de colisão usando Sweep and Prune com kDOPs em GPU

Abstract

Collision detection is an important consideration for physical simulation of rigid and deformable objects, or even fluids. For each type of simulation and object, different bounding volumes can be used in order to generalize the real object in the scene, with the goal to improve performance and to support huge quantities of objects. Due to the high cost of this procedure, many algorithms and techniques have been investigated, in addition to specific hardware such as GPUs, that tend to be more efficient for this task than CPUs. In this thesis, an alternative approach to the collision detection model based on the Sweep and Prune algorithm is investigated, where k-Discrete Oriented Polytopes (kDOPs) are used as bounding volumes instead of the more traditional axis-aligned bounding boxes, since they tend to approximate objects with irregular shapes better. Furthermore, GPUs are very amenable for implementing this approach since the algorithms have a high degree of parallelism. In order to build objects simulation with collisions, it is required to use any rigid body dynamic, whose was chosen meshless deformation based on shape matching technic. physically-based animation, collision detection, sweep-and-prune, k-dop, gpgpu, meshless deformation, shape matching.