Algoritmo De Bresemham

Algoritmo de Bresenham para Pintar Círculos y Cuádricas en General
Carlos E. Alvarez D. 06-39141

Contenido
- Introducción - Algoritmo de Bresenham para Dibujar Líneas Rectas - Algoritmo deBresenham para Dibujar Círculos - Algoritmo Rápido Basado en Algoritmo de Bresenham para Dibujar Elipses - Generalización del Algoritmo de Bresenham para Curvas Cuadráticas - Resumen de Aplicaciones eImportancia

Introducción
Desarrollado por Jack E. Bresenham en I.B.M. en 1962 Publicado en 1965 Originalmente para dibujar líneas rectas Modificado posteriormente para dar origen al conocidoBresenham’s Circle Algorithm

Imagen: http://wscg.zcu.cz/wscg2003/Photos_2003/Bresenham.jpg

Bresenham – Líneas Rectas
Algoritmo Original
- Para líneas en el primer octante desde p1 = (x1, y1 ) hastap2 = (x2 , y2 )

(se traslada para que parta

del origen) - Decisión E( ) o NE ( )

- El error para un píxel se define como la distancia vertical entre el píxel y la recta que se quiere dibujar[3,5,6]

Bresenham – Líneas Rectas
Algoritmo Original Cont.
Se usa el parámetro de decisión
e0 < 0 ⇒ E ei+1 = ei + 2dy y e0 = 2dy− 2dx

y

e0 > 0 ⇒ NE

El error se calcula de maneraincremental, de modo que
ei+1 = ei + 2dy− 2dx

si se elige E o NE donde

respectivamente en el paso anterior,
dy = y2 − y1
[3,5,6]

dx = x2 − x1 y

Bresenham – Líneas Rectas
Algoritmo OriginalCont.
dx = x2 - x1 dy = y2 - y1 E = 2 * dy - dx Dn = E + dx = 2dy Dp = E - dx = 2dy - 2dx x = x1 DO WHILE x eSO ⇒ SO
⇔

eS > eS − 2x +1 ⇒ SO
⇔
−2x −1 ≤ −1∧ 0 < es 2x −1 ⇒ SO
Sólo operacionesenteras
[2,3,5,8]

Bresenham - Elipses
- Ecuación
x2 y2 + 2 =1 2 a b

- Se divide en 4 cuadrantes (4-way symmetry) - Se dibuja primero el arco señalado por 1 y luego 2 - Decisión - 1 N ( ) oNO ( ) - 2 E( ) o SE ( ) - Error b2 x2 + a2 y2 = b2 a2
[2,3,6]

Bresenham - Elipses
Error y Decisión
Caso 1
⇔ ⇔

(Caso 2 es análogo)

eNO < eN ⇒ NO

2 b2 x2 + a2 y2 − b2 a2 + a2 (...