AABB – uma árvore para controle espacial e otimização de colisão

Vou começar alguns posts sobre “árvores de controle espacial e otimização de colisão”. Espacial nesse caso nada tem a ver com o universo, é espaço mesmo, ou seja, uma estrutura de dados que tem como objetivo organizar e otimizar os objetos espalhados em um determinado espaço.

Quando você aplica certo controle dos objetos no espaço, e essas estruturas de dados garantem isso, a implementação de diversas tecnicas de computação grafica se tornam viavies.

A primeira arvore que vou tratar é a arvore AABB (Axis Aligned Boundary Box). É uma das mais simples de implementar e que, nos meus projetinhos, já garantiram funcionalidades interessantes, como a “seleção de objetos 3D com o mouse”.

Figura 1 – Exemplo de AABB Tree – Existem caixas de volume para cada objeto, mas também caixas de volume que englobam as organizações hierárquicas de pai e filhos. Na figura, a cena tem dois filhos e um de seus filhos possui um filho também (confira a árvore de cena à esquerda)

Ela também pode ser usada para otimizar detecção de colisões. É possível refina-la em um nivel que, mesmo ela sendo alinhada ao eixo, garanta uma forma acurada de detecção de colisão

Figura 2 – É possível refinar a AABB para o mesmo objeto, aumentando assim a precisão em um possível teste de colisão. Fonte da Imagem: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/AABB_tree/Chapter_main.html

Uma árvore AABB é uma árvore de caixas de volume.  AABB é a menor caixa alinhada aos eixos x, y e z, que envolve um objeto 3D. Sua construção é trivial: percorrem-se todos os vértices de um objeto 3D a fim de encontrar suas coordenadas x, y e z máximas e mínimas, que definirão a diagonal da caixa de volume AABB.

Uma árvore AABB pode armazenar as caixas de volume de todos os objetos da cena. Contudo, como os objetos podem ser organizados de forma hierárquica, ela também é organizada de forma hierárquica, ou seja, caso um objeto possua filhos, além da caixa de volume do objeto pai, a árvore constrói uma caixa de volume que engloba tanto o objeto pai quanto seus filhos (veja a figura 1).

Utilizando-se dessa característica de caixas de volume organizadas hierarquicamente, varias aplicações podem ser otimizadas. A principal aplicação (usada para o Picking) é detecção de colisão. Para melhor compreensão, considere um objeto que tem 10 filhos e é necessário fazer um teste de colisão de um cubo com cada um deles. Sem a árvore, seria preciso testar a colisão para todos os 11 objetos. Com a árvore, primeiro a colisão com a caixa de volume que engloba o pai e seus filhos é testada e, caso o resultado seja positivo (o que significa que a intersecção com algum objeto desse volume possa ocorrer), o teste é feito para os 11 objetos dentro desse volume.

Quanto melhor a cena estiver organizada hierarquicamente, mais eficiente será o teste de colisão. Além disso, é possível refinar a árvore e criar camadas intermediárias de caixas de volume para alguns objetos e assim otimizar ainda mais os testes de colisão.

Lembre-se que, caso utilize as caixas em objetos dinâmicos, isso é, que possam ser transladados, rotacionados e escalados, é necessário atualizar a sua caixa e de todos os seus pais na árvore da cena toda vez que uma dessas operações forem efetuadas.

Picking

Figura 3 – A partir do clique do mouse na tela (que representa o plano mais próximo da câmera), um raio é lançado à cena selecionando os objetos que são intersectados por ele.

Picking é a funcionalidade de selecionar um objeto através do mouse. O usuário seleciona um objeto 3D que pertence à cena clicando em sua representação no plano de projeção 2D da tela.

Para sua implementação, é possivel utilizar a árvore de caixas de volume da cena (AABB Tree – Axis Aligned Boundary Box Tree) e sua intersecção com o raio originado pelo clique do usuário no plano da tela, ou seja, o nearPlane da câmera (veja a idéia do algoritmo na Figura 3).

Assim que o usuário clica na tela, a informação das coordenadas x e y criam, junto com a posição da câmera e seu método de projeção (paralela ou perspectiva), um raio em direção à cena. Testa-se a intersecção desse raio com os objetos da cena, e todos os objetos que o raio atingiu são retornados.

A estrutura AABB tree pode ser usada pois, caso a cena esteja organizada hierarquicamente, o processo de verificação de intersecção pode ser otimizado já que, na hipótese de o raio não atingir a caixa de volume que envolve um objeto pai e seus filhos, não é necessário testar as intersecções com seus filhos.

Os objetos podem ser retornados na ordem das intersecções. Uma boa estrategia para tratar multiplas seleções é a seguinte: Caso o raio intersecte mais de um objeto, o algoritmo retorna o primeiro que foi intersectado. Havendo nova consulta e o resultado apresentando sendo o mesmo da consulta anterior, o segundo objeto é retornado, e assim por diante, possibilitando a seleção de objetos que se encontram atrás de outros objetos.

Anúncios

Deixe um comentário

Arquivado em 3D, Computação Gráfica, Desenvolvimento, Desenvolvimento de Jogos

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s