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.

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.

Exemplo 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);
 }
}

Uma 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:

• «The Octree» 
• «Octree C++ Class Template» 
• «Octree Textures on the GPU» 

Este artigo sobre computação gráfica é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e