quarta-feira, 19 de outubro de 2016

Implementação do Pipeline Gráfico

Definição do trabalho:

Para este trabalho, deveríamos implementar todos os passos do pipeline gráfico usando um objeto importado, no caso, o macaco do Blender. Para isso, nos foi passado um exemplo sobre qual deveria ser o resultado final.

Resultado do programa fornecido pelo professor para ser usado como base

O programa para importar o objeto também foi fornecido pelo professor.

O Pipeline:

O pipeline gráfico é o processo pelo qual transformamos imagens para serem exibidas na tela.

Esquema do Pipeline gráfico retirado daqui.

O Pipeline gráfico consiste de etapas que podem ser descritas pela mudança de espaços. O primeiro é o espaço do objeto, que define apenas as coordenadas do objeto com relação a origem de uma base xyz genérica. O segundo, é o espaço do universo, que define o comportamento do objeto no espaço da cena. O terceiro é o espaço da câmera, onde são definidos os parâmetros de visualização da cena. O quarto é o espaço de recorte, onde é definido o que será visto, então, temos o espaço canônico responsável pela projeção e, por fim, o espaço de tela, onde os objetos tridimensionais são transformados para bidimensionais para poderem ser exibidos na tela.

Implementação:

Espaço do objeto - universo:

O primeiro passo, era transformar o objeto para o espaço do universo e definir o seu comportamento, como o objeto foi colocado na origem, a matriz transformação era composta apenas pela matriz identidade, porém, como foi aplicada uma rotação, essa matriz identidade foi multiplicada por uma matriz rotação do modelo

Matrizes de rotação retiradas daqui.

Como a rotação foi ao redor de y, usamos a segunda matriz (Ry), para manter a rotação constante com efeito de animação, criamos uma variável que era incrementada a cada quadro e usamos as funções da biblioteca math para calcular senos e cosenos.

Espaço do universo - câmera:

Para transformar o objeto do espaço do universo para o espaço da câmera, era necessário fazer uma rotação e uma translação, mas, primeiramente, deveríamos definir as configurações da câmera. Seguindo o modelo do programa auxiliar, coloquei a minha câmera também na posição (0, 0, 4) olhando para o ponto (0, 0, 0) e com o vetor "up" em y. Tendo as configurações da minha câmera no espaço do universo, eu precisava gerar o espaço da câmera. Pelo posicionamento da minha câmera, eu não precisei aplicar uma rotação, pois os vetores do espaço do universo e os vetores do espaço da câmera tinham a mesma direção. A translação foi contrária a da câmera, ou seja, -4 em z.

Modelo de matriz de rotação para o espaço da câmera retirado dos slides de aula do professor Christian Pagot.

Modelo de matriz de translação para o espaço da câmera retirado dos slides de aula do professor Christian Pagot.

No modelo das matrizes acima, as coordenadas x, y e z da matriz de rotação são dos vetores do espaço da câmera e, na matriz de translação, as coordenadas p são da posição da câmera. Para esse caso, a matriz de rotação era a matriz identidade e a matriz de translação possuia apenas pz diferente de 0.

Espaço da câmera - recorte:

A próxima etapa era calcular a distorção de projeção na visualização do objeto, para isso, usamos uma matriz do tipo

Modelo de matriz de projeção para o espaço da câmera retirado dos slides de aula do professor Christian Pagot.

Para esse caso, assumimos d=1.

Espaço de recorte - canônico:

Esta transformação consiste em dividir as coordenadas dos vértices pela sua coordenada homogênea, causando uma distorção na cena.

Espaço canônico - tela:

Para essa transformação, usaremos matrizes desse molde:

Matrizes retiradas do script auxiliar do octave feito pelo professor Christian Pagot.
A matriz que transforma para o espaço de tela é composta por duas escalas e uma translação. Os parâmetros w e h são relativos à largura e altura da janela. Nesse caso, usei uma janela de tamanho 600x600. Em seguida, usei o algoritmo de rasterização implementado no trabalho anterior para exibir a imagem.

Resultados:

Print do objeto exibido pelo programa criado nesse trabalho.
Objeto gerado pelo programa criado nesse trabalho.


Problemas apresentados:

Tive alguns problemas ao relacionar o programa de rasterização e esse, bem como para ler diferentes objetos, algumas funções das bibliotecas também me causaram alguns problemas. Eu perdi um pouco de tempo no FOV, mas foi por estar interpretando errado os parâmetros da câmera do openGL.

Possíveis melhorias:

Seria interessante poder carregar outros objetos, mesmo os que não são compostos apenas por triângulos. Achei alguns modelos interessantes, mas possuiam faces com mais vértices e eu não consegui editar a biblioteca para poder usá-los.

Diferentes modelos:

Também achei alguns modelos interessantes que eu consegui carregar.

Um anão do filme Branca de Neve

Referências:

https://en.wikipedia.org/wiki/Graphics_pipeline
https://www.ntu.edu.sg/home/ehchua/programming/opengl/CG_BasicsTheory.html
http://goanna.cs.rmit.edu.au/~gl/teaching/rtr&3dgp/notes/pipeline.html
Notas de Aula e Material complementar do professor Christian Pagot.
http://www.turbosquid.com/FullPreview/Index.cfm/ID/671354 (Modelo do anão)
http://www.turbosquid.com (Mais modelos em 3D)
http://blender.stackexchange.com/questions/8322/understanding-3d-transforms-and-rotations

terça-feira, 9 de agosto de 2016

Implementação do algoritmo de Bresenham

Um monitor é um dispositivo matricial composto por pixels, o que torna complexo o desenho de linhas. Tudo o que é exibido no monitor é gravado em uma memória de vídeo que não podemos acessar, portanto, usamos um framework que simula essa memória e nos permite edição. Então, para exibir uma linha, precisávamos de um algoritmo para acertar o próximo pixel a ser pintado de modo a manter a angulação.

O primeiro passo foi entender o algorimo. Em sala nos foi mostrado que o algoritmo de Bresenham é utilizado para imprimir pixels em uma linha reta calculando o próximo pixel a ser preenchido com base em um ponto médio entre dois pixels verticais e no coeficiente angular da reta. Porém, o algoritmo só funcionava para o primeiro octante, ou seja, para ângulos menores ou iguais a 45°. A grande vantagem do algoritmo de Bresenham é a sua eficiência, pois não realiza séries de operações de divisão e arredondamento.

Algoritmo de Bresenham:

Nota: As imagens foram retiradas do blog Learning Bits, porém, as imagens contendo as fórmulas são originais do Wikipedia-EN (Bresenham line algorithm).

Baseada na explicação do algoritmo por Learning Bits, temos:

Dados dois pontos, considere que o ponto (x1,y1) seria o inferior esquerdo, e (x2,y2) o superior direito. Assim, veja a imagem abaixo:

1 - Tomada de decisão por algoritmo do ponto médio (algoritmo de Bresenham)

Seguindo a imagem, o último ponto pintado foi o ponto P e o próximo pode ser o ponto I ou o ponto S. O algoritmo de Bresenham utiliza um ponto médio M entre os dois pontos possíveis e um ponto Q da reta com a mesma coordenada x que M. Logo, se M está acima de Q, o ponto a ser pintado é o de baixo e, caso contrário, o de cima. Por esse motivo, esse algoritmo também é chamado de algoritmo do ponto médio.

O método para calcular se o ponto M está acima ou abaixo da reta é:

dX = x2-x1          &          dY = y2-y1         

Sendo a equação da reta: 

Definimos então a função:

Multiplicando os valores da equação por dX:


 O modelo da equação acima é:

Sendo assim, f(x, y) = 0 para pontos na reta, f(x, y) < 0 para pontos abaixo da reta e f(x, y) > 0 para pontos acima da reta. Então, usaremos d como uma variável de decisão e, usando as coordenadas do ponto M da imagem, temos:


Se d > 0, o ponto S deverá ser pintado, se d < 0 o ponto I deverá ser pintado e, se d = 0, qualquer um dos pontos pode ser pintado sem influenciar na visualização da reta.

Após a decisão de qual ponto será pintado, é necessário atualizar  o valor de d. Se I foi o último ponto pintado, M será incrementado somente na direção x e, caso S tenha sido pintado, M será incrementado nas direções x e y.





Então, basta apenas verificar o valor inicial de d:



Logo:


Caso o ponto I tenha sido escolhido:


Caso o ponto S tenha sido escolhido:


Porém, esse algoritmo só funciona para o primeiro octante e para o seu oposto, contanto se que invertam os pontos inicial e final da reta antes de realizar as operações. Para adequar aos outros octantes, devemos alterar os valores de d, como mostrado na tabela:

2 - Variação do algoritmo para todos os octantes

A primeira coluna da tabela mostra as relações do coeficiente angular da reta (m) que é usado para definir o octante em que se encontra a reta. A segunda mostra o valor inicial de d, tratado no texto acima também como dold. A terceira e a quarta colunas mostram o caso em que d é maior ou igual a 0: quais coordenadas devem ser incrementadas no ponto m e o quanto aumenta o valor de d. A quinta e a sexta colunas mostram o mesmo que a terceira e a quarta, mas para os valores em que d é menor do que 0. 


São 4 possíveis operações para os valores de d, pois a operação utilizada para um octante, serve para o seu oposto contanto que se invertam os pontos iniciais e finais da reta.

3 - Teste do algoritmo desenhando linhas nos octantes

Descrição do código:

Foram criados os structs cor e ponto. Cor continha os valores de RGBA e Ponto continha as coordenadas x e y do ponto escolhido. Cor e coordenadas não foram colocadas no mesmo struct para tornar mais fácil a leitura e compreensão do código.  Em seguida foi implementada a função putPixel que exibia um ponto na tela escrevendo na memória de vídeo. Foram criadas, também, 5 funções drawLine: uma para cada octante e seu oposto e uma para retas verticais, com as quais tive problemas em lidar nas funções dos octantes 2, 3, 6 e 7. Em seguida, foi criada uma função com o nome drawLine que verificava o valor do coeficiente angular da reta (m) com base nos pontos inicial e final da mesma e a posição dos pontos, então os passava para a função drawLine correspondente ao octante com os pontos na ordem correta. Cada função drawLine verificava o valor de d, selecionava o ponto a ser pintado, incrementava os valores do ponto M e usava a função putPixel em um laço de repetição while para pintar sequencialmente todos os pontos da reta.

Quanto à função drawTriangle, é bem simples. Basta usar o algoritmo de Bresenham implementado nas funções drawLine para desenhar linhas entre os 3 pontos passados como parâmetros, formando, assim, o contorno de um triângulo.

4 - Teste da função drawTriangle (há um pixel de cor diferente no ponto inferior esquerdo e no ponto superior devido à um bug que só ocorre quando o ponto inicial é verde (componente RGB: 0, 255, 0).


Com relação à variação das cores. Foram selecionadas as cores dos pontos iniciais e finais, então basta que cada um dos componentes RGB seja calculado da seguinte forma:

                                   cor.r = (cor1.r - cor2.r)/l
                                   l = pontof.x - pontoi.x(para retas horizontais ou inclinadas)
                                   l = pontof.y - pontoi.y(para retas verticais ou inclinadas)
 
l é a distância entre os pontos inicial e final da reta, porém, usar a equação da hipotenusa para retas diagonais estava causando um erro que fazia com que a escala terminasse no ponto médio da reta e se repetisse até o final da mesma.

As cores e os pontos foram passados como parâmetros.



Referências:

Imagens das fórmulas utilizadas no cálculo retiradas de:
https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Imagens 1 e 2 retiradas de e explicação do algoritmo baseada em:
http://letslearnbits.blogspot.com.br/2014/10/icgt1-algoritmo-de-bresenham.html

Imagens 3 e 4 originais de teste do programa produzido.

Outras referências:
https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html
https://jansebp.wordpress.com/2012/12/16/icg-t1-rasterizacao/
Foley, J. D.; van Dam, A.; Fundamentals of Interactive Computer Graphics. Addison Wesley. 1982.
Foley, J. D.; van Dam, A.; Feiner, S. K.; Hughes, J. F. Computer Graphics: Principles and Practice. 2a edição. Addison-Wesley Professional, 1996.
Slides de aula da disciplina Introdução à Computação Gráfica (Rasterization), Professor Christian Azambuja Pagot CI/UFPB (Currículo lattes).




Nota: o código foi feito em C.






Nota menos útil: o teste com a função drawTriangle me lembrou