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…

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