Algoritmo de Bresenham y DDA

Algortimo de Bresenham

El algoritmo de Bresenham es un algoritmo creado para dibujar rectas en los dispositivos de gráficos rasterizados, como por ejemplo: un monitor de una computadora, que determina pixeles que se rellenarán, en función de la inclinación del ángulo de la recta a dibujar. 

Es un algoritmo preciso para la generación de lineas de rastreo que convierte mediante rastreo las lineas al utilizar solo cálculos incrementales con enteros que se pueden adaptar para desplegar circunferencias y curvas. Los ejes verticales muestran las posiciones de rastreo y los ejes horizontales identifican columnas de pixel.

Pseudocódigo:

Si 0<|m|<1

*Se capturan los extremos de la línea y se almacena el extremo izquierdo en (x0,y0).

*Se carga (x0,y0) en el bufer de estructura (se traza el primer punto)

*Se calculan las constantes Δx,Δy, 2Δy y 2Δy-Δx y se obtiene el valor inicial para el parametro de decisión p0=2Δy-Δx.

Para j=0 mientras j<Δx

*En cada xk a lo largo de la línea, que inicia en k=0 se efectúa la prueba siguiente:

Si pk<0

*Trazamos (xk+1,yk).

*Asignamos pk+1= pk+2Δy.

Sino

*Trazamos (xk+1,yk+1).

*Asignamos pk+1= pk+2Δy-2Δx.

Fin Para

Si |m|>1

*Recorremos la dirección en pasos unitarios y calculamos los valores sucesivos 

de x que se aproximen más a la trayectoria de la línea.

Ejemplificamos el algoritmo con la siguiente imagen:

Algoritmo DDA (Algoritmo Diferencial Digital)

El algoritmo DDA es un algoritmo de linea de conversión de rastreo que se basa en el cálculo ya sea en el incremento de X o en el incremento de Y. La finalidad de este algoritmo es determinar los valores enteros correspondientes más próximos a la trayectoria para la otra coordenada.

Los DDAs se usan para rastreo de líneas, triángulos y polígonos.

Pseudocódigo:

Si m>=0 (pendiente positiva)

Si m<=1

de izquierda a derecha

* muestreo de x (Δx =1)

* yk+1 = redondeo(yk + m) k=1,2,...

de derecha a izquierda

* muestreo de x (Δx =-1)

* yk+1 = redondeo(yk - m) k=1,2,...

Si m > 1 (para evitar la aparición de agujeros)

de izquierda a derecha

* muestreo de y (Δy =1)

* xk+1 = redondeo(xk + 1/m) k=1,2,...

de derecha a izquierda

* muestreo de y (Δy =-1)

* xk+1 = redondeo(xk - m) k=1,2,...

Si m<0 (pendiente negativa)

Si |m|<1

de izquierda a derecha

* muestreo de x (Δx =1)

* yk+1 = redondeo(yk + m) k=1,2,...

de derecha a izquierda

* muestreo de x (Δx =-1)

* yk+1 = redondeo(yk - m) k=1,2,...

Si |m| > 1 (para evitar la aparición de agujeros)

de izquierda a derecha

* muestreo de y (Δy =1)

* xk+1 = redondeo(xk + 1/m) k=1,2,...

de derecha a izquierda

* muestreo de y (Δy =-1)

* xk+1 = redondeo(xk - m) k=1,2,...