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!

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