INTRODUÇÃO
A indústria da informática, durante algumas décadas, sempre se preocupou como as pessoas iriam interagir com os computadores. Essa interação passou da linha de comando - no formato de textos - para computadores com imagens em três dimensões, softwares e hardwares que aceitam comandos por voz e/ou gestos, a fim de facilitar e tornar mais intuitiva a utilização das máquinas. Outro grande salto para a indústria foi a ideia de se utilizar uma interface gráfica, chamada de Interface Gráfica ao Usuário (do inglês Graphical User Interface), que começou muito tempo antes de possuirmos a tecnologia necessária para implementá-la e vem evoluindo cada vez mais com o passar do tempo.
Este trabalho tem como objetivo por em prática algoritmos de rasterização utilizados em computação gráfica para rasterização de pontos e linhas e, por meio da rasterização de linhas, desenhar as arestas de triângulos. Para este trabalho foi utilizado um framework que simule acesso direto à memória de vídeo, visto que os sistemas operacionais modernos proíbem este tipo de acesso pelo usuário.
O QUE É RASTERIZAÇÃO ?
De forma sucinta, rasterização é um processo de converter primitivas matemáticas (pontos, retas, polígonos ou quaisquer objetos do plano cartesiano) em pixels e desenhá-los na tela.
RASTERIZAÇÃO DE UM PONTO NA TELA
Antes de mostrar como rasterizar um ponto, primeiro vamos entender como funciona os nossos monitores. Diferentemente dos Vector Displays (Monitores Vetoriais), que desenhavam em uma tela de fósforo por meio de disparos de elétrons contra ela, os Raster Displays (Monitores Raster) passaram a utilizar pixels que, entre as inúmeras vantagens, permitiram o uso de cores e o preenchimento de polígonos.
A tela de um monitor raster é representada por uma matriz com linhas e colunas. Cada elemento dessa matriz é um pixel, que está associado a um endereço de memória. Todo os pixels podem ser representados por um par ordenado X e Y, onde X e Y assumem valores inteiros.
Um dos sistemas de cores mais utilizados para pintar os pixels é o RGBA (R de Red, G de Green, B de Blue e A de ALPHA), onde o alfa é a transparência. Cada componente desse sistema, em geral, está associado a 1 byte (8 bits) de memória, permitindo assim 256 tons de vermelho, 256 tons de verde e 256 tons de azul. Logo, cada pixel contém 4 bytes e o número de pixels na tela é calculado multiplicando-se a quantidade de linhas pela quantidade de colunas.
Então, para pintarmos um pixel, precisamos encontrar o endereço da memória de vídeo e configurarmos as componentes R,G,B e A. Como cada pixel contém 4 bytes, é possível definir uma relação matemática que permite encontrar esse endereço :
offset = 4*X + 4*Y*W
Onde :
X é o valor da coordenada x
Y é o valor da coordenada y
W é a quantidade de colunas
Função PutPixel
Esta função acha o endereço de memória utilizando a relação matemática acima e seta os valores das componentes R,G,B e A. Além disso, ela faz um tratamento para garantir que o ponto será desenhado dentro da tela. Se o valor de x ou de y for menor do que zero ou for maior do que a largura ou o comprimento da tela (definida como 512 x 512), a função encerra. O trabalho foi feito utilizando a linguagem de programação C/C++ e o sistema operacional Ubuntu 15.10 de 64 bits - kernel Linux. Perceba que a componente alfa é setada por padrão com o valor 255. Fazendo isso, só iremos nos preocupar com os valores das demais componentes nas futuras chamadas da função.
FIGURA 1 - Trecho de código : função PutPixel em C/C++.
Resultado 1 : Rasterizando um ponto vermelho na posição (300,300) - R com valor 255 e G e B com valor zero.
FIGURA 2 - Ponto vermelho na tela.
Resultado 2 : Rasterizando 3 pontos em diagonal - o ponto mais abaixo possui as componentes R , G e B com valores iguais a 255.
FIGURA 3 - Pontos na diagonal.
RASTERIZAÇÃO DE UMA LINHA NA TELA
Como faremos isso? Para rasterizar uma linha é necessário determinar quais pixels devem ser “acessos” a partir de dois pontos com coordenadas (x,y) fornecidos. Como uma primeira abordagem para a nossa solução, poderíamos determinar uma equação da reta gerada pelos dois pontos da nossa linha e, para cada valor de x inteiro, encontrar o valor de y associado. Logo após, “acenderíamos” os pixels cujos centros estão mais próximos do ponto de interseção da reta com os eixos verticais formados pelos centros dos pixels - como podemos ver no esquema abaixo, onde os círculos vermelhos representam os centros dos pixels e os círculos azuis representam quais deles serão pintados.
FIGURA 4 - Rasterizando uma linha.
Uma boa ideia, não? Porém, infelizmente este método não é tão eficiente quanto parece ser, pois os pixels a serem pintados teriam coordenadas "x" com os mesmos valores dos pontos de interseção e o valor de "y" seria o resultado de um processo de aproximação. Logo, se utilizássemos essa lógica de implementação, trabalharíamos com operações randômicas e com ponto flutuante.
Algoritmo de Bresenham
Algoritmo de Bresenham
Para a nossa sorte, existe um algoritmo incremental que se mostrou bastante eficiente para esse tipo de análise : o algoritmo de Bresenham. Desenvolvido por Jack Elton Bresnham em 1962, ele se baseia no fato de que dado um segmento de reta com inclinação entre 0º e 45º e partindo-se do pixel mais à esquerda (do qual é tomado como referência ou ponto inicial), o pixel seguinte estará ou à sua direita (e - Leste) ou à sua diagonal superior direita (ne - Nordeste).
xI = x inicial
xF = x final
yI = y inicial
yF = y final
FIGURA 5 - Lógica de implementação do algoritmo do Bresenham.
Para o trabalho utilizei uma derivação (variação) do algoritmo de Bresenham: o algoritmo do Ponto Médio. Porém, esse algoritmo se assemelha bastante ao algoritmo do qual foi originado.
FIGURA 6 - Algoritmo bastante reduzido.
O grande problema da solução proposta acima é a limitação da inclinação do segmento de reta entre 0º e 45º, isso faz com que ele sirva bem para o primeiro octante. Por conta disso, devemos generalizar o código para os demais octantes. Antes de analisarmos cada octante, tome que :
Delta x (dx) = variação no eixo x
Delta y (dy) = variação no eixo y
Coeficiente angular (m) = tangente do ângulo = dy/dx
xF = x final
yI = y inicial
yF = y final
FIGURA 7 - Valores assumidos em cada um dos octantes.
Algumas características de cada octante:
primeiro octante: o coeficiente angular varia entre 0 e 1 (0 <= m <= 1) e xI < xF;
segundo octante: o coeficiente angular é maior do que 1 (m > 1) e yI < yF;
terceiro octante: o coeficiente angular é menor do que -1 (m < -1) e yI < yF;
quarto octante: o coeficiente angular varia entre 0 e -1 (0 >= m >= -1) e xF < xI;
quinto octante: o coeficiente angular varia entre 0 e 1 (0 <= m <= 1) e xF < xI;
sexto octante: o coeficiente angular é maior do que 1 (m > 1) e yF < yI;
sétimo octante: o coeficiente angular é menor do que -1 (m < -1) e yF < yI;
oitavo octante: o coeficiente angular varia entre 0 e -1 (0 >= m >= -1) e xI < xF.
Lembre-se que o eixo y é invertido em relação ao que estamos acostumados, ou seja, ele aponta positivamente de cima para baixo. Por conta disso, o primeiro octante fica no canto inferior direito (como observado na figura abaixo).
FIGURA 8 - Octantes invertidos.
Para deixar o código mais legível, criei uma função chamada de Swap que troca os valores das coordenadas x e y entre si com a ajuda de uma variável auxiliar. Note que os parâmetros formais da função são ponteiros, simulando assim uma passagem por referência em C/C++.
FIGURA 9 - Trecho de código : função Swap em C/C++.
Interpolação linear
Até o momento, as linhas que serão desenhadas terão uma cor única (como podemos ver na figura abaixo). Porém, podemos adicionar um efeito visual e utilizarmos um gradiente de cor entre dois pontos do segmento de reta (linha), ou seja, a cor mudaria suavemente ao longo da linha variando entre as cores dos pontos inicial e final.
Para fazer esse efeito, basta calcular as variações de cada componente R, G e B das cores dos pontos extremos e dividir pelo delta x (dx) ou pelo delta y (dy) e, logo em seguida, ir incrementando esse delta na cor (como podemos ver no trecho de código da FIGURA 12). 
FIGURA 10 - Linha renderizada na tela com uma única cor.
Função DrawLine
Esta função implementa o algoritmo de Bresenham, a sua generalização para os demais octantes e a interpolação linear entres cores dos vértices. Ela utiliza duas variáveis inteiras (int) sinalizadoras: houveTroca e inclinacao. A primeira é inicializada com zero (representando false ) e é setada com 1 (representando true) se os eixos forem trocados e a segunda é inicializada com 1 e setada com -1 caso dy(delta y) seja menor que zero. No cabeçalho da função são passados dez parâmetros, são eles : x0, y0, x1, y1, r0, g0, b0, r1, g1 e b1, respectivamente.
FIGURA 11 - Trecho de código : generalização para os demais octantes - função DrawLine em C/C++.
FIGURA 12 - Trecho de código : generalização para os demais octantes, interpolação linear e parte da implementação do algoritmo de Bresenham - função DrawLine em C/C++.
Resultado 1 : Rasterizando uma linha interpolada na tela - x0 = 100, y0 = 300 , x1 = 200 , y1 = 50 , r0 = 255 , g0 = 0, b0 = 255, r1 = 50 , g1 = 50 e b1 = 50.
FIGURA 13 - Linha interpolada.
Resultado 2 : Rasterizando 4 linhas interpoladas na tela com valores de r0 = 0, g0 = 0, b0 = 255 (azul) e r1 = 255, g1 = 0, b1 = 0 (vermelho).
FIGURA 14 - Linhas interpoladas e interseccionadas no centro da tela.
Resultado 3 : Rasterizando 3 linhas interpoladas na tela.
Linha 1 : DrawLine(0, 511, 511, 0, 255, 0, 0, 0, 0, 255)
Linha 2 : DrawLine(0, 481, 481, 0, 50, 255, 50, 70, 70, 250)
Linha 3 : DrawLine(0, 451, 451, 0, 255, 0, 0, 0, 255, 255)
FIGURA 15 - Linhas interpoladas e paralelas.
DESENHANDO UM TRIÂNGULO NA TELA
Desenhar um triângulo na tela utilizando as técnicas de rasterização de linha para fazer suas arestas é bastante trivial, como você podemos ver na descrição da função DrawTriangle logo abaixo. Mas por que é desenho de um triângulo e não rasterização de um triângulo como nos tópicos acima ? Intitulei esta secção dessa maneira, pois o triângulo não é preenchido, sendo assim, não é uma rasterização.
Função DrawTriangle
Esta função simplesmente realiza chamadas da função DrawLine - uma chamada para cada aresta, resultando em 3 chamadas. Na chamada da função é passada as coordenadas (x,y) dos 3 vértices que compõe o triângulo (x0, y0, x1, y1, x2 e y2), e que posteriormente darão origem às arestas, e os valores das componentes R, G e B de cada um deles (r0, g0, b0, r1, g1, b1, r2, g2 e b2).
Resultado 1: Desenhando um triângulo na tela - x0 = 10, y0 = 50 , x1 = 20 , y1 = 150, x2 = y2 = 250 , r0 = 255 , g0 = 0 , b0 = 0 (vemelho), r1 = 0 , g1 = 255 , b1 = 0 (verde), r2 = 0 , g2 = 0 e b2 = 255.
Resultado 2: Desenhando um triângulo na tela - x0 = 10, y0 = 50 , x1 = 20 , y1 = 150, x2 = y2 = 250 , r0 = 255 , g0 = 100 , b0 = 50, r1 = 60 , g1 = 255 , b1 = 25 , r2 = 180 , g2 = 70 e b2 = 255.
FIGURA 18 - Triângulo com a mesma posição anterior, mas interpolado com outras cores.
Resultado 3: Desenhando um triângulo na tela - x0 = 50, y0 = 70 , x1 = 70 , y1 = 150, x2 = 250 y2 = 350 , r0 = 255 , g0 = 195 , b0 = 200, r1 = 99 , g1 = 250 , b1 = 250 , r2 = 180 , g2 = 200 e b2 = 245.
FIGURA 19 - Triângulo com posição e interpolação diferentes.
Resultado 4: Desenhando dois triângulos na tela
Triangle 1 : DrawTriangle (70,50,160,300,250,250,255,195,200,99,250,250,180,200,245)
Triangle 2 : DrawTriangle(470,450,260,400,350,350,255,0,0,0,255,0,0,0,255)
FIGURA 20 - Triângulos com posições e interpolações diferentes.
DIFICULDADES ENCONTRADAS
Com certeza a maior dificuldade encontrada neste trabalho foi na lógica de funcionamento e na implementação da função DrawLine, mais especificamente na generalização para os demais octantes (entender as características de cada octante e visualizá-las no sistema de coordenadas utilizado nas telas) e na interpolação das cores. Implementar o gradiente em si não é tão difícil, porém, como as cores possuem sua intensidade variando entre 0 e 255, ou seja, números inteiros, primeiramente declarei as componentes R, G e B como variáveis do tipo inteiro (int).O gradiente existe, mas não da forma esperada (como podemos ver no Triangle 2 da FIGURA 21). Então, qual seria a solução ? Para que a variação entre as cores ocorresse de forma mais suave, a solução foi declarar as componentes como valores reais (do tipo float).
Resultado : Triangle 1 com as componentes do tipo float e Triangle 2 com as componentes do tipo int. Ambos os triângulos são interpolados com os vértices nas cores vermelho, verde e azul.
FIGURA 21 - Dois triângulos interpolados com as cores vermelho, verde e azul.
POSSÍVEIS MELHORIAS
Poderia ter sido utilizado neste trabalho classes (em C++) ou estruturas (struct em C) para modularizar os vértices e as componentes R, G e B das cores, pois, como pode ser observado na FIGURA 16, a utilização desses módulos reduziria a quantidade de parâmetros passado nas funções. Porém, optei por não modularizar para que o(s) leitor(es) deste blog veja(m) quais e a quantidade de parâmetros passados para a função de forma explícita. Outras possíveis melhorias seriam preencher os triângulos e aplicar filtros para evitar o serrilhamento das linhas e dos triângulos.
REFERÊNCIAS
- Notas de aula do Prof. Christian Azambuja Pagot
- https://courses.engr.illinois.edu/ece390/lecture/potts/lecture17_6pps.pdf
