terça-feira, 3 de novembro de 2015

T2 - Transformações do Pipeline Gráfico


O pipeline gráfico é, em Computação Gráfica, a sequência de passos para a rasterização de uma representação em 2D a partir de um cenário em 3D. O pipeline conta com os seguinte passos:

Passos do Pipeline Gráfico
 
Espaço do Objeto para o Espaço do Universo: Transforma os vértices de um objeto para o espaço do Universo, ou espaço do Mundo, por meio da multiplicação de cada vértice pela a matriz Model, cada objeto tem sua própria matriz Model separada. É nesse espaço que ocorre as transformações geométricas, sendo elas a rotação, shear, translação e escala.

Espaço do Universo para o Espaço da Câmera: Essa mudança é equivalente a sobrepor o espaço de referência da câmera sobre o sistema de referência do Universo, isso ocorre pela multiplicação da matriz Model pela matriz View. Para a construção da matriz View é necessário saber a posição da câmera, o look at, que seria para onde a câmera está olhando, e o vetor up, que indica o lado para cima da cena.

Com essa informação é possível criar a base da câmera. A matriz View é equivalente a transposta de B multiplicada por T, onde T seria a matriz de translação responsável por transladar a origem do sistema de coordenadas do universo para a origem do sistema de coordenadas da câmera e B é a rotação para alinhar os eixos da câmera com os eixos do universo.

Espaço da Câmera para o Espaço de Recorte: A cena sai do espaço da Câmera para o espaço de Recorte por meio da multiplicação pela matriz de Projeção. A matriz de Projeção simula a distorção perspectiva, onde os objetos mais perto da câmera ficam maiores enquanto os objetos mais longe da câmera ficam menores. No OpenGL, toda a imagem fica contida num espaço chamado de View Frustum. Na implementação deste trabalho é impossível determinar se a cena fica contida ou não, pois a matriz de projeção utilizada não contem alguns parâmetros presentes na matriz de projeção do OpenGL.

Espaço de Recorte para o Espaço Canônico: A mudança do Espaço de Recorte para o espaço canônico se dá pela homogenização dos vértices (a divisão das coordenadas dos vértices por w). No OpenGL, toda imagem fica contida em um cubo que vai de (1, 1, 1) à (-1, -1, -1).

Espaço Canônico para o Espaço da Tela: A imagem contida no espaço canônico é mapeada para o espaço da tela através de escalas e translações.

Implementação do Pipeline Gráfico
Suzanne após a passagem pelo pipeline gráfico

Transformações/Matrizes utilizadas ao longo do Pipeline gráfico foram os seguintes:

Operações antes de entrar no Pipeline Gráfico: As faces, ou triângulos, que formam a imagem são salvas em uma lista encadeada, cada nó contem 4 variáveis, que são 3 vetores no tipo glm::vec3, tipo primitivo pertencente a biblioteca GLM, e um ponteiro para o próximo nó. 

Operações no Espaço do Objeto: A matriz Model é igual a matriz identidade, ou seja, os vértices do objeto não sofre alteração quando sai do espaço do Objeto para o espaço do Universo. No vídeo abaixo, a Suzanne é rotacionada 0.005 graus a mais que a rotação anterior em torno do eixo Y a cada chamada da função MyGlDraw. 


Operações no Espaço do Universo: Para a construção da câmera foi utilizado as seguintes parâmetros: a câmera se encontra na posição (0, 0, 2), a câmera está olhando para a origem do sistema de coordenadas e o vetor up é paralelo ao eixo y.

posição = (0, 0, 2) , look at = (0, 0, 0) , vetor up = (0, 1, 0)

Operações no Espaço da Câmera: Nesse espaço aplicamos a matriz de projeção que foi ministrada em sala de aula, onde temos apenas como parâmetro a distância do plano de projeção e o centro de projeção da câmera.
 d = 1

Operações no Espaço de Recorte: Apenas dividimos cada coordenada do vértice por w.

Operações no Espaço Canônico: Neste espaço realizamos três tipos de transformações, primeiro invertemos o eixo y com a multiplicação por uma matriz de escala. Depois transladamos a imagem em w, no espaço canônico w é equivalente a 1, para as coordenadas x e y. E por último, escalamos os vértices de acordo com a largura e a altura da tela. As escala e a translação foi realizada de acordo com a matriz ministrada em sala.

Comparação com a Suzanne gerada pelo OpenGL
Melhorias: Pode notar que o resultado obtido comparado com o OpenGL não ficou muito parecido, alguns ajustes nos parâmetros da câmera poderia solucionar este problema.


sexta-feira, 1 de maio de 2015

T1 Extra - Preenchimento de triângulos

O trabalho extra é, com três pontos não alinhados, preencher o triângulo gerado por esses três pontos. Para fazer isso, vamos utilizar as coordenadas baricêntricas para determinar se um ponto pertence ou não a um triângulo.

Definição: De acordo com esse método, cada ponto p do plano pode ser escrito na forma p = λ1 p1 + λ2 p2 + λ3 p3 , onde λ1, λ2 e λ3 são números reais e λ1 + λ2 + λ3 = 1 . Os coeficientes λ1, λ2 e λ3 são denominados coordenadas baricêntricas de p em relação a p1, p2 e p3.

Os valores de  λ1, λ2 e λ3 podem ser obtidos pela regra de Cramer:


O método de coordenadas baricêntricas nos diz que, se λ1, λ2 e λ3 forem maior que 0, então o ponto p pertence ao triângulo formado pelos pontos p1, p2, p3.

Problematização: Mas para saber quais pontos pertencem a um triângulo teríamos que checar todos os pontos da tela.

Bom, para otimizar o algoritmo, podemos limitar quantas comparações o programa pode vir a fazer. Pegando os maiores e menores valores para as coordenadas (x,y) dos vértices dos triângulos, iremos criar um retângulo que engloba o triângulo, limitando assim o número de comparações.

Exemplo da otimização, considere o triângulo abaixo:

Ilustração de um triângulo
Sem a otimização para preencher este triângulo deveríamos checar todos os pontos da tela. Com a otimização, vamos checar apenas os pontos dentro do retângulo, como ilustra a imagem abaixo.

Exemplificação da área de comparação utilizando a otimização

A imagem abaixo exibe o resultado final:
Resultado final do exemplo

Referências Bibliográfica: Bancos de Dados Geográficos - Capítulo 2. Algoritmo geométricos e relacionamentos topológicos. Disponível em:  <http://mtc-m12.sid.inpe.br/archive.cgi/sid.inpe.br/iris@1912/2005/07.01.19.38.>
How to determinate a point in a triangle - Stackoverflow. Disponível em: <http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle>

T1 - Função DrawTriangle();

DrawTriangle: Uma função que desenhe um triângulo na tela, recebendo como parâmetros as posições dos três vértices (xa,ya), (xb,yb) e (xc,yc) bem como as cores (RGBA) de cada um dos vértices. As cores dos pixels das arestas do triângulo devem ser obtidas através da interpolação linear das cores de seus vértices. Não é necessário o preenchimento do triângulo.

Para implementar esta funções é necessário apenas rasterizar 3 linhas ligando os 3 vértices. Como a função de rasterização de linhas já esta implementada, iremos utiliza-lá.

Agora um exemplo de execução:

Exemplo de execução da função DrawTriangle() - exemplo 1

Outro exemplo de execução:
Exemplo de execução da função DrawTriangle() - exemplo 2

T1 - Função DrawLine();

DrawLine: Uma função que rasteriza uma linha na tela, recebendo como parâmetros os seus vértices (inicial e final, representados respectivamente pelas tuplas (x0,y0) e (x1,y1)), e as cores (no formato RGBA) de cada vértice. As cores dos pixeis ao longo da linha rasterizada devem ser obtidas através da interpolação linear das cores dos vértices extremos. O algoritmo de rasterização a ser implementado deve ser o algoritmo de Bresenham.

 Sabemos como rasterizar linhas com o coeficiente angular (m) entre 0 e 1 utilizando o algoritmo de Bresenham. Foi demostrado o cálculo realizado para chegar em um algoritmo que rasteriza linhas com m entre 0 e 1. Utilizando os mesmos cálculos, vamos obter o algoritmo para realizar as rasterizações em retas com o coeficiente angular fora do intervalo 0 e 1.

O algoritmo demostrado em sala rasteriza linhas nos octantes 1 e 6 (rasterização de linha no 6 é obtido por reflexão no algoritmo para o octante 1). Precisamos apenas implementar o algoritmo de Bresenham para os octantes 2, 7 e 8. Pois os demais octantes podem ser rasterizados pela reflexão dos octantes citados.

"Como realizar a reflexão?": Para obter a reflexão basta mudar o octante da linha a ser rasterizada. Os algoritmos para rasterização apenas rasteriza em octantes em que o dx > 0. Antes de inicia a rasterização bastar checar se o dx é positivo, em caso negativo, é necessário realizar a troca do P1 com o P2 (o algoritmo rasteriza do ponto P1 até o P2, onde P1 tem menor valor de coordenada X comparado a P2). Assim o octante será trocado.

Os seguintes cálculos foram obtidos:

Para o segundo octante (m > 1): O valor inicial (d) é igual a dy - 2*dx. Se o valor inicial for maior que  0, o incremento será igual a -2*dx e o pixel a ser rasterizado será o (Xc + 1, Yc), caso contrario, o incremento é igual a 2*(dy - dx) e o pixel a ser rasterizado será o (Xc + 1, Yc + 1).

Para o sétimo octante (m < -1): O valor inicial (d) é igual a dy + 2*dx. Se o valor inicial for maior que  0, o incremento será igual a 2*dx e o pixel a ser rasterizado será o (Xc + 1, Yc), caso contrario, o incremento é igual a 2*(dy + dx) e o pixel a ser rasterizado será o (Xc+ 1, Yc - 1).

Para o oitavo octante (-1 <= m < 0): O valor inicial (d) é igual a 2*dy + dx. Se o valor inicial for maior que  0, o incremento será igual a 2*dy e o pixel a ser rasterizado será o (Xc + 1, Yc - 1), caso contrario, o incremento é igual a 2*(dy + dx) e o pixel a ser rasterizado será o (Xc, Yc - 1).

Imagens:

Rasterização de linhas

T1 - Função PutPixel();

PutPixel() : Uma função que rasteriza um ponto na memória de vídeo, recebendo com parâmetros a posição do pixel na tela (x,y) e sua cor (RGBA).

Como foi passado em sala de aula, para acessar e rasterizar um determinado pixel é necessário multiplicar por 4 a linha a qual o pixel se encontra e somar com a multiplicação da coluna em que o pixel se encontra por 4 e pela largura da tela. Representado pela formula:

Pixel(i, j) = 4*i + 4*Width*j

Estruturas:

Abaixo segue um exemplo de execução:

Exemplo de execução da função PutPixel

T1 - Interpolação de cores

A primeira ideia para a resolução do problema foi, pegar a diferença entre as duas cores e dividir a diferença entre a distância entre os dois pontos. E essa divisão seria incrementada a cor do pixel anterior para definir a cor do próximo pixel. Mas gerou o seguinte resultado:
Rasterização com a diferença de cor dividida pela distância entre os dois pontos

Isso ocorreu por que a distância entre dois pontos não nos dá a quantidade de pixeis que serão pintados, fazendo com que o incremento seja diferente do necessário para fazer a interpolação.

Bom, para saber quantos pixeis serão pintados, basta saber em que octante se encontra e qual é a distância entre uma de suas coordenadas.

Por exemplo, no primeiro octante (0 <= m <= 1), a quantidade de pixeis que serão pintados é igual a diferença entre Xf - Xi, ou seja , Δx. Isso também acontece no oitavo octante.

Já no sétimo e no segundo octante, a quantidade de pixeis que serão pintados é igual a diferença entre o Yf - Yi, ou seja, Δy.

Rasterização com a diferença de cor dividida pela diferença de coordenadas

terça-feira, 21 de abril de 2015

T1 - Definição de octantes

Como foi demonstrado na apresentação do algoritmo de Bresenham para o primeiro octante, é dito do primeiro octante a reta com o coeficiente de angular entre 0 e 1. Para o segundo, sétimo e oitavo octante, usaremos o seguinte cálculo:

- A reta se encontra no segundo octante se satisfazer as seguintes condições:
  1. Δx > 0 e Δy > 0
  2. O coeficiente angular deve ser maior que 1, ou seja, Δy/Δx > 1
- A reta se encontra no sétimo octante se satisfazer as seguintes condições:
  1. Δx > 0 e Δy < 0
  2. O coeficiente angular deve ser menor que -1, ou seja, Δy/Δx < -1
- A reta se encontra no oitavo octante se satisfazer as seguintes condições:
  1. Δx > 0 e Δy < 0
  2. O coeficiente angular estiver entre 0 e -1, ou seja,  -1 <= Δy/Δx < 0.
Representação das octantes e suas propriedades
Observação: Note que nos 4 octantes o dx é positivo, isso servirá na troca de octantes (reflexão).