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:
- Câmeras
- Luzes
- Malhas triangulares
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
- Não é necessário alterar a paleta durante a execução do programa
- Simples implementação
Desvantagens
- É impossível utilizar todas as 256 cores disponíveis
- As fronteiras de quantização são muito visíveis
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
- Usa todas as 256 cores de maneira eficiente
- Não é necessário nenhum esforço por parte do código que utiliza as cores
Desvantagens
- Implementação complicada e lenta
- A imagem precisa ser redesenhada toda vez que há uma troca de cores na paleta
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
- Mantém todos os detalhes da imagem
- Permite a reutilização do algoritmo de quantização da solução 1
Desvantagens
- Renderização é três vezes mais lenta
- É necessário mais um passo na pipeline de visualização
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.