IMPORTANTE: Entregar em aula o documento pedido e enviar por email, até a meia-noite do dia 10/11/08 ao professor (marcelo.walter at gmail.com) os arquivos fontes de seu programa e qualquer outro fonte necessário para compilar seu executável! A cada hora de atraso no envio do email, será descontado 1.0 (um) ponto do total da nota. Você pode enviar também arquivos script descrição de cena que você escreveu para testar seu programa. Explicitar no documento qualquer informação necessária para compilar corretamente seu programa. Este trabalho poderá ser feito em grupos de até 2 alunos.

Para saber quanto vale cada item, acesse o Esquema de Correção (NEW!)

1. Introdução

Traçado de Raios (Ray Tracing - RT) é um método simples mas poderoso de gerar ou renderizar imagens com certo grau de realismo. O algoritmo original de RT foi proposto por Appel em 1968 (Some Techniques for Shading Machine Renderings of Solids, AFIPS 1968 Spring Joint Comp. Conference, p. 37-45). Em 1980 Turner Whitted (Communications of the ACM N. 23, V. 6, June 1980, p. 343-349) implementou uma versão mais completa sobre a idéia original de Appel e produziu inúmeras imagens que impressionaram na época pela qualidade e desde então RT desenvolveu-se significativamente (veja um exemplo do artigo de 1980 na figura baixo).

Por simplicidade neste trabalho assumiremos que a janela está sempre localizada no plano z=0. Portanto, o observador estará sempre numa posição com z positivo e os objetos da cena vão sempre estar em posições com z negativo.

2. Superfícies Quádricas

Os objetos presentes na cena serão apenas superfícies quádricas. Este tipo de superfície facilita os cálculos de intersecção dos raios. Uma superfície quádrica é definida como:

f(x,y,z) = ax2 + by2 + cz2 + 2dxy + 2eyz + 2fxz + 2gx + 2hy + 2jz + k = 0

A superfície é definida por um conjunto de pontos (x,y,z) no espaço que satisfazem a equação f(x,y,z) = 0. Podemos obter diferente superfícies quádricas atribuindo valores diferentes aos 10 coeficientes a,b,c,d,e,f,g,h,j,k (observe que não utilizamos a letra "i"). As equações familiares de esferas, elipsóides e planos podem ser re-escritas como quádricas. Por exemplo, considere uma esfera com raio igual a 25 centrada na posição (0,5,-20). A equação que define esta esfera é dada por

x2 + (y-5)2 + (z+20)2 = 252

x2 + y2 + z2 - 10y + 20z - 200 = 0

Portanto, os coeficientes que definem esta esfera em formato de quádrica seriam:

a=1,b=1,c=1,d=0,e=0,f=0,g=0,h=-5,j=10,k=-200

Para este trabalho você poderá contar com um módulo escrito em C++ que deverá ajudá-lo na implementação. Este módulo contém rotinas para calcular intersecção entre raios e quádricas, calcular o vetor normal num ponto de uma superfície quádrica, normalizar um vetor bem como outras operações úteis sobre vetores. Os arquivos são quadric.cpp e quadric.h. Nestes arquivos você encontrará várias definições de estruturas de dados que você deve usar no seu programa. Estude-os com atenção.

3. Determinando a cor do objeto

Quando um raio intersecciona um objeto, como iremos determinar a cor do objeto naquela posição da cena? Suponha que a superfície do objeto tem uma cor RGB dada por (r,g,b) com 0.0 <= r,g,b <= 1.0. Primeiro assumimos que nosso objeto é iluminado por uma quantidade de luz ambiente Ia que é refletida pelo objeto de acordo com um coeficiente ka. A intensidade de luz ambiente refletida é independente do observador e é definida por:

Rambiente = Ia*kar

Gambiente = Ia*kag

Bambiente = Ia*kab

A seguir precisamos considerar as fontes de luz na cena. Para cada fonte de luz visível (veja explicação sobre sombras no item 4 abaixo), a superfície do objeto retorna alguma fração de reflexão difusa. Esta fração depende de: a intensidade da fonte de luz Ip, o coeficiente de reflexão difuso kd e do cosseno do ângulo q entre a direção da luz (vetor L) e a normal à superfície no ponto sendo iluminado (vetor N) cfe figura.

Rdifuso = Ip*kd(L.N)r

Gdifuso = Ip*kd(L.N)g

Bdifuso = Ip*kd(L.N)b

Finalmente iremos considerar reflexão especular. A intensidade de reflexão especular depende do ângulo a entre a direção de reflexão perfeita R e a direção do observador (veja a próxima figura) Utilizaremos o modelo de Phong para aproximar a reflexão especular. Neste modelo cada objeto possui um coeficiente de reflexão especular ks e um expoente de reflexão especular n. n determina o "tamanho" da reflexão especular. Valores maiores de n produzem highligths menores. Dados estes valores e a intensidade da fonte de luz Ip, a intensidade de reflexão especular é dada por:

Respecular = Ip*ks*(cos a)n

Gespecular = Ip*ks*(cos a)n

Bespecular = Ip*ks*(cos a)n

Note que, diferentemente das componentes ambiente e difusa, a reflexão especular no modelo de Phong não depende da cor do objeto. O reflexo especular será sempre da cor da fonte de luz. Se ambos R e V forem normalizados teremos cos a = R.V e as equações acima ficam:

Respecular = Ip*ks*(R.V)n

Gespecular = Ip*ks*(R.V)n

Bespecular = Ip*ks*(R.V)n

Vamos assumir que temos um número total variável l de fontes de luz na cena. Neste modelo simplificado, a cor do objeto num ponto P é simplesmente a soma das equações acima para o número l de fontes de luz.

4. Enviando raios secundários

A cada interseccão de um raio com um objeto, precisamos recursivamente disparar  raios secundários no ambiente. Potencialmente estes raios podem ser de 2 tipos: refletido e transmitido. Cada um destes 2 raios podem gerar outros 2 e assim por diante. A profundidade da recursão é um dos parâmetros que você irá ler do arquivo de descrição da cena, bem como os valores paa KS e KT (ver item 7 abaixo).

As características físicas do objeto é que determinarão os tipos de raios (por exemplo, se o objeto não for transparente, não há raio transmitido). A cor final do ponto será dada pela seguinte fórmula:

I = Ilocal + KS*Irefletido + KT*Itransmitido

5. Sombras

A sombra nada mais é do que um ponto do objeto que não recebe luz da(s) fonte(s) de luz na cena. Para cada ponto de intersecção entre um objeto e o raio corrente precisamos verificar se o mesmo não está na sombra, antes de calcular sua cor de acordo com o modelo de iluminação. Os pontos na sombra recebem apenas a contribuição da componente de luz ambiente, que é constante para todos os objetos na cena.

6. Arquivos de Saída

Nós estaremos gerando imagens que precisam ser visualizadas. Sendo assim precisamos uma maneira de gerar estas imagens em algum formato conhecido. Você pode gerar as imagens em qualquer formato que você tiver conhecimento (gif, jpg, etc). Uma biblioteca bastante utilizada para estas tarefas de manipulacão de imagens é a ImageMagik.

Aqui daremos a sugestão para você utilizar o formato PNM.

O formato PNM apresenta várias vantagens. Inicialmente ele pode ser facilmente lido por qualquer editor de texto, já que pode ser um arquivo ASCII. A desvantagem óbvia é o tamanho excessivo das imagens. O arquivo redwhite.pnm é um exemplo de arquivo pnm.

O formato de um arquivo PNM é composto por um cabeçalho dado pelos seguintes valores, separados por espaços em branco:

MagicValue

P3 para versão ASCII, P6 para binário

ImageWidth

Largura da Imagem em pixels (ASCII decimal value)

ImageHeight

Altura da Imagem em pixels (ASCII decimal value)

MaxGrey

Valor de cor máxima, normalmente para nossas imagens 255 (ASCII decimal value)

Após o cabeçalho, seguem os valores dos pixels propriamente ditos em ordem de largura versus altura. A descrição de cada pixel é dada por valores decimais ASCII entre 0 e o valor máximo especificado no cabeçalho (MaxGrey). O primeiro pixel especificado é o do canto superior esquerdo, prosseguindo linha a linha.

Abaixo um exemplo de um arquivo simples e pequeno em PNM:

P3

# exemplo.pnm

4 4

15

0  0  0    0  0  0    0  0  0   15  0 15

0  0  0    0 15  7    0  0  0    0  0  0

0  0  0    0  0  0    0 15  7    0  0  0

15  0 15    0  0  0    0  0  0    0  0  0

Qualquer linha que iniciar com # é considerada uma linha de comentário e todos os caracteres entre # e o próximo caracter de final de linha são desconsiderados. Sugere-se que cada linha tenha no máximo 70 caracteres.

7. Arquivo para descrição da cena

Nós precisamos de uma maneira de descrever a cena que será renderizada. Para isto utilizaremos uma linguagem de descrição de cena simples (SDL - Scene Description Language). Os comandos nesta linguagem permitirão ao usuário especificar toda a informação necessária para o seu uniray renderizar a cena. Os comandos da SDL são descritos abaixo:

    * #...comentário

Qualquer linha iniciando com o caracter # é considerada uma linha de comentário. Todos os caracteres após o # até o próximo caracter de final de linha são desconsiderados

    * output nomedearquivo

Especifica o nome do arquivo de saída que será gerado

    * eye x y z

Especifica a posição (x,y,z) do observador virtual. Z deve ser maior do que 0

    * ortho x0 y0 x1 y1

Especifica a janela no universo. (x0,y0) especificam a posição do canto inferior esquerdo e (x1,y1) especificam a posição do canto superior direito. A janela está sempre no plano z=0

    * size w h

Especifica como dividir a janela nos pixels individuais. A janela do universo especificada pelo comando ortho deve ser dividida em w pixels de largura e h pixels de altura

    * background r g b

Especifica a cor de fundo, ou seja, a cor a ser utilizada para os pixels cujos raios não atingem nenhum objeto. Valores no intervalo [0,1]

    * ambient Ia

Especifica a intensidade da luz ambiente na cena. 0 <= Ia <= 1

    * light x y z Ip

Especifica uma fonte de luz com intensidade Ip na direção (x,y,z). Trabalharemos apenas com fontes de luz direcionais. Uma mesma cena pode ter várias fontes de luz.

    * supersample [on/off]

Especifica se a cena a ser gerada utilizará supersampling ou não (ver o item 10 deste documento)

    * profundidade n

Especifica a profundidade da recursividade. Por exemplo, com n=0, significa que os raios páram no primeiro objeto, n=1 os raios percorrem uma vez a cena recursivamente e assim por diante.

    * object a b c d e f g h j k red green blue ka kd ks n KS KT ir

Especifica uma superfície quádrica através dos coeficientes de a até k. A cor do objeto é especificada pelas componentes red, green, blue, valores no intervalo [0,1]. ka, kd, ks e n são os coeficientes de reflexão do objeto. KS e KT são so coeficientes de reflexão e transmissão globais do objeto (no intervalo [0,1]). Para objetos transparentes o coeficiente ir especifica o índice de refração do objeto. O índice de refração do ar é 1. Outros índices interessantes: água a 20oC = 1.33, Gelo=1.31, vidro=1.5 e diamante=2.417. Uma mesma cena pode ter vários objetos.

8. Especificação do trabalho

Você deverá implementar o seguinte:

    * Rotinas para ler e interpretar um conjunto de comandos da SDL conforme especificado no item 6 deste documento. Estes comandos serão lidos de um arquivo passado como parâmetro para o seu programa. Exemplo:

uniray onesphere.sdl

    * Rotinas que implementam um Traçador de Raios (RayCife), que suporta um modelo de iluminação conforme especificado no item 3 deste documento.

Abaixo alguns exemplos de arquivos SDL que você pode usar para testar seu programa.

onesphere.sdl               oneshadow.sdl

oneplanesphere.sdl      threeshadow.sdl           twoplanessphere.sdl

twoshadow.sdl              twospheres.sdl

    * Documentação a ser entregue. Você deverá entregar um documento COM NO MÁXIMO 2 PÁGINAS, onde você descreverá o trabalho implementado, dificuldades encontradas e outros pontos que você achar relevante (por exemplo, se você implementou algo extra no trabalho). Incluir neste documento explicações necessárias para compilar seu programa.

9. Dicas

    * Você não deverá utilizar OpenGL neste trabalho.

    * A soma das componentes ambiente, difusa e especular pode resultar num valor maior do que 1. Neste caso simplesmente limite o valor máximo em 1 (veja comentário sobre isto no item Extras abaixo).

10. Extras

a) Implemente uma modalidade de supersampling no seu RayCife para diminuir o aliasing da imagem. A técnica simples sugerida lança apenas um raio por pixel, no centro do pixel. Esta baixa amostragem pode resultar no que se conhece em computação gráfica por aliasing na imagem. Isto acontece principalmente em áreas onde o sinal tem alta freqüência, por exemplo, partes do objeto onde a curvatura muda rapidamente.

Uma maneira simples de melhorar o problema é lançar mais de um raio por pixel, lançando por exemplo 4 raios por pixel, nos "cantos" do pixel. A cor final será então uma média das 4 cores obtidas para cada canto. Observe que somente precisamos fazer isto para os pixels que realmente atingem algum objeto, ou seja, inicialmente envie um raio pelo centro do pixel. Se o raio atingir um objeto e o modo supersampling estiver ativado, então envie mais 4 raios e faça uma média das cores obtidas. Caso contrário siga para o próximo pixel.

b) Você pode optar por exibir a imagem enquanto ela estiver sendo gerada numa janela independente e com refinamento “progressivo” da seguinte forma. Inicialmente a imagem tem apenas 4x4 pixels, depois 8x8, 16x16 e assim por diante, ate chegar à resolução desejada. Estas imagens intermediárias fornecem uma aproximacão da imagem final.

c) Implemente um algoritmo mais inteligente para lidar com a possibilidade do valor final de iluminacão ser maior do que  1.

d) Implemente rotinas de intersecção dos raios com triângulos. Desta forma você poderá visualizar os objetos do Sivop no Raycife com maior realismo. A intersecão com triângulos primeiro encontra a intersecção com o plano suporte do triângulo para depois verificar se este ponto de intersecção está contido no triângulo. Você precisará pesquisar uma maneira de decidir se um ponto está contido num triângulo.

Observação Importante: A fraude escolar (cópia de trabalhos, trabalhos não feitos pelo aluno, etc) constitui falta grave e pode resultar em nota zero para o aluno no trabalho e dependendo da gravidade da fraude inclusive em sanções mais duras.