Algoritmos Bresenham y DDA (Digital Diferencial Analizer)

Algoritmo DDA (Digital Diferential Analizer)

 

Es un algoritmo de línea de conversión de rastreo que se basa en el cálculo ya sea de ∆y o ∆x.

Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determina los valores enteros correspondientes más próximos a la trayectoria de la línea para la otra coordenada para esto, se debe elegir como variable de rastreo a la variable que vaya a tener mayor variación, es decir, si ∆x > ∆y se debe elegir a x como variable de rastreo y de lo contrario a y, nos referimos como variable de rastreo a la que se incrementa en uno en cada iteración, el Algoritmo DDA hace esto y hace uso de la función signo para que el mismo código se pueda utilizar independientemente de la pendiente de la recta o del cuadrante en el que se quiere trazar la recta.

Pseudocódigo del algoritmo DDA

Algoritmo de Bresenham

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.

El problema con el Algoritmo DDA es que hace uso de aritmética de punto flotante y eso lo hace lento y difícil de implementar en hardware. El algoritmo de Bresenham hace uso de aritmética entera, para entenderlo veamos primero una versión preliminar que todavía utiliza flotantes. Si se quiere trazar una recta en el primer octante, entonces la pendiente es un valor entre 0 y 1, en tal caso, realmente en cada paso solo x se incrementa y respecto a y solo tenemos que decidir si y se incrementa o se queda igual. Llamamos error e a la distancia entre la línea ideal que se desea trazar y el pixel que queda más cerca de dicha línea, si el pixel más cercano queda por arriba de la línea el error será positivo y si el pixel más cercano queda por debajo de la línea el error será negativo. El algoritmo de Bresenham hace uso solo de dicho signo para decidir cuál pixel debe elegirse, si se elige no incrementar y, el error se acumula y si se incrementa y se le resta 1 al error, a continuación, se muestra el algoritmo de Bresenham en su versión simple que usa flotantes.

Pseudocódigo del algoritmo Bresenham