Relações Espaciais, Temporais e de Ordem para Detecção de Colisão Broad Phase Genérica e Escalável

Abstract

Simulações físicas são fundamentais para a representação computacional de situações do mundo real. Neste contexto, a detecção de colisões entre objetos 3D é crucial, uma vez que provê a ilusão de que estes são sólidos, porém, não há uma solução simultaneamente capaz de eficientemente atuar genericamente e escalar de maneira competitiva. Este trabalho apresenta e valida uma nova solução otimizada para a detecção de colisão broad phase que preenche esta lacuna, a qual é baseada em uma associação entre a KD-Tree e as técnicas Sweep-and-Prune e incremental. A solução obteve resultados duas a três vezes melhores que as demais soluções do estado-da-arte, sendo robusta a variações de comportamento, tamanho e distribuição dos objetos. Além disso, mostrou-se capaz de atuar eficientemente em todos os cenários testados e escalar em ambientes com até um milhão de objetos.