Algoritmo Bresenham y DDA

Algoritmo de Bresenham

Definición: Es un algoritmo preciso para la generación de líneas de rastreo que convierte mediante rastreo las líneas 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. El algoritmo de Bresenham es un algoritmo creado para dibujar rectas en los dispositivos de gráficos rasterizados, como por ejemplo un monitor de ordenador, que determina qué pixeles se rellenarán, en función de la inclinación del ángulo de la recta a dibujar.

Pseudocódigo

Algoritmo DDA (Analizador Diferencial 

Digital)

Definición: El Algoritmo DDA es un algoritmo de línea 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 de la línea para la otra coordenada.

Es un algoritmo que se basa en el cálculo y la evaluación de un DeltaX (X) y un DeltaY (Y). Por medio de las siguientes ecuaciones:

DeltaY = m * DeltaX

Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determinan los valores enteros correspondientes más próximos a la trayectoria de la línea para la siguiente coordenada.

Se aceptan como datos de entradas las dos posiciones de los pixeles correspondientes a los extremos de la línea P1(Xinicial,Yinicial) y P2(Xfinal,Yfinal). Las diferencias horizontal y vertical entre las posiciones de los extremos dados, se asignan a las varialbles DeltaX y DeltaY respectivamente. La diferencia con la mayor magnitud determina el valor del parámetro Pasos. Se procede a determinar la compensación necesaria(incremento), para generar la posición del pixel siguiente a lo largo de la trayectoria de la línea. Luego, se ilumina la posición en la pantalla y se repite este proceso cíclico Pasos Veces, hasta obtener la línea deseada.

Pseudocódigo

Leer Coordenadas P1(Xinicial, Yinicial)

Leer Coordenadas P2(Xfinal,Yfinal)

Asignar a DeltaX la diferencia de Xfinal - Xinicial

Asignar a DeltaY la diferencia de Yfinal - Yinicial

Si ABS( DeltaX) > ABS(DeltaY)

Asignar a Pasos el ABS(DeltaX)

De lo contrario

Asignar a Pasos el ABS(DeltaY)

Asignar a Xincremento el resultado de DeltaX / Pasos

Asignar a Yincremento el resultado de DeltaY / Pasos

Asignar a X el valor de Xinicial

Asignar a Y el valor de Yinicial

Iluminar pixel en coordenada X,Y

Desde k=1 hasta Pasos

Asignar a X la suma de X + Xincremento

Asignar a Y la suma de Y + Yincremento

Iluminar pixel en Coodenada X,Y

Fin de Algoritmo(DDA)