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.

Anúncios

Um comentário sobre “Projeto VirtualWorlds: Mais experiências com BSP Trees e Portais

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