TrabalhosCG: agosto 2016

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: