Nesse post será abordado uma
forma de implementação dos algoritmos de rasterização de pontos e
linhas escritos na linguagem de programação C/C++, com o suporte
das bibliotecas da GLUT (The OpenGL Utility Toolkit) e do
framework disponibilizado pelo professor, que simula o acesso à
memória de vídeo.
Rasterização de pontos
A rasterização dos pontos
será feita através da função PutPixel que
rasteriza um
ponto na memória de vídeo, recebendo
como parâmetros as
coordenadas (x,y) do pixel na
tela e uma
cor em RGBA.
A implementação da função
PutPixel é bem
simples, primeiro é necessário identificar a posição do pixel na
memória de vídeo uma vez
que as coordenadas recebidas
estão em um plano bidimensional, e a memória é linear. Para
isso, foi apresentado em sala de aula uma expressão que calcula a
posição de um pixel na memória, considerando a largura (em
pixels) da janela.
Abaixo segue um exemplo da
implementação da função PutPixel.
 |
| Função PutPixel |
Resultado da função:
 |
| Teste da função PutPixel |
Rasterização de Linhas
A rasterização de linhas consiste em, dado dois pontos extremos de um seguimento de reta, determinar que pixeis localizados entre eles devem ser plotados para compor o seguimento.
A função DrawLine rasteriza uma linha na tela, recebendo como parâmetros os pontos extremos, ou seja, o ponto inicial (x0,y0) e o ponto final (x1,y1), além da cor (RGBA) da linha.
O algoritmo
O algoritmo utilizado para rasterização, nesse caso, é o algoritmo de Bresenham que realiza a rasterização de linhas empregando apenas operações com números inteiros, permitindo assim, um melhor desempenho. Ele é baseado no critério do ponto médio.
 |
| Algoritmo de Bresenham |
O problema desse algoritmo é que ele funciona apenas para retas no primeiro octante, ou seja, retas entre 0º e 45º.
Abaixo temos dois printscreens que demonstram a limitação do algoritmo.
 |
| Desenho no primeiro octante |
 |
| Desenho no quinto octante |
Para que possamos representar as retas nos demais octantes, precisamos generalizar o algoritmo.
Generalização do algoritmo de Bresenham
Como a tela não possui coordenadas negativas e precisamos representar as retas dos demais octantes, modificaremos o algoritmo de tal forma que, todas as retas consigam ser representadas no primeiro quadrante, mantendo seu sentido e inclinação.
A primeira modificação a ser feita, e a mais fácil, é considerar apenas os valores absolutos das variações dx e dy.
A segunda modificação é expandir o algoritmo para ar suporte à simetria das retas com o seguinte algoritmo:
Passo 1: Verificar se os valores das coordenadas (xf, yf) do ponto final são menores que as coordenadas (xi,yi) do ponto inicial.
Passo 2: Se xf < xi então o valor de x será decrementado, ou seja, o próximo pixel estará à esquerda do pixel anterior, caso contrário, x será incrementado e o próximo pixel estará à direita.
Passo 3: Se yf < yi então o valor de x será decrementado, ou seja, o próximo pixel estará abaixo do pixel anterior, caso contrário, x será incrementado e o próximo pixel acima.
Código:
A terceira modificação adiciona ao algoritmo uma rotina que desenha retas com ângulo de 90º.
Passo 1: Verificar se há variação da reta no eixo x do plano.
Passo 2: Se a reta for invariante no eixo x, ou seja, dx = 0. plota-se os pontos com o valor constante de x e incrementa o valor de y até que yi = yf.
Código:
Para a quarta e ultima modificação, verificamos se o valor da variação da reta no eixo y é maior que a variação da reta no eixo x.
Passo 1: Verificar se dy > dx.
Passo 2: Se dy > dx então troque o valor de dx com o valor de dy e faça a iteração em relação ao eixo y.
Código:
Resultado após as modificações feitas no algoritmo:
 |
| Resultado da generalização do algoritmo de Bresenham |
Interpolação de cores
A interpolação de cores em aplicada a uma reta nada mais é que a mudança gradativa das cores ao longo dessa reta, partindo da cor do ponto inicial até chegar na cor do ponto final.
Tendo isso em mente, foi desenvolvida a função ColorIncrement que calcula o valor de incremento da cada componente RGBA baseado na variação de cada um.
Para obter a variação é preciso calcular a diferença entre os valores da cor inicial e os valores da cor final, e depois dividir os resultados pela distância entre os pontos, uma vez que queremos que a cor mude gradativamente.
Obs.: Neste trabalho não é utilizado o valor do Alfa (A).
Código:
 |
| Cálculo do valor de incremento |
Resultado da aplicação da interpolação de cores:
 |
| Resultado da interpolação de cores |
Rasterização de triângulos
Após ter implementado e modificado o algoritmo de rasterização de Brasenham, é possível plotar triângulos a partir da rasterização de suas arestas na tela. A função DrawTriangle será implementada com esse propósito, rasterizar arestas, recebendo como parâmetros as posições dos três vértices vem como as cores (RGBA) de cada vértice.
Código:
Resultado da rasterização de triângulos:
 |
| Resultado da função DrawTriangle |
Dificuldades
Na generalização do algoritmo de Brasenham esteve a maior dificuldade encontrada neste trabalho, levando em conta a análise do algoritmo e o tempo para desenvolver uma solução do problema, incluindo tentativas e erros.
Melhorias
Melhorias podem ser feitas no desempenho do algoritmo generalizado, implementar um algoritmo para o preenchimento dos triângulos e desenvolver funções que permitam alterar a inclinação das retas em tempo de execução.
Comentários
Postar um comentário