Lineas

Algoritmo DDA para generacion de lineas.

Es un algoritmo que se basa en el calculo y la evaluacion de un DeltaX(X) y un DeltaY(Y). Por medio de las siguientes ecuaciones:

DeltaX = DeltaY / m
DeltaY = m * DeltaX 

Se efectua un muestreo de la linea en intervalos unitarios en una coordenada y se determinan los valores enteros correspondientes mas proximos a la trayectoria de la linea para la siguiente coordenada.

Se aceptan como datos de entradas las dos posiciones de los pixeles correspondientes a los extremos de la linea p1(Xinicial, Yinicial) y p2(Xfinal, Yfinal). Las diferencias horizontal y vertical entre las posiciones de los extemos dados, se asigna las variables DeltaX y DeltaY respectivamente. La diferencia con la mayor magnitud determina el valor del parametro Pasos. Se procede a determinar la compensacion necesaria (incremento), para generar la posicion del pixel siguiente a lo largo de la trayectoria de la linea. Luego, se ilumina la posicion en la pantalla y se repite este proceso ciclico, hasta obtener la linea deseada.

Pseudocodigo.

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)

Código:
void DDA(int x0,int y0,int xFin,int yFin)
{
int dx = xFin - x0, dy = yFin - y0, steps, k;
float xIncremento, yIncremento;
float x = x0, y = y0;

if (fabs (dx) > fabs (dy))
steps = fabs (dx); /* |m|<1>
else
steps = fabs (dy); /* |m|>=1 */


xIncremento=float(dx)/float (steps);
yIncrement = float (dy) / float (steps);
setPixel (round (x), round (y));
for (k = 0; k <>
{
x += xIncremento;
y += yIncremento;
setPixel (round (x), round (y));
}
}

Algoritmo de Bresenham para trazar líneas.

Es un algoritmo creado para dibujar rectas en los dispositivos de graficos rasterizados, como por ejemplo un monitor de computadora, que determina que pixeles se rellenaran, en funcion de la inclinacion del angulo de la recta a dibujar.

Es un algoritmo preciso para la generacion de lineas de rastreo que convierte mediante rastreo las lineas al utilizar solo calculos 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 las columnas de pixel.

Es considerado uno de los algoritmos más efectivos para dibujar líneas mediante rastreo. Emplea cálculos incrementales con valores enteros. La forma de determinar el siguiente pixel a dibujar en la generación de una línea, se describe a continuación:

1.- Punto inicial  P1(Xinicial,Yinicial).
2.- Se desplaza una columna (incrementando la posición en X)
3.- 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)
4.- Se dibuja el primer pixel correspondiente al extremo izquierdo de la línea(P1)
5.- Se calculan los parámetros que permitien decidir cuál será el proximo pixel a dibujar (DeltaX, DeltaY y ConstanteP).
6.- Dependiendo del valor que tome el Parámetro ConstanteP se evalúa y determina la coordenada a dibujar que puede ser: 
       1.- (X+1,Y) para ConstanteP < 0
       2.- Sino (X+1,Y+1)
El proceso anterior debe repetirse 4DeltaX veces.

Pseudocodigo.

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<Ultimo
Asignar X + 1 a X
Si ConstanteP < 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)

Código:
void Bres(int x0,int y0,int xFin,int yFin)
{
int dx = fabs(xFin - x0),
dy = fabs(yFin - y0);
int p = 2 * dy - dx;
int dosDy = 2 * dy,
dosDyMenosDx = 2 * (dy - dx);
int x, y;
/* Determinamos que punto usamos como inicio. */
if (x0 > xFin) {
x = xFin;
y = yFin;
xFin = x0;
}
else {
x = x0;
y = y0;
}
setPixel (x, y);
while (x <>
x++;
if (p <>
p += dosDy;
else {
y++;
p += dosDyMenosDx;
}
setPixel (x, y);
}
}