Baixe o app para aproveitar ainda mais
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 1ny 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 1ny . Esta condição ocorre para 1a 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
Compartilhar