Algoritmo

19/04/2011

COMPUTAÇÃO GRÁFICA
AULA005
Prof. Pier Marco Ricchetti

• Ao final desta aula você estará apto a:
•
•
•
•

Explicar os algoritmos disponíveis para a construção de retas
Implementar os algoritmos apresentados
Questionar a viabilidade de cada algoritmo
Explicar os algoritmos para a construção de círculos e validá-los

1

19/04/2011

•
•
•
•
•
•

Algoritmo Genérico de Traçado de Linhas
Algoritmo DDA
Algoritmo de Bresenham (proposta)
Construção de Círculos
Construção de Círculos : O algoritmo de Bresenham.
Atividades

Algoritmo Genérico (Declive)
A equação para o traçado de linha no eixo cartesiano é dada por:
Y = m.x + b
Onde:
m
...
b
...

representa a inclinação da linha; é o ponto em que a reta cruza o eixo y;

2

19/04/2011

Algoritmo Genérico (Declive)
Para um segmento de reta que liga o ponto P1(x1, y1) ao ponto
P2(x2, y2), pode-se definir os valores “m“ e “b“ da seguinte forma:

Com isso, para intervalos de x, podemos obter intervalos de y, ou seja: Algoritmo Genérico (Declive)
Implementação proposta por Bajuelos [1]
Podemos determinar os valores de y incrementando o valor de x de x1 a x2.
Passos exigidos:
1. Calcular dx e dy: dx = x2-x1 e dy = y2-y1
2. Calcular m: m = dy/dx
3. Calcular b = y1-m*x1
4. Inicializar (x,y) com as coordenadas do ponto extremo inferior esquerdo e xfim com o maior valor de x:
Se dx0, então x=x1, y=y1 e xfim =x2

3

19/04/2011

Algoritmo Genérico (Declive)
Implementação proposta por Bajuelos [1] cont. 5. Testar se todo o segmento de reta já foi desenhado. Se x > xfim parar
6. Desenhar o ponto nas coordenadas correntes
(x,y)
7. Incrementar x: x=x+1
8. Calcular o próximo valor de y: y = m*x + b
9. Continuar no passo 5

Algoritmo Genérico (Declive)
Quais as implicações?
- 2 operações de ponto flutuante a cada passo
- o que ocorre com retas verticais?
- que sugestões você teria para resolver estes problemas?

y y2 y1

x x1 x2