Serigrafia no computador: Stencil Buffer

Você já viu como fazem aquelas camisetas com estampas desenhadas? Usa-se um filtro onde a tinta passa ou não por poros de uma malha muito fina. Nos poros onde a tinta passa ela é absorvida pelo tecido da camisa, onde não passa, ela é mascarada e fica na malha. Eis um exemplo de confecção de placa de circuito impresso pelo método serigráfico:

Serigrafia, usada para criar a máscara que não será corroída numa PCB

Na foto, a parte amarela da “malha” ou “tela” deixa passar a tinta, a parte verde, não deixa. A tinta, é claro, está do lado de lá do aplicador, sendo arrastada sobre a superfície da “malha”…

Mas, o que diabos isso tem a ver com “computação gráfica” fora a palavra “gráfica”?

A maneira de implementar o método serigráfico num computador é criando um buffer onde cada bit equivale ao “deixa passar” ou “não deixa passar” da malha que será exposta à tinta. A tinta, neste caso é um pixel, que “passará” ou não pelo teste do bit (1, deixa passar, 0, não deixa).

Considere que você tem uma tela de 1280 por 720 pixels. Se cada bit é um filtro para um único pixel, então o buffer “stencil” (é assim que gringos chamam o processo serigráfico) poderia ser composto de 1280 por 720 bits. 1280 bits por linha dá 160 bytes por linha, o que nos dá 115200 bytes para a tela inteira (que no formato RGBA terá pouco mais de 3,5 MiB. Ou seja, o stencil buffer terá apenas cerca de 3% do tamanho da tela real).

Considerando que cada byte do stencil buffer está associado a 8 pixels e o bit zero está associado ao pixel onde x=0, na linha corrente, então, nessa resolução gráfica, para achar o bit correspondente da posição (x,y) da tela, basta fazer:

  // divide x por 8 para obter o offset da linha.
  size_t offset = (size_t)x >> 3;

  // Obtem o resto da divisão por 8 para obter o 
  // bit correspondente.
  size_t bit = 1 << (x & 7);

  // stencilbase é o ponteiro para o stencil buffer bitmap.
  // stencilwidth é o comprimento, em bytes, de cada linha.
  char *stencilp = (char *)stencilbase +
                      (stencilwidth*y) + offset;

  // basta agora testar o bit para decidir se devemos ou 
  // não modificar o pixel.
  if (*stencilp & bit) 
    setpixel(x,y,color);

Essa pequena rotina poderia ser chamada de stencil_setpixel(), onde passaríamos, pelo menos, o ponteiro para uma estrutura contendo os dados do stencil, as coordenadas (x,y) e a cor do pixel.

Note que esse método só tem um problema: Para ele funcionar, o comprimento (width) do buffer tem que ser, sempre, múltiplo de 8. Se o comprimento não for múltiplo de 8 podemos complementá-lo com bits zerados, considere um retângulo de 70 por 70 pixels. Teremos 70 linhas e isso não é problema, mas 70 não é múltiplo de 8… Teremos que colocar 00 nos dois últimos bits do último byte da linha (que terá 9 bytes por linha: 9\cdot8=72).

Eis um exemplo de uso de stencil buffers, mas para partes da tela. Por exemplo, no auxílio de desenho de janelas com bordas não retangulares:

Pequeno stencil para uma janela de 320×200 pixels

Deixei uma borda preta de 1 pixel de tamanho em cada canto dessa imagem para que ela ficasse perfeitamente visível contra o fundo branco deste blog. Essas linhas não existem neste stencil de exemplo… E esse meu stencil também é de baixa resolução porque quero mostrá-lo para vocẽ (por isso a “ampliação” central)… Neste caso ai, o stencil será usado numa área retangular de 320 por 200 pixels e os bits 0 (pretos) simplesmente não alterarão a cor do “fundo” dessa área… toda a área “branca” (bits setados) será afetada pelos pixels correspondentes da imagem original…

Vale lembrar que isso ai não é uma “transparência”, já que este outro efeito exige uma “mistura” (blending) de cores e é para isso que existe o canal alpha no esquema RGBA de cores. O stencil é somente uma máscara de bits… uma “máscara” que mais mostra do que esconde, neste caso em particular.

No desenho acima fiz, propositalmente, o zoom do canto superior direito e o separei em um bloco de 16 por 16 bits… Note que não precisamos, em certos casos, do stencil buffer inteiro. Numa janela retangular poderíamos aplicar stencils apenas aos cantos para arredondá-los e o restanet da área seria desenhada sem passar por essa filtragem. É claro, vale a pena limitar os tamanhos horizontal e vertical mínimos para qualquer janela para que isso funciona… Neste caso, nossa janela jamais poderia ter tamanho menor que 32 por 32 pixels, por causa dos 4 cantos…

 

Anúncios

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.

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…