Implementação Colisão

...

Detecção de colisão é um requisito fundamental para que uma aplicação da computação gráfica possa simular o mundo real com maior fidelidade. Precisão e desempenho são características cruciais para um algoritmo eficiente de detecção de colisão.

Se tratando de um dos componentes mais importantes e dependentes das informações de interação monitoradas em um ambiente virtual, a detecção de colisão permite responder às interações entre objetos no mundo virtual.

Detectar uma colisão é verificar a aproximação entre objetos, sendo que essa aproximação deve ser suficientemente pequena a ponto de possibilitar a ocorrência de uma sobreposição entre objetos, fornecendo, assim, um maior realismo às aplicações. Para que essa percepção ocorra são necessários pelo menos dois objetos, em que pelo menos um deles deve estar em movimento. Trata-se de um problema complexo, visto que objetos virtuais podem ter formas, tamanhos e movimentos variados, dependendo de suas naturezas e da finalidade da aplicação. Para uma colisão, os objetos em cena podem ser rígidos ou deformáveis.

A seguir um conjunto de abordagens relacionadas à detecção de objetos rígidos e deformáveis será mostrado como possibilidades para detecção de colisão.

3.1. Volumes Limitantes

A detecção de colisão por volumes limitantes são algoritmos que utilizam primitivas simples para delimitação do espaço de colisão do objeto, tais como esferas, caixas alinhadas aos eixos AABB[2] e caixa orientada OBB[3]. A principal ideia desse tipo de abordagem é verificar os pontos mais afastados do objeto e inserir nesse espaço a primitiva.

3.2. Subdivisão Hierárquica do Espaço

Na subdivisão hierárquica do espaço, o ambiente é subdividido em um espaço hierárquico. Objetos no ambiente são agrupados de acordo com a região em que se encontram. Quando um objeto no ambiente se movimenta e troca de posição, movendo-se para uma outra região do espaço, apenas os objetos do novo espaço precisam ser verificados se colidem ou não com o objeto em movimento. Há várias formas de subdividir o AV utilizando alguns métodos conhecidos tais como octree, K-d trees e BSP trees, descritos a seguir.

Octrees: São estruturas de árvores hierárquicas em que cada nó interno possui até oito filhos e é organizada para que cada nó corresponda a uma região do espaço tridimensional. O esquema de codificação divide regiões de espaços tridimensionais, normalmente cubos, em octantes e guarda elementos em cada nó da árvore. Cada nó da octree armazena um ponto tridimensional, que é o centro do octante que foi dividido. O ponto define um dos cantos para cada um dos oito filhos. O ponto de subdivisão é implicitamente o ponto central do espaço que o nó representa.

K-d trees: Árvores k-dimensionais, em que k é o número de dimensões, são estruturas de árvores multidimensionais balanceadas para partição do espaço. Essas árvores são estruturas de dados úteis em várias aplicações, tais como as buscas que envolvem chaves multidimensionais (busca em escala e busca do vizinho mais próximo). Uma k-d tree utiliza apenas planos de divisão que são perpendiculares a um dos eixos de coordenadas do sistema. Como consequência, cada plano de divisão deve atravessar um dos outros pontos da árvore [2].

BSP trees: Representa uma divisão recursiva hierárquica ou a subdivisão de um espaço n-dimensional em subespaços convexos. A construção da BSPtree é um processo que considera um subespaço e o particiona por qualquer hiperplano que intersecta o interior do subespaço. Como resultado, dois novos espaços são criados que podem ser novamente particionados por um método recursivo.

3.3 Subdivisões Hierárquicas do Objeto

Nesta abordagem, o objeto é subdividido em regiões, e a detecção de colisão é feita quando uma dessas regiões é interceptada por outro objeto. Uma forma de se implementar a subdivisão hierárquica do objeto é utilizar o método de árvores de volume limite (AVL), onde cada nó n corresponde a um subconjunto Cn pertencente a C, com o nó raiz sendo associado a um volume limite com o total do conjunto C. Cada nó interno possui dois ou mais filhos. O número máximo de filhos para cada nó interno é chamado de grau da árvore. A união desses subconjuntos associados com o filho do conjunto n é igual a Cn. Cada nó é associado também a um volume limite V(C), que é uma aproximação do espaço ocupado por Cn, usando formas mínimas de representação como caixas e esferas. Os métodos mais conhecidos e que utilizam AVL serão mostrados a seguir:

Spheres-trees: O objeto é envolvido por uma esfera e, recursivamente, há uma união sucessiva de mais esferas fazendo com que estas se aproximem ao máximo da resolução do objeto. O método de sphere-trees é um dos mais simples, sendo esse um motivo por ter-se tornado muito popular em aplicações de RV. Considerando que as esferas são invariantes quanto à rotação, então, para um objeto rígido a hierarquia é construída por um pré-processamento e as transformações da hierarquia são as mesmas transformações lineares aplicadas ao objeto.

AABB-trees: Similarmente à sphere-trees, o objeto é envolvido por uma caixa e, recursivamente, outras caixas são inseridas até que esses cubos cheguem bem próximos aos limites reais do objeto.

OBB-trees:Variação do método AABB-trees, em que a caixa inserida é orientada ao eixo do objeto, tal que a área de colisão segue as direções do objeto.

Para os algoritmos descritos acima são conhecidos outras variações, porém estas são baseadas nos métodos fundamentais para detecção de colisão já apresentados.

3.4 Computação Incremental da Distância

A distância mínima é verificada de modo incremental entre um par de objetos, assim, quando essa distância for tão pequena a ponto de que os objetos possam se colidir, há uma notificação sobre a detecção da colisão, ou seja, a cada iteração do ambiente é é necessário uma verificação da distância entre os objetos. Existem vários métodos propostos para a computação incremental da distância, assim como para a computação hierárquica da distância para corpos convexos em movimento e para detecção de colisão entre polígonos.

3.5 Objetos Rígidos e Deformáveis

Algoritmos de detecção de colisão podem ser classificados em duas categorias, para objetos rígidos e para objetos deformáveis. A grande