Detecção de Colisão Usando Sweep and Prune com K-Dops em GPU
Autores
7074 |
3126,455
|
|
7075 |
3126,455
|
Informações:
Publicações do PESC
No ambiente computacional, a detecção de colisão consiste em verificar se dois objetos ocupam o mesmo lugar no espaço virtual, sejam em ambientes bidimensionais ou tridimensionais, portanto, é tema imprescindível em simulações de objetos rígidos, deformáveis e dinâmica de fluidos. Para as simulações que requerem tempo real, normalmente, são utilizados volumes envolventes para aproximação do real objeto em cena, com objetivo de aumentar consideravelmente o desempenho, assim suportando centenas de objetos ou maiores taxas de quadros por segundo. Devido ao alto custo computacional desses algoritmos e técnicas de aceleração, estes são temas de interesse, assim como o uso de hardware especializado, como, por exemplo, GPU, para tratar do problema com eficiência superior às unidades centrais de processamento (CPUs).
São apresentados nesta dissertação experimentos acerca do modelo de detecção de colisão através do algoritmo Sweep and Prune, visto que estudos recentes comprovaram a efetividade desse algoritmo. Nosso estudo adota os k-Politopos Discretos Orientados (k-DOPs) ao invés de caixas alinhadas com os eixos (AABBs) ou esferas como volumes envolventes, já que os k-DOPs melhor aproximam geometricamente objetos com formas irregulares, podendo ser mais efetivos na eliminação dos pares que não se encontram em colisão.
Além da utilização de GPU, com objetivo de extrair melhor performance do paralelismo ofertado por esse hardware.
Para realizar a simulação dos objetos com resposta às colisões, faz-se necessário aplicar a dinâmica de corpos rígidos, a qual é implementada neste trabalho através da técnica de casamento de formas.
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 (k-DOPs) 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 technique.