Algoritmos rápidos de detecção de colisão : broad phase utilizando KD-trees / Algoritmos Rápidos de Detecção de Colisão Broad Phase utilizando KD-Trees.

AUTOR(ES)

RAFAEL DE SOUSA ROCHA

DATA DE PUBLICAÇÃO

2010

RESUMO

In this work, three novel and fast broad phase collision detection algorithms, which utilize the spatial partitioning structure known as KD-Tree, were proposed and implemented: KDTreeSpace, DynamicKDTreeSpace and StatelessKDTreeSpace. These algorithms were integrated to the Open Dynamics Engine (ODE) library, which is in charge of calculating the motion of the dynamic objects, as possible alternatives to the algorithms available in this library. The algorithms of the broad phase methods in ODE were also presented and their performance were compared to the algorithms that utilize KD-Tree. The results show that the KDTreeSpace exhibit better performance than the QuadTreeSpace, which, in general, represents the best alternative among the algorithms available in ODE. Furthermore, for scenarios without well defined boundaries or with memory restrictions, the results indicate that the DynamicKDTreeSpace presents a satisfactory alternative because it is able of quickly adapting its cutting planes to the arrangement of objects in scene. Finally, the StatelessKDTreeSpace shows the best performance for scenerios with low degree of temporal coherence. Keywords: Collision Detection, Broad Phase, Spatial Partitioning Structures, KD-Tree.

ASSUNTO(S)

algoritmos - dissertaÇÕes sistemas de informacao computaÇÃo grÁfica - dissertaÇÕes estrutura de dados - dissertaÇÕes

Documentos Relacionados

• Detecção de colisão utilizando grids e octrees esféricas para ambientes gráficos interativos
• Detecção de colisão utilizando grids e octrees esféricas para ambientes gráficos interativos
• Fast IRWA algorithms for all-optical networks
• Sobre a estabilidade numerica dos algoritmos de minimos quadrados rapidos
• Algoritmos de previsão utilizando modelos de estudos : aplicações em telegrafos