Detecção de colisão em ambientes bidimensionais e tridimensionais utilizando estruturas de dados hierárquicas Quadtrees e Octrees

Abstract

A detecção de colisão entre objetos e outros eventos situados no espaço é uma grande problemática nas áreas da simulação, uma vez que o custo computacional cresce de maneira proporcional à complexidade computacional envolvida. Portanto, a escolha da técnica utilizada para realizar estas tarefas se torna importante, tanto em questão de qualidade quanto de desempenho. Entretanto, é possível encontrar este equilíbrio entre robustez e eficiência com a utilização de quadtrees e octrees. Estas estruturas de dados hierárquicas, combinam desempenho e qualidade e podem atender à diversas necessidades, tornando-se uma solução flexível e ao mesmo tempo eficiente para a indexação de eventos no espaço. De modo a evidenciar a eficiência destas estruturas de dados, este trabalho aborda um estudo comparativo realizado entre as mesmas e o modo convencional de detecção de eventos no espaço com foco na detecção de colisão e em uma análise quantitativa dos resultados obtidos.