Sistemas Gráficos 3D

Projeto final

Linguagem de Descrição de Cena

A linguagem de descrição de cena escolhida foi o LISP, pela simplicidade da sintaxe, o que evita o uso do lex e do yacc. Assim, a análise léxica é feita ao mesmo tempo que a sintática. A função responsável por ler uma lista é a função tk_read_list(FILE*):

tkList tk_read_list(FILE* inputFile)
  {
    tkList l; char c; real r; char s[200]; char* p;
    l = tk_empty_list();
    if (getc(inputFile) != '(')
      {
	tk_die("no opening parenthesis");
      }
    while (1)
      {
	c = getc(inputFile);
	if (c == ')')
	  {
	    return l;
	  }
	else if (c == ' ' || c == '\n' || c == '\t')
	  {
	    continue;
	  }
	else if (c == '.' || c == '-' || ('0' <= c && c <= '9'))
	  {
	    ungetc(c, inputFile);
	    fscanf(inputFile, "%lf", &r);
	    tk_append_child(&l, tk_make_child(TK_CHILD_FLOAT, \
					      NULL, r, tk_empty_list()));
	    continue;
	  }
	else if (('a' <= c && c <= 'z') || (c == '_'))
	  {
	    p = s;
	    do
	      {
		*p++ = c;
		c = getc(inputFile);
	      } while (('a' <= c && c <= 'z') || (c == '_'));
	    ungetc(c, inputFile);
	    *p = '\0';
	    tk_append_child(&l, tk_make_child(TK_CHILD_STRING, \
					      s, 0, tk_empty_list()));
	    continue;
	  }
	else if (c == '(')
	  {
	    ungetc(c, inputFile);
	    tk_append_child(&l, tk_make_child(TK_CHILD_LIST, \
					      NULL, 0, \
					      tk_read_list(inputFile)));
	    continue;
	  }
	else
	  {
	    sprintf(s, "unrecognized character: %c", c);
	    tk_die(s);
	  }
      }
  }

Análise semântica

A cena é, na SDL, encapsulada por um operador (scene ...), que contém todas as primitivas da cena. Por isso, uma única chamada ao tk_read_list(FILE*) é suficiente para carregar a lista que corresponde à cena. Para converter essa lista em objetos, é necessário efetuar uma chamada à função tk_parse_scene(tkList):

tkScene tk_parse_scene(tkList list)
  {
    int i;
    tkScene S;
    tkCamera C;
    tkLight W;
    tkMesh M;
    tkList L;
    if (strcmp(tk_get_string(list, 0), "scene"))
      {
	tk_die("invalid syntax: (scene <camera>+ <light>+ <mesh>+)");
      }
    S = tk_empty_scene();
    for (i = 1; i < list.numChildren; i++)
      {
	L = tk_get_list(list, i);
	if (!strcmp(tk_get_string(L, 0), "camera"))
	  {
	    C = tk_parse_camera(L);
	    tk_append_camera(&S, C);
	  }
	else if (!strcmp(tk_get_string(L, 0), "light"))
	  {
	    W = tk_parse_light(L);
	    tk_append_light(&S, W);
	  }
	else
	  {
	    M = tk_parse_mesh(L);
	    if (M.numVertexes != 0)
	      {
		tk_append_mesh(&S, M);
	      }
	  }
      }
    return S;
  }

Exemplo de cena

(scene
    (camera
        (center ( 0  0  5))
        (normal ( 0  0 -1))
        (up     ( 0  1  0))
        (near_plane 1)
        (focal_plane 2)
        (far_plane 20)
    )
    (camera
        (center ( 5  0  0))
        (normal (-1  0  0))
        (up     ( 0  0  1))
        (near_plane 1)
        (focal_plane 2)
        (far_plane 20)
    )
    (camera
        (center ( 0  8  5))
        (normal ( 0  -1.6 -1))
        (up     ( 0  2  1))
        (near_plane 1)
        (focal_plane 2)
        (far_plane 20)
    )
    (light
        (center (3 3 3))
        (color (1 1 0.9))
        (intensity 30)
    )
    (rotate (0 0 1) 90
        (revolution_solid
            (vertex (0.1  0.0  0.0))
            (vertex (0.1  1.0  0.0))
            (color  (0.6  0.6  0.6))
        )
    )
    (revolution_solid
        (vertex (0.1  0.0  0.0))
        (vertex (0.1  1.0  0.0))
        (color  (0.0  0.6  0.0))
    )
    (rotate (1 0 0) -90
        (revolution_solid
            (vertex (0.1  0.0  0.0))
            (vertex (0.1  1.0  0.0))
            (color  (0.0  0.0  0.6))
        )
    )
    (translate (1 0 0)
        (revolution_solid
            (vertex (0.3 0.1  1.1))
            (vertex (0.3 0.6 -1.3))
            (vertex (0.4 0.7  0.0))
            (color  (1.0  0.0 0.0))
        )
    )
    (translate (0 0 1)
        (revolution_solid
            (vertex (0.3 0.1  1.1))
            (vertex (0.3 0.6 -1.3))
            (vertex (0.4 0.7  0.0))
            (color  (0.0  0.0 1.0))
        )
    )
)

Arquitetura

Todas os objetos do sistema são de três tipos:

As câmeras e luzes são definidas pelas primitivas (camera ...) e (light ...). Malhas triangulares podem ser geradas por vários operadores, alguns dos quais apenas transformam as malhas. Por isso, o TK possui um dicionário que associa os nomes dos operadores às suas funções geradoras:

static tkMeshParserTableEntry tkMeshParserTable[] = {
  {"triangle_mesh", tk_parse_triangle_mesh},
  {"translate", tk_parse_translate},
  {"rotate", tk_parse_rotate},
  {"scale", tk_parse_scale},
  {"group", tk_parse_group},
  {"revolution_solid", tk_parse_revolution_solid},
  {"extrusion_solid", tk_parse_extrusion_solid},
  {NULL, NULL}
};

Para criar uma malha, deve ser invocada a função tk_parse_mesh(tkList*).

tkMesh tk_parse_mesh(tkList list)
  {
    int i;
    if (list.numChildren > 0)
      {
	for (i = 0; tkMeshParserTable[i].keyword != NULL; i++)
	  {
	    if (!strcmp(tkMeshParserTable[i].keyword, \
	                tk_get_string(list, 0)))
	      {
		return tkMeshParserTable[i].parser(list);
	      }
	  }
      }
    return tk_empty_mesh();
  }

Os operadores (translate ...), (rotate ...) e (scale ...) aceitam, além dos parâmetros usuais, um parâmetro que é uma outra malha:

tkMesh tk_parse_translate(tkList list)
  {
    int i;
    tkMesh M;
    tkPoint3D v;
    if (strcmp(tk_get_string(list, 0), "translate"))
      {
	tk_die("invalid syntax: (translate <point> <mesh>)");
      }
    v = tk_parse_point3d(tk_get_list(list, 1));
    M = tk_parse_mesh(tk_get_list(list, 2));
    for (i = 0; i < M.numVertexes; i++)
      {
	M.vertexes[i] = tk_add3d(M.vertexes[i], v);
      }
    return M;
  }

No entanto, esses operadores aceitam apenas uma malha de entrada. Por isso, é necessária a implementação do operador (group ...) que costura duas ou mais malhas para formar uma única malha maior.

tkMesh tk_parse_group(tkList list)
  {
    int i, j, oldV;
    tkMesh M, N;
    M = tk_empty_mesh();
    if (strcmp(tk_get_string(list, 0), "group"))
      {
	tk_die("invalid syntax: (group <mesh>+)");
      }
    for (i = 1; i < list.numChildren; i++)
      {
	N = tk_parse_mesh(tk_get_list(list, i));
	oldV = M.numVertexes;
	for (j = 0; j < N.numVertexes; j++)
	  {
	    tk_append_vertex(&M, N.vertexes[j]);
	  }
	for (j = 0; j < N.numTriangles; j++)
	  {
	    N.triangles[j].v[0] += oldV;
	    N.triangles[j].v[1] += oldV;
	    N.triangles[j].v[2] += oldV;
	    tk_append_triangle(&M, N.triangles[j]);
	  }
      }
    return M;
  }

Visualização

A visualização do TK é feita através de subdivisão — todas as superfícies são divididas em triângulos, convertendo-as em malhas triangulares (esse é um dos motivos pelos quais malhas triangulares são primitivas). Depois, cada um desses triângulos é rasterizado e desenhado via um z-buffer, levando em conta fatores como iluminação.

Gerenciamento de cores

Um problema que torna-se bastante evidente durante a renderização é a limitação do número de cores da imagem. Apesar das 256 cores serem suficientes para interação com o usuário, a renderização final usa transições suaves entre as cores, e, por isso, geralmente se utiliza de bem mais do que 256 cores. Como lidar com esse problema?

Solução 1: Usar uma paleta uniforme

Uma solução é usar uma paleta de tamanho m3 e adicionar à paleta cores da forma (i/(m-1), j/(m-1), k/(m-1)), onde i, j e k variam no conjunto {0, 1, ..., m-1}. A quantização é feita através do algoritmo vizinho-mais-próximo.

Vantagens
Desvantagens

Solução 2: Escolha dinâmica da paleta

Outra solução é criar uma estrutura de dados para armazenar os pedidos de ternos de cores. Periodicamente, o programa poderia aplicar um algoritmo como populosidade ou corte mediano para escolher a paleta ideal.

Vantagens
Desvantagens

Solução 3: Criar uma paleta para cada canal de cor

Esta solução, que foi a adotada pelo programa, consiste em criar uma paleta só com cores da forma (t, 0, 0), e analogamente para as outras cores. A quantização é feita com o algoritmo de vizinho-mais-próximo (que equivale a uma projeção). Para obter a imagem final, são renderizadas três imagens, que são subseqüentemente combinadas para formar a imagem final.

Vantagens
Desvantagens

Exemplos

Exemplo 1: Cubo

Esta cena exemplifica como adicionar uma malha triangular a uma cena. O cubo é composto de 12 triângulos e oito vértices. Cada face é pintada de uma cor diferente, exemplificando que os triângulos da malha podem ter cores distintas. Apesar de que este recurso não foi implementado, é possível usar um método similar para implementar uma primitiva de texturização — basta efetuar uma subdivisão sobre a malha e pintar os triângulos da cor do pixel que lhe corresponde na textura.

Exemplo 2: Vasos

Esta cena é formada por cinco sólidos de revolução (os cilindros cinza, verde e azul, alinhados com os eixos x, y e z, respectivamente, e os dois vasos). Ela possui duas fontes de luz: uma mais próxima da cena, de cor amarelada, mas pouco intensa, simulando uma lâmpada, e outra, azulada, mais intensa porém mais distante, simulando uma iluminação ambiente.

A curva de perfil dos dois vasos foi projetada através de um programa editor de curvas feito especialmente para esse sistema gráfico, o curved, incluido no tarball do sistema.

Exemplo 3: Raquete

Esse é um exemplo de modelo que, infelizmente, exibe as limitações da arquitetura baseada em z-buffer -- apesar da estrutura da raquete ser renderizada corretamente, os fios que constituem a malha da raquete são exibidos e iluminados incorretamente. Os fios tem um diâmetro muito fino e, por isso, a diferença entre as coordenadas z dos pontos que os constituem é muito pequena. Por isso, o rasterizador desenha pontos que não deveriam ser visíveis no lugar de visíveis, ou deixa de desenhar pedaços de triângulos.

Os fios são vários sólidos de revolução apropriadamente escalados e transladados. Para criar a logomarca, um script Python foi utilizado — este script, alimentado com o logotipo, imprimiu automaticamente o conjunto de cilindros, com as cores associadas, para criar a ilusão da malha na raquete.

Apêndices

Referência SDL

Algumas notações deste apêndice:

<x>
Um objeto qualquer do tipo x.
<a>+ <b>* <c>?
Um ou mais objetos do tipo a, seguidos de zero ou mais objetos do tipo b, seguidos, opcionalmente, por um objeto do tipo c.
<float>
Um número de ponto flutuante qualquer.
<point>
Um objeto do tipo (<float> <float> <float>).

Todos os comandos da SDL são da forma (opcode ...). Somente cadeias de texto, números e outras listas são aceitáveis como argumentos de um comando.

(scene <camera>+ <light>+ <mesh>+)
Cria uma cena com as câmeras, luzes e malhas especificadas. Deve ser necessariamente o único comando na raiz do arquivo de entrada.
(camera (center <point>) (normal <point>) (up <point>) (near_plane <float>) (focal_plane <float>) (far_plane <float>))
Cria uma câmera com os parâmetros especificados.
(light (center <point>) (color <point>) (intensity <float>))
Cria uma fonte de luz com os parâmetros especificados.
(revolution_solid (vertex <point>)+ (color <point>)?)
Cria um sólido de revolução. O eixo do sólido é o eixo y do sistema de coordenadas. A curva de perfil é definida pelos vértices passados para a função: as coordenadas x e y dos vértices são as coordenadas x e y da curva de perfil; a coordenada z dos pontos de controle indica qual é a derivada da curva. A interpolação é cúbica, gerando uma curva C1.
(extrusion_solid (vertex <point>)+ (color <point>)?)
Cria um sólido de extrusão. O eixo de extrusão é o eixo y do sistema de coordenadas. A curva de perfil é definida pelos vértices passados para a função: as coordenadas x e y dos vértices são as coordenadas x e z da curva de perfil; a coordenada z dos pontos de controle indica qual é a derivada da curva. A interpolação é cúbica, gerando uma curva C1.
(triangle_mesh (vertex <point>)+ (triangle <point> (color <point>)?)+)
Cria uma malha triangular. Os vértices da malha são os passados nos operadores "vertex", e são indexados a partir de 0, na ordem em que aparecem; os triângulos são representados pelos índices de seus vértices.
(group <mesh>+)
Cria uma malha triangular que é a fusão das suas malhas componentes.
(translate <point> <mesh>)
Cria uma malha triangular que é a malha original translada pelo vetor especificado pelo primeiro parâmetro.
(rotate <point> (angle <float>) <mesh>)
Cria uma malha triangular que é a malha original rodada, no sentido anti-horário, em torno do eixo especificado pelo ângulo especificado (em graus).
(scale <point> <mesh>)
Cria uma malha triangular que é a malha original escalada nos eixos x, y, e z pelos fatores especificados no primeiro parâmetro.