Octree
Uma Octree (Oct + Tree ou árvore de oito) é uma árvore, onde cada nó que não seja folha possui interligação com mais outros oito nós da estrutura de dados, esta interligação se faz normalmente por meio de ponteiros. A Octree é uma técnica de modelagem bastante comum no uso de tratamento de colisões.
Descrição
editar
Basicamente definimos uma bounding box, ou caixa delimitadora onde nosso algoritmo atuará e dentro dos limites desta caixa está a primitiva ou cenário que desejamos modelar. O espaço é então dividido em oito partes iguais, e verificamos se existe intersecção desta primitiva ou cenário com cada um dos hexaedros resultantes da divisão.
Caso não ocorra intersecção deixamos o cubo resultante em branco ou vazio. se houver intersecção há duas possibilidades: caso o hexaedro esteja completamente inserido na primitiva ou cenário, pintamos o hexaedro para que seja exibido na tela; caso o hexaedro esteja parcialmente inserido na primitiva, dividimos este por sua vez em mais oito partes menores e repetimos o algoritmo até que profundidade máxima de nossa árvore seja alcançada ou a primitiva ou cenário sejam modelados por completo. Também é possível usarmos algum algoritmo de corte da árvore, de forma a torná-la menor e mais eficiente.
Quando tratamos com Octrees estamos sempre nos referindo ao espaço tridimensional, caso desejamos dividir o espaço bidimensional, como uma figura em uma plano cartersiano poderemos usar a Quadtree, onde dividimos o espaço por quatro partes iguais ao invés de oito.
Implementação
editarExemplo de algoritmo de Octree em C:
void constroi_OCT(Tesfera e, Toctree *filho, GLint profundidade){
/*montar arvore*/
Toctree *pai;
char estado;
int i;
pai=filho;
estado='B';
if (profundidade>1)
estado=classifica_esfera(e, (*pai).coordenadas, (*pai).lado);
(*pai).estado=estado;
if (estado=='('){
subdivide(pai);
for (i=0;i<8;i++)
constroi_OCT(e, (*pai).filhos[i],profundidade-1);
}
}
Representação
editarUma maneira comum de descrevermos uma Octree é através de uma representação DF (Depth First, profundidade primeiro). Por exemplo, usando B para blocos cheios (Black), W para blocos vazios (White) e ( para blocos parciais poderíamos descrever a figura apresentada no topo deste artigo através da linha:
