Buscar

CG aula03 Rasterização Retas v2 2017 2

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 63 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 63 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 63 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Computação Gráfica I 
aula 03 
Algoritmos Rasterização de Retas 
 
 
Computação Gráfica I 2 
 Seja um segmento de reta entre P1= (x1, y1) e P2= (x2, y2) 
 
 Vamos adotar a equação da reta: 
 
 
 y = a x + b 
 
Segmentos de Reta 
? 
? 
Computação Gráfica I 3 
 Entendendo a equação com P1 = (x1, y1) na origem: 
 
 
 
 
 
 
 
 
 
 
 
 
 
Segmentos de Reta 
x1 x2 
y1 
y2 

Computação Gráfica I 4 
 Entendendo a equação com P1 = (x1, y1) na origem: 
 
Segmentos de Reta 
x1 x2 
y1 
y2 

xmy
xtgy
xtgy
x
y
xx
yy
tg










22
2
2
12
12
y = a . x 
Computação Gráfica I 5 
 Entendendo a equação com P1 = (x1, y1) fora da origem : 
 
 
 
Segmentos de Reta 
x1 x2 
y1 
y2 

Computação Gráfica I 6 
 Entendendo a equação com P1 = (x1, y1) fora da origem : 
 
 
 
Segmentos de Reta 
x1 x2 
y1 
y2 

 
1122
1212
1212
12
12
xmyxmy
yyxmxm
yyxxm
xx
yy
tg






b 
a 
a 
a 
a 
a 
Computação Gráfica I 7 
 Como temos P1= (x1, y1) e P2= (x2, y2) fica fácil calcular a e b, e 
posteriormente calcular o valor de y a partir de x, a e b : 
 
Segmentos de Reta 
cxmy
xmyc
xx
yy
m





11
12
12
a 
a 
a 
b 
b 
Computação Gráfica I 8 
 A partir dos pontos P1= (x1, y1) e P2= (x2, y2), basta variar x de x1 
até x2 e seguir calculando o valor de y para cada x 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 b = y1 - a * x1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a * x1 + b; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
Computação Gráfica I 9 
 Versão em C (compilado no Dev C++): 
 
#include <stdio.h> 
 
void desenha_linha(int x1, int y1, int x2, int y2, int color) 
{ 
 float a = ((float) y2-y1) / ((float) x2-x1); 
 float b = y1 - a*x1; 
 float y; 
 
 printf("(%d, %d)\n", x1, y1); 
 
 while( x1 < x2 ) 
 { 
 x1++; 
 y = a*x1 + b; 
 
 printf("(%d, %d)\n", x1, (int) (y + 0.5)); 
 } 
} 
 
Segmentos de Reta 
arredonda o valor de y 
Computação Gráfica I 10 
 Executando esse algoritmo para os pontos P1= (2, 2) e P2= (10,4): 
 
 
 
 
(2, 2) 
(3, 2) 
(4, 3) 
(5, 3) 
(6, 3) 
(7, 3) 
(8, 4) 
(9, 4) 
(10, 4) 
Segmentos de Reta 
Computação Gráfica I 11 
 Executando esse algoritmo para os pontos P1= (2, 2) e P2= (10,7). 
Repare que os valores de x variam de x1 a x2, ou seja, de 2 até 10, 
enquanto os valores de y são calculados e podem se repetir: 
 
 
(2, 2) 
(3, 3) 
(4, 3) 
(5, 4) 
(6, 5) 
(7, 5) 
(8, 6) 
(9, 6) 
(10, 7) 
 
Segmentos de Reta 
Computação Gráfica I 12 
 O algoritmo apresentado anteriormente é bastante simples, porém: 
 Usa aritmética em ponto-flutuante (m precisa ser do tipo real !) 
 Erro de arredondamento no cálculo de y 
 É muito lento ! 
 
 
 
 
 Entretanto, podemos eliminar a multiplicação em: 
 
 y = a . x + b 
 
com uma substituição. 
Segmentos de Reta 
Computação Gráfica I 13 
 Sabemos que: 
xi+1 = xi + 1 
yi = a . xi + b 
yi+1 = a . xi+1 + b 
 
Segmentos de Reta 
Computação Gráfica I 14 
 Sabemos que: 
xi+1 = xi + 1 
 
Segmentos de Reta 
Xi Xi + 1 
Computação Gráfica I 15 
 Sabemos que: 
xi+1 = xi + 1 
yi = a . xi + b 
yi+1 = a . xi+1 + b 
 
Segmentos de Reta 
Xi 
Yi 
Xi + 1 
Yi + 1 
Computação Gráfica I 16 
 Sabemos que: 
xi+1 = xi + 1 
yi = a . xi + b 
yi+1 = a . xi+1 + b 
 
Logo: 
 
yi+1 = a . (xi + 1) + b 
yi+1 = a + a . xi + b 
 
Segmentos de Reta 
Computação Gráfica I 17 
 Sabemos que: 
xi+1 = xi + 1 
yi = a . xi + b 
yi+1 = a . xi+1 + b 
 
Logo: 
 
yi+1 = a . (xi + 1) + b 
yi+1 = a + a . xi + b 
 
Então: 
 
yi+1 = a + yi 
 
 Assim, podemos substituir a multiplicação pela fórmula acima. 
Segmentos de Reta 
Computação Gráfica I 18 
 No algoritmo anterior temos que ajustar: 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 b = y1 - a * x1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a * x1 + b; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
Computação Gráfica I 19 
 Nova versão do algoritmo: 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 y = y1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
 
Segmentos de Reta 
Computação Gráfica I 20 
 Nova versão em C (compilado no Dev C++): 
 
#include <stdio.h> 
 
void desenha_linha(int x1, int y1, int x2, int y2, int color) 
{ 
 float y = y1; 
 float a = ((float) y2-y1) / ((float) x2-x1); 
 
 printf("(%d, %d)\n", x1, y1); 
 
 while( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 printf("(%d, %d)\n", x1, y >= 0 ? (int) (y + 0.5) : (int) (y - 0.5)); 
 } 
} 
Segmentos de Reta 
Computação Gráfica I 21 
 Executando esse algoritmo para os pontos P1= (2, 2) e P2= (10,4) o 
resultado é idêntido ao anterior : 
 
 
 
 
(2, 2) 
(3, 2) 
(4, 3) 
(5, 3) 
(6, 3) 
(7, 3) 
(8, 4) 
(9, 4) 
(10, 4) 
Segmentos de Reta 
Computação Gráfica I 22 
 Executando esse algoritmo para os pontos P1= (2, 2) e P2= (10,7) o 
resultado é idêntido ao anterior: 
 
 
 
 
(2, 2) 
(3, 3) 
(4, 3) 
(5, 4) 
(6, 5) 
(7, 5) 
(8, 6) 
(9, 6) 
(10, 7) 
 
Segmentos de Reta 
Computação Gráfica I 23 
 Analisando esse algoritmo podemos destacar três limitações 
importantes: 
 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 y = y1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
Computação Gráfica I 24 
 Analisando esse algoritmo podemos destacar três limitações 
importantes: 
 Se x1 = x2 então temos um erro no cálculo de “a” 
 Se x1 = x2 então não entramos nenhuma vez no loop 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 y = y1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
x1 = x2 
y1 
y2 
090
Computação Gráfica I 25 
 Analisando esse algoritmo podemos destacar três limitações 
importantes: 
 Se x1 = x2 então temos um erro no cálculo de m 
 Se x1 = x2 então não entramos nenhuma vez no loop 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 y = y1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
x1 = x2 
y1 
y2 
090
Não trata x1 = x2 
Computação Gráfica I 26 
 Analisando esse algoritmo podemos destacar três limitações 
importantes: 
 Se x1 > x2 então não entramos nenhuma vez no loop 
 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 y = y1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
x1 x2 
y1 
y2 

Não trata x1 > x2 
Computação Gráfica I 27 
 Analisando esse algoritmo podemos destacar três limitações 
importantes: 
 X varia sempre de 1 em 1 enquanto Y é calculado a partir de X, podendo 
variar ou não 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 y = y1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
x1 x2 
y1 
y2 
o45
Não trata 
 
o45
Computação Gráfica I 28 
 Dois problemas com esse algoritmo: 
 O erro de arredondamento ainda persiste 
 Não trata linhas horizontais 
 Só funciona no 1º octante ! 
 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 a = (y2 – y1) / (x2 – x1); 
 y = y1; 
 PlotaPixel(x1, y1, cor); 
 
 enquanto ( x1 < x2 ) 
 { 
 x1++; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
y 
x 
y=x y=-x 
Computação Gráfica I 29 
 Tratando o caso de x1 = x2, temos: 
Segmentos de Reta 
x1 = x2 
y1 
y2 
090
Computação Gráfica I 30 
 Tratando o caso de x1 = x2, temos: 
função desenha_linha(x1, y1, x2, y2, cor) 
{ 
 se ( x1 <> x2 ) entao 
 a = (y2 – y1) / (x2 – x1); 
 incr = 1; 
 senao 
 a = 1; 
 incr = 0; 
 fim-se 
 PlotaPixel(x1, y1, cor); 
 y = y1; 
 
 enquanto ( x1 < x2 ou (x1 = x2 e y < y2 ) ) 
 { 
 x1 = x1 + incr; 
 y = a + y; 
 PlotaPixel(x1, y, cor); 
 } 
} 
Segmentos de Reta 
Computação Gráfica I 31 
 E quando temos o caso em que x1 > x2, esse algoritmo funciona? 
Segmentos de Reta 
x1 x2 
y1 
y2 

Computação Gráfica I 32 
 Basta inverter a os parâmetros P1 e P2 quando chamar a função 
desenha_linha: 
 desenha_linha(x2, y2, x1, y1, cor) 
 
 
 
 
 
 
 
 
 
 
 Nesse caso o valor de a fica negativo e o valor de y varia de y2 para 
y1 decrementando de a. 
Segmentos de Reta 
x1 x2 
y1 
y2 

Computação Gráfica I 33 
 Versão em C. Esse algoritmo funciona para linhas verticais, horizontais e nos 
octantes 1, 4, 5 e 8 (com x1 < x2): 
#include <stdio.h> 
 
void desenha_linha(int x1, int y1, int x2, int y2, int color) 
{ 
 float y = y1; 
 float a; 
 int incr; 
 
 if (x1 != x2) { 
 a = ((float) y2-y1) / ((float) x2-x1); 
 incr = 1; 
 } 
 else { 
 a = 1; 
 incr = 0; 
 } 
 
 printf("(%d, %d)\n", x1, y1); 
 
 while( x1 < x2 || (x1 == x2 && y < y2)) 
 { 
 x1 += incr; 
 y = a + y; 
 printf("(%d, %d)\n", x1, y >= 0 ? (int) (y + 0.5) : (int) (y - 0.5)); 
 } 
} 
Segmentos de Reta 
y 
x 
y=x 
y=-x 
Computação Gráfica I 34 
 Versão em C. Esse algoritmo funciona para linhas verticais, horizontais e nos 
octantes 1, 4, 5 e 8 (sempre com x1 < x2): 
 
 
 
(2, 7) 
(3, 6) 
(4, 6) 
(5, 5) 
(6, 5) 
(7, 4) 
(8, 3) 
(9, 3) 
(10, 2) 
Segmentos de Reta 
x1 x2 
y1 
y2 
Computação Gráfica I 35 
Algoritmo-1: DDA 
• Gera as linhas a partir de equações diferenciais. 
• Uma curva qualquer em 2D pode ser definida matematicamente por: 
– Expressão do tipo y = f(x), 
 
 
 - Equação diferencial ordinária: 
dx
xdf
dx
dy )(

Para uma linha reta: y = a.x + b, tem-se: a
dx
dy

Então: dy = a . dx (a primeira derivada é uma constante, e é proporcional a dx e dy)
Um incremento de dx em x, significa um incremento dy (em y) proporcional a dx.
dx 
dy =a dx 
Analisador Diferenciais Digitais - DDA 
Computação Gráfica I 36 
Analisador Diferenciais Digitais - DDA 
• Procedimento: Incrementar simultaneamente x e y de pequenos valores 
dx e dy, proporcionais à primeira derivada de x e y. Este incremento deverá 
ser aplicado a toda extensão do comprimento da linha. 
Isto é: dxxx nn 1 e dxayy nn .1 
dx 
X 
Y 
Y2 
Y1 
Reta de 45º com a =1.0 
Espaço vazio sem pixel 
ligado 
X1 X2 
dy = 3. dx 
Problema: Dependendo do valor de "a" pode acontecer do valor de 1ny diferir de mais de
um pixel do valor de ny  gera espaço vazio na tela, quebrando a continuidade da reta.
Ex: Para a  3 tem-se: dxyy nn .31  , o que deixa 2 pixels vazios entre ny e 1ny .
Esta condição ocorre para 1a  Retas com inclinação superior a arctang(1) = 45.
Computação Gráfica I 37 
Solução: 
 
dx 
X 
Y 
Y2 
Y1 
Reta de 45º com a =1.0 
Espaço preenchido com 
todos os pixels ligados 
X1 X2 
dy = 3. dx 
Analisador Diferenciais Digitais - DDA 
Computação Gráfica I 38 
UVA – Universidade Veiga de Almeida 
Análise: De uma maneira geral tem-se: 
• Região com a > 1: as variações de y são maiores que as variações de x. 
O eixo dos y é o de maior movimento. 
• Região com a < 1: as variações de x são maiores que as variações de y. 
O eixo dos x é o de maior movimento 
Região com a < 1.0 
Y 
X 
Reta de 45º com a = 1.0 
Região com a > 1.0 
45º 
Analisador Diferenciais Digitais - DDA 
Computação Gráfica I 39 
• Se a > 1, então x2 - x1 < y2 - y1: 
– Ay = (y2 - y1) / (y2 - y1) = 1  Y é o eixo de maior movimento 
– Ax = (x2 - x1) / (y2 - y1) < 1 
• Se a < 1, então x2 - x1 > y2 - y1: 
– Ax = (x2 - x1) / (x2 - x1) = 1  X é o eixo de maior movimento 
– Ay = (y2 - y1) / (x2 - x1) < 1 
Considerando que 
12
12
xx
yy
Dx
Dy
a


 , tem-se, portanto:
Então basta fazer: Axxx nn 1 e Ayyy nn 1
Ay 
Ax 
X2 X1 
Y1 
Y2 
DX 
DY 
Analisador Diferenciais Digitais - DDA 
Computação Gráfica I 40 
 Algoritmo Analisador de diferenciais digitais – Versão Visual Basic 
 
Private Sub DDA(X1 As Integer, Y1 As Integer, X2 As Integer, Y2 As Integer) 
 DX = Abs(X2 - X1) 
 DY = Abs(Y2 - Y1) 
 If DY > DX Then 
 DA = DY 
 If DY <> 0 Then 
 Ax = (X2 - X1) / DY 
 Ay = (Y2 - Y1) / DY 
 End if 
 Else 
 DA = DX 
 If DX <> 0 Then 
 Ax = (X2 - X1) / DX 
 Ay = (Y2 - Y1) / DX 
 End if 
 End if 
 X = X1 + 0.5 
 Y = Y1 + 0.5 
 For i = 1 To DA 
 Picture1.PSet (X, Y) 
 X = X + Ax 
 Y = Y + Ay 
 Next 
End Sub 
Analisador Diferenciais Digitais - DDA 
Computação Gráfica I 41 
 Algoritmo Analisador de diferenciais digitais - simplificado 
 
Private Sub DDA(X1 As Integer, Y1 As Integer, X2 As Integer, Y2 As Integer)
 DX = Abs(X2 - X1)
 DY = Abs(Y2 - Y1)
 If DY > DX Then DX = DY
 If DX <> 0 Then
 Ax = (X2 - X1) / DX
 Ay = (Y2 - Y1) / DX
 X = X1 + 0.5
 Y = Y1 + 0.5
 For i = 1 To DX
 Picture1.PSet (X, Y)
 X = X + Ax
 Y = Y + Ay
 Next
 End if
End Sub
 End if 
Analisador Diferenciais Digitais - DDA 
Computação Gráfica I 42 
 O problema que persiste com esse algoritmo é que ele ainda usa um 
valor em ponto-flutuante (a) 
 
 Quando é calculado: 
 
 y = a + y 
 
 o arredondamento de a + y para um número inteiro pode causar 
distorções. 
 
 Outro algoritmo, bastante famoso, para rasterizar segmentos de reta 
é o Bresenham. 
Analisador Diferenciais Digitais - DDA 
Computação Gráfica I 43 
 Só utiliza aritmética de números inteiros. 
 
 Ao invés de calcular o novo valor de y como um incremento apartir do valor anterior, baseia-se na idéia do ponto médio. 
 
 Ou seja, se o algoritmo acabou de plotar um valor (x, y), o 
próximo valor será: 
 
(x+1, y) 
 
OU 
 
(x+1, y+1) 
 
 
Algoritmo Bresenham 
Computação Gráfica I 44 
 Em outras palavras: se o pixel (i, j) acabou de ser plotado o 
próximo será o pixel E(i+1, j) ou NE (i+1, j+1). 
 
 
 
Algoritmo Bresenham 
Computação Gráfica I 45 
 Para decidir, basta verificar se o próximo valor está mais próximo 
de y ou y+1. 
 
 
Algoritmo Bresenham 
Computação Gráfica I 46 
 Calculando o ponto médio entre E e NE. 
 
 
Algoritmo Bresenham 
Computação Gráfica I 47 
 A partir do ponto médio temos o algoritmo de decisão: 
se o segmento de reta passar acima do ponto médio 
 então 
 pinta o ponto NE 
 senão 
 pinta o ponto E 
 
 
Algoritmo Bresenham 
Computação Gráfica I 48 
 Versão em C: 
 
#include <stdio.h> 
 
void bresenham(int x1, int y1, int x2, int y2, int color) 
{ 
 int dx = x2 - x1; 
 int dy = y2 - y1; 
 int pm = 2 * dy - dx; /* Valor inicial do ponto medio */ 
 int incrE = 2 * dy; /* incremento p/ mover E */ 
 int incrNE = 2 * (dy-dx); /* incremento p/ mover NE */ 
 int x = x1; 
 int y = y1; 
 
 printf("(%d, %d)\n", x1, y1); 
Algoritmo Bresenham 
Computação Gráfica I 49 
 Versão em C (continuação): 
 
 
 while ( x < x2 ) { 
 if (pm <= 0) { 
 pm += incrE; 
 } 
 else { 
 pm += incrNE; 
 y++; 
 } 
 x++; 
 printf("(%d, %d)\n", x, y); 
 } 
} 
 
 
 
Algoritmo Bresenham 
Computação Gráfica I 50 
 O algoritmo apresentado anteriormente só funciona para o 1º 
octante, onde: 
 
x1 < x2 
y1 <= y2 
|x2 - x1| >= |y2 - y1| 
 
 
 
Algoritmo Bresenham 
P1 
P2 
Computação Gráfica I 51 
 Para os demais octantes, temos as seguintes regras: 
 
 Se x2 < x1 
 Trocar P1 com P2 
 
 Se y2 < y1 
 y1 = - y1 
 y2 = - y2 
 PlotarPixel(x, -y) 
 
 Se |x2 - x1| < |y2 - y1| 
 Rodar o mesmo algoritmo trocando x com y 
Algoritmo Bresenham 
Neste caso basta 
trocar os pontos 
Computação Gráfica I 52 
 Para os demais octantes, temos as seguintes regras: 
 
 Se x2 < x1 
 Trocar P1 com P2 
 
 Se y2 < y1 
 y1 = - y1 
 y2 = - y2 
 PlotarPixel(x, -y) 
 
 Se |x2 - x1| < |y2 - y1| 
 Rodar o mesmo algoritmo trocando x com y 
Algoritmo Bresenham 
Computação Gráfica I 53 
 Para os demais octantes, temos as seguintes regras: 
 
 Se x2 < x1 
 Trocar P1 com P2 
 
 Se y2 < y1 
 y1 = - y1 
 y2 = - y2 
 PlotarPixel(x, -y) 
 
 Se |x2 - x1| < |y2 - y1| 
 Rodar o mesmo algoritmo trocando x com y 
Algoritmo Bresenham 
Neste caso temos 
que informar se o y 
vai ser negativo ou 
positivo na hora de 
plotar o ponto 
Computação Gráfica I 54 
 Para os demais octantes, temos as seguintes regras: 
 
 Se x2 < x1 
 Trocar P1 com P2 
 
 Se y2 < y1 
 y1 = - y1 
 y2 = - y2 
 PlotarPixel(x, -y) 
 
 Se |x2 - x1| < |y2 - y1| 
 Rodar o mesmo algoritmo trocando x com y 
Algoritmo Bresenham 
Neste caso 
temos que 
escrever outro 
algoritmo para 
tratar x no lugar 
de y e vice-versa 
Computação Gráfica I 55 
 Para tratar essas regras temos o seguinte código: 
 
void bresenham(int x1, int y1, int x2, int y2, int color) 
{ 
 int i, sinal = 1; 
 
 if (x2 < x1) { 
 i = x1; x1 = x2; x2 = i; 
 i = y1; y1 = y2; y2 = i; 
 } 
 
 if (y2 < y1) { 
 y1 = -y1; 
 y2 = -y2; 
 sinal = -1; 
 } 
 
 if (abs(y2-y1) > abs(x2-x1)) 
 bresenhamY(x1, y1, x2, y2, color, sinal); 
 else 
 bresenhamX(x1, y1, x2, y2, color, sinal); 
} 
Algoritmo Bresenham 
Computação Gráfica I 56 
void bresenhamX(int x1, int y1, int x2, int y2, int color, int sinal) 
{ 
 int dx = x2 - x1; 
 int dy = y2 - y1; 
 int pm = 2 * dy - dx; /* Valor inicial do ponto medio */ 
 int incrE = 2 * dy; /* incremento p/ mover E */ 
 int incrNE = 2 * (dy-dx); /* incremento p/ mover NE */ 
 int x = x1; 
 int y = y1; 
 
 printf("(%d, %d)\n", x1, sinal*y1); 
 
 while ( x < x2 ) { 
 if (pm <= 0) 
 pm += incrE; 
 else { 
 pm += incrNE; 
 y++; 
 } 
 x++; 
 printf("(%d, %d)\n", x, sinal*y); 
 } 
} 
Algoritmo Bresenham 
Computação Gráfica I 57 
void bresenhamY(int x1, int y1, int x2, int y2, int color, int sinal) 
{ 
 int dx = x2 - x1; 
 int dy = y2 - y1; 
 int pm = 2 * dx - dy; /* Valor inicial do ponto medio */ 
 int incrE = 2 * dx; /* incremento p/ mover E */ 
 int incrNE = 2 * (dx-dy); /* incremento p/ mover NE */ 
 int x = x1; 
 int y = y1; 
 
 printf("(%d, %d)\n", x1, sinal*y1); 
 
 while ( y < y2 ) { 
 if (pm <= 0) 
 pm += incrE; 
 else { 
 pm += incrNE; 
 x++; 
 } 
 y++; 
 printf("(%d, %d)\n", x, sinal*y); 
 } 
} 
Algoritmo Bresenham 
Computação Gráfica I 58 
 Executando o algoritmo de Bresenham para os pontos P1= (2, 2) 
e P2= (10,7) o resultado é ligeiramente diferente do anterior: 
 
 
(2, 2) 
(3, 3) 
(4, 3) 
(5, 4) 
(6, 4) 
(7, 5) 
(8, 6) 
(9, 6) 
(10, 7) 
Algoritmo Bresenham 
Computação Gráfica I 59 
Algoritmo Bresenham 
Ti
Si
 xi-1 xi-1+1 x
 yi-1
 yi-1+1
 y
 si
 ti
A principal vantagem deste algoritmo reside no fato de utilizar somente adições e 
subtrações inteiras para efetuar a conversão por varrimento, além de multiplicações por 
2. O algoritmo baseia-se na suposição que a melhor aproximação ao segmento de reta é 
dado pelos pixels que estiverem mais perto da reta. Para isto, admita que a diferença 
 i i is t 
 defina qual dos dois pontos possíveis para a composição do próximo ponto a 
ser desenhado, Si ou Ti, está mais próximo da reta. Se i for positivo, então 
s ti i
 e o 
ponto Ti deve ser escolhido. Se i for negativo, então Si será escolhido. Mas 
s f x yi i i   ( )1 11
t y f xi i i    1 11 1( )
Algoritmo Bresenham 
Computação Gráfica I 60 
Substituindo si e ti na expressão de 
i
, chega-se a: 
 
12)1(2 11   iii yxf
. 
 
Mas como i pode ser qualquer, o termo 
1 i
 pode ser obtido fazendo-se i = i + 1 na 
expressão acima, o que resulta: 
 
12)1(21   iii yxf
 
Supondo que 
i
 seja positivo, então a distância si é maior do que a distância ti, o que 
significa que o ponto a ser escolhido será Ti, cujas coordenadas são: 
)1,1( 11   iii yxT
. Em outras palavras, os novos valores de xi e yi serão obtidos de Ti: 
 
xi = xi-1 + 1 e 
yi = yi-1 + 1 
 
que substituidos em 
1 i
 resulta: 
 
122)11(2 111   iii yxf
 
Algoritmo Bresenham 
Computação Gráfica I 61 
UVA – Universidade Veiga de Almeida 
Sabendo que, para a reta, 
f x a f x m a( ) ( )  
, onde a é uma constante qualquer, pode-se 
fazer a seguinte transformação: 
 
mxfmxfxf iii   )1(1)1()11( 111
. 
 
Substituindo esta expressão em 
1 i
, chega-se à: 
 
2212)1(2 111   myxf iii
 
 
Comparando agora a expressão acima com aquela de 
i
, verifica-se que são iguais, a menos 
dos termos 2m – 2, e portanto, pode-se obter uma solução recorrente(isto é, que depende do 
termo anterior) para os 
i
: 
 
221   mii
 
 
Sabendo que 
y y y 2 1
 e 
x x x 2 1
, e ainda que 
xym  /
, fazendo 
d xi i  
 (o 
resultado não se altera pois 
x  0
), resulta que: 
 
)(21 xydd ii 
. 
Algoritmo Bresenham 
Computação Gráfica I 62 
No caso em que 
i
 é negativo, então a distância ti é maior do que a distância si, e portanto as 
coordenadas do próximo ponto serão dadas por: 
),1( 11   iii yxS
, ou seja: 
 
xi = xi-1 + 1, e 
yi = yi-1 
 
Procedendo de forma análoga ao realizado anteriormente, chega-se em: 
 
ydd ii  21
 
 
Substituindo as coordenadas do o primeiro ponto, P1 = (x1, y1) em di obtém-se: 
 
    xyymyxyxfxd  2122212)1(2 11112
 
Algoritmo Bresenham 
Computação Gráfica I 63 
UVA – Universidade Veiga de Almeida 
O algoritmo de Bresenhan para a reta fica então: 
 
1. Desenhar o ponto P1 nas coordenadas (x1, y1). 
2. Calcular 
xyd i  2
 
3. Se di for positivo, então desenhar um ponto nas coordenadas 
11  ii xx
, e 
11  ii yy
. 
Atualizar o valor de di na forma 
)(21 xydd ii 
. 
4. Se di for negativo, então desenhar um ponto nas coordenadas 
11  ii xx
, e 
1 ii yy
. 
Atualizar o valor de di na forma 
ydd ii  21
 
5. Incrementar o valor de i e voltar ao passo 3 
 
Este método de Bresenhan é eficiente para retas com inclinações inferiores a 45 (
m  1
). 
Caso a inclinação seja superior a 45, então as coordenadas x e y devem ser permutadas 
antes do cálculo, e permutadas novamente no instante de serem desenhadas. Caso x seja 
negativo, então P1 e P2 devem ser permutados, resultando novos valores para m e b. 
Finalmente, se m < 0, então x será incrementado e y decrementado ou permanecerá 
inalterado a cada passo. 
Algoritmo Bresenham

Outros materiais