TAREA: ALGORITMOS DE TRAZADO DE LINEAS

Algoritmo de Bresenham

Considerado uno de los algoritmos más efectivos para el trazo de líneas mediante rastreo. Emplea cálculos incrementales con valores enteros. La forma de determinar el siguiente pixel a iluminar en la generación de una línea, se describe a continuación: Se parte de un punto inicial P1(Xinicial,Yinicial). Luego se desplaza una columna (incrementando la posición en X) y se traza el pixel cuyo valor de Y de la línea de rastreo se aproxima más a la trayectoria de la línea.

Se capturan los dos extremos de la línea P1(Xinicial,Yinicial) y P2(Xfinal,Yfinal), se ilumina el primer pixel correspondiente al extremo izquierdo de la línea(P1). Luego se calculan los parámetros que permitien decidir cuál será el proximo pixel a iluminar (DeltaX, DeltaY y ConstanteP). Dependiendo del valor que tome el Parámetro ConstanteP se evalúa y determina la coordenada a iluminar que puede ser: (X+1,Y) para ConstanteP < 0, en caso contrario se ilumina (X+1,Y+1). El proceso anterior debe repetirse 4DeltaX veces.

El algoritmo es el siguinete:

Leer Coordenadas P1(Xinicial, Yinicial)
Leer Coordenadas P2(Xfinal, Yfinal)
Asignar a DeltaX el ABS( Xfinal - Xinicial)
Asignar a DeltaY el ABS( Yfinal -Yinicial)
Asignar a ConstanteP el resultado de 2*DeltaY - DeltaX
Si Xinicial > Xfinal
Asignar Xfinal a X
Asignar Yfinal a Y
Asignar Xinicial a Ultimo
De lo contrario
Asignar Xinicial a X
Asignar Yinicial a Y
Asignar a Xfinal a Ultimo
Iluminar pixel en coordenada X,Y
Hacer mientras X es menor a Ultimo
-Asignar X + 1 a X
-Si ConstanteP es mayor a 0
Asignar ConstanteP + 2 *DeltaY a ConstanteP
De lo contrario
Asignar Y+1 a Y
Asignar a ConstanteP el resultado de ConstanteP+2 *(DeltaY-DeltaX)
Iluminar pixel en coordenada X,Y
Fin de Algoritmo (Bresenham)*/



ALGORITMO DDA (Digital Differential Analyzer)

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

DeltaX = DeltaY /m 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.

El algoritmo es:

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)