Binary Space Partitioning (BSP) Trees

Já tem algum tempo que tenho um projeto pessoal de criar um framework para animação 3D em realtime. Eu poderia usar biblitecas como Ogre3D, G3D, Crystal Space, Irriltch, Unity, Unreal Engine ou diversas outras que existem por ai. Aqueles que me conhecem sabem que gosto de fazer as coisas do modo mais difícil possível. Então, o que faço eu?! Tento criar o meu próprio framework…

Chegou a hora de realmente pensar e entender como dividir o trabalho do framework, isto é, quebrar o espaço em partições, em pedaços menores, ordenados. Existem algumas maneiras de fazer isso, mas uma das mais performáticas e, acreditem em mim, mais simples, é usando uma técnica chamada Particionamento Espacial Binário. Quer dizer, usando as hoje famosas árvores BSPs.

Imaginem um mapa simples como esse:

Visto de cima, um quarto sem janelas e sem portas com uma parede no meio.

Dependendo da posição da câmera, algumas das paredes não precisarão ser desenhadas. Para facilitar o trabalho dos testes de qual parede precisará ou não ser desenhada, quebramos (partcicionamos) o espaço do quarto em 2, usando a parede g como divisora.

De posse do polígono da parede g, calculamos o plano divisor (s) e montamos uma árvore binária (dai o B de BSP) onde o nó raiz é o plano e os nós filhos (as “folhas”) contém uma lista dos polígonos que pertencem ao lado da frente do plano s, colocando-a no nó-filho direito; e pegamos também os polígonos que estão atrás do plano s e os colocamos numa lista, no nó-filho esquerdo:

Note a diferença de formato no diagrama, entre um nó e uma "folha".

No que isso nos ajuda?

Quando formos desenhar a cena precisamos determinar em que “folha” estamos. Isso é bem rápido… Se a distância da camera ao plano raiz for maior que zero, estamos na frente do plano, senão estamos atrás. Sabendo disso, podemos tomar algumas decisões:

  • Se a direção da câmera é a mesma do plano, não precisamos nos preocupar com o que está atrás do plano… Dai o teste com o frustum só é feito com os polígonos onde estamos (e seus filhos, se houverem);
  • Caso contrário, temos como determinar a ordem em que os testes serão feitos para as outras partições somente percorrendo a árvore!

É isso… se a direção da sua câmera aponta para o plano divisor, continuo tendo que testar outro polígonos baseado em seus vetores normais, só que posso, de antemão, fazer isso de forma ordenada. Tomemos como exemplo uma câmera localizada na frente do plano ‘s’ a apontando para ele. Percorrendo a árvore constatamos que estaremos na “folha” da direita (direita, na árvore, significa “na frente do plano”).  Testamos os polígonos a, b, g e f. Podemos ter a situação em que apenas o polígono g esteja visível… Colocamos ele na lista de polígonos a serem desenhados. Agora, percorremos a árvore (indo para o nó raiz) e, já que esse nó não é uma “folha”, vamos para a esquerda. Já que estamos numa “folha”, verificamos os polígonos c, d e e para determinarmos se são visíveis ou não. Podemos determinar que não são e não colocamos ninguém na lista.

Uma vez que a árvore inteira foi percorrida, temos a lista de polígonos a desenhar (apenas o polígono ‘g’, neste exemplo).

Eu disse “pode ser que” alguns polígonos não sejam visíveis, por que isso é determinado pelo frustum da câmera, ok? Agora dêem uma olhada na primeira figura de novo… notem a parte pontilhada que demarca o plano divisor s… Em cima dele temos o polígono g que, arbitrariamente, eu considerei como “na frente” do plano s (pode ser melhor colocar o polígono no mesmo nó do plano, já que a camera pode estar do outro lado. Só que um polígono tem um lado bem definido, assim, se o polígono g tem seu vetor normal no mesmo sentido do plano s, faz sentido colocá-lo na “folha da frente” do plano, não é?). Mas, notem também os lados do polígono (em cima da reta pontilhada)… Esses “falsos” polígonos (as áreas vazias) poderiam ser polígonos de verdade, porém invisíveis, que seriam usados apenas para terminar se o lado de trás do plano s deveria ser considerado ou não… Esses são portais.

Se portais associados ao plano s fossem selecionados para serem desenhados, então consideraríamos analisar o outro lado do plano s. Poupando tempo de processamento precioso ao não ter que percorrer toda a árvore. No exemplo acima, se a análise da “folha” onde estamos não selecionar nenhum portal, paramos por ai! Embora os portais tenham lado que nem os polígonos “normais”, esse “lado” não tem muito sentido (já que são invisíveis de ambos os lados!). Eles sõ existirão para decidirmos se o outro lado do plano s deve ser considerado ou não…

Acho que, talvez, criar um algoritmo assim seja mais performático do que minha suposição anterior (criar sub-frustums para os portais – veja aqui)… veremos…

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. 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 )

Foto do Google+

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

Conectando a %s