Rasterização de pontos, linhas (Bresenham) e triângulos

 

Esse post faz parte faz parte da avaliação prática da disciplina Introdução a Computação Gráfica (UFPB - 2016.1), ministrada pelo professor Prof. Christian Pagot.

Instalando a OpenGL

 

 Para realizar esse trabalho é necessário ter instalado a OpenGL que é uma API livre bastante utilizada em computação gráfica. Também é necessário termos instalado a GLUT, uma biblioteca de funcionalidades do OpenGL. No meu caso esse problema foi resolvido com um comando único para sistemas Debian e Ubuntu, basta entrar no terminal e digitar o seguinte comando:

$ sudo apt-get install freeglut3-dev 

Conceitos Básicos

Pixel

O pixel é o menor elemento em um dispositivo de exibição (monitor), ao qual é possível atribuir uma cor. De outra forma, um pixel é o menor ponto que forma uma imagem digital e o conjunto de pixels formam uma imagem inteira. O computador representa os pixels do monitor em uma região da mémoria de vídeo conhecida como Color buffer. Agora que já sabemos a definição de um pixel, vamos conhecer como podemos representar um pixel.


Para representar um pixel utilizamos um sistema de cores chamado RGBA. Esse sistema é formado pelas cores Red (vermelho), Green (verde), B (Azul) e pelo canal Alpha que é reponsavél pela transparência. No maioria dos casos, cada uma das componentes do pixel é representada no computador por 8 bits. Ou seja, seus valores variam de 0 até 255. Assim, o valor de cada componente para o pixel significa a quantidade de vermelho, verde e azul que o pixel deverá possuir. O valor de alpha está relacionado com a transparência, não possuindo importância para esse trabalho. Com essa variação de valores para as componentes primárias de cores conseguimos gerar 256³ ≈ 16 milhões de cores.

Representação do espaço de cores RGB

Exemplo de representação (Big-Endian) das componentes de um pixel na mémoria

Estruturas de dados

Para realizar a programação do problema foram criados duas estruturas de dados auxiliares: color e point. A estrutura color tem 4 componentes para armazenar o valor RGBA para cada pixel e a estrutura point é formada pelas componentes x (horizontal), y (vertical) e pela estrutura cor.

Rasterizar um ponto ( PutPixel() )

Rasterizar um ponto no monitor é a primitiva mais básica que temos. Essa tarefa consiste simplesmente em escolher qual ponto do monitor queremos rasterizar (colorir) e escolhermos a cor na qual vamos pintar o ponto. Para realizar essa tarefa temos que sair de um domínio matemático, cartesiano formado por coordenadas (x,y) para o domínio do computador. As cores de todos os pixels do monitor são armazenados em uma região da mémoria de vídeo chamada Color buffer. O Color buffer funciona da seguinte forma: a primeira região de mémoria armazena as informações relativas ao primeiro pixel do monitor. As informações do segundo pixel estão salvas na segunda região de mémoria e assim sucessivamente. Dessa forma, já é possível determinamos uma função que nos tire de uma determinada posição cartesiana (x, y) para a sua correspondente região de mémiora do Color buffer.

  OffSet = x + y*IMAGE_WIDTH;

Assim, conseguimos ter acesso a região da mémoria de vídeo do pixel escolhido e assim configuramos os valores das suas variavéis de cores. Abaixo está o código da função PutPixel que recebe um ponto e as suas componentes RGBA.

void PutPixel(point p, color c){
    int x = p.x;
    int y = p.y;
    int offSet = x + IMAGE_WIDTH*y;   

    FBptr[offSet*4]   = c.red;
    FBptr[offSet*4+1] = c.green;
    FBptr[offSet*4+2] = c.blue;
    FBptr[offSet*4+3] = c.alpha;
   
}

 

Resultado:

Função PutPixel rasterizando um ponto branco no centro da tela

Rasterização de retas ( DrawLine() )

Existem vários algoritmos de rasterização de retas. Entretanto, o escolhido para ser implementado foi o algoritmo de Bresenham, também conhecido como algoritmo do ponto médio. Esse algoritmo é bem eficiente e gera resultados bem satisfatórios. O funcionamento do algoritmo será explicado brevemente.

Para desenhar uma reta no espaço matemático basta simplesmente escolher um ponto inicial e um ponto final e desenhar um segmento de reta entre esses dois pontos. Para levar esse conceito para o mundo do computador, um espaço discreto, temos o seguinte problema. Se uma reta passar em determinado ponto por 2 pixels, como escolher o pixel que deve ser pintado na tela? Já que não é uma boa ideia pintar dois pixels adjacentes para representar uma reta, pois a reta na sua descrição matemática deve ter espessura quase nula.

Ilustação de um algoritmo de rasterização de reta e o problema de escolher qual pixel pintar.

Algoritmo de Bresenham

O algoritmo de Bresenham não é um algoritmo muito custoso computacionalmente em comparação com outros algoritmos para rasterização de retas, sendo um algoritmo incremental e que evita multiplicações e arredondamentos.

O algorimo de Bresenham será explicado brevemente. Primeiro toma-se como caso particular retas que possuem coeficiente angular m ,entre 0 ≤ m ≤ 1.

A partir da equação da reta :    y = m*x + b

e com manipulações algébricas podemos chegar na seguinte expressão :  
Φ ( x , y )=Δ y⋅x−Δ x⋅y + b⋅Δ x =0.

E chamamos os seguites termos:
α = Δ y
β = −Δ x
γ = b⋅Δ x

Chegando em Φ (x , y ) = α x +β y + γ = 0 

A equação implícita da reta permite dizer que a partir da coordenada x e y de um ponto se ele está ou não está presente na reta. Bresenham observou que através dessa equação podemos saber se um ponto está abaixo ou acima da reta, através do sinal da equação explícita, como pode ser observado abaixo.

Bresenham teve a ideia de avaliar o ponto médio (ponto m da figura acima) para saber qual dos pixels cadidatos rasterizar, ou o pixel NE ou pixel E. Se observamos que a equação implícita avaliada no ponto médio der um valor positivo a reta está mais próxima do pixel E e portanto devemos rasteriza-lo. E se o resultado for negativo devemos rasterizar o pixel NE.



Assim cria-se uma variável de decisão d.

if (d < 0)   next pixel = ne
else  next pixel = e 

Porém avaliar cada pixel com a equação implícita da reta é custoso computacionalmente. Entretanto, Bresenham observou que se o pixel E foi o pixel escolhido para ser rasterizado a expressão de rasterização para o próximo ponto obedecia a seguinte expressão:

d_new =d_old +α



E caso o pixel escolhido fosse o pixel NE, a expressão para o próximo pixel obedecia a seguinte expressão:


d_new =d_old +α +β

E para o pixel inicial a seguinte expressão:

d =2 Δ y −Δ x


Dessa maneira, o algoritmo de Bresenham para valores de m ,entre 0 ≤ m ≤ 1, é expresso abaixo:

Algoritmo de Bresenham para o primeiro octante

Expandindo o algoritmo de Bresenham para os outros octantes

Oito octantes do plano cartesiano

A figura acima mostra as relações dos 8 octantes do plano cartesiano e relações entre os coeficientes angulares de reta e pontos. 

Para criar um algoritmo de Bresenham genérico foi observado primeiro que só era necessário conseguir rasterizar retas em uma das metades do plano, pois por simetria podemos rasterizar retas na outra metade apenas trocando a ordem dos pontos entre si. Por exemplo, visualmente temos o mesmo resultado desenhando uma reta entre (x1,y1) para (x2,y2) e de (x2,y2) para (x1,y1).

Dessa forma, eu escolhi fazer somente a rasterização para a metade direita do plano quando x2 > x1. Se x1 > x2, chamamos a função DrawLine outra vez com os pontos trocados entre si. 

Para o 8° octante observamos que os pixels escolhidos só podem ser E ou SE. Realizando o raciocínio análogo obtemos as seguintes expressões:

Para direção E:

d_new = d_old – 2dy

Para direção SE:

d_new = d_old – 2(dy + dx)

Portanto, no primeiro octante tanto x quanto y são incrementados a cada iteração. No oitavo octante o x é incrementado e y decrementado a cada iteração. Com essa ideia podemos obter todas as expressões para os outros octantes, sempre partindo da coordenada que x e y irão assumir.

Agora analisando quando o m > 1 (2° octante) e quando m < -1 (7° octante) , seguindo a mesma lógica e raciocínio do primeiro octante, obtemos:

2° Octante:
Para m > 1
int incl = (dy>0)? 1:-1;
int d = (2 * dx – dy) * incl;
int incr_e = 2 * dx * incl; 
int incr_ne = 2 * (dx – dy) * incl;

7° Octante
Para m < -1
int incl = (dy<0)? 1:-1;
int d = (2 * dx – dy) * incl;
int incr_e = 2 * dx * incl;
int incr_ne = 2 * (dx + dy) * incl;

Assim, conseguimos rasterizar qualquer reta em qualquer direção do plano cartesiano com o algoritmo de Bresenham.

Resultado:

Retas rasterizadas em várias direções com o algoritmo de Bresenham

Interpolação Liner de cores

Para realizar a interpolação linear de cores das retas foi utilizada a seguinte expressão:
 

 C(λ) = (1 - λ)C_A + λC_B, onde 0 ≤ λ ≤ 1. 

No qual, C_A e C_B são as cores passadas como parâmetros da função do primeiro ponto e di segundo ponto respectivamente. A expressão acima calcula a cor de acordo com λ que foi passado com parâmetro. Para calcular o λ realizamos a seguinte operação:

λ = (posição_atual - posição_inicial) / (posição_final- posição_inicial)

Esse cálculo do λ é realizado tanto para a posições X (variação no eixo OX) e para posições Y (variação no eixo OY) e em seguida calcula-se a média do
λx e λy. Gerando uma interpolação linear dependendo da variação de X quanto de Y.

Resultado:

Interpolação de 6 segmentos de retas

 

 

 

 Rasterização de Triângulos ( DrawTriangles () )

Para rasterizar um triângulo a partir da rasterização de uma linha é algo bem simples. A função DrawTriangle() mostrada abaixo realiza essa tarefa.

void DrawTriangle(point p1, color c1, point p2, color c2, point p3, color c3){

    DrawLine(p1, p2, c1, c2);
    DrawLine(p2, p3, c2, c3);
    DrawLine(p3, p1, c3, c1);

}

Resultado:
 

Triângulo rasterizado com interpolação de cores

 Dificuldades encontradas

O trabalho foi relativamente simples e com poucas dificuldades. A primeira dificuldade foi como adaptar o algoritmo de Bresenham para todos os octantes, mas através de analise de simetria e de crescimento e decrescimento de determinadas posições foi relativamente tranquilo fazer a generalização.

Possíveis melhoras

Uma possível melhora seria a implementação do algoritmo de Bresenham através de matriz de rotação para os outro octantes e comparar qual forma de execução é mais rápida. Uma segunda melhora seria implementar o preenchimento de todo o triângulo rasterizando pontos intermédiarios de uma aresta com o vértice oposto do triângulo. Acredito que isso não deve preencher todo o triângulo, pois como o algoritmo utilizado é o de Bresenham ele deve deixar alguns pontos sem serem coloridos.

 

 Conclusão

O trabalho não foi de grande dificuldade, mas bastante didático para entender a primeira parte do pipeline gráfico utilizado no OpenGL através da rasterização de primitivas (pontos, retas e trinângulos).

Referências

<pt.wikipedia.org/wiki/Algoritmo_de_Bresenham> Acesso: 7 de agosto de 2016
<http://howaboutanorange.com/blog/2011/08/10/color_interpolation/> Acesso em 7 de agosto de 2016
Notas de Aula do Prof. Christian Pagot