Implementação de Algoritmos de Rasterização
Usando C/C++, OpenGL e um simulador de framebuffer
A computação gráfica é capaz de gerar imagens incríveis nas telas dos computadores, mas para isso, antes houve a necessidade de resolver problemas mais simples, como por exemplo como desenhar uma linha na tela do computador. Neste artigo trataremos de alguns algoritmos que são de grande importância para o cenário, eles são: o posicionamento de ponto na tela, algoritmo de Bresenham, desenho de um triangulo.
Para conseguir fazer os exemplos práticos, fiz uso de um pequeno framework, que simula o framebuffer dos computadores, visto que nos dias atuais os sistemas operacionais não permitem acesso direto a memoria.O framework é bastante simples de se usar, sendo necessário algum conhecimento em C/C++ e o OpenGL instalado na maquina.
Pixel
Um pixel na memoria dos nossos computadores são, normalmente, representados por 4 bytes de informação, cada byte representa respectivamente Red (Vermelho), Blue (Azul), Green (verde) e Alpha(transparência ou brilho), os valores que cada um assume são entre 0 e 255, o alpha varia de 0 a 1. Estes 4 componentes misturados produzem uma gama de cores grande e comumente o suficiente para os trabalhos realizados nos computadores.
Pintando Um Pixel
A tela é uma matriz de pixeis, mas na memoria do computador ela é representada de uma forma contígua, ou seja, ela é uma linha que tem 4*largura*altura bytes de tamanho, para acessar um pixel de posição (x,y) é necessário fazer: 4*x + 4*y*largura, isto é o offset do pixel, ou acesso a primeira cor dele o vermelho, para acessar as outras basta incrementar offset.
void putPixel(int x, int y, Color * c) {int offset = 4*x + 4*y*IMAGE_WIDTH;FBptr[offset] = c->R;FBptr[offset + 1] = c->G;FBptr[offset + 2] = c->B;FBptr[offset + 3] = c->A;}
A função exemplifica o paragrafo anterior, FBptr é um ponteiro para o inicio da memoria e Color é um struct que contem 4 inteiros e cada um é um componente RGBA.
Como fazer isso ??
co = (struct Color *) malloc(sizeof(Color));
co->R = 0;
co->G = 0;
co->B = 0;
co->A = 255;
Pos * p = (struct Pos *) malloc(sizeof(Pos));
p->x = 0;
p->y = 0;
int i,j;for(i = 0; i < IMAGE_WIDTH;i+=4) {
for(j = 0; j < IMAGE_HEIGHT; j+=4) {
putPixel(p->x+i,p->y+j,co);
// co->R = (co->R + j) % 255;
// co->G = (co->G + j) % 255;
co->B = (co->B + j+i) % 255;
}
}
Alterando as variáveis de cor é fácil altera o resultado gerado, assim também como é possível alterar a forma de como os pixels são postos na imagem, retiando o “// “ das linhas e alterando as o numero do loop.
Algoritmo de Bresenham
Rasterizar uma linha na tela do computador não é uma tarefa trivial, pois ela deve selecionar o numero minimo de pixel possível, para a linha ficar fina, ficar parecida como a linha é na matemática. Jack Elton Bresenham criou o algoritmo que resolve este problema, ele é baseado no na ideia do ponto médio.
Na imagem acima cada circulo, no grid, representa o ponto central de um pixel, exatamente no meio entre cada circulo é chamado de ponto médio, baseado nesse ponto é que o algoritmo decide qual pixel que ele selecionará. Quando a posição de seleção for (x,y), a próxima será (x+1,y) se a reta passar por baixo do ponto médio. Caso a reta passe por cima, o pixel selecionado será o (x+1,y+1). Pois assim a a garantia que a reta estará mais próxima do ponto central selecionado.
O exemplo de código:
void drawLineA(Pos * p0, Pos * p1, Color * c){
int dx = p1->x - p0->x, dy = p1->y - p0->y,
e,ix = 1, iy = 1,
x, y,i;
if(dx < 0) ix = -ix;
if(dy < 0) iy = -iy;
float dR = (c2->R - c->R),
dG = (c2->G - c->G),
dB = (c2->B - c->B),
dA = (c2->A - c->A);
dx = abs(dx);
dy = abs(dy);
x = p0->x;
y = p0->y;
if (dx > dy) {
e = (dy << 1) - dx;
dR /= dx; dG /= dx; dB /= dx; dA /= dx;
for(i = 0; i < dx; i++) {
c->R += dR;
c->G += dG;
c->B += dB;
c->A += dA;
putPixel(x,y,c);
if(e < 0)
e += dy << 1;
else {
y += iy;
e += (dy - dx) << 1;
}
x += ix;
}
} else {
e = (dx << 1) - dy;
dR /= dy; dG /= dy; dB /= dy; dA /= dy;
for(i = 0; i < dy; i++) {
c->R += dR;
c->G += dG;
c->B += dB;
c->A += dA;
putPixel(x,y,c);
if(e < 0)
e += dx << 1;
else {
x += ix;
e += (dx - dy) << 1;
}
y += iy;
}
}
}Calma, eu explico.
Em uma posição (x-1,y) temos que descobrir se em (x,y+e) , y + e < 0.5 + y, para com isso decidirmos qual pixel sera pintado. Repete-se o mesmo processo para que (x+1,y+e+m), y+e+m < 0.5 + y.
Temos que para Δy/Δx = m, pois para cada unidade de x, y aumentará em m. Logo, temos a equação e + (Δy/Δx) < 0.5, multiplicando a equação por 2Δx, obtemos a equação: 2eΔx + 2Δy < Δx, para evitar multiplicação por pontos flutuantes, temos uma pequena manobra matemática onde: e’ = eΔx, e => e + m (“=>” significa atribuição como em programação), multiplicando os 2 lados por Δx, obtemos e’ => e’ + Δy (Δx = m*Δy), assim 2(e’+ Δy) < Δx, temos 2(e’+ Δy) -Δx < 0.
int dx = p1->x - p0->x, dy = p1->y - p0->y,
e,ix = 1, iy = 1,
x, y,i;
Color * c = (struct Color *) malloc(sizeof(Color));
c->R = c1->R;
c->G = c1->G;
c->B = c1->B;
c->A = c1->A;Aqui calculamos os Δ’s para o algoritmos em valores absolutos, reservo ix e iy que são as variáveis que serão somadas para mover o cursor de desenho, as demais são variáveis auxiliares.Além de fazer o buffer o struct que cuidar'de alterar as cores da linha.
if(dx < 0) ix = -ix;
if(dy < 0) iy = -iy;
float dR = (c2->R - c->R),
dG = (c2->G - c->G),
dB = (c2->B - c->B),
dA = (c2->A - c->A);
dx = abs(dx);
dy = abs(dy);
x = p0->x;
y = p0->y;Neste bloco o valor das variáveis são negadas, caso os Δ’s sejam negativos pois, assim nos permite mover o ponteiro de desenho em todos os sentidos do plano. Os valores dR, dG, dB, dA são as variações das cores, eles podem assumir valores negativos para que as variações possam diminuir, esses cálculos são feitos para ser possível a interpolação entre 2 cores.Depois os Δ’s são normalizados para não causar erro, visto que agora eles só são uteis para o algoritmo como valores absolutos e por ultimo é salvo a posição inicial da linha.
if (dx > dy) {
e = (dy << 1) - dx;
dR /= dx; dG /= dx; dB /= dx; dA /= dx;
for(i = 0; i < dx; i++) {
c->R += dR;
c->G += dG;
c->B += dB;
c->A += dA;
putPixel(x,y,c);
if(e < 0)
e += dy << 1;
else {
y += iy;
e += (dy - dx) << 1;
}
x += ix;
}
}Aqui entra a ideia das equações tratadas um pouco acima, suponha que (x,y), e = 2Δy-Δx, caso o é seja e < 0, o pixel selecionado será o pixel (x+1,y), ou seja o valor novo de e’ => e’ + Δy (eΔx = Δy), logo e’ => 2Δy, caso e ≥ 0 crescemos o apontador y somamos com o valor de acordo com o Δy, e atualizamos e’ => 2(Δy -Δx), em seguida apenas saímos do laço e incrementamos x. No meio deste código exitem as somas na cor, elas são responsáveis por mudar a cor durante o desenho da linha, ou seja a cor atual mas a sua variação ao decorrer no desenho do seu eixo.O código que vem em seguida deste if segue este mesmíssimo principio só que os valores são todos trocados, quem possuir alguma relação com x passará a relaciona-se com y e quem relaciona-se com y passará a relaciona-se com x.
Os Triângulos
Estes que são estruturas importantíssimas para composição dos objetos 3-d, possui um algoritmo “bastante simples” para o seu desenho, ele basicamente aproveita-se do Bresenham fazendo 3 chamadas para desenhar 3 linhas, a partir dos vértices passados no parâmetro.
void drawTriangle(Pos * p0,Pos * p1,Pos * p2,Color * c, Color * c1) {drawLineA(p0,p1,c,c1);drawLineA(p1,p2,c,c1);drawLineA(p2,p0,c,c1);}
Desempenho
Certamente, estes algoritmos são eficientes, mas mesmo com toda a eficiência que pode ser obtida com a “escovação dos bits” ainda não foi o suficiente, atualmente estes algoritmos são implementados em hardware, visto que para obter máxima performance não existe outra forma mais apropriada, com alguns comandos no openGL ele cuidará de fazer com que a placa grafica rasterize oque se pede.
Problemas Encontrados
O algoritmo de Bresenham que apresento, não foi facil de encontrar, na internet existem varias versões, mas que algumas funcionam e outras não, além de que as que funcionam corretamente, normalmente, não são o Bresenham generalizado, ou seja não conseguem desenhar linhas em todo o plano. A versão funcional que encontrei está em no livro Computer graphics : principles and practice in C. a versão que eu fiz é um pouco diferente mas é inspirada total por ele.
Referencias
Foley, J. (2010). Computer graphics. 2nd ed. Boston [u.a.]: Addison-Wesley.
https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html
