Algoritmo de Bresenham y DDA

Algoritmo de Bresenham

El algoritmo de Bresenham para el dibujo de lineas, utiliza la adición, resta y multiplicación por 2 para definir el siguiente punto que se debe representar en la linea, y ya que las computadoras son rápidas para ejecutar estas operaciones, resulta un método considerado eficiente en cuestiones de tiempo.

El algoritmo funciona aumentando una unidad en el eje X o Y dependiendo de la pendiente de la linea que se busca trazar, y el aumento en el otro eje se determina por la distancia al centro del pixel más cercano, esta distancia se llama error. Como se muestra en la imagen.

Dicho algoritmo consiste de:

1. identificar los extremos de la linea, si son el mismo punto se dibuja el punto y se termina.
2. dX = |X2 - X1|  y dY = |Y2 - Y1|
3. se inicializa X = X1 y Y = Y1
4. e = 2 * dY - dX
5. I = 1
6. dibuja el punto (X,Y)
7. mientras (e >= 0){
                    Y = Y + 1
                    e = e - 2dX
          }
          X = X + 1
          e = e + 2dY
8. I = I + 1
9. si I <= dX regresar al paso 6
10. terminar

Es importante mencionar que este algoritmo solo funciona en el primer octante. Existen variantes de este algoritmo con enfoques al dibujo  de curvas y otras lineas, como el siguiente pseudocódigo para el trazo de lineas en todos los octantes:

Funcion LineaBresenham( X1, Y1, X2, Y2)

      // 0 - Distancias que se desplazan en cada eje

      dY = (Y2 - Y1)

      dX = (X2 - X1)

    

      // 1 - Incrementos para las secciones con avance inclinado

      Si (dY >= 0) luego

          IncYi = 1

      Sino

          dY = -dY

          IncYi = -1

      Fin si

    

      Si (dX >= 0) luego

          IncXi = 1

      Sino

          dX = -dX

          IncXi = -1

      Fin si

    

      // 2 - Incrementos para las secciones con avance recto:

      Si (dX >= dY) luego

          IncYr = 0

          IncXr = IncXi

      Sino

          IncXr = 0

          IncYr = IncYi

    

          // Cuando dy es mayor que dx, se intercambian, para reutilizar el mismo bucle.

          // ver octantes blancos en la imagen encima del código

          k = dX: dX = dY: dY = k

      Fin si

    

      // 3  - Inicializar valores (y de error).

      X = X1: Y = Y1

      avR = (2 * dY)

      av = (avR - dX)

      avI = (av - dX)

    

      // 4  - Bucle para el trazado de las línea.

      Hacer

          DibujarPixel(X, Y, Color) // Como mínimo se dibujará siempre 1 píxel (punto).

          Mensaje(av + " ") // (debug) para ver los valores de error global que van apareciendo.

          Si (av >= 0) luego

              X = (X + IncXi)     // X aumenta en inclinado.

              Y = (Y + IncYi)     // Y aumenta en inclinado.

              av = (av + avI)     // Avance Inclinado

          Sino

              X = (X + IncXr)     // X aumenta en recto.

              Y = (Y + IncYr)     // Y aumenta en recto.

              av = (av + avR)     // Avance Recto

          Fin si

      Repetir hasta que (X = X2) // NOTA: La condición de 'Repetir Hasta', se debe cambiar si se elige 'Repetir Mientras'

   Fin función

Digital Differential Analyzer - DDA

Sabemos que la pendiente de una recta se da como :

m = Ay/Ax=y2-y1/x2-x1

La ecuación diferencial anterior puede ser usada para obtener una línea recta rasterizada.

Para cualquier x dentro del intervalo Ax a lo largo de la linea, podemos  calcular su correspondiente y del intervalo Ay desde la ecuación siguiente:

Ay = (y2-y1/x2-x1)Ax

Similarmente, podemos obtener el x del intervalo Ax correspondiente a un especifico Ay como

Ax = (x2-x1/y2-y1)Ay

Una vez que los intervalos son conocidos, los valores para los siguientes x y el siguiente y de la pendiente de la recta puede ser

obtenido como sigue:

Xi+1 = Xi + AX
             = Xi + (X2 - X1)Ay/(Y2 - Y1)
Yi+1 = Yi + AY
             = Yi + (Y2 - Y1)Ax/(X2 - X1)

Las ecuaciones anteriores representan una relación de recursión para los sucesivos valores de x y y a lo largo de la linea requerida.

tal forma de rasterizar una línea se llama analizador diferencial digital (DDA).

Veamos la rutina del analizador diferencial digital para rasterizar una linea.

Algoritmo de línea DDA

1. Leer los puntos finales (x1,y1) y (y1,y2) tal que no sean equivalentes

[Si son iguales entonces trazar ese punto y salir]

2. Ax = |x2-x1| y Ay = |y2-y1|

3. si (Ax >= Ay) entonces 

longitud = Ax

otro

longitud = Ay

finsi

4. Ax = (x2-x1)/longitud

Ay = (y2-y1)/longitud

[Esto hace que tanto Ax como Ay sean iguales a 1 porque longitud es tanto |x1-x2| 

o |y1-y2|. Por lo tanto, el valor incremental de x como y es uno.]

5. x = x1 + 0.5*Sign(Ax)

y = y1 + 0.5*Sign(Ay)

[Aqui, la funcion Sign realiza el algoritmo funcione en todo cuadrante. Este regresa -1, 0, 1 dependiendo en como su argumento es < 0, = 0, > 0

respectivamente. El factor 0.5 hace es posible redondear los valores en la función entera en lugar de truncarlos]

6. i = 1 [Empieza el ciclo, en este lazo se trazan los puntos]

mientras (i <= longitud)

Plot(integer(x),Integer(y))

x = x + Ax

y = y + Ay

i = i +1

7. detener

Ventajas del algoritmo DDA

1. Es el mas simple algoritmo y no requiere de habilidades especiales para su implementación

2. Es un rápido método para calcular la posición de un pixel que el uso directo de la ecuación y = mx +b .

Desventajas del algoritmo DDA

1. Aritmética de punto flotante sigue requiriendo mucho tiempo.

2. La precisión del punto final es deficiente.

Bibliografía:

Atul P. Godse. Computer Graphics, Technical Publications

Algoritmo de Bresenham. Wikipedia