Rasterização de Primitivas

Este primeiro post é referente à primeira atividade prática da Disciplina de Introdução à Computação Gráfica. Atualmente, os sistemas operacionais não permitem o acesso direto na memória de vídeo, então será utilizado um framework, desenvolvido pelo professor Christian Azambuja Pagot, que tem como objetivo simular a memória de vídeo, o frame buffer e o color buffer, sendo utilizado em conjunto com o OpenGl.

Rasterização, o que é?
O processo de converter uma imagem vetorial em uma imagem raster (pontos ou píxel) para a saída em vídeo ou em impressora, dá-se o nome de Rasterização. O termo Rasterização também é utilizado para converter uma imagem em vector para um arquivo de formato bitmap (como converter SVG para PNG). É a aproximação de uma primitiva matemática ideal usando píxels da tela.

Rasterização de Pontos

Framebuffer é a região da memória responsável por armazenar as definições de imagem que será representada na tela ou monitor. O framebuffer é subdividido em partes, sendo uma delas o color buffer que é responsável pela representação das cores. As cores possuem diversas formas de representação, sendo a RGBA (Red, Green, Blue, Alpha) uma das mais comuns, entre elas. O RGBA é normalmente definido por um byte para cada cor RGB, sendo o Alpha responsável por calcular elementos de "transparência".

Para acessar o pixel localizado na posição (0,0) da memória, fiz o uso do ponteiro FBptr. Como foi dito anteriormente, em cada pixel encontramos quatro informações de cor (RGBA), sendo cada uma delas representada por um byte, totalizando quatro bytes por pixel. 

 O pixel é organizado no Color Buffer (um tipo de "array" que guarda as informações de cor do pixel) da seguinte forma: o primeiro pixel corresponde as posições 0-3, o segundo pixel 4-7, e assim sucessivamente. Para fazer a rasterização de pontos na tela, utilizei os seguintes códigos:

Como base, foi definida as seguintes estruturas:

Onde, a struct tCor armazena as informações de cor do pixel, e a struct tPonto as informações de posição+cor do pixel.

Função putPixel() : Desenha um pixel

A primeira função e mais básica à ser implementada foi a função putPixel, que é responsável por desenhar um pixel na tela, indo na memória de vídeo e escrevendo o RGBA de cor do pixel. A função putPixel é necessária, pois com o uso dela, faremos os pontos de referencia para construir as linhas e depois, a partir de três pontos, construir o triângulo.
Como mencionado anteriormente, os pixels ficam alinhados em sequência na memória. Para acessarmos o pixel no ponto 0,0 acessamos o primeiro elemento do array representante da memória. Lembrando que cada pixel constitui 4 bytes na memória, logo 4 elementos no array. A informação de posição do pixel foi calculado utilizando a seguinte fórmula: 

(4*x)+(4*y*IMAGE_WIDTH);

Chamando a função putPixel, temos os seguintes resultados:

Rasterização de Linhas : O algoritmo de Bresenham

O algoritmo de Bresenham foi desenvolvido com o intuito de melhorar a eficiência de procedimentos gráficos, como é o caso do desenho de uma reta. Ao invés de analisarmos cada ponto do eixo X e recorrer à equação para todos os pontos, usamos o estudo da simetria da reta. 

Qual pixel escolher?
O algoritmo consiste da avaliação de um determinado ponto médio, onde a cada coluna de píxels, temos duas opções de pixels à serem escolhidos (denominados em sala por E e NE) e a partir da avaliação do ponto médio entre os dois píxeis em relação à reta, teremos uma forma simples de determinar qual dos píxeis deve ser seleccionado.

No exemplo que vimos em sala, mnew é o ponto médio que servirá de referência para a escolha do próximo pixel a ser destacado, já que o algoritmo trabalha primeiramente com dois pontos, inicial e final, e a partir do primeiro vai determinando qual o próximo ponto que dever ser destacado, até chegar ao ponto final.

Exemplo: Como podemos perceber, o pixel azul posicionado abaixo do ponto médio mnew está posicionado mais próximo da intersecção da reta, do que o pixel acima do mnew, sendo assim, como pixel à ser destacado deve ser o mais próximo da reta, então o pixel abaixo do mnew deverá ser destacado.

Print do slide do professor

OBS: Neste caso, o algoritmo de Bresenham trabalha com 1º octante, onde o coeficiente angular varia entre 0-1 (máx 45º). Desta forma, para que a linha seja rasterizada da forma mais "perfeita" possível, não podemos destacar 2 pixels na mesma coluna. Caso o algoritmo seja utilizado baseado em uma variação de 45º-90º, não se pode destacar 2 pixels na mesma linha. A utilização da ideia do ponto médio é exatamente para escolher o pixel que melhor define a reta, como no exemplo:

O problema é que o algoritmo funciona apenas para retas do primeiro octante, isto é, quando Δx>0 , Δy>0 e |Δx|>|Δy|, porém, algumas modificações podem ser feitas para generalizar o algoritmo para os outros octantes. Foi observado em relação ao modelo matemático temos uma inversão na posição dos octantes. Isto acontece porque para os computadores o eixo y cresce para baixo.

Então, porque usar o algoritmo de Bresenham?

Alguns algoritmos de desenho de retas apresentam vários inconvenientes, tanto quanto a precisão, como no que se refere ao tipo de aritmética usada - que é muito importante para o desempenho da rasterização - desta forma, uma operação entre inteiros é mais rápida do que a correspondente operação entre operandos em vírgula flutuante. O algoritmo de Bresenham realiza a rasterização de segmentos de reta empregando apenas operações de aritmética de inteiros e, portanto, permite um maior desempenho do que outras variações de algoritmos para o desenho de retas.

Função drawLine()

Na rasterização de linhas, a função recebe como parâmetros as coordenada (x0,y0) e (x1,y1) e duas estruturas de cor, referente ao primeiro ponto e o segundo ponto.  Para fazer a variação da cor ao longo da reta, eu fiz uma media considerando o quanto cada cor varia. O algoritmo de Bresenham é falho em casos onde o y varia mais que o x, então, nesse caso, temos que inverter os eixos.  Para forçar uma variação maior de x ao invés do y , quando for pintar os pixels, é necessário fazer uma inversão novamente dos eixos para que a linha seja desenhada corretamente, fazendo o espelhamento de eixos com a função.

Segue o código com as aplicações anteriores:

Resultados obtidos:

Rasterização de Triângulos

Função drawTriangle(): Desenha triângulos

A função drawTriangle nada mais é, do que uma função que recebe como parâmetros as estruturas das três vértices do triangulo, com informação de coordenadas de cada ponto e cor, e chama a função drawLine() para rasterizar as linhas. 

Resultados obtidos:

Maiores dificuldades encontradas: 

A maior dificuldade foi o entendimento do funcionamento do algoritmo de Bresenham e o funcionamento do algoritmo para os demais octantes, que foi minimizado após pesquisas sobre o assunto. 
Após conseguir construir as linhas com ajuda do algoritmo, a segunda dificuldade mais aparente foi em relação à como deveria ser feita a interpolação das cores nas retas. 

Possíveis melhoras:
Conseguir construir um código menor.
Tentar melhorar o código para preencher triângulos.

Referências: 

Link1 - Link2 - Link3 - Link4

- FOLEY, JAMES. D. - Computer Graphics: Principles and Practice in C. 2nd Edition: Addison-Wesley, 1990.

- Notas de aula.