6 pág.
Denunciar
Pré-visualização | Página 1 de 1
07/03/19
1
Traçado de Retas
Computação Gráfica (N521)
Profa. Andréia Formico, Ph.D.
PPGIA - UNIFOR
Algoritmos de Traçado de Retas
• Dados os pontos extremos em coordenadas do dispositivo:
• P1(x1, y1) (inferior esquerdo)
• P2(x2, y2) (superior direito)
• Determina quais pixels devem ser marcados para gerar uma boa
aproximação do segmento de reta ideal
• DDA
• Algoritmo de Bresenham
07/03/19
2
Equação Geral da Reta
• Limitações
• Arredondamentos
• Multiplicação com pontos-flutuantes
• Traçado de retas verticais
DDA (Digital Diferential Analyzer)
• Baseia-se na aplicação direta da fórmula que descreve uma reta no
plano
• Algoritmo incremental
• Aquele em que uma das variáveis tem incrementando o seu valor, por
exemplo x = x + 1, e a outra variável é calculada usando uma fórmula, a partir
da primeira.
07/03/19
3
DDA (Digital Diferential Analyzer)
• Para 0 < m < 1
• Assume-se que os valores em x crescem
mais rapidamente que os em y
• Define-se x em intervalos unitários e
calcula-se o y correspondente
• Para m > 1, basta inverter os o uso das
variáveis x e y
• Assume-se que os valores em y crescem
mais rapidamente que os em x
• Define-se y em intervalos unitários e
calcula-se o x correspondente
function DDA(int x1,int y1,int x2,int y2) {
int x;
float y, m;
m = (y2 - y1) / (x2 - x1);
for (x = x1 ; x <= x2 ; x++) {
y = y1 + m * (x - x1 );
write_pixel (x, round(y));
}
}
(0,0) – (3,2)
(1,3) – (4,5)
Algoritmo de Bresenham (1965)
• Conhecido também por Algoritmo do Ponto Médio
• Solução iterativa
• Inicialmente, considera 0 < m < 1
• Similarmente ao DDA, incrementa-se x em intervalos unitários,
calculando-se o y correspondente ( e y, calculando-se o x
correspondente)
• Utiliza o ponto médio entre dois pixels para decidir qual pixel pintar
• Não necessita de arredondamentos
• Utiliza apenas aritmética inteira
07/03/19
4
Algoritmo de Bresenham
• Retas com inclinação entre 0 e 1
0 < m < 1
• Devemos escolher entre o pixel
localizado à direita (E, pintar o
pixel à direita) e o pixel localizado
à nordeste (NE, pintar o pixel
localizado à direita e acima)
• Devemos observar em que lado da
reta o ponto M está
• Se o ponto M estiver abaixo da reta,
então o pixel NE será aceso, caso
contrário, E será aceso
Algoritmo de Bresenham
• Como calcular em que lado da reta o ponto médio está localizado?
Se e
Pode-se escrever a equação da reta:
Tem-se então uma equação implícita F(x, y) :
07/03/19
5
Algoritmo de Bresenham
• F(x, y) é zero para pontos na reta, positivo para pontos abaixo da reta e
negativo para pontos acima da reta
• Com base nisso, para o teste do ponto-médio, basta calcular o valor de F para
o primeiro ponto-médio, com coordenadas
substituindo-se estas coordenadas na função F(x, y) e atribuir o valor
resultante à variável de decisão (erro) inicial d
(Xp, Yp)
d dnew E
dnew NE
Análise do Sinal de d
• d > 0, significa que M está abaixo do pixel onde a curva ideal passa,
então é escolhido o pixel localizado à NE
• d < 0, significa que M está acima do pixel onde a reta ideal passa, então é
escolhido o pixel localizado à E
• No possível caso em que d = 0, é escolhido qualquer um dos dois pixels,
NE ou E
07/03/19
6
Algoritmo de Bresenham
• À cada iteração, após a decisão de qual pixel será pintado, deve-se atualizar o valor
da variável de decisão d
• Se E foi o último pixel escolhido, M será incrementado somente na direção x.
• Têm-se então as seguintes igualdades:
• Subtraindo dold de dnew para obter a diferença incremental, tem-se dnew = dold + a
• Dessa forma, quando o último pixel escolhido é E, deve-se incrementar d de a = Δy
(Xp, Yp)
dold dnew
Algoritmo de Bresenham
• Por outro lado, se NE foi escolhido, M é incrementado de 1 em ambas as
direções, x e y:
• Subtraindo dold de dnew para obter a diferença incremental, tem-se dnew = dold +
a + b. Dessa forma, quando o último pixel escolhido é NE, deve-se
incrementar d de a + b = Δy - Δx.
(Xp, Yp)
dold
dnew
07/03/19
7
Cálculo do valor inicial de d
• Agora é preciso descobrir qual será o valor inicial de d. Sendo (x1, y1) o primeiro
ponto a ser traçado, a próxima decisão será feita para (x1 + 1, y1 + 1/2):
• Sendo (x1,y1) um ponto da reta, F(x1, y1)= 0. Dessa forma:
• Pode-se eliminar a fração acima multiplicando F(x, y) por 2. Isto multiplica cada
constante e a variável de decisão por 2, mas não afeta o sinal da variável de decisão
Cálculos dos Valores de Decisão (erros/
resíduos) e suas Atualizações
condição inicial
se E for escolhido
se NE for escolhido
07/03/19
8
Código
function bresenham(int x0, int y0, int x1, int y1) {
int dx, dy, incrE, incrNE, d, x, y;
dx = x1 - x0;
dy = y1 - y0;
d = dy * 2 - dx;
incrE = dy * 2;
incrNE = (dy - dx) * 2;
x = x0;
y = y0;
drawPixel(x, y);
while (x < x1) {
if (d <= 0) {
d += incrE;
x++;
} else {
d += incrNE;
x++;
y++;
}
drawPixel(x, y)
}
}
Generalização para Todos os Octantes
07/03/19
9
Generalização para Todos os Octantes
Generalização para Todos os Octantes
07/03/19
10
Observações
• Para saber a qual octante pertence uma reta, basta calcular a sua
declividade m
• Para implementar o algoritmo para os demais quadrantes, basta
substituir o par (x,y) pelo par adequado, dependendo do octante em
questão
• Por exemplo, para o segundo octante, substituir o par (x, y) por (y, x)
• Retas que estão nos octantes da esquerda podem ser transformadas
em retas dos octantes da direita
• Invertendo-se a ordem dos pontos se dx for negativo
Exercícios (incluindo avaliação atitudinal)
• Implemente o algoritmo e Bresenham para traçado de retas para
todos os octantes.
• Torneio do Algoritmo de Bresenham. Bresenham em execução!
07/03/19
11
Referências
• Slides:
http://www.demic.fee.unicamp.br/~jeff/ArquivosIndex/Bresenham
http://letslearnbits.blogspot.com.br/2014/10/icgt1-algoritmo-de-
bresenham.html
• As apostilas de CG que estão no unifor online
• Livro: Computer Graphics with Java, Rowe, Palgrave.
• Artigo do Hill (em inglês) no unifor online: com a derivação detalhada
do Algoritmo de Bresenham (melhor referência na área)Página1
