Algoritmos para Detecção de Colisões em Ambientes Gráficos Bidimensionais Rodrigo R. Ferreira1, Rafael R. Ferreira1 rodrigorf33@hotmail.com, rafaelrferreira@gmail.com
Um ambiente gráfico dinâmico, seja um jogo ou um simulador virtual, necessita transcrever da forma mais realista possível às características físicas do mundo real permitindo um maior envolvimento do usuário com a aplicação. Uma das principais características que deve ser levada em consideração é a impenetrabilidade, isto é, a propriedade da matéria que consiste na impossibilidade de dois corpos ocuparem no mesmo tempo o mesmo lugar no espaço. Partindo dessa premissa, se dois corpos colidirem em um cenário virtual, suas velocidades, direções e formas podem se modificar. No entanto, esta tarefa não é trivial e tem se caracterizado muitas vezes como um gargalo no desempenho em aplicações que simulam ambientes gráficos interativos, isso porque o custo computacional pode ser alto. Um dos maiores problemas no tratamento de colisões é o de realizar o mínimo de cálculos possíveis, melhorando conseqüentemente o tempo de resposta e sem perder a precisão. O primeiro item deste artigo traz a presente introdução, o segundo item apresenta uma fundamentação sobre tratamento de colisões, o terceiro item aborda técnicas de envoltórios geométricos, o quarto item apresenta técnicas de decomposição espacial, o quinto item discute sobre testes realizados com uma Quadtree. As quadtrees são estruturas de dados que utilizam o conceito de árvore em programação para otimização computacional onde cada nó da árvore possui até quatro filhos. Uma quadtree divide um cenário em quatro partes de tamanhos iguais, e divide essas partes em outras quatro partes, e assim sucessivamente até que alcance um determinado tamanho e pare de dividir. A estrutura da árvore é montada a partir da cena principal, sendo esta o nó raiz (root node), e cada uma das subdivisões serão filhas de suas divisões superiores. As partes que não sofrerem divisões serão as folhas.
Com base nos resultados obtidos com os testes de desempenho de CPU, quadros por segundo (fps) e número de testes de colisão, fica claro que o algoritmo da quadtree reduz expressivamente o número de cálculos que precisam ser realizados entre pares de objetos na cena, se comparado com a quantidade de testes que é realizado pelo algoritmo de força-bruta. Contudo, à medida que o número de subdivisões do cenário aumenta, apesar da redução do número de testes de colisão, a demanda computacional exigida para manter a estrutura da árvore torna-se um problema grave. Portanto a quadtree deve ser utilizada baseada no contexto em que se aplica, se a colisão entre dois corpos desencadear muitos eventos o uso da quadtree é uma boa idéia, e o algoritmo deve ser configurado de forma a obter o menor número de cálculos sem que isso comprometa a execução do sistema. O artigo é muito grande para ser colocado aqui, portanto, fiz o upload do artigo e do código da aplicação que foi desenvolvida para testar a colisão de objetos em um cenário utilizando a quadtree.
Qualquer dúvidas me mandem um e-mail: rodrigorf33@hotmail.com.
Abraços
|