Projeto Virtual Worlds

Computação Gráfica 3D em C

Arquivos da Categoria: Meshes e Objetos

Dois casos de clipping que parecem complicados (mas não são!)

Um amigo me chama a atenção para os dois casos abaixo:

Caso 1

Caso 1

Caso 2

Caso 2

Em ambos os casos acabaremos com 3 triângulos depois dos recortes. Notem que existem 2 planos de clipping (n1n2). Isso significa que a explicação que dei no último post sobre esse assunto (este aqui) continua válido, basta aplicar as regras um plano por vez. Verifique que no caso 1, por exemplo, se escolhermos primeiro o plano n1, obteremos 2 triângulos. Depois, ambos terão que ser recortados pelo plano n2, (experimente!).

É claro que poderíamos tornar o caso 1 especial. Afinal, basta dividir o quadrilátero formado no primeiro quadrante em dois triângulos. Mas, neste caso, teríamos outros casos “especiais” a considerar (por exemplo, coloque o ponto A, do triângulo do caso 2, no terceiro quadrante, ou seja, atrás de ambos os planos, mantendo os pontos B e C no lugar onde estão!).

 

Mudança de base e “bump mapping”

Eis mais uma demonstração do poder das matrizes. Especialmente quanto falamos de mudança de base do sistema de coordenadas (ou, no jargão da álgebra linear: do subespaço vetorial).

Dê uma olhada nas 3 texturas abaixo:

Textura original, mapa de normais e textura modificada.

Textura original, mapa de normais e textura modificada.

A textura da esquerda é a original, parece com um muro de pedra, mas é “achatada” (se você rotacioná-la verá o efeito). A textura do meio, azulada, é, na verdade, um mapa com os vetores normais de cada pixel da textura, usada para causar o efeito final, o da textura da direita, onde o “rejunte” está  num nível abaixo do das pedras.

Cada componente da textura do meio equivale ao comprimento de um vetor numa base bem definida: R corresponde ao vetor associado ao eixo X; G ao Y; e B ao Z. A imagem é azulada porque o vetor Z é o mesmo do vetor normal original. O vetor normal original é o mais proeminente. Os outros dois são usados para modificar o vetor normal original. Por isso as bordas das pedras, nessa textura, têm cores tendendo ao violeta (componente R grande) ou ao “ciano” (componente G grande).

Visualmente, esses vetores correspondem ao diagrama abaixo:

Visualizando os vetores tangente e binormal.

Visualizando os vetores tangente e binormal.

Essa textura central é baseada, ou seja, tem como base do sistema de coordenadas, 3 vetores unitários: O vetor normal original e dois outros, chamados de tangente e binormal (ou bitangente). Tudo o que um shader tem que fazer para obter o vetor original é saber qual é a base e aplicar a mudança de base abaixo:

\displaystyle \vec{N}' = \begin{bmatrix} \vec{t}^T \\ \vec{b}^T \\ \vec{n}^T \end{bmatrix} \cdot \vec{N}

Onde \vec{t} é o vetor tangente, \vec{b} é o binormal e \vec{n} é o normal; obtidos do vertex buffer, junto com os outros atributos do vértice. \vec{N} são as 3 coordenadas obtidas da textura do meio e \vec{N}' é o vetor normal recalculado. Como quem fará esse calculo é o fragment shader, o vetor \vec{N} é obtido da textura via um Sampler. Ou seja, cada pixel da textura é um vetor. Mas, diferente da figura anterior, cada um dos vetores “tangentes” e o vetor “normal” são definidos para cada um dos vértices.

Note que a equação acima, na verdade, é uma conversão de base do sistema de coordenadas original, onde o vetor normal está para outro, baseado na superfície do objeto e \vec{N} “perturba” o vetor normal original… Ainda existe um passo intermediário: Os valores de \vec{N} precisam estar na faixa entre [-1,1], ao invés de [0,1], como acontece com os valores RGB numa textura. Isso pode ser facilmente feito escalonando \vec{N} duas vezes (multiplicando por 2) e subtraindo 1.

Calculando a iluminação:

Ainda não chegamos lá, mas um modelo para calcular iluminação (especialmente iluminação “ambiente”) é através do produto escalar entre o vetor normal e o vetor diretor da fonte de luz. Já que estamos “dando um solavanco” (bumping) os vetores normais de cada pixel, a impressão que ficará é a de que a superfície do objeto texturizado é, de fato, parecida com um muro, com rejunte e tudo. Pode-se enxergar esses “solavancos” na figura simplificada abaixo:

Antes e depois do "solavanco".

Antes e depois do “solavanco”.

O problema do bump mapping:

Nem tudo é perfeito… Bump Mapping tem um problema: A ilusão de profundidade só pode ser mantida em alguns casos. Se a superfície estiver voltada diretamente para a câmera, a ilusão ficará perfeita, mas rotacione a superfície e o encanto se quebra. A figura abaixo ilustra:

Bump Mapping e Parallax Mapping, lado a lado.

Bump Mapping e Parallax Mapping, lado a lado.

Do lado esquerdo temos um cubo texturizado e usando a técnica descrita acima. Do lado direito, temos o mesmo cubo, usando uma técnica diferente, mais complexa, chamada Steep Parallax Mapping.

Em ambos os casos temos o mesmo cubo (liso) com a mesma textura aplicada, mas com diferentes tipos de mapas de vetores normais, usando diferentes técnicas. Descreverei Steep Parallax Mapping assim que entendê-la melhor…

Isso não significa que bump mapping seja ruim… Dê uma olhada, por exemplo, no jogo Watch Dogs. Especialmente nos teclados que aparecem no jogo, sobre mesas… Eles são colocados lá por bump mapping e, ás vezes, dá para perceber o efeito acima… mas, só às vezes! :)

Usando papel e tesoura – recortando triângulos…

Imagine que você tenha um objeto complexo, feito com milhares de triângulos, por exemplo, este:

Mesh complexo de triângulos - formando um terreno.

Mesh complexo de triângulos – formando um terreno.

Parte dos triângulos no mesh não são visíveis para a câmera, como você pode observar. O que se deve fazer, neste caso, é recortar parte do mesh e desenhar apenas aqueles triângulos que são, de fato, visíveis. Este é um dos motivos da existência das rotinas de frustum culling. O frustum é uma figura trapezoide imaginária que existe na frente da câmera. Uma de seuas funções é usar os 6 planos que o definem para recortar os objetos que estão total ou parcialmente no seu interior e “jogar fora” todo o resto.

Uma nota de rodapé: Podemos usar sub-frustums, definidos por “portais” no mapa (que consta numa BSP) para determinar a visibilidade de objetos nas diversas regiões do mapa, a partir da posição da câmera, e recortar aqueles que não são visíveis, descartando-os.

Mas, ainda temos um problema: O que fazer com aqueles triângulos que são apenas parcialmente visíveis? Temos que pegar a tesoura e recortá-los para que caibam na parte vísivel, jogando fora as arestas! Neste processo de recorte alguns, senão muitos, triângulos que formam um objeto serão transformados em quadriláteros, como mostrado na figura abaixo:

Triângulo recortado por plano. Área cinza é descartada.

Triângulo recortado por plano. Área cinza é descartada.

O recorte é feito contra um dos planos do frustum. O que está dentro do frustum pode ser visto, o que está fora, não.

Na figura acima, ao ser recortado pelo plano o triângulo ABC é “transformado” no quadrilátero ABB’A’ (node o sentido anti-horário!). A mesma coisa não acontece se apenas um vértice do triângulo estiver do lado de “dentro” do frustum:

Triângulo recortao por plano. Área cinza é descatada.

Triângulo recortao por plano. Área cinza é descatada.

Sempre que temos apenas um dos vértices dentro do frustum vamos obter um triângulo, no recorte. Como regra geral, se apenas um vértice encontra-se do lado de fora do frustum, acabamos com um quadrilátero. Mas, como estamos lidando apenas com triângulos, precisaremos transformar um polígono (no caso, um quadrilátero) em um conjunto de triângulos. Esse processo chama-se tesselation. No nosso caso, fazer isso é simples. Basta escolher um dos vértices originais dentro do frustum e um dos novos vértices, no lado oposto, que está sobre o plano de clipping:

"Tesselando" o quadrilátero em 2 triângulos.

“Tesselando” o quadrilátero em 2 triângulos.

Outra coisa que você pode notar é que, não importa como os triângulos estejam dispostos, precisaremos obter dois novos vértices em dois dos lados (edges), exceto em um único caso: Se um dos vértices estiver precisamente sobre o plano de clipping. Neste caso, a área resultante também não precisará passar pelo processo de tesselation, já que a área “branca” continuará sendo um triângulo. A maneira de resolver essa possibilidade é considerar que se a distância do vértice ao plano for menor ou igual a zero, então ele está “atrás” do plano, deixando um vértice à frente o outro atrás.

Claro, que se todos os 3 vértices estiverem na frente do plano, nenhum clipping é necessário!

Bem… cadê o código para realizar o clippingtesselation? Você não vai encontrá-lo no código em C do projeto…. Isso é tarefa para os shaders. Se processarmos cada triângulo da cena sequencialmente, o tempo gasto será excessivo e os shaders são processos que executam em paralelo. No caso, os geometry shaderstesselation shaders operam em conjuntos de vértices. Se sua placa de vídeo pode usar 1024 shaders, por exemplo, cerca de 1024 triângulos podem ser clippadostesselados (se é que esses verbos existem) ao mesmo tempo.

Depois de explicar todos os tipos de shaders e seus funcionamentos, explicarei como implementar clipping.

Árvores de Particionamento Espacial Binarias (Binary Spatial Partitioning Trees – BSPs)

Às vezes a coisa é simples e eu faço uma confusão danada procurando significados escondidos que não estão lá… Esse foi o meu problema com as BSPs, que existem para solucionar um único problema:

Como podemos saber quais polígonos (objetos) devem ser desenhados antes de outros sem fazer muitas comparações?

O problema pode ser respondido organizando os polígonos antes de desenhá-los. Poderíamos ter uma lista com todos os polígonos e colocá-los em ordem com algum algoritmo tipo quick sort ou bubble sort, mas isso tomaria um tempo enorme. Essa aproximação ao problema torna impossível executar uma animação gráfica em tempo real, já que esses métodos levam tempo de, pelo menos, da ordem de O(N) ou O(N2), ou pior. Qual é a outra estrutura que podemos usar onde os itens são automaticamente colocados de forma ordenada e, na pesquisa, o tempo é proporcional a O(log2N)? Isso mesmo: Árvores Binárias!

Mas não podemos usar a tradicional árvore binária onde há apenas uma comparação de valores entre os nós. Nossa árvore precisa ter dois tipos de nós: Os nós contendo informações sobre o “mundo” e os nós contendo informações sobre os polígonos que serão desenhados em cada pedaço desse mundo. Precisamos dividir nosso mundo em pedaços, chamados partições (daí o nome “Particionamento Espacial”). Nossa árvore tem, então, nós (nodes) contendo planos e nós “folha” (leaf nodes), contendo os polígonos que pertencem a uma partição do mundo.

Como acredito que já tenha mostrado, planos são artefatos matemáticos onde todos os pontos contidos nele obedecem uma equação simples:

\displaystyle \vec{n}\cdot\dot{p}+d=0

Onde \vec{n} é o vetor unitário normal (perpendicular) ao plano, \dot{p} é a coordenada de um ponto na superfície do plano e d é a distância deste a origem do sistema de coordenadas à qualquer ponto do plano (por isso d é calculado pela projeção sobre o vetor normal e tem seu sinal invertido!). A operação “∙” é um produto escalar, o que denota a projeção do ponto \dot{p} sobre o vetor normal \vec{n}. O ponto \dot{p} é a variável da equação.

Você também encontra a equação de um plano, em livros de geometria, escrito dessa maneira:

\displaystyle Ax+By+Cz+D=0

Onde A, B e C são os componentes X, Y e Z do vetor unitário normal \vec{n}, as variáveis x, y e z são as coordenadas do ponto \dot{p} e D é a distância da projeção de \dot{p} sobre \vec{n}, em relação à origem… Com isso, podemos determinar se um outro ponto qualquer \dot{q} está na frente, sobre ou atrás do plano definido pela equação. E, só para constar, prefiro a equação vetorial… Acho naus intuitiva e elegante!

Voltando à BSP, se cada nó que não é leaf contém a equação do plano que particiona o mundo (ou o sub-mundo, digamos assim) em dois, podemos determinar se um ponto \dot{q} qualquer está na frente ou atrás do plano em questão. Basta colocar as coordenadas do ponto \dot{q} no lugar do ponto \dot{p} e verificar o valor final da equação do plano… Se o valor for zero, o ponto encontra-se no plano, se for maior que zero, está na frente, caso contrário, atrás. Ao determinar isso podemos decidir se vamos continuar percorrendo a árvore do lado da frente ou de trás do plano, repetindo o teste com os outros planos que encontrarmos até acharmos um nó leaf.

O que queremos? Desenhar as regiões em ordem de proximidade…

A primeira coisa que faremos é determinar o nó leaf onde o nosso ponto \dot{p} está contido (agora uso o ponto \dot{p} como o ponto da câmera, não o da equação)… Considere esse simples mapa, onde as partes pretas são paredes (que considerarei como tendo espessura muito fina, para facilitar a explicação) e as áreas delimitadas pelos planos (linhas vermelhas) e paredes fronteiriças são “setores” definidos pelas partições (o parte pontilhada do “plano” c tem uma explicação que explicarei logo):
map
O plano a divide o mapa na região A e nas regiões B, C e D. Ele divide o mapa em duas partes…

O plano b divide o lado da frente do plano a nas regiões B, de um lado, e C e D, do outro.
Por sua vez, o plano c divide C e D, que eram uma região só, em duas partes.

Se escolhermos o plano b para ser o nó raiz de nossa árvore, teremos:

tree
Onde, o que está à esquerda de um nó é tudo aquilo que está atrás dele e, por consequência, o que está à direita, está na frente. Assim, o plano a está atrás do plano b e região D está na frente do plano b (mas, atrás do plano c). Eu escolhi o plano b como raiz por que sabia, de antemão, que obteria uma árvore perfeitamente balanceada. A escolha do plano divisor raiz é essencial para obter uma árvore “ótima”. Mas isso pode ser conseguido usando-se um algoritmo de árvore balanceada…

Agora que temos nossa BSP montada, tudo o que temos que fazer é percorrê-la em pre-order (raiz primeiro, depois os nós filhos). A cada visita a um nó não leaf (os nós pretos) temos que fazer o teste para saber se nossa câmera está na frente ou atrás do plano do nó. Suponha que nossa câmera esteja na parte inferior da região A.

Estamos no nó raiz: A câmera encontra-se em frente ou atrás do plano b? Para saber isso basta usar a equação do plano, lá em cima… No caso, a câmera está atrás do plano b, então vamos, recursivamente, para o nó da esquerda e fazemos a pergunta de novo, mas para o plano a. Ora, a câmera está atrás do plano a, então vamos para a esquerda, de novo, e encontramos o nó leaf contendo a região A. Este nó contém todos os polígonos que estão na região, então os desenhamos todos, exceto aqueles que falham nos testes de visibilidade (frunstum culling e aqueles cujos vetores normais estejam na mesma direção do vetor da câmera, por exemplo). Já que o nó A não tem filhos, a rotina recursiva retornará, fazendo com que o nó B, filho do nó do plano a, seja visitado. Ao retornar, o nó de c será visitado e um novo teste com o plano é feito. Nossa câmera pode estar ou não atrás do plano c (e eis o motivo do tracejado no mapa). Já nossa câmera está na parte inferior da região A, ela estará atrás do plano c, fazendo com que o nó da região D seja visitada e depois o nó da região C.

Note que as regiões visitadas seguiram a ordem A, B, D e C.

Se a câmera estivesse na região superior de B, a ordem seria: B, A, C e D (faça o teste!). Se estivesse na região D, teríamos: D, C, B e A… Repare que a ordem das regiões segue um padrão útil: São regiões ordenadas de acordo com a proximidade de onde câmera está!

E é só para isso que serve o particionamento espacial: Colocar as regiões em ordem! A partir daí, podemos usar outros algoritmos (que usam a BSP) para determinar quais superfícies escondidas podem ser removidas (Hidden Surface Removal) e qual conjunto de polígonos são potencialmente visíveis (Potentially Visible Set), mas isso eu deixo para outra ocasião… O código para percorrer a árvore BSP, uma vez que ela tenha sido montada, é mais ou menos esse:

struct bspnode_s {
  struct bspnode_s *front, *back;
  float plane[4]; // equação do plano, para nós não "folha".
  struct objectlist_s objlist; // Lista de objetos na região (nó folha).
};

void bsp_traverse(struct bspnode_s *node)
{
  struct bspnode_s *f, *b;

  if (node->front == NULL && node->back == NULL)
    drawobjlist(node->objlist);
  else
  {
    // Assume que a câmera esteja na frente do plano.
    f = node->front;
    b = node->back;

    // A câmera está atrás do plano? Então trocamos a ordem de pesquisa!
    if (PlaneGetDistance(node->plane, camera) < 0.0f)
    {
      f = b;
      b = node->front;
    }

    // Recursivamente visita os nós filhos, na ordem especificada no teste acima.
    bspnode_traverse(f);
    bspnode_traverse(b);
  }
}

O código que “compila” a BSP eu também deixo para outra ocasião. Ele é meio complicado porque envolve alguns detalhes interessantes, como aquele do plano pontilhado e outros, como, determinação de conjunto convexo de polígonos, sem contar com o balanceamento da árvore. Sobre esse último item, em breve escreverei um artigo para o Bit Is Myth sobre Red-Black Trees.

O motivo de ter descartado o formato Wavefront

Estou trabalhando na carga de objetos construídos a partir do Blender. Ao invés de usar o formato binário do editor preferi usar um formato mais “amigável” para importar os objetos e, talvez, criar meu próprio formato binário. Um dos formatos mais simples de lidar é o da WaveFront Technologies (a mesma empresa que criou o Maya)… Só que vi que o exporter default do Blender para esse formato não me dá aquilo que desejo:

  1. Aparentemente os agrupamentos de objetos não são exportados;
  2. exporter não otimiza os meshes para triangle strips ou triangle fans;

Um exemplo é este: Criei dois cubos (e “triangulei” as faces!). O da direita tem o nome de Cube1 e o da esquerda, Cube2. Coloquei ambos os objetos num grupo chamado Group1 e exportei para .OBJ. Abaixo você vê um grab da tela do Blender e o arquivo cubes.obj gerado:

Cubes

Eis o arquivo cubes.obj:

# Blender v2.63 (sub 0) OBJ File: 'untitled.blend'
# www.blender.org
mtllib cubes.mtl
o Cube2
v -1.000000 -1.000000 -1.000000
v -1.000000 -1.000000 1.000000
v -3.000000 -1.000000 1.000000
v -3.000000 -1.000000 -1.000000
v -1.000000 1.000000 -0.999999
v -1.000001 1.000000 1.000001
v -3.000000 1.000000 1.000000
v -3.000000 1.000000 -1.000000
vn 0.000000 -1.000000 0.000000
vn -0.000000 1.000000 0.000000
vn 1.000000 -0.000000 0.000000
vn -0.000000 -0.000000 1.000000
vn -1.000000 -0.000000 -0.000000
vn 0.000000 0.000000 -1.000000
vn 1.000000 0.000000 0.000001
usemtl Material
s off
f 1//1 2//1 3//1
f 5//2 8//2 6//2
f 1//3 5//3 2//3
f 2//4 6//4 3//4
f 3//5 7//5 8//5
f 5//6 1//6 4//6
f 4//1 1//1 3//1
f 8//2 7//2 6//2
f 5//7 6//7 2//7
f 6//4 7//4 3//4
f 4//5 3//5 8//5
f 8//6 5//6 4//6
o Cube1
v 3.000000 -1.000000 -1.000000
v 3.000000 -1.000000 1.000000
v 1.000000 -1.000000 1.000000
v 1.000000 -1.000000 -1.000000
v 3.000000 1.000000 -0.999999
v 2.999999 1.000000 1.000001
v 1.000000 1.000000 1.000000
v 1.000000 1.000000 -1.000000
usemtl Material
s off
f 9//1 10//1 11//1
f 13//2 16//2 14//2
f 9//3 13//3 10//3
f 10//4 14//4 11//4
f 11//5 15//5 16//5
f 13//6 9//6 12//6
f 12//1 9//1 11//1
f 16//2 15//2 14//2
f 13//7 14//7 10//7
f 14//4 15//4 11//4
f 12//5 11//5 16//5
f 16//6 13//6 12//6

Algumas coisas que você pode observar:

  1. O grupo Group1 não foi exportado;
  2. A lista de vértices e vetores normais (e se tivesse, a lista de coordenadas de texturas) são compartilhadas pelos objetos − e isso é bom! − Mas, não há quaisquer informações sobre strips ou fans;

Eu ainda não sei se formatos mais “modernos” como COLLADA e X3D fazem esses tipos de otimizações. Mas, estou estudando ambos para ver se abandono de vez o formato Wavefront.

Abaixo, temos o código (parcial) de como montar um objeto lendo o arquivo .OBJ. Deixei o tratamento de texturas e outros “comandos” fora desde código para ilustrar a facilidade de lidar com o formato… Começe olhando para LoadOBJ().

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>
#include <malloc.h>

/* Tamanho máximo de uma linha do arquivo .OBJ. */
#define MAX_LINE_SIZE 255

/* Mantém a lista de vértices e normais. */
static float *vertices = NULL;
static float *normals = NULL;
static int numvertices = 0;
static int numnormals = 0;

/* Estrutura que contém os índices dos triangulos. */
struct triangle_s {
  float vertice[3];
  float normal[3];
};

/* Estrutura de um "objeto". */
struct object_s {
  char name[32];

  struct triangle_s *triangles;
  int numtriangles;
};

/* Mantém a lista de "objetos" */
struct object_s *objects = NULL;
int numobjects = 0;

/* Realoca espaço para uma "lista" */
static void *grow_array(void **pp, size_t itemsize, size_t numitems)
{
  void *tmpp;

  if ((tmpp = realloc(*pp, itemsize * numitems)) != NULL)
    *pp = tmpp;

  return tmpp;
}

/* Lê uma linha do arquivo, retirando '\n' do final e
   retornando um ponteiro para o primeiro caracter não 'vazio'. */
static char *ReadLine(FILE *f, char *buffer, size_t max_size)
{
  char *cp;

  if ((cp = fgets(buffer, max_size, f)) != NULL)
  {
    char *tmpcp;

    cp += strspn(buffer, " \t\r");
    if ((tmpcp = strchr(cp, '\n')) != NULL)
      *tmpcp = '';
  }
  return cp;
}

static void Vector3Copy(float *dest, const float *src);
static int GetAllVerticesAndNormals(FILE *fin);
static int GetObjectsAndTriangles(FILE *fin);

/* Carrega .OBJ, retorna -1 em caso de erro ou 0 se ok. */
int LoadOBJ(char *filename)
{
  FILE *fin;
  jmp_buf jb; /* Usando setjmp() para tratar erro. */

  if ((fin = fopen(filename, "rt")) == NULL)
    return -1;

  if (setjmp(jb))
  {
    int i;

    fclose(fin);

    /* Joga todos as listas "no lixo" e retorna -1. */
    free(vertices); vertices = NULL; numvertices = 0;
    free(normals); normals = NULL; numnormals = 0;
    for (i = 0; i < numobjects; i++)
    {
      free((objects + i)->triangles);
      (objects + i)->triangles = NULL;
      (objects + i)->numtriangles = 0;
    } 
    free(objects); objects = NULL; numobjects = 0;

    return -1;
  }

  /* A leitura do arquivo .OBJ é feita em dois passos. Primeiro,
     lemos todos os vértices, vetores e vetores normais. */
  if (GetAllVerticesAndNormals(fin) < 0)
    longjmp(jb, 1);

  /* Passo 2: Lemos os objetos e suas faces, associando-as com os
     objetos. */
  if (GetObjectsAndTriangles(fin) < 0)
    longjmp(jb, 1);

  /* Neste ponto não precisamos mais dos vetores vertices e normals. */
  free(vertices); vertices = NULL; numvertices = 0;
  free(normals); normals = NULL; numnormals = 0;

  fclose(fin);

  /* Agora temos a lista de objetos em "objects" pronta para ser
     colocada em vertex buffers e enviadas ao OpenGL via DrawArrays(). */
  return 0;
}

/* Lê todos os vértices e vetores normais do arquivo. */
static int GetAllVerticesAndNormals(FILE *fin)
{
  char line[MAX_LINE_SIZE+1];
  char *cp;

  fseek(fin, 0L, SEEK_SET);

  while ((cp = ReadLine(fin, line, MAX_LINE_SIZE)) != NULL)
  {
    char *cp2;

    /* Isola o comando dos seus parâmetros. */
    if ((cp2 = strpbrk(cp, " \t")) != NULL)
      *cp2++ = '';

    /* Temos um vértice? */
    if (strcasecmp(cp, "v") == 0)
    {
      float *vp;

      if ((vp = grow_array((void **)&vertices, 3*sizeof(float), 
                  numvertices+1)) == NULL)
        return -1;
 
      vp += 3 * numvertices++; // Aponta para último item.

      /* Eu DEVERIA testar o retorno de sscanf(), mas... What the hell,
         isto é só um exemplo, certo? */
      sscanf(cp2, "%f %f %f", vp, vp + 1, vp + 2);
    }

    /* Temos um vertor normal? */
    if (strcasecmp(cp, "vn") == 0)
    {
      float *np;

      if ((np = grow_array((void **)&normals, 3*sizeof(float), 
                  numnormals+1)) == NULL)
        return -1;
 
      np += 3 * numnormals++; // Aponta para último item.

      /* Eu DEVERIA testar o retorno de sscanf(), mas... What the hell,
         isto é só um exemplo, certo? */
      sscanf(cp2, "%f %f %f", np, np + 1, np + 2);
    }
  } 

  return 0;
}

/* Lê objetos e "faces" */
static int GetObjectsAndTriangles(FILE *fin)
{
  char line[MAX_LINE_SIZE+1];
  char *cp;
  struct object_s *op = NULL;
  int i;

  fseek(fin, 0L, SEEK_SET);

  while ((cp = ReadLine(fin, line, MAX_LINE_SIZE)) != NULL)
  {
    char *cp2;

    /* Isola o comando dos seus parâmetros. */
    if ((cp2 = strpbrk(cp, " \t")) != NULL)
      *cp2++ = '';

    /* Temos um novo objeto? */
    if (strcasecmp(cp, "o") == 0)
    {
      if ((op = grow_array((void **)&objects, sizeof(struct object_s), 
                  numobjects + 1)) == NULL)
        return -1;

      op += numobjects++;

      strcpy(op->name, cp2);
      op->triangles = NULL;
      op->numtriangles = 0;
    }

    /* Temos um triangulo? */
    if (strcasecmp(cp, "f") == 0)
    {
      int indexes[6];
      struct triangle_s *tp;

      /* Temos que ter alocado o último objeto, pelo menos! */
      if (op == NULL)
        return -1;

      if ((tp = grow_array((void **)&op->triangles, 
                           3*sizeof(struct triangle_s), 
                           op->numtriangles + 1)) == NULL)
        return -1;

      tp += 3*op->numtriangles++;

      /* Eu DEVERIA testar o retorno de sscanf(), mas... What the hell,
         isto é só um exemplo, certo? */

      /* Obtém os índices. */
      sscanf(cp2, "%d//%d %d//%d %d//%d",
        indexes, indexes + 1,
        indexes + 2, indexes + 3,
        indexes + 4, indexes + 5);

      /* Usa os índices (que são baseados em 1, não em 0!) para
         copiar os vetores. */
      for (i = 0; i < 3; i++, tp++)
      {
        Vector3Copy(tp->vertice, vertices + 3*indexes[0+3*i] - 1);
        Vector3Copy(tp->normal, normals + 3*indexes[1+3*i] - 1);
      }
    }
  }

  return 0;
}

/* Copia um vetor para outro. */
static void Vector3Copy(float *dest, const float *src)
{
  dest[0] = src[0];
  dest[1] = src[1];
  dest[2] = src[2];
}

PS: O código acima é um exemplo e não for depurado!

Na frente da onda

Eu reluto em usar orientação à objetos em meus códigos. Os motivos? São dois: Performance e tamanho do código. Se você usar os fundamentos da OO (herança, polimorfismo e encapsulamento) terá um monstrengo de código binário nas mãos. Em meus testes, usar C++ ao invés de C aumenta o código em, pelo menos, 30% do tamanho. Além disso, um conjunto de estruturas e rotinas são adicionadas ao código final que você não tem o mínimo controle… Ou seja, se o compilador resolver traduzir seu código da maneira que ele bem entender, estará adicionando bugs irreparáveis (ou muito difíceis de debugar).

Dito isso, como vocês podem ler neste artigo que escrevi para o Bit Is Myth, me rendi aos containers da STL. Uma demonstração da força e facilidade de uso é a leitura de modelos, no formato da Wavefront Technologies (criadora do Maya):

#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <GL/gl.h>

struct vec3 { float x, y, z; };
struct indexes { int v, n; };

GLuint readObj(const char *filename)
{
#define MAX_LINE_SIZE 256

  static char line[MAX_LINE_SIZE+1];
  static char auxBuffer[64];
  FILE *f;
  GLuint displayList;
  vec3 v;
  indexes i, j, k;
  std::vector<vec3> vertices;
  std::vector<vec3> normals;
  std::vector<indexes> idxs;
  std::vector<indexes>::iterator nIdx;

  if ((f = fopen(filename, "rt")) == NULL)
  {
    fprintf(stderr, "Unable to open file.\n");
    exit(EXIT_FAILURE);
  }

  /* Aqui eu leio a linha completa para depois
     separar, usando sscanf, os tokens e
     seus dados. */
  while (fgets(line, MAX_LINE_SIZE, f) != NULL)
  {
    /* NOTA: Não precisamos nos preocupar com
             o '\n' no final da string! */

    /* Pega o token. */
    if (sscanf(line, "%s", auxBuffer) == 1)
    {
      if (strcmp(auxBuffer, "v") == 0) /* vertices*/
      {
        sscanf(line, "v %f %f %f", &v.x, &v.y, &v.z);
        vertices.push_back(v);
      }
      else
      if (strcmp(auxBuffer, "vn") == 0) /* normais */
      {
        sscanf(line, "vn %f %f %f", &v.x, &v.y, &v.z);
        normals.push_back(v);
      }
      else
      if (strcmp(auxBuffer, "f") == 0) /* faces (índices) */
      {
        /* NOTA: Não estou usando coordenadas de texturas. */
        /* NOTA: Todas as faces precisam ser triangulares. */
        sscanf(line, "f %d//%d %d//%d %d//%d",
          &i.v, &i.n, &j.v, &j.n, &k.v, &k.n);

        /* Armazena os 3 índices */
        idxs.push_back(i);
        idxs.push_back(j);
        idxs.push_back(k);
      }
    }
  }

  fclose(f);

  /* Usando display lists pq o teste foi feito com
     OpenGL 1.4 (vertex buffers existem no 1.5+). */
  displayList = glGenLists(1);

  /* 0 significa erro! */
  if (displayList != 0)
  {
    glNewList(displayList, GL_COMPILE);
      glBegin( GL_TRIANGLES );

      /* Usa o iterador para o vector para obter os índices */
      for (nIdx = idxs.begin(); nIdx != idxs.end(); ++nIdx)
      {
        /* NOTE: indexes begin @ 1, instead of 0 */
        v = normals[nIdx->n - 1];
        glNormal3fv( (float *)&v );

        v = vertices[nIdx->v - 1];
        glVertex3fv( (float *)&v );
      }

      glEnd();
    glEndList();
  }

  return displayList;

#undef MAX_LINE_SIZE
}

Vale observar que não estou usando Vertex Buffer Objects porque este teste foi criado numa máquina que não implementa OpenGL 1.5 ou superior (Um LeNovo, com chipset Intel obsoleto, que só implementa OpenGL 1.4). Então, fui obrigado a usar display lists.

Mas, o que quero demonstrar é o uso do container sequencial vector e na leitura de um modelo qualquer gerado no Blender ou em qualquer software de modelamento 3D que preste.

Como os containers vector são declarados como locais à função, os arrays são alocados no heap e dealocados logo antes de saírem do escopo da função. É como se tivéssemos um garbage collector, sem a inconveniência de deixar o espaço alocado “no limbo” por algum tempo. a classe, por sí só, ocupa pouco mais de 8 bytes na pilha (experimente pegar o tamanho do objeto com sizeof)… O container não faz múltiplas realocações à medida que adicionamos itens e podemos pegar o ponteiro para o primeiro item com a garantia de que os próximos itens seguem o primeiro (por isso é possível usar as funções glNormal3fv e glVertex3fv).

Quanto ao formato do arquivo de modelos da Wavefront, nada mais simples: Todos os vértices do modelo são definidos em linhas separadas iniciadas com o token ‘v’, seguido das 3 coordenadas (x,y,z). Os vetores normais seguem o mesmo princípio, só que o token é ‘vn’. Com base nessas duas listas usamos a lista de índices que compõem os triângulos do objeto (token ‘f’, seguindo de 3 índices: vertice/textura/normal – Note que não gerei meus arquivos .OBJ com  coordenadas de texturas, portanto o componente central é vazio – se houvessem coordenadas de texturas, então uma lista com o token ‘vt’ estaria presente, bem como tokens ‘usemtl’, dentro da lista de faces).

Um cubo, por exemplo, pode ser definido, num arquivo .OBJ, assim:

# Lista de vértices
v 1.000000 -1.000000 -1.000000
v 1.000000 -1.000000 1.000000
v -1.000000 -1.000000 1.000000
v -1.000000 -1.000000 -1.000000
v 1.000000 1.000000 -1.000000
v 1.000000 1.000000 1.000000
v -1.000000 1.000000 1.000000
v -1.000000 1.000000 -1.000000

# Lista de normais
vn 0.000000 0.000000 -1.000000
vn -1.000000 -0.000000 -0.000000
vn -0.000000 -0.000000 1.000000
vn 1.000000 -0.000000 0.000000
vn 1.000000 0.000000 0.000001
vn -0.000000 1.000000 0.000000
vn 0.000000 -1.000000 0.000000

# Lista de faces
f 5//1 1//1 8//1
f 1//1 4//1 8//1
f 3//2 7//2 8//2
f 3//2 8//2 4//2
f 2//3 6//3 3//3
f 6//3 7//3 3//3
f 1//4 5//4 2//4
f 5//5 6//5 2//5
f 5//6 8//6 7//6
f 5//6 7//6 6//6
f 1//7 2//7 3//7
f 1//7 3//7 4//7

Nada mais simples! A desvantagem é que precisamos ler as listas completamente para montarmos a geometria do objeto de acordo com as faces. A coisa seria mais fácil se os vértices já estivesse pré-ordenados e com seus vetores normais e de textura (se tivessem) associados a eles. Ficaria mais fácil de montar um Vertex Buffer Object… C’est la vie…

Como você deve ter observado, neste exemplo, tive que tomar cuidado com algumas coisas:

  1. Todas as faces têm que ser triangulares;
  2. Não usei texturas.

Assim, no Blender, tive que “triangulizar” o modelo (no Edit Mode, selecionar Quads to Tris, no menu Faces), depois pedi para recalcular os vetores normais (just in case!) e, finalmente, ao exportar, deselecionei a geração das coordenadas UV, selecionei Normals e High Quality Normals (porque não quis usar um vetor pré-calculado com vetores normais, como é usado em modelos MD2). Selecionei também “Triangulate” (também just in case!) e voilà!

O modelo do macaco, com a aplicação do modificador de subdivisão (para aumentar o número de triângulos) ficou porreta, depois de renderizado no OpenGL:

Monkey, renderizado a partir de um modelo OBJ, gerado no Blender.


UPDATE: Recentemente (2014) abandonei o formato Wavefront porque ele não atende minhas necessidades. Ainda, coloquei um código de teste mais “completo” e “confiável” em posts mais recentes.