Tendo em mãos a função que desenha um pixel na tela, o passo seguinte é criar um algoritmo que desenhe linhas, conectando dois pixels na tela e interpolando as cores entre eles. Nesta primeira parte, focarei apenas no algoritmo para desenhar as linhas.
Conectando dois pixels: o algoritmo de Bresenham
O algoritmo mais clássico para desenhar linhas é o de Bresenham. Apesar de não ser tão intuitivo, é elegante, pois não emprega nenhuma operação de divisão ou arredondamento, funções associadas diretamente à processos de discretização.
Em resumo, representa-se a reta como uma função de duas variáveis (equação 1), cujo resultado é zero para pontos que estejam contidos na reta, maior que zero se o ponto estiver acima, e menor que zero se estiver abaixo da reta. Manipulando a outra forma de representação matemática da reta (equação 2), onde (x0, y0) é o ponto inicial e (x1, y1) é o ponto final, obtém-se a equação 3.
 |
| Representações matemáticas de uma reta |
Utilizando a equação obtida, o algoritmo avalia a interseção da reta com uma determinada coluna de pixels e o ponto médio entre dois pixels dessa coluna, entre os quais a reta passa. Se o ponto médio estiver abaixo da reta, ou seja, a reta passa acima do ponto médio, o pixel superior é aceso. Caso contrário, o pixel inferior é aceso. A partir do resultado dessa escolha, o próximo ponto médio a ser comparado com a reta é deslocado a cada coluna de pixels avaliada, de forma que a reta passe entre dois pixels. Uma representação gráfica pode ser vista a seguir.
 |
| Figura 1: ponto médio acima da reta |
Dado que o pixel c foi aceso, avalia-se a posição do próximo ponto médio, m. Para isso, utiliza-se a função d = F(x,y) definida anteriormente. Sendo d = F(m), se d < 0 (ponto médio abaixo da reta), o pixel ne (nordeste) é aceso. Caso contrário (d >= 0, ponto médio acima da reta, como na figura), o pixel e (east, leste) é aceso. Assim, temos a equação
Supondo que o pixel e tenha sido escolhido, para a coluna de pixels seguinte, temos:
 |
| Figura 2: novo ponto médio dado que o anterior estava acima da reta |
O que nos dá a equação
Ou seja, para avaliar o próximo ponto médio, só é necessário adicionar α à variável de decisão anterior. Se o pixel ne fosse escolhido na avaliação anterior, teríamos então
 |
| Figura 3: novo ponto médio dado que o anterior estava abaixo da reta |
O que nos daria a equação
Assim, a cada pixel escolhido basta fazer os devidos incrementos na variável de decisão d. Quanto ao 1º pixel,
O que resulta em
Para que não seja feita nenhuma divisão, multiplica-se F(x,y) por 2 em todas as equações. Assim, está descrito o algoritmo de Bresenham. Substituindo alfa e beta pelos valores apresentados anteriormente, chegamos à seguinte função:
void DrawLine(pixel_t p0, pixel_t p1) {
int dx = p1.x - p0.x;
int dy = p1.y - p0.y;
int d = 2*dy - dx;
int incNE = 2*(dy-dx);
int incE = 2*dy;
pixel_t cur = p0;
PutPixel(cur);
while(cur.x < p1.x) {
if(d > 0) {
cur.x++;
cur.y++;
d += incNE;
} else {
cur.x++;
d += incE;
}
PutPixel(cur);
}
PutPixel(p1);
}
A função recebe dois pontos, p0 e p1, e utiliza a variável de decisão d para determinar a posição do próximo ponto médio, baseada na escolha do ponto médio atual. Porém, este algoritmo apresenta duas limitações: 1) só traça retas com coeficiente angular entre 0 e 1, ou seja, dx > dy; 2) se os pontos forem fornecidos em ordem diferente, não funciona.
A primeira limitação se deve ao fato de o processo avançar no eixo x, isto é, incrementando a variável x e avaliando a posição y da reta, onde x varia entre o ponto inicial e o final. Se a reta possuir uma inclinação maior que 1, este método é falho, visto que para um mesmo valor de x, pode haver mais de um pixel aceso na coluna. Foley explica:
Considere uma aproximação da reta de 1 pixel de espessura; Que propriedades deveria ter? Para linhas com inclinações entre -1 e 1 (inclusive), exatamente 1 pixel deve ser aceso em cada coluna; para linhas com inclinações fora desse intervalo, exatamente 1 pixel deve ser aceso em cada linha.
Vamos, então, estudar como adaptar o algoritmo para inclinações maiores que 1. Em seguida, trataremos de coeficientes negativos. Vejamos, então, como se comporta uma reta do primeiro caso.
Agora temos uma rotina diferente, porém a função de decisão F(x,y) descrita anteriormente ainda é válida. Se o ponto médio estiver à esquerda da reta (acima da reta, logo d > 0), acende-se o pixel n (norte). Caso contrário, se estiver à direita (abaixo da reta, logo d < 0), escolhe-se o pixel ne. Assim, temos a equação abaixo para a variável de decisão:
Perceba que os incrementos em xc e yc são diferentes, uma vez que a progressão do ponto médio também é diferente. Vamos agora para o próximo pixel.
Se o pixel escolhido anteriormente for o norte, o próximo ponto médio sofrerá apenas um incremento na sua coordenada y. Assim,
Já se o pixel escolhido anteriormente tivesse sido o ne,
Teríamos a equação
E quanto à 1º variável de decisão,
O que nos dá
Comparando os dois casos vistos até agora, percebe-se que são bastante similares. Analisemos agora os casos em que o coeficiente angular é negativo. Primeiro, para a inclinação entre -1 e 0.
Percebe-se que, agora, o dy é negativo, e o ponto médio sofre decremento em y. Além disso, se o ponto médio atual estiver acima da reta, o próximo ponto médio sofrerá deslocamento tanto vertical (para baixo), quanto horizontal. Caso esteja abaixo da reta, sofrerá apenas o deslocamento horizontal. Assim, é desnecessário mostrar todas as equações para os dois casos. Basta deduzir os incrementos e decrementos a partir da imagem.
Agora, para inclinações menores que -1, o raciocínio é o mesmo para inclinações maiores que 1.
Organizando todas as combinações possíveis para o coeficiente angular e para a variável de decisão, montei a tabela abaixo, que sumariza tudo o que foi explicado até agora.
A coluna "d+=" representa o incremento na variável de decisão baseado no resultado anterior. Já a coluna "coord." mostra os incrementos nas coordenadas. E se os pontos forem fornecidos em ordem diferente? Bem, isso significa que x1 < x0. Neste caso, há dois casos possíveis:
Isto pode ser resolvido facilmente trocando os pontos de posição e, consequentemente, invertendo os sinais de dx e dy:
Agora, finalmente, vamos ao algoritmo!
void DrawLine(pixel_t p0, pixel_t p1) {
int dx = p1.x - p0.x;
int dy = p1.y - p0.y;
int d, incDPos, incDNeg;
if(dx < 0) { // inverter os pontos se em ordem contrária
pixel_t temp = p0;
p0 = p1;
p1 = temp;
dx = -dx;
dy = -dy;
}
int dySig = (dy < 0)?(-1):1; // dy signal
pixel_t cur = p0; // variável temporária
PutPixel(p0);
if( dySig*dy <= dx ) { // |m| <= 1
d = 2*dy - dySig*dx; // d_start
incDPos = 2*(dy - dySig*dx); // if d >= 0
incDNeg = 2*dy; // if d < 0
while(cur.x < p1.x) { // para cada x
if(d < 0) {
d += incDNeg;
cur.x++;
} else {
d += incDPos;
cur.x++;
cur.y += dySig;
}
PutPixel(cur);
}
} else { // |m| > 1
d = dy -2*dySig*dx; // d_start
incDPos = -2*dx*dySig; // if d >= 0
incDNeg = 2*(dy - dySig*dx); // if d < 0
while( cur.y*dySig < p1.y*dySig ) { // for each y
if(d < 0) {
d += incDNeg;
cur.x++;
cur.y += dySig;
} else {
d += incDPos;
cur.y += dySig;
}
PutPixel(cur);
}
}
PutPixel(p1);
}
Para avaliar as quatro faixas de inclinação, utilizei o código a seguir:
int i = 0;
void MyGlDraw(void) {
pixel_t p0, p1;
composePixel(100, 250, 255, 255, 255, 255, &p0);
composePixel(200, 400-i, 255, 255, 255, 255, &p1);
DrawLine(p0, p1);
if(i++ >= 300) i = 0;
}
Me utilizei do fato que esta função é executada continuamente, porém com um pequeno delay entre chamadas consecutivas, o que permite visualizar cada loop. O resultado pode ser visto no vídeo a seguir:
Para m > 0, o algoritmo funcionou como deveria (lembrando que o ponto de origem da tela está no canto superior esquerdo). O problema apareceu ao traçar retas com m < 0.
Após algumas tentativas de solucionar o problema, acidentalmente consegui resolver para -1 < m < 0, invertendo o sinal dos incrementos quando dy < 0 (linhas 21 e 22 do código anterior).
incDPos = dySig*2*(dy - dySig*dx); // if d >= 0 incDNeg = dySig*2*dy; // if d < 0
Daí, fui tentar descobrir o porquê de ter dado certo. Voltando aos cálculos, percebi que cometi um erro. Quando m < 0, isto é, dy < 0 (dado que dx > 0 sempre), a função de decisão assume sinais opostos aos presumidos anteriormente.
Cheguei a essa conclusão através de exemplos. Suponha a reta definida pela equação y = -x/4. Como dito anteriormente, dado que dx > 0, dy < 0 e, portanto, assumamos dy = -1 e dx = 4.
Usando a outra representação da reta, F(x,y) = αx + βy + γ e substituindo os coeficientes, chega-se à função de decisão F(x,y) = -x - 4y. Tomemos como referência o ponto (x,y) = (4,-1). Percebe-se que o mesmo está contido na reta, pois F(4,-1) = -4 - 4*(-1) = 0. Incrementemos a coordenada y em 1 unidade, obtendo o ponto (4,0), claramente acima da reta. Daí, F(4,0) = -4 - 4*0 = -4 < 0. Decrementemos a coordenada y do ponto de referência em 1 unidade. Obtemos F(4,-2) = - 4 - 4*(-2) = 4 > 0. Ou seja, para pontos acima da reta, d < 0, e para pontos abaixo, d > 0.
Isto muda drasticamente o algoritmo, pois, para -1 < m < 0, por exemplo, se o ponto estiver abaixo da reta (e, portanto, d > 0), incrementa-se apenas a coordenada x. Já se estiver acima da reta (e, portanto, d < 0), incrementa-se ambas as coordenadas x e y. O mesmo raciocínio se aplica para m < -1 (com os devidos incrementos e decrementos, é claro).
Assim, obtemos uma nova tabela de possibilidades, que pode ser vista a seguir.
Corrigindo o algoritmo, percebi que não adiantaria muito generalizar as variáveis de decisão e de incrementos, pois o trabalho seria praticamente o mesmo para trocar de sinal e/ou permutar os incrementos ao longo do programa, além de não ser tão intuitivo quanto discretizar os casos possíveis. Assim, segue a função corrigida.
void DrawLine(pixel_t p0, pixel_t p1) {
int dx = p1.x - p0.x;
int dy = p1.y - p0.y;
int d, incDPos, incDNeg;
if(dx < 0) { // exchange points if order reversed
pixel_t temp = p0;
p0 = p1;
p1 = temp;
dx = -dx;
dy = -dy;
}
int dySig = (dy < 0)?(-1):1; // dy signal
pixel_t cur = p0; // buffer for current pixel
PutPixel(p0);
if( dySig*dy <= dx ) { // |m| <= 1
if(dy < 0) {
d = 2*dy + dx; // d_first
while(cur.x < p1.x) { // for each x
if(d < 0) { // midpoint ABOVE the line
d += 2*(dy + dx);
cur.x++;
cur.y--;
} else { // midpoint BELOW the line
d += 2*dy;
cur.x++;
}
PutPixel(cur);
}
} else {
d = 2*dy - dx; // d_first
while(cur.x < p1.x) { // for each x
if(d < 0) { //midpoint BELOW the line
d += 2*dy;
cur.x++;
} else { // midpoint ABOVE the line
d += 2*(dy - dx);
cur.x++;
cur.y++;
}
PutPixel(cur);
}
}
} else { // |m| > 1
if(dy < 0) {
d = dy + 2*dx; // d_first
while( cur.y > p1.y ) { // for each y
if(d < 0) { // midpoint ABOVE the line
d += 2*dx;
cur.y--;
} else { // midpoint BELOW the line
d += 2*(dy + dx);
cur.x++;
cur.y--;
}
PutPixel(cur);
}
} else {
d = dy -2*dx; // d_first
while( cur.y < p1.y ) { // for each y
if(d < 0) { // midpoint BELOW the line
d += 2*(dy - dx);
cur.x++;
cur.y++;
} else { // midpoint ABOVE the line
d += -2*dx;
cur.y++;
}
PutPixel(cur);
}
}
}
PutPixel(p1);
}
O vídeo a seguir prova o funcionamento do algoritmo, inclusive para os pontos fornecidos em ordem contrária. Executando o código a seguir,
int i = 0;
void MyGlDraw(void) {
pixel_t p0, p1;
composePixel( 0, 250, 255, 255, 255, 255, &p0);
composePixel(200, 500-i, 255, 255, 255, 255, &p1);
DrawLine(p0, p1);
composePixel(500, 250, 255, 255, 255, 255, &p0);
composePixel(300, i, 255, 255, 255, 255, &p1);
DrawLine(p0, p1);
if(i++ >= 500) i = 0;
}
Colorindo as linhas: interpolação linear de cor
Não basta apenas desenhar as linhas. Elas têm que ter cor. E não uma cor só, mas uma que varie entre as cores de suas extremidades. Para isso, utiliza-se a interpolação linear, sugerida pelo professor.
Interpolação é "o método que permite construir um novo conjunto de dados a partir de um conjunto discreto de dados pontuais previamente conhecidos. (...) Através da interpolação, pode-se construir uma função que aproximadamente se 'encaixe' nestes dados pontuais, conferindo-lhes, então, a continuidade desejada" [Wikipedia]. Um dos métodos de interpolação é o linear, que faz esse processo através de um polinômio de primeiro grau (uma reta).
No nosso caso, temos uma função y = f(x), que recebe como parâmetro uma das coordenadas de um pixel intermediário (ou x ou y, como será visto mais à frente), e retorna a cor desse pixel, baseada na cor dos pixels das extremidades do intervalo.
Para visualizar o processo, considere dois pontos, Pi = (xi, yi) e Pi+1 = (xi+1, yi+1), onde yi = f(xi). Deseja-se encontrar o valor da função para uma determinada coordenada μ situada entre xi e xi+1, como na figura abaixo.
Por semelhança de triângulos, sabe-se que:
Manipulando os termos, tem-se:
O que nos dá a equação da reta que passa pelos dois pontos conhecidos. Adaptando para o nosso caso, consideramos que yi e yi+1 são as cores dos pixels inicial e final da reta, respectivamente, e y é a cor que se deseja obter do pixel intermediário. Como são quatro componentes de cor, faz-se o processo para cada um deles, considerando os respectivos componentes dos pixels das extremidades.
Quanto à coordenada de entrada, segue-se o mesmo raciocínio utilizado no algoritmo de Bresenham (relembre): para |m| <= 1, será a coordenada x; caso contrário, será a coordenada y.
Assim, segue a função que faz este processo. Ela recebe os dois pixels que definem a linha (extremidades), e o ponteiro para o pixel que será sendo processado dentro da função DrawLine.
void interpolateColor(pixel_t p0, pixel_t* p, pixel_t p1) {
int dx = (p1.x - p0.x);
int dy = (p1.y - p0.y);
int dySig = (dy < 0)?-1:1; // checks dy signal
if( dy*dySig <= dx ) { // |m| <= 1
for(int i = RED; i <= ALPHA; i++) { // for each component, interpolate
p->color[i] = (unsigned char)(p0.color[i] + (p->x - p0.x)*(p1.color[i] - p0.color[i])/dx);
}
} else { // |m| > 1
for(int i = RED; i <= ALPHA; i++) { // for each component, interpolate
p->color[i] = (unsigned char)(p0.color[i] + (p->y - p0.y)*(p1.color[i] - p0.color[i])/dy);
}
}
}
E, no arquivo main.cpp,
int i = 0;
void MyGlDraw(void) {
pixel_t p0, p1;
composePixel(250, 0, 255, 0, 0, 255, &p0);
composePixel(500-i, 200, 0, 0, 255, 255, &p1);
DrawLine(p0, p1);
composePixel(250, 500, 0, 0, 255, 255, &p0);
composePixel(0+i, 300, 0, 255, 0, 255, &p1);
DrawLine(p0, p1);
if(i++ >= 500) i = 0;
}
O resultado desse código pode ser visto no vídeo a seguir.
Desenhando "triângulos"
A terceira função requisitada pelo professor foi uma que traçasse um triângulo dados três pontos. Assim, essa função faz nada mais do que traçar uma linha entre cada um dos vértices. Muito simples. Por isso é um "triângulo", pois um de verdade seria preenchido. Segue o código.
void DrawTriangle(pixel_t p1, pixel_t p2, pixel_t p3) {
DrawLine(p1, p2);
DrawLine(p2, p3);
DrawLine(p3, p1);
}
Executando na função principal MyGlDraw o seguinte código
// x y r g b a struct
composePixel(250, 50, 255, 0, 0, 255, &p0);
composePixel(100, 200, 255, 255, 0, 255, &p1);
composePixel(400, 100, 0, 0, 255, 255, &p2);
DrawTriangle(p0, p1, p2);
Obtém-se a figura abaixo.
 |
| DrawTriangle(p0, p1, p2), de coordenadas e cores descritas no código anterior. |
Referências FOLEY et al. Computer Graphics - Principles and Practice with C. 2ª ed. Addison-Wesley.
MONTERA, Luciana. Interpolação. Facom/UFMS. [Link]
Nenhum comentário:
Postar um comentário