Trabalho 2 - Pipeline Gráfico

Introdução

Este é o segundo trabalho da disciplina de Computação Gráfica, lecionada pelo professor Christian Azambuja Pagot.

O trabalho consiste em implementar todas as etapas do pipeline gráfico, ou seja, sera feito uma sequência de passos que vai desde o Espaço do objeto até o Espaço da tela, como mostra a imagem abaixo. 

Cada passo desse pipeline será explicado ao longo deste trabalho, assim como a implementação do mesmo.

1- Espaço do Objeto -> Espaço do Universo

O Espaço do objeto é onde vão ser criados os objetos separadamente, ou seja, cada objeto terá seu próprio sistema de coordenadas. Para que possamos unir esses objetos em um mesmo sistema de coordenadas, sairemos do Espaço do Objeto e iremos para o Espaço do Universo através de transformações geométricas:  Escala, Shear, Rotação e Translação.

1.1 - Escala

A escala modifica as dimensões do objeto, ou seja, o seu tamanho será aumentado ou diminuído, como ilustra a imagem abaixo.

Nesta transformação, cada coordenada (x,y) será multiplicada por um fator de escala:

Temos dois tipos de escalas: Isotrópicas e anisotrópica.

• Escalas Isotrópicas: Onde Sx = Sy;
• Escalas Anisotrópicas: Onde Sx != Sy;

Podemos espelhar o objeto invertendo as coordenadas:

• Espelhamento no eixo X: Sx=-1, Sy=1;
• Espelhamento no eixo Y: Sx=1, Sy=-1;
• Espelhamento em ambos os eixos: Sx=-1, Sy=-1;

Ilustração abaixo do espelhamento no eixo Y:

Note que, as imagens acima mostram as escalas sendo usadas em objetos que estão na origem dos eixos XY. Caso o objeto estiver fora da origem, o mesmo deverá ser levado à origem, podendo então ser aplicado a escala, e depois retorná-lo onde estava. Pois se for usado a escala fora da origem, seu objeto modificará de tamanho, mas mudará também de posicionamento, ou seja, ele será transladado, como ilustra a imagem abaixo:

1.2 - Shear

O shear faz com que o objeto tenha formato distorcido. Podemos ter a distorção do objeto em relação ao eixo X, ao eixo Y, ou em ambos os eixos. A imagem abaixo mostra um objeto distorcido.

Nesta transformação, será multiplicado uma constante na coordenada em que o objeto for distorcido:

 

Em ambas as coordenadas:

1.3 - Rotação

Nesta transformação, o objeto será rotacionado com um angulo theta. Para chegarmos a fórmula da rotação, os valores dos pontos originais (x,y) são:

Para os novos pontos (x',y'), vamos somar o valor de alpha com theta:

 Tendo em vista que:

• cos(a+b) = cos(a)*cos(b) - sin(a)*sin(b)
• sin(a+b) = sin(a)*cos(b) + sin(b)*cos(a)

Usaremos as fórmulas acima para encontrar (x',y'):

Onde tem r*cos(alpha) será substituído por x e onde tem r*sin(alpha) será substituído por y, pois como vimos acima, (x,y) correspondem a estes valores. Abaixo segue a fórmula da rotação.

Assim como a escala, para que a rotação seja feita o objeto deve estar na origem, caso não esteja, o mesmo será transladado implicitamente, abaixo segue rotações na origem e fora dela, respectivamente.

1.4 - Translação

Nesta transformação, o objeto será movido (transladado) de lugar. 

A fórmula da translação consiste em adicionar quantidades inteiras as coordenas (x,y).

Temos como objetivo expressar todas as transformações geométricas através de matriz. Notemos que a translação não pode ser expressada através de matriz. Para resolver este problema, utilizaremos coordenadas homogêneas.

• Coordenadas Homogêneas

Um ponto (x,y), do espaço euclidiano, será representado no espaço homogêneo adicionando uma coordenada homogênea "w". Para irmos ao espaço homogêneo, cada coordenada do espaço euclidiano será multiplicado pela coordenada w, ou seja, (x,y) -> (xw, yw, w). Para voltarmos para o espaço euclidiano, dividimos todas as coordenadas do espaço homogêneo por w, ou seja, (xw, yw, w) -> (x/w, y/w), para todo w!=0.

Com isso, poderemos representar a translação em forma de matriz.

• Representação Matricial da Translação

Note que, saímos de matrizes 2x2 e agora iremos utilizar matrizes 3x3.

Vale ressaltar que usaremos w=1.

1.5 - Escala, Shear e Rotação com Coordenadas Homogeneas

• Escala:

• Shear:

• Rotação:

1.6 - Transformações Geométricas em 3D

• Escala:

• Shear:

• Rotação:

A rotação em 3D é feita em torno de um dos eixos XYZ.

• Rotação em torno do eixo X:

• Rotação em torno do eixo Y:

• Rotação em torno do eixo Z:

• Translação:

2 - Espaço do Universo -> Espaço da Câmera

Nesta etapa do pipeline, os vértices que estão no sistema de coordenadas do Universo serão levados para o sistema de coordenadas da câmera, onde a câmera será posicionada na origem deste sistema.

A câmera possui um vetor posição, um vetor direção e um vetor UP.

• Vetor Posição: p = (px, py, pz);
• Vetor Direção: d = (dx, dy, dz);
• Vetor UP: u = (ux, uy, uz);

Usaremos os vetores citados acima para encontrarmos o sistema de coordenadas da câmera, onde denotaremos seus eixos por Xc, Yc e Zc.

• Para calcularmos o Zc, dividimos o simétrico do vetor direção (-d) pela sua norma;
• Para calcularmos Xc, faremos o produto vetorial entre o vetor UP e o vetor Zc (calculado anteriormente) e dividimos pela sua norma;
• Para calcularmos Yc, faremos o produto vetorial entre o vetor Zc e o vetor Xc  e dividimos pela sua norma;

A imagem abaixo ilustra o que foi dito anteriormente.

Agora que sabemos como encontrar os eixos do sistema de coordenadas da câmera, para que possamos levar os objetos do Espaço do Universo para o Espaço da Câmera, criaremos a Matriz View, que consiste de uma translação (T) e uma rotação (B), respectivamente.

A translação consiste em unir as origens do sistema de coordenadas do Universo com o sistema de coordenadas da câmera. A rotação será uma matriz formada por cada componente dos eixos da câmera, mas como essa matriz é ortogonal, usaremos sua transposta. Ilustração do que foi dito abaixo.

3 - Espaço da Câmera -> Espaço de Recorte

Nesta etapa do pipeline, sairemos do Espaço da câmera e iremos para o Espaço de Recorte, utilizando a matriz de projeção. Essa matriz fará com que os objetos tenham projeção perspectiva ou ortogonal. Na projeção perspectiva teremos uma sensação de profundidade dos objetos na tela, diferente da projeção ortogonal que preserva o paralelismo das retas. A imagem abaixo mostra ambas as projeções.

A matriz de projeção leva em conta apenas a distancia da câmera ao view plane, ou seja, é uma matriz de projeção simples. A matriz é mostrada abaixo.

4 - Espaço de Recorte -> Espaço Canônico

Nesta etapa do pipeline sairemos do Espaço de Recorte e iremos para o Espaço Canônico, onde cada coordenada será dividida pela coordenada w. É neste espaço que teremos a distorção perspectiva.

5 - Espaço Canônico -> Espaço de Tela

No Espaço de Tela, os vértices que foram obtidos no Espaço Canônico serão rasterizados.

6 - Desenvolvimento do Trabalho

Faremos uma implementação do pipeline gráfico seguindo os passos que foram explicados anteriormente.

• Partiremos do Espaço do Objeto para o Espaço do Universo multiplicando os vértices do objeto pela matriz de modelagem (M_model);

• Agora iremos do Espaço do Universo para o Espaço da Câmera utilizando a matriz de visualização (M_view). Ela é obtida através da multiplicação da matriz de Rotação (Bt) pela matriz de translação (T).

          

           Vale lembrar que já foi visto como calcular os componentes da matriz de rotação (Bt).  

• Sairemos do Espaço da Câmera para o Espaço de Recorte através da utilização da matriz de projeção (M_projection);

• Foi criado a matriz M_modelviewprojection que é a multiplicação das matrizes M_projection e M_modelview. Após a criação dessa matriz, multiplicaremos cada vértice do espaço do objeto por ela. Com os novos vértices encontrados, faremos a homogenização, ou seja, dividiremos as coordenadas de cada vértice por sua coordenada w. Sendo assim, chegaremos no Espaço Canônico;
• Agora iremos para a tela através da M_viewport, que é o resultado da multiplicação das três matrizes mostradas abaixo.

• Abaixo temos o objeto final rasterizado:

• Abaixo temos a comparação dos resultados obtidos pela sequencia de passos acima (lado direito) com o objeto disponibilizado pelo professor Christian Azambuja Pagot (lado esquerdo). 

• Abaixo segue o vídeo de ambos os objetos sendo rotacionados.

Dificuldades

A maior dificuldade foi na manipulação de matrizes.

Melhorias

Poderia melhorar o código, deixando o mesmo mais enxuto.

Referências

• Slides do professor Christian Azambuja Pagot;
• http://www.lcad.icmc.usp.br/~rosane/CG/TransfGeomAndersonIcaro.pdf

Trabalho 1 - Rasterização

Introdução

Este é o primeiro trabalho da disciplina de computação gráfica, lecionada pelo professor Christian Azambuja Pagot.

O  trabalho consiste em rasterizar pontos e linhas, e a partir da rasterização de linhas, formamos um triângulo. O professor disponibilizou um framework para simular o acesso direto a memória de vídeo.

1 - Pixel e Monitores

Pixel é a menor unidade de uma imagem digital, que é fruto da combinação de três cores básicas: Red (vermelho), Green (verde) e Blue (azul), RGB.

Um pixel é composto por 4 bytes, onde nos 3 primeiros bytes contém as cores ditas anteriormente, e no último byte terá a componente A(alpha), que permite mencionar a opacidade de uma cor.

Cada uma das 3 cores possui 256 tonalidades, que combinadas, geram mais de 16 milhões de possibilidades de cores.

A imagem abaixo ilustra o que foi dito acima.

Um tela de um monitor é composto por pixels. Tenhamos como exemplo um monitor com 1366 x 788, ele terá 1366 pixels de largura por 788 pixels de altura. Para saber onde um pixel vai esta na tela de seu computador, tenha em mente o sistema cartesiano de coordenadas (x,y). A coordenada x, corresponde a linha, e a coordenada y corresponde a coluna.

Note que nestas imagens, vemos o sentido positivo da coordenada x da esquerda para direita, ou seja, do mesmo jeito que no sistema cartesiano, mas o sentido positivo da coordenada y é de cima para baixo, ou seja, o oposto do sistema cartesiano.

2 - Desenvolvimento do Trabalho

Como já temos noção do que é Pixel e de como funciona em um monitor, vamos a explicação de como foi desenvolvido o trabalho.

O trabalho foi feito na linguagem C++, onde foram criadas quatro classes: 

• Classe Cor, onde são passados os valores das cores RGBA no seu construtor;
• Classe Ponto, onde são passados os valores das coordenadas (x,y) no seu construtor, também contém o método PutPixel, que vai pintar o ponto na tela;
• Classe Linha, onde são passados os valores de duas coordenadas (x,y) no seu construtor, também contém o método DrawLine, que vai rasterizar uma linha na tela;
• Classe Triangulo, onde são passados os valores de três coordenadas (x,y) no seu construtor, também contém o método DrawTriangle, que vai formar um triangulo na tela;

2.1 - PutPixel()

Como dito anteriormente, este método vai pintar um ponto na tela, usando o ponteiro FBptr (disponibilizado pelo professor), que aponta para o primeiro byte da memória de vídeo simulada. Para calcular o endereço, usaremos a seguinte fórmula: x*4 + y*w*4, onde x e y são as coordenadas, e w é o numero de colunas. Faremos FBptr ser uma array de 4 posições, pois como dito antes, um pixel tem 4 bytes.

2.2 - Rasterização de Linhas

Para rasterizarmos uma linha, vão ser dados dois pixels com coordenadas (x1, y1) e (x2, y2), que serão os extremos de um segmento de reta (linha). Nós iremos determinar quais pixels entre esses dois extremos vão ser selecionados para compor visualmente a linha.

Na imagem abaixo, se selecionarmos apenas os pixels que estão sobre o segmento de reta, como por exemplo o segmento AK, seriam selecionados apenas os pixels A, F e K, resultando numa fraca densidade visual.

Para que a densidade seja o mais uniforme possível, iremos selecionar o maior número de pixels entre o segmento de reta, ou seja, também serão selecionados os pixels que estão fora do segmento. Continuando com o exemplo do segmento AK, os possíveis pixels selecionados seriam B, C, D, E, G, I, J. Mas tenha em mente que para dois pixels situados em uma mesma linha vertical, como por exemplo os pixels B e C, será escolhido o pixel mais próximo ao segmento de reta. Assim, o segmento AK seria composto pelos pixels B, E, G e I. Portanto, a linha seria feita pelos pixels A, B, E, F, G, I e K. 

Na imagem abaixo vemos outra ilustração do que foi dito acima, note que os pixels pintados de azul são os mais próximos do segmento de reta, então eles serão os escolhidos para compor o segmento.

2.3 - Algoritmo de Bresenham

Para realizarmos a rasterização de linhas, que foi explicada anteriormente, utilizaremos o algoritmo de Bresenham, pois o mesmo permite um maior desempenho já que usa a aritmética de inteiros. 

O algoritmo baseia-se no critério do ponto médio, ou seja, pegaremos o ponto médio entre dois pixels em relação a reta. Para determinar a posição do ponto médio em relação a reta, consideremos F(x,y)=ax+by+c.

Mas quem são a, b e c? Para achá-los, partiremos da equação explícita da reta Y=(dy/dx)*X+C, onde dy = deltaY, e dx = deltaX. Multiplicando ambos os lados da igualdade por dx, teremos: dxY=dyX+dxC. Passando o dxY pro outro lado, teremos: dyX - dxY + dxC = 0. Percebemos que partimos da forma explícita e chegamos na forma implícita, onde:  F(x,y)=dyX+dxY+dxC. Logo, a=dy, b=dx e c=dxC.

Após sabermos a função, tenhamos em mente que: Se a função for maior que zero, o ponto médio encontra-se abaixo da reta, caso a função seja menor que zero, ponto encontra-se acima da reta, então como mostra a figura abaixo.

Na figura abaixo vemos que, o ponto médio, que foi calculado pela F(x,y), encontra-se acima da reta, logo você seleciona o pixel imediatamente abaixo dela, ou seja, o ponto (x+1, y). Caso o ponto médio fosse encontrado abaixo da reta,  seria pintado o pixel imediatamente acima dela, ou seja o ponto (x+1, y+1).

• Caso o ponto incrementado seja (x+1, y), o valor de decisão 'd' seria: d = 2 * dy ;
• Caso o ponto incrementado seja (x+1, y+1), o valor de decisão 'd' seria: d = 2 * (dy-dx) ;

2.4 - Drawline()

Este método irá desenhar uma linha tela com o algoritmo de Bresenham, que foi explicado anteriormente, mas este algoritmo funciona apenas para o primeiro octante, ou seja, de 0º a 45º graus. Antes de continuar falando sobre o método DrawLine, iremos abrir um parênteses e explicar o que são os octantes.

Na figura abaixo é mostrado os 8 octantes no sistema cartesiano. A letra 'm' mostrada na imagem equivale a seguinte divisão: dy/dx. Note o seguinte:

• 0<=m<=1, equivale ao primeiro e quinto octante;
• m>1, equivale ao segundo e sexto octante;
• m<-1, equivale ao terceiro e ao sétimo;
• -1<=m<0, equivale ao quarto e ao oitavo;

Ou seja, podemos reduzir de oito octantes, para apenas quatro, como mostra a imagem abaixo.

Já temos a noção de octantes, e também sabemos que o algoritmo de Bresenham aplica-se ao primeiro octante. Para rasterizar uma linha de segmentos de reta que não estão no primeiro octante, iremos transformar esses segmentos para o primeiro octante.

No método DrawLine, antes de aplicar o algoritmo de Bresenham, faremos algumas condições para que a transformação dita anteriormente aconteça.

• Inicie duas variáveis: inclinacao e simetrico com valor 0;
• Se dx*dy < 0, as coordenadas 'y' dos extremos e o dy serão trocados pelos seus simétricos. Logo em seguida mude o valor da variável simetrico para 1;
• Se abs(dx) < abs(dy), troque as coordenadas (x0, y0), ou seja, x0 = y0 e y0 = x0,  o mesmo faça com as coordenadas (x1, y1), e também troque dx com dy. Logo em seguida, mude o valor da variável inclinacao para 1;
• Se x0 > x1, troque x0 por x1 e y0 por y1, também dx e dy serão trocados pelos seus simétricos;

Após esses passos, o segmento de reta foi transformado para o primeiro octante. Então, para cada pixel (x,y), calculado pelo algoritmo de Bresenham, faça os seguintes paços:

• Se inclinacao = 1, troque os valores de x e y;
• Se simetrico = 1, troque o valor de y pelo seu simetrico;

Feito isso, podemos desenhar as linhas, como mostra o programa em execução na imagem abaixo:

2.5 - Interpolação Linear

Para fazermos a interpolação linear entre as cores foram criados dois vetores auxiliares de 4 posições, um vetor para a cor e o outro uma constante.

O vetor auxiliar de cor, será inicializado pelas cores do primeiro ponto (x0, y0), por exemplo,:

• vetorCor[0] = cor1->getRed();
• vetorCor[1] = cor1->getGreen();
• vetorCor[2] = cor1->getBlue();
• vetorCor[3] = cor1->getAlpha();

O vetor constante armazena em cada posição a diferença entre as cores de cada componente RGBA, dividindo o resultado pela distância entre os pontos extremos, por exemplo:

• const[0] = (cor2->getRed() - cor1->getRed() ) / dx; 
• const[1] = (cor2->getGreen() - cor1->getGreen() ) / dx;
• const[2] = (cor2->getBlue() - cor1->getBlue() ) / dx;
• const[3] = (cor2->getAlpha() - cor1->getAlpha() ) / dx;

Vale lembrar que a divisão é por dx pois transformamos todos os segmentos de reta para o primeiro octante. 

Após isso, pegamos o resultado de cada posição do vetor constante e somamos com o vetor auxiliar de cor, por exemplo:

• vetorCor[0] =  vetorCor[0] + constante[0];
• vetorCor[1] =  vetorCor[1] + constante[1];
• vetorCor[2] =  vetorCor[2] + constante[2];
• vetorCor[3] =  vetorCor[3] + constante[3];

Feito isso, as linhas são interpoladas, como mostra a imagem abaixo:

2.6 - DrawTriangle

Este método desenha triângulos na tela sendo passadas 3 coordenadas (x,y). 

Será usado o método DrawLine para ligar essas coordenadas, como segue na imagem abaixo:

Como foi dito no início do trabalho, o valor das coordenadas são passados no construtor da classe Triangulo.

Alguns resultados são mostrados nas imagens abaixo:

2.7 - Dificuldades

A maior dificuldade encontrada foi no que se refere aos octantes, pois fiz uma transformação para o primeiro octante.

2.8 - Melhoras

• Poderia melhorar o código, deixando o mesmo mais enxuto;
• Poderia ter preenchido o triângulo;

3 - Referências

• Slides do professor Christian Azambuja Pagot;
• http://disciplinas.ist.utl.pt/leic-cg/textos/livro/Rasterizacao.pdf