Octree

Exemplo de Octree

Uma Octree(Oct + Tree ou árvore de oito) é uma árvore, aonde cada nó que não seja folha possui interligação com mais outros oitos 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.

Índice

[editar] Descrição

Uma esfera modelada com profundidade 7

Basicamente definimos uma bounding box, ou caixa delimitante aonde 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, divimos 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, aonde dividimos o espaço por quatro partes iguais ao invés de oito.

[editar] Implementação

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

[editar] Representação

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 poderiamos descrever a figura apresentada no topo deste artigo através da linha:

(BWWBBW(BWWBBBWWW