Projeto Virtual Worlds

Computação Gráfica 3D em C

Arquivos Mensais: março 2012

Mais sobre o frustum…

Já falei sobre ele aqui. O frustum é um sólido trapezóide, uma pirâmide sem a parte de cima. O ponto focal (o topo da pirâmide) é onde está a câmera. Na projeção perspectiva essa pirâmide é calculada de acordo com o campo de visão (field of view), que é a amplitude angular que a câmera pode “enxergar”. Esse ângulo, no OpenGL, é fornecido como sendo o ângulo dos dois planos, superior e inferior, do frustum.

Ao chamar uma das funções, glFrustum ou gluPerspective, fornecemos os parâmetros para que o OpenGL calcule os 6 planos, baseados nas coordenadas do plano near e fare o campo de visão. O cálculo é simples e pode ser feito por semelhança de triangulos, dê uma olhada:

O frustum, com suas coordenadas calculadas por semelhança de triângulos.

Dá para entender agora porque as coordenadas (left,top,rright,bottom) fornecidas nas funçções glFrustum e gluPerspective são sempre relativas ao plano near . Com base neassas coordenadas e no field of view podemos calcular o plano far facilmente. Aqui vocẽ acha uma dedução do que essas funções fazem.

Com base nessa matriz podemos extrair o frustum de acordo com a orientação da câmera, levando em conta a matriz modelview.

/* plane.h */
...
typedef struct plane_s {
  float a, b, c, d;
} plane_t;

/* Veja observação após essa listagem */
void plane_normalize(plane_t *plane_p);

/* mat4.h */
...
#define MAT4_INDEX(col, row) ((row)*4 + (col))

void mat4_mult(float *mout_p, float *m1_p, float *m2_p);

/* frustum.c */

#include <GL/gl.h>
#include "mat4.h"
#include "plane.h"

void frustum_get_planes_from_opengl(plane_t *planes_p)
{
  float mat4_modelview[16];
  float mat4_projection[16];
  float mat4_temp[16];

  glGetFloatv( GL_MODELVIEW_MATRIX, mat4_modelview);
  glGetFloatv( GL_PROJECTION_MATRIX, mat4_projection);

  mat4_mult(mat4_temp, mat4_modelview, mat4_projection);

  /* left plane */
  planes_p->a = mat4_temp[MAT4_INDEX(3,0)] + mat4_temp[MAT4_INDEX(0,0)];
  planes_p->b = mat4_temp[MAT4_INDEX(3,1)] + mat4_temp[MAT4_INDEX(0,1)];
  planes_p->c = mat4_temp[MAT4_INDEX(3,2)] + mat4_temp[MAT4_INDEX(0,2)];
  planes_p->d = mat4_temp[MAT4_INDEX(3,3)] + mat4_temp[MAT4_INDEX(0,3)];
  plane_normalize(planes_p++);

  /* right plane */
  planes_p->a = mat4_temp[MAT4_INDEX(3,0)] - mat4_temp[MAT4_INDEX(0,0)];
  planes_p->b = mat4_temp[MAT4_INDEX(3,1)] - mat4_temp[MAT4_INDEX(0,1)];
  planes_p->c = mat4_temp[MAT4_INDEX(3,2)] - mat4_temp[MAT4_INDEX(0,2)];
  planes_p->d = mat4_temp[MAT4_INDEX(3,3)] - mat4_temp[MAT4_INDEX(0,3)];
  plane_normalize(planes_p++);

  /* bottom plane */
  planes_p->a = mat4_temp[MAT4_INDEX(3,0)] + mat4_temp[MAT4_INDEX(1,0)];
  planes_p->b = mat4_temp[MAT4_INDEX(3,1)] + mat4_temp[MAT4_INDEX(1,1)];
  planes_p->c = mat4_temp[MAT4_INDEX(3,2)] + mat4_temp[MAT4_INDEX(1,2)];
  planes_p->d = mat4_temp[MAT4_INDEX(3,3)] + mat4_temp[MAT4_INDEX(1,3)];
  plane_normalize(planes_p++);

  /* top plane */
  planes_p->a = mat4_temp[MAT4_INDEX(3,0)] - mat4_temp[MAT4_INDEX(1,0)];
  planes_p->b = mat4_temp[MAT4_INDEX(3,1)] - mat4_temp[MAT4_INDEX(1,1)];
  planes_p->c = mat4_temp[MAT4_INDEX(3,2)] - mat4_temp[MAT4_INDEX(1,2)];
  planes_p->d = mat4_temp[MAT4_INDEX(3,3)] - mat4_temp[MAT4_INDEX(1,3)];
  plane_normalize(planes_p++);

  /* near plane */
  planes_p->a = mat4_temp[MAT4_INDEX(3,0)] + mat4_temp[MAT4_INDEX(2,0)];
  planes_p->b = mat4_temp[MAT4_INDEX(3,1)] + mat4_temp[MAT4_INDEX(2,1)];
  planes_p->c = mat4_temp[MAT4_INDEX(3,2)] + mat4_temp[MAT4_INDEX(2,2)];
  planes_p->d = mat4_temp[MAT4_INDEX(3,3)] + mat4_temp[MAT4_INDEX(2,3)];
  plane_normalize(planes_p++);

  /* far plane */
  planes_p->a = mat4_temp[MAT4_INDEX(3,0)] - mat4_temp[MAT4_INDEX(2,0)];
  planes_p->b = mat4_temp[MAT4_INDEX(3,1)] - mat4_temp[MAT4_INDEX(2,1)];
  planes_p->c = mat4_temp[MAT4_INDEX(3,2)] - mat4_temp[MAT4_INDEX(2,2)];
  planes_p->d = mat4_temp[MAT4_INDEX(3,3)] - mat4_temp[MAT4_INDEX(2,3)];
  plane_normalize(planes_p);
}

A função frustum_get_from_opengl() extrai os seis planos do frustum da combinação das matrizes, só que essas equações provavelmente não são normalizadas. Lembre-se que a equação do plano é:

Ax + By + Cz + D = 0

Onde (A,B,C) é um vetor unitário, normal (perpendicular) ao plano. Ao extrair os planos com a rotina acima esse vetor não será, provavelmente, unitário. Daí a necessidade de “normalizar” a equação:

void plane_normalize(plane_t *plane_p)
{
  float len;
  vec3_t *vnormal_p;

  vnormal_p = (vec3_t *)plane_p;
  len = vec3_length(vnormal_p);

  if (len != 0.0f)
  {
    plane_p->a /= len;
    plane_p->b /= len;
    plane_p->c /= len;
    plane_p->d /= len;
  }
}

Como a constante D é calculada a partir do vetor unitário, é necessário dividi-la pelo tamanho do vetor (A,B,C) original também.

Obter os planos do frustum é importante para fazermos testes de visibilidade. Um desses testes usa uma esfera onde o objeto está inscrito:

bool frustum_sphere_test(plane_t *planes_p, vec3_t *pt_p, float radius)
{
  int i;
  float distance;

  for (i = 0; i < 6; i++, planes_p++)
  {
    distance = plane_distance_from_point(planes_p, pt_p);

    /* Se o ponto está distante de -radius unidades
       do lado "negativo" do plano, então a esfera onde
       o objeto está inscrito está totalmente fora do frustum! */
    if (distance < -radius)
      return false;
  }

  /* A esfera está dentro ou parcialmente dentro do frustum. */
  return true;
}

O teste esférico é o primeiro teste de visibilidade que faremos (e o mais rápido).

Neste ponto você deve ter notado que o algoritmo tem um pequeno problema. Imagine uma esfera num dos vértices do frustum, cujo centro está distante do vértice exatamente do raio da esfera. Neste contexto a distância do centro do objeto (e da esfera onde está inscrito) está distante de dois planos por menos que o raio da esfera e o algoritmo dirá que o objeto está parcialmente dentro do frustum!

A solução para isso é considerar um delta_radius, uma fração do raio, somada ao raio da esfera — ou, visto de outra forma, como se o furstum tenha sido “estendido” por uma fração do raio da esfera. Essa solução eliminará o problema acima, mas criará outro. Objetos distantes de um dos planos pelo raio da esfera que estão, de fato, fora do frustum passarão a ser interpretados como estando parcialmente dentro dele. Assim, acabaríamos com mais objetos na lista de objetos possivelmente visíveis do que poderíamos querer.

Lembre-se que o teste esférico é apenas o primeiro teste. Usamos este teste para selecionar os objetos que potencialmente estão dentro do frustum para filtrá-los com testes mais precisos. No VirtualWorlds usarei testes com Object Oriented Bounding Boxes e Elipsóides, nesta ordem… Os testes com OOBB’s são mais precisos do que os esféricos, filtrando ainda mais os objetos possivelmente visíveis. E os testes com elipsoides filtrarão ainda mais. A vantagem é que esses outros testes terão que lidar com um subconjunto mais restrito de objetos…

Para facilitar, poderíamos mudar a rotina acima para marcar os objetos que são selecionados como potencialmente visíveis como estando totalmente ou parcialmente visíveis. Somente esses últimos seriam passados para a próxima fase de testes e assim por diante.

Anúncios

Um padrão para o estilo desenvolvimento do projeto

Olá, gente! Quanto tempo! O projeto não morreu não, só deu uma parada para refrescar a cabeça e para mais estudos. Não me lembro se eu já disse isso aqui, mas estou estudando mais à fundo o GLSL e OpenCL.

Para não parecer que eu sumi de vez, eis um padrão que estou usando no desenvolvimento da biblioteca base do Virtual Worlds.

  • Todo o código será construído em C, não em C++;
  • O código será totalmente modular, ou seja, existem pacotes separados. Até o momento tenho: MathLib, Graphics, MemoryManager, um pedaço do NetworkIO e um pedacinho do Effects (depth of field, motion blur, shadows, bump e parallax mapping, etc). Ainda faltam muitos módulos, com o Shaders e SceneGraph, Lighting, entre outros;
  • Todas as funções são nomeadas a partir do nome do módulo.

Com relação aos nomes das funções. Eis um exemplo de como os headers ficaram:

/* module: vec3.h */
#ifndef _VEC3_H_
#define _VEC3_H_

#include <stdbool.h>

typedef struct vec3_s {
  float x, y, z;
} vec3_t;

void vec3_zero(vec3_t *v_p);
void vec3_assign(vec3_t *vout_p, float x, float y, float z);
void vec3_copy(vec3_t *vout_p, vec3_t *v_p);
void vec3_insert(vec3_p *vout_p, vec3_t *v_p);

float vec3_length(vec3_t *v_p);

void vec3_add(vec3_t *vout_p, vec3_t *v1_p, vec3_t *v2_p);
void vec3_sub(vec3_t *vout_p, vec3_t *v1_p, vec3_t *v2_p);
void vec3_scale(vec3_t *vout_p, vec3_t *v_p, float scale);

float vec3_dot(vec3_t *v1_p, vec3_t *v2_p);
void  vec3_cross(vec3_t *vout_p, vec3_t *v1_p, vec3_t *v2_p);

/* Recebe o vector e retorna-o nomrmalizado */
void vec3_normalize(vec3_t *v_p);

bool vec3_is_equal(vec3_t *v1_p, vec3_t *v2_p);
bool vec3_is_oposite(vec3_t *v1_p, vec3_t *v2_p);
bool vec3_is_invserted(vec3_t *v1_p, vec3_t *v2_p);

#endif /* _VEC3_H_ */

Diferente de códigos como o do Quake III, eu uso o padrão de C para assinalamento. Quer dizer, os parâmetros que receberão a alterações, se houverem mais que um, são os primeiros da lista. Isso me permitirá usar número de parâmetros variáveis (usar “…” nas funções), se necessário.

Ao invés de trabalhar com arrays como tipo primário para os vetores, defino typedefs específicos, como mostrado acima. De fato, para cada tipo de “objeto”, defino um tipo e o nomeio com sufixo “_t”, que denota typedefs. O sufixo “_s” é usado para structs. Do mesmo jeito, “_e” significa enums.

Nomes de variáveis são sempre uma descrição abreviada e, se houverem espaços, estes são substituídos por um undescore (“_”), como no exemplo abaixo:

int num_vertices;
vec3_t vnormal;
void frustum_get_from_opengl(plane_t *pout_p);

Note que o sufixo “_p” não é usado para tipos, mas para variáveis do tipo ponteiro. Se for necessário usar ponteiros para ponteiros, adiciono um ‘p’ extra:

object_t **objects_list_pp;

Faço isso porque, sinceramente, a tal da Notação Húngara, usada ad nauseum pela Microsoft já encheu o meu pobre e velho saquinho. Mas ela não é inútil… assim, uso uma variação que me agrada mais, colocando a descrição da variável no início…

E, falando em nomes de variáveis, aquelas que uso como iterators são nomeadas, na maioria das vezes, como um único caracter: i, j, k, w, etc… exceto quando o código ficar confuso…

Outra prática é evitar a supressão de variáveis auxiliares. Por exemplo, o fragmento abaixo ilustra o jeito “errado” e depois o “certo”, no meu código:

/* ERRADO */
if (plane_distance_from_point(plane_p, pt_p) < 0.0f)
{
  ...
}

/* CERTO */
float distance;

distance = plane_distance_from_point(plane_p, pt_p);
if (distance < 0.0f)
{
  ...
}

Essa variável extra ai não faz mal algum. O compilador provavelmente se livrará dela…

É isso… depois coloco aqui mais informações sobre o estilo de desenvolvimento do projeto…