Ambientes gráficos – Não é tão simples como você pensa!

Um leitor amigo me pediu para falar um cadinho sobre ambientes gráficos. Infelizmente o assunto é tão extenso que é meio difícil cobrir aqui. Pretendo mostrar, superficialmente, uma técnica usada ma maioria das GUIs…

Já reparou como suas janelas são desenhadas na tela? Observe isso:

01-2-windows

Para os propósitos deste texto, esqueça os efeitos especiais como a sombra projetada da janela do terminal sobre a janela do browser e de ambas as janelas sobre o desktop.

A janela do browser, embaixo da do terminal, é parcialmente desenhada. O pedaço onde o terminal está não pode aparecer para o usuário (a não ser que você seja um daqueles que goste de usar terminais “transparentes”). No caso de janelas com conteúdos estáticos isso pode parecer bem simples de fazer. Mas, e quanto a vídeos?

Nada de dstrações com a beleza da moça!
Nada de distrações com a beleza da moça!

Vídeos são apenas sequências de imagens desenhadas em intervalos regulares para causar a sensação de movimento. No caso do vídeo da moça acima (linda, não?), o mesmo pedaço da janela, à esquerda, não é tocado pelas imagens que compõem o vídeo… Como isso é feito?

A GUI divide a janela sobreposta em “sub janelas” ou regiões. Ele faz isso porque só sabe manipular áreas retangulares e, então, a divisão em regiões da janela do vídeo fica assim:

grab3-2-regions

No exemplo acima usei as cores verde e azul para exemplificar a divisão da janela em regiões… Todos os pixels que não estão nessas áreas simplesmente não são desenhados. Mas, como fica quando temos várias janelas sobrepostas? A GUI monta uma lista de regiões retangulares, por exemplo:

03-3-regions

Aqui temos 3 “regiões” (verde, azul e vermelha).

Obviamente que quanto mais janelas na tela, mais complexa tende a ficar. Especialmente se algum efeito especial é usado (sombras e janelas não retangulares, por exemplo). Sem contar que, às vezes, teremos que lidar com casos onde a janela é subdividida em diversas regiões de apenas 1 pixel…

Hoje em dia é mais provável que as GUIs usem stencil buffers para mascarar os bits que não serão plotados. No caso do Linux, por exemplo, os ambientes X11 modernos costumam usar OpenGL para esse fim. É provável que cada janela tenha seu próprio stencil buffer e o sistema mantenha uma lista das janelas visíveis e suas coordenadas z (quem está na frente de quem). Assim, para cada janela, as janelas com z>z_{corrente} são desenhadas no stencil buffer da janela em questão (apenas os contornos e preenchidas de branco), criando a máscara.

Assim, quando a GUI for, de fato, desenhar a janela, basta aplicar o stencil… É como serigrafia: As áreas mascaradas não deixam passar a tinta… Isso evita a complicação de manter uma lista de regiões. E, como raster operations são o default nas placas de vídeo atuais, é pouco provável que existam problemas com processamento ao lidarmos com áreas grandes ou com múltiplas subdivisões.

Anúncios

Teste: Usando STL para ler modelos Wavefront

No meu artigo no Projeto Virtual Worlds sobre leitura de modelos no formato Wavefront (aqui) usei as funções de streaming da biblioteca padrão de C. Aqui vai uma ligeira modificação, usando a STL, de C++:

#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <fstream>

struct vec3 { float x, y, z; }
struct indexes { int v, n; }

int readObj(const char *filename)
{
  std::ifstream f(filename);

  if (!f.is_open())
  {
    fprintf(stderr, "Unable to open file.\n");
    exit(EXIT_FAILURE);
  }

  vec3 v;
  indexes i;

  std::string line;
  std::vector<vec3>    vertices;
  std::vector<vec3>    normals;
  std::vector<indexes> idxs;
  
  while (!getline(f, line).eof())
  {
    std::stringstream sstrm(line);
    std::string token;

    sstrm >> token;
    
    /* Não me preocupei com texturas aqui. */
    if (token == "v")
    {
      sstrm >> v.x;
      sstrm >> v.y;
      sstrm >> v.z;
      vertices.push_back(v);  
    }
    else if (token == "vn")
    {
      sstrm >> v.x;
      sstrm >> v.y;
      sstrm >> v.z;
      normals.push_back(v);  
    }
    else if (token == "f")
    {
      /* NOTA: Como os índices começam com 1, no arquivo OBJ, então
               decremento antes de colocar na lista. */
      std::string value;

      sstrm >> value; 
      sscanf(value.c_str(), "%d//%d", &i.v, &i.n);  
      i.v--; i.n--;
      idxs.push_back(i);

      sstrm >> value; 
      sscanf(value.c_str(), "%d//%d", &i.v, &i.n); 
      i.v--; i.n--;
      idxs.push_back(i);

      sstrm >> value; 
      sscanf(value.c_str(), "%d//%d", &i.v, &i.n); 
      i.v--; i.n--;
      idxs.push_back(i);
    }
  }

  f.close();

  /* Usando display lists pq o teste foi feito com
     OpenGL 1.4 (vertex buffers existem no 1.5+). 

     Poderíamos usar o mesmo loop abaixo para monstar um
     vertex buffer object. */
  int displayList = glGenLists(1);
  
  if (displayList)
  {
    glNewList(displayList, GL_COMPILE);
      glBegin( GL_TRIANGLES );
  
      std::vector<indexes>::iterator nIdx;
  
      for (nIdx = idxs.begin(); nIdx != idxs.end(); ++nIdx)
      {
        v = normals[nIdx->n];
        glNormal3fv( (float *)&v );
  
        v = vertices[nIdx->v];
        glVertex3fv( (float *)&v );
      }
  
      glEnd();
    glEndList();
  }
  
  return displayList;

  /* NOTA: Todos os vetores serão limpos aqui... */
}

A rotina é essencialmente a mesma do artigo original, só uso a classe stringstream para separar as substrings automaticamente e para realizar as conversões para float… O uso da classe ifstream também facilita a vida, mas não é tão diferente assim do que usar fopen e fclose.

Outra vantagem é que as strings são alocadas sem a interferência do programador. A STL faz isso de uma maneira performática… A liberação de recursos também é “automática” assim que os objetos saem do escopo…

A desvantagem, é claro, é que o código final fica um pouco balofo. Mas, só um pouquinho…

VirtualWorlds: Roteiro de estudos

Há alguns anos (desde 1988, pelo menos) apaixonei-me pela Computação Gráfica. Eu e meu amigo MaRZ chegamos até a comprar o primeiro livro que tive na área, nessa época, quando fazíamos o curso de Instrumentação Industrial, no SENAI/ES. De lá pra cá muita coisa mudou: O antigo GKS (Graphical Kernel System) deu lugar ao OpenGL (Open Graphics Library), coisas como z-buffering eram impensáveis, na época, para computadores pessoais. Texturas também… Em 1993 o jogo DOOM, desenvolvido por John Carmack, da Id Software, mudou a forma como pensamos em jogos e, recentemente (há uns 5 anos) venho tentando acompanhar tudo o que posso relacionado com o desenvolvimento de aplicações em 3D.

Resolvi, há 2 anos, iniciar um projeto com base numa idéia não tão original… Um amigo têm “contatos” com vários empresários da área imobiliária por aqui, em minha cidade (Vitória/ES). “Que tal desenvolver um framework que permita aos clientes dessas empresas ‘passearem’ pelos imóveis, em tempo real?”. Confesso que tive essa idéia depois de uma imersão no jogo Half-Life, dado o realismo de algumas das cenas!

Enumerei algumas coisas que sabia que precisava estudar para levar o projeto adiante. Na lista abaixo vocês podem ver alguns desses itens, marcados com ×, para aqueles que ainda não cheguei lá, , para aqueles que já entendi e já tenho algum código implementado, ±, para aqueles que ainda estou “mais ou menos” ou quase chegando lá, e ?, para aqueles que ainda não sei se são realmente necessários:

– Matemática vetorial e matricial;
 – Geometria no espaço R3 (triângulos, planos, volumes, elipsóides, etc);
 – Particionamento espacial (BSPs);
 – Iluminação (OpenGL);
 – Aplicação de texturas e “misturas” (blending);
 – Determinação de visibilidade;
 – Programação em multiprocessamento usando pthreads;
 – Uso de Streamming SIMD Extensions (SSE);
 – Leitura de modelos, aplicação de texturas e seus materiais (via Wavefront OBJ file);
 – Áudio 3D via OpenAL;
? – Particionamento espacial (Octrees);
? – Uso de BSPs para audio (obstáculos causando reverberação, ecos, ruídos, atenuações, etc);
± – Balanceamento de árvores binárias;
± – Gerenciamento de cenas (scene graph management);
± – Iluminação dinâmica (com multi-texturas);
± – Programação em multiprocessamento usando OpenMP;
± – GUI mesclada com OpenGL;
× – Modelamento (Blender);
× – Inteligência Artificial (para Games);
× – Mapeamento de normais (bump mapping);
× – Mapeamento de sombras (shadow mapping);
× – Soft shadows (penumbras);
× – Radiosidade;
× – Ray Tracing;
× – Programação em multiprocessamento usando a GPU (preferência pelo OpenCL);
× – Leitura de cenas, mapas, modelos, aplicação de texturas e seus materiais (via COLLADA);
× – Realismo através de efeitos físicos, atmosféricos e outros efeitos especiais;

Essa é uma lista resumida do que pude pensar nos minutos que gastei escrevendo esse post. Cada item desses apresenta uma dezena de sub-itens. Por exemplo, embora eu tenha “dominado” o conceito e a implementação de BSPs, ainda me faltam alguns detalhes sobre usos além da determinação de visibilidade (line of sight determination, por exemplo)…

Vocês podem notar que ainda tenho um longo (e põe longo nisso) período de estudos para atingir o objetivo que me impus. Mas o caminho é divertido!

Coloquei essa lista para que você, que porventura também goste de CGI, tenha uma idéia de um roteiro a seguir em seus estudos… A lista também está ai para vocês terem uma idéia do que pretendo postar por aqui a respeito do projeto, se houver interesse.

VirtualWorlds – O problema final da visibilidade

Pelo menos eu espero que esse seja o fim das regras de determinação de visibilidade. Esse conjunto de regras é conhecido, no jargão da matemática, como PVS (Potentially Visible Set – ou, “Conjunto potencialmente visível”).

O problema que resta é a tentativa de aumentar a precisão dos testes de visibilidade particionando os testes. Ou seja, criando listas de  bounding spheres, boxes e elipsóides para um único objeto complexo. Essa técnica é usada em jogos 2D, como mostra a figura abaixo:

Bounding boxes dierentes para o mesmo modelo, em posições diferentes. Em 2D.

Com listas de bounding boxes para certas posições evitamos os testes de grandes espaços vazios, se usássemos apenas uma caixa.

É claro que, no nosso caso, vale a pena fazer isso, com moderação, para todos os testes. Criar listas de esferas para o modelo inteiro, listas de aabboxes e listas de elipsóides. Seguindo a mesma sequência de testes que mostrei no post anterior, se todos os testes esfericos retornarem falso (zero), então descartamos o objeto inteiro, senão, se todos os testes de aabboxes retornarem falso (zero), então descartamos o objeto… a mesma coisa para os testes de elipsóides. Esses 3 testes são feitos pelas funções planeTestSphere, planeTestAABBox e planeTestEllipsoid, mostradas nos posts anteriores.

Não podemos ter, contudo, muitas esferas, aabboxes e elipsóides, porque senão seria melhor verificar todos os vértices do objeto e esses testes perderiam todo o sentido de existirem…

Um esboço da estrutura que contém o objeto seria essa:

/* Toda esfera tem um centro e um raio */
struct sphere_s
{
  float center[3];
  float radius;
};

/* Toda elipsóide tem 3 vetores e um centro */
struct ellipsoid_s
{
  float center[3];
  float vectors[3][3];
};

struct object_s
{
  int numVertices;
  int numBoundingSpheres;
  int numAABBoxes;   /* calculado em realtime. */
  int numEllipsoids;
  /* ... Outros atributos aqui ... */

  float (*vertices)[3];
  struct sphere_s *boundingSpheres;
  float (*aabboxes)[2][3];  /* alocado e calculado em realtime */
  struct ellipsoid_s *boundingEllipsoids;
  /* ... Outras listas aqui ... */
};

Note que o número de AABBoxes e as coordenadas dessas caixas devem ser calculadas em realtime por causa daquele problema de rotação… Só devo lembrar que nós precisamos das AABBoxes por que elas são mais rápidas do que usar elipsóides!

Não vou mostrar as rotinas que lidam com essas estruturas porque são bastante óbvias. Mais óbvio ainda que esses testes são feitos todos contra um plano, que pode ser o de um frustum ou de um plano divisor vindo da BSP Tree.

Vocẽ deve ter notado que não usei os containers da STL. Eu poderia muito bem usar o template vector e poupar o trabalho de manipular os buffers contendo os vetores, esferas, aabboxes e elipsóides, manualmente… Acontece que estou desenvolvendo esse framework totalmente em C e de forma otimizada (medindo ciclos, usando SSE quando possível, etc). C++ é prático, fácil, mas não é performático.

VirtualWorlds – Mais sobre testes de visibilidade

No dois últimos artigos tentei mostrar que é possível usar métodos mais performáticos para determinar se um objeto é visível ou não. Primeiro, usando uma árvore binária para “particionar” (dividir) o espaço (do sistema de coordenadas view, ou do “universo”); depois, para colocar objetos neste espaço e testar se estes podem ser vistos sem termos que testar todos os seus vértices (imagine fazer isso com um objeto que tenha 3000 vértices… agora, imagine fazer isso com 1000 objetos!).

O primeiro método que mostrei foi o teste esférico, onde o objeto é inscrito numa esfera com centro no sistema de coordenadas do modelo (do objeto). Uma vez que temos as equações dos planos do frustum (da câmera) e as dos planos divisores, na BSP, calcular a distância deste centro é uma moleza.

O segundo método é imaginar uma caixa em torno do objeto. Mas essa caixa estará alinhada com o sistema de coordenadas do “universo”, ou seja, se o objeto for rotacionado a caixa não o será e precisa ser recalculada, com base nos vértices mais distantes do centro do objeto, no sistema de coordenadas do modelo.

O primeiro método é mais rápido do que o segundo. Ele testa apenas um ponto contra o plano desejado. Acontece que o objeto pode não preencher totalmente a esfera (e isso vai acontecer na maioria das vezes). Então, esse teste dirá ao engine que é provável que o objeto seja visível ou não. O teste é rápido, mas impreciso. O segundo método é um pouco mais preciso, já que a caixa não é regular (no sentido de que não precisa ter lados iguais). Ela pode ser mais fina lateralmente ou na profundidade, ou na altura. Mas, mesmo assim, parte de seu volume pode conter… vazio!

É aqui que eu apresento pra vocês dois métodos adicionais. O teste da caixa orientada (OBB, de Oriented Bounding Box) e o teste da elipsoide.

O teste OBB resolve o problema do teste AABB (Axis Aligned Bounding Box). Em essência o teste OBB é o mesmo do que mostrei no último post, mas a caixa é rotacionada junto com o objeto. Assim, temos que testar todos os 8 vértices da caixa para termos certeza que ela encontra-se totalmente atrás de um plano, ou não… Mesmo assim o teste não é preciso, porque a caixa, mesmo que alinhada com o sistema de coordenadas do modelo (não o do “universo”) também pode possuir espaços vazios. Basta imaginar uma bounding box em torno de uma esfera, por exemplo. Os cantos perto dos vértices da caixa estarão “vazios”, certo?

Deu pra perceber que:

  1. O teste esférico é mais rápido do que os demais, mas é mais impreciso;
  2. O teste AABB é mais lento do que o esférico, é mais preciso do que este último, mas nem tanto;
  3. O teste OBB é mais lento do que o teste AABB, um pouco mais preciso, mas também nem tanto.

Pra quê usar OBBs se podemos usar elipsoides?

Existe alguma outra figura geométrica que envolva nosso objeto, seja um pouco mais precisa e que possa ser rotacionada junto com objeto? Hummmm… que tal colocar um “ovo” em torno dele?

Elipsoide é uma elipse revolucionada em torno de um eixo. Essa revolução pode ser também uma elipse:

Exemplo de uma elipsoide, com revolução em forma de circunferência.

A definição de uma elipsoide é uma coisa complicada (nem tanto, se você pensar bem):

\displaystyle\dot{p}=\vec{i}\cdot\cos\theta\cdot\sin\delta +\vec{j}\cdot\sin\theta\cdot\sin\delta+\vec{k}\cos\delta

Onde os vetores \vec{i}, \vec{j} e \vec{k} são vetores perpendiculares entre si (ortogonais). O ângulo \delta é formado entre o ponto \dot{p} e o vetor \vec{k}. Já o ângulo \theta é o da projeção do ponto \dot{p} no plano formado pelos vetores \vec{i} e \vec{j}, em relação a \vec{i}.

Muito complicado isso… Acontece que essa definição não nos interessa (muito). O que interessa é que a elipsoide pode ser definida por apenas os 3 vetores ortogonais. Imagine que o vetor \vec{i} esteja alinhado com o eixo x, o vetor \vec{j} com o eixo y e o vetor \vec{k} com o eixo z (apenas imagine, já que eles podem não estar alinhados com esses eixos!). O comprimento desses vetores nos dão os limites da elipsoide.

Com esses 3 vetores podemos determinar a distância da borda da elipsoide que está voltada para o plano, em relação ao centro da elipsoide e ao vetor normal do plano. Demonstrar isso consumiria tempo e espaço que não temos neste post, mas você pode verificar essa demonstração no capítulo 7 do livro Mathematics for 3D Game Programming and Computer.Graphics, 2nd Edition – de Eric Lengyel – Charles River Media – ISBN 1-58450-227-0:

\displaystyle r=\sqrt{(\vec{i}\cdot\vec{n})^2 + (\vec{j}\cdot\vec{n})^2 + (\vec{k}\cdot\vec{n})^2}

Onde, r é a distância a partir do centro da elipsoide e \vec{n} é o vetor normal do plano.

De novo, se você pensar bem, a equação acima é, de fato, bem simples de compreender. Agora, tudo o que temos que fazer é agir como se estivéssemos fazendo um teste esférico:

/* vecs são os 3 vetores da elipsoide, center, sua posição. */
int planeEllipsoidTest(float plane[4], float center[3], float vecs[3][3])
{
  float a, b, c, r;

  a = vector3Dot(vecs[0], plane); a *= a;
  b = vector3Dot(vecs[1], plane); b *= b;
  c = vector3Dot(vecs[2], plane); c *= c;
  r = sqrtf(a + b + c);

  a = planeDistanceToPoint(plane, center);

  if (a <= -r)
    return 0;
  return 1;
}

A sequência dos testes

Lembre-se que o objetivo desses 3 testes (esférico, aabbox e elipsoide) e evitar o teste de cada um dos vértices do objeto contra um plano, para determinar sua posição relativa (na frente ou atrás). Assim, vale a pena realizar os testes mais rápidos primeiro, deixando os mais lentos por último (e somente para aqueles que passaram nos testes anteriores!). Nossa sequência de testes estão será, para cada objeto na cena:

  1. Testes esféricos – porque testam o centro da esfera, dado o raio desta. A esfera não precisa ser rotacionada junto com o objeto;
  2. Testes da caixa alinhada aos eixos – porque testamos apenas 2 pontos da caixa contra o plano. A caixa não pode ser rotacionada junto com o objeto (portanto, temos que calcular os 2 pontos diametralmente opostos da caixa depois de uma rotação);
  3. Testes de elipsoides – porque testamos 3 vetores e o centro contra o plano. A elipsoide pode ser rotacionada junto com o objeto.

Pulei os testes com OBBs porque, dada a elipsoide, esses testes testam 8 pontos contra o plano. A elipsoide testa 4 vetores. O teste da elipsoide é ligeiramente mais lento que o teste de OBBs, mas, já que os 2 testes anteriores determinaram a probabilidade da visibilidade do objeto e o teste da elipsoide pode ser mais acurado, pra quê um quarto teste?

Ainda temos um problema!

Gradualmente melhoramos a precisão dos testes, mas ainda existe o potencial para que os containers desses testes estejam parcialmente vazios, criando falsos positivos. A maneira de minimizar isso ainda mais é assunto para o próximo post. Fiquem tranquilos. É bem mais simples e envolve mais lógica do que matemática!

Pra que duplicar o trabalho?

Se você der uma olhada nos engines 3D que existem por ai verá que, em seus códigos-fonte, existem rotinas de transformações geométricas (translação, rotação e escalonamento). Mas, isso já não é feito pelo OpenGL?

Nos últimos artigos sobre o meu projeto VirtualWorlds mostrei o que é e como usar uma árvore binária de particionamento espacial (BSP Tree) para decidir quais polígonos serão desenhados ou não.  E é exatamente ai que o problema do retrabalho acontece.

As BSPs existem, à princípio, para decidirmos quais porções do mapa serão desenhados. Usar  BSPs para decidir quais objetos serão desenhados é um bônus que exige alguns procedimentos extras… Por exemplo, não podemos verificar todos os vértices dos objetos para determinar se parte do objeto está dentro ou fora do frustum (de um dos planos que compõem o frustum) ou se é obstruído por outro conjunto de polígonos que estejam em sua frente. Se fizessemos isso, o tempo de processamento será enorme e a animação seria impossível.

Duas técnicas são usadas para diminuir esse tempo: testes esféricos e testes de caixas (conhecidas como axis aligned bounding boxes ou AABBoxes). A idéia, no caso dos testes esféricos, é achar o ponto mais longe da origem do sistema de coordendas do modelo e usá-lo como raio de uma esfera. Se essa esfera estiver totalmente atrás de um plano, então o objeto também estará. O teste esférico é tão simples quanto:

int planeSphereTest(float plane[4], float center[3], float radius)
{
  float distance;

  distance = planeDistanceToPoint(plane, center);
  if (distance <= -radius)
    return 0;
  return 1;
}

Já o teste da aabbox exige que encontremos dois vértices diametralmente opostos, que formem uma caixa. Um desses vértices é o left-bottom-far e o outro é o right-top-near:

Left, Bottom e Far é o vértice da caixa com as menores coordenadas, Right, Top e Near é o com as maiores. A escolha desses vértices não importa, desde que eles sejam diametralmente opostos. É evidente que escolhi essa ordem e devo mantê-la nos testes…

Da mesma maneira que o teste esférico, se a caixa (ou parte dela) estiver na frente de um plano, então o objeto contido nela também está (ou, parte dele). Ou, falando a mesma coisa de forma diferente, se ambos os vértices estiverem do lado de trás do plano, então o objeto também estará:

int planeAABBoxTest(float plane[4], float box[2][3])
{
  float d1, d2;

  d1 = planeDistanceToPoint(plane, aabbox[0]);
  d2 = planeDistanceToPoint(plane, aabbox[1]);

  if (d1 <= 0.0f && d2 <= 0.0f)
    return 0;
  return 1;
}

Acontece que não podemos pré-calcular os vértices da caixa. O motivo é um só: rotações. Se o nosso objeto for transladado, a caixa permanecerá a mesma, só que transladada junto com o centro do objeto. Se o objeto for escalonado, basta escalonar também a caixa (ou a esfera)… Mas, se o objeto for rotacionado, toda a caixa será alterada. Isso é fácil de demonstrar: Suponha que o nosso objeto seja (em 2D) um retângulo. O retângulo que o contém coincide com suas coordenadas, de acordo com a figura (a), abaixo…

(a) é o objeto original; (b) é o objeto escalonado e (c) é o objeto rotacionado 45º para a esquerda...

Note como o “retângulo” que cerca nosso objeto, no caso (c) parece mais um quadrado e foge completamente à aabbox do objeto original (em (a)). Os cantos inferior e superior da aabox, no caso (c),  são definidos pelos vértices de menor e maior coordenadas, respectivamente.

É por esse motivo que os engines duplicam o trabalho já realizado pelo OpenGL. Eles precisam calcular as aabboxes do objeto rotacionado. Uma vez que tenhamos o objeto rotacionado, achar esses vértices é simples, basta percorrer a lista de vértices do objeto selecionando os menores e maiores valores, atribuindo-os à caixa:

#include "aabbox.h"

#ifndef max
#define max(a, b) ((a) > (b) ? (a) : (b))
#endif

#ifndef min
#define min(a, b) ((a) < (b) ? (a) : (b))
#endif

/*
  Axis Aligned Boxes são definidas como um conjunto de 2 pontos,
  onde a ordem é: left-far-bottom, right-near-top.

        +------+                 +y
        |\      \                    |
        | +------+ rtn               +--> +x
        | |      |                    \
   lfb  + |      |                     +z
         \|      |
          +------+

  aabbox[0] = lfb;
  aabbox[1] = rtn;

  Antes de chamar essa rotina, a rotação (e o possível escalonamento)
  no sistema de coordenadas do modelo já deverão estar aplicadas
  no conjunto de vértices.
*/
void aabboxCalculate(float aabbox[2][3],
                     float viewTranslation[3],
                     float (*pVertices)[3], int nVertices)
{
  int i, j;

  for (i = 0; i < 4; i++)
    aabbox[0][i] = pVertices[0][i];

  for (i = 1; i < nVertices; i++)
    for (j = 0; j < 4; j++)
    {
      aabbox[0][j] = max(aabbox[0][j], pVertices[i][j]);
      aabbox[1][j] = min(aabbox[1][j], pVertices[i][j]);
    }

  for (i = 0; i < 4; i++)
  {
    aabbox[0][i] += viewTranslation[i];
    aabbox[1][i] += viewTranslation[i];
  }
}

O detalhe diferente, como já falei, é que, nessas rotinas, rotações e escalonamentos levam em conta apenas o sistema de coordenadas do modelo. E as translações feitas para o objeto, no sistema de coordenadas view.

Repare também que eu não falei que os testes esféricos sofrem do mesmo problema! A não ser pelo escalonamento, as rotações não afetam os testes esféricos. Por isso, geralmente, eles são feitos antes dos testes com aabboxes. Se o testes esférico disser que o objeto está do lado de trás de um plano, então não precisamos fazer o teste das aabboxes, poupando ciclos preciosos em não ter que recalcular as coordenadas da caixa!

Para criar uma aabbox, é claro que vocẽ é bem vindo para criar algum algorítimo inteligente para evitar percorrer toda a lista de vértices do objeto. No momento não consigo pensar em um…

Projeto VirtualWorlds: Mais experiências com BSP Trees e Portais

Não sei se ficou claro, mas a árvore BSP não é construída em tempo de execução. Ela precisa ser pré-compilada e é alinhada com o sistema de coordenadas do “universo” (view coordinate system). Para quem não tem muita experiência com OpenGL, existem alguns sistemas de coordenadas: model, view, clipping, textures… As duas primeiras são, na prática, misturadas em uma única matriz, a terceira é associada à matriz de projeção… O sistema de coordenadas do modelo (model) é o usado para definir os objetos na cena. A origem desse sistema de coordenadas (3D) é o centro do objeto em si. O sistema de coordenadas view tem sua origem no centro do “universo”, onde os objetos serão colocados (transladados, rotacionados, escalonados, etc).

A experiência que estou querendo fazer é relacionada à performance. No artigo anterior mostrei que, quando usamos BSPs, “particionamos” (uma palavrinha bonitinha para “dividir”) o universo em dois pedaços através de um plano (lembro que “planos” são superfícies sem limites laterais, ou seja, o plano xy  não tem limites nem em x, nem em y, e sua componente z tem espessura zero!). Isso é bem diferente de um polígono, que tem limites laterais (mas tem espessura zero também!).

Minha dúvida (que ainda precisa ser medida) é se eu realmente preciso pré-calcular os planos divisores ou se estes podem ser calculados em realtime, através de polígonos divisores. A vantagem dessa outra aproximação é que tenho como determinar se um polígono está na frente do outro — não há como fazer isso com planos, a não ser que eles sejam paralelos!

A rotina para cálculo de um plano é bem simples, baseada em um triângulo:

/* A rotina assume que o triângulo seja "orientado", ou seja,
   que seus vértices sejam fornecidos numa ordem definida.
   Os pontos são fornecidos no sentido anti-horário para
   aproveitar os vetores normais para determinar se o
   triângulo é visível ou não. */
void planeFromTriangle(floar plane[4], float triangle[3][3])
{
  float v1[3];
  float v2[3];

  /* Calcula 2 vetores baseados nas coordenadas
     do triângulo. */
  vector3Sub(v1, triangle[2], triangle[1]);
  vector3Sub(v2, triangle[3], triangle[2]);

  /* Obtém o vetor normal do triângulo */
  vector3Cross(plane, v1, v2);
  vector3Normalize(plane);

  /* Calcula a projeção da distância de um ponto
     do triângulo em relação ao vetor normal. */
  plane[4] = -vectorDot(plane, triangle[0]);
}

Aproveitei o ponteiro plane para armazenar o vetor normal já que este será copiado para o array plane de qualquer jeito mesmo!

A rotina pode parecer confusa para o não iniciado em geometria, mas um plano é definido como um vetor de orientação (um vetor unitário, perpendicular ao plano) e a distância de um dos pontos, do plano, em relação à origem. O uso de um triângulo como base para o cálculo dos coeficientes da equação do plano deve-se ao fato de que apenas triângulos são garantidos de estarem totalmente sobre a superfície de um plano… A equação do plano é:

Ax + By + Cz + D = 0

Onde A, B e C são as coordenadas do vetor normal ao plano e D é a distância. No que a equação do plano nos ajuda? A calcular se um ponto está na frente ou atrás dele:

float planeDistanceToPoint(float plane[4], float point[3])
{
  return plane[0] * point[0] +
         plane[1] * point[1] +
         plane[2] * point[2] +
         plane[3]);
}

A rotina acima retorna zero se o ponto point coincide com o plano, algum valor maior que zero se o ponto está na frente ou algum valor menor que zero se está atrás. Acredito que está explicado porque, no cálculo da equação do plano,  o produto escalar que determina o coeficiente D é negativo: Ao calcular o produto escalar entre o vetor normal e o ponto, na rotina acima, temos a projeção do ponto sobre o vetor normal, isto é, a distância do ponto em relação a origem na mesma direção do vetor normal. Para determinar se o ponto está sobre o plano ou não, o coeficiente D precisa ter sinal contrário deste produto para dar o valor 0.0!

Considere o plano xy com sobre o eixo z, na posição 3. O vetor normal, é claro, deverá ser um dos dois: (0,0,1) ou (0,0,-1), de acordo com para qual lado do plano está voltado. Usaremos o primeiro (0,0,1). O coeficiente D será -3. A equação do plano será:

z - 3 = 0
Plano mostrado aqui como um retângulo...

O ponto (3,4,5) está  na frente do plano, já que 2 é maior que 0. Mas, o ponto (1,2,3) com certeza estará sobre o plano (já que sua componente z é 3!

Meu dilema é: Se eu precisar verificar se um dos dois polígonos que definem os planos divisores estão na frente ou atrás do outro, não poderei fazer isso com as equações dos planos. Ao mesmo tempo, calcular as equações do plano pode ser um fator que influencia muito a performance: vector3Cross, vector3Dot e vectorNormalize são rotinas que realizam multiplicações e, particularmente no caso de vectorNormalize, temos um cálculo de raiz quadrada (para determinar o tamanho do vetor) e 3 divisões (para dividir os componentes do vetor pelo seu tamanho, obtendo um vetor unitário).

Esse dilema pode ser resolvido, acho eu, transferindo a total responsabilidade da criação da árvore para outro lugar que não o engine (e é isso o que é feito!). Só que se o uso de portais exigirem algum cálculo com os polígonos divisores (provavelmente não!) e se o blender (software de modelagem 3D que usarei) não for suficiente para a criação de uma BSP perfeita1, então o pré-calculo dos planos não me ajuda muito.

Pode ser necessário usar ferramenta mais especializada, com o GtkRadiant, por exemplo, para a criação da BSP, mas eu não gostaria de ter que aprender mais uma ferramenta de modelagem (especialmente porque o GtkRadiant não tem uma documentação tão boa!)… Não consegui aprender direito nem o blender ainda, ora bolas…

Assim que eu fizer a experiência e chegar a uma conclusão, digo pra vocês.

1 – Sobre a árvore BSP perfeita: É necessário usar árvores balanceadas para garantir que o tempo de pesquisa pelas “folhas” onde a câmera está seja o mínimo possível. Como vocês provavelmente já sabem, uma árvore não-balanceada pode tender a ser degradada numa lista, ficando bem lenta.