Algoritmo DDA para generación de líneas

Algoritmo de Línea DDA

El analizador diferenciador digital (DDA - Digital Differential Analyzer) es un algoritmo de conversion de rastreo

que se basa en el calculo ya sea de

Dy o Dx por medio de las ecuaciones (4) o (5).

Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determina los valores enteros

correspondientes mas próximos a la trayectoria de la línea para la otra coordenada.

Tomemos una línea con pendiente positiva, si la pendiente |

m | £ 1, se hace el muestreo en x en intervalos

unitarios (

Dx = 1 y Dy = m dado que m = Dy / Dx) y se calcula cada valor sucesivo de y como:

(6)

yk+1 = yk+ m

El subíndice toma valores enteros a partir de 1 y aumenta a razón de 1 hasta alcanzar el valor final.

Ya que

m puede ser cualquier numero real entre 0 y 1, los valores calculados de y deben redondearse al entero mas

cercano.

Para líneas con una pendiente |

m | > 1, se revierten las funciones de x y y, o sea, se realiza un muestreo de y en

intervalos unitarios (

Dy = 1 y Dx = 1/m dado que m = Dy / Dx) y se calcula cada valor sucesivo de x como:

(7)

xk+1 = xk+ 1/m

Las ecuaciones (6) y (7) se basan en la suposición de que las líneas deben procesarse del extremo izquierdo al

derecho.

Si este procesamiento se revierte, entonces

Dx o Dy serian -1, y

y

k

+1 = yk - m o xk+1 = xk - 1/m

(x

i,round(yi))

(x

i,yi)

(x

i+1,round(yi+m))

(x

i+1,yi+m)

línea

deseada

Dx

 

D

y

El procedimiento completo de dibujo seria el siguiente:

void Line(Display* display, Window win, GC gc, int x0, int y0, int x1, int y1)

{

float x, y, xs, ys;

int dx, dy, steps;

dx = x1 - x0;

dy = y1 - y0;

/* se asigna el punto de donde se comenzara a dibujar la línea */

x = x0;

y = y0;

/* verificar si la pendiente es mayor de x o y, para luego asignarla a steps */

if (abs(dx) > abs(dy))

steps = abs(dx);

else

steps = abs(dy);

/* se divide por la pendiente mayor, para dar xs o ys igual a 1 (o -1) */

Alfredo Weitzenfeld Gráfica: Línea

3

if (steps == 0) {

XDrawPoint(display,win,gc,round(x),round(y));

fprintf(stderr,”this line is a point”);

return;

}

xs = dx/steps;

ys = dy/steps;

/* se cicla uno a la vez hasta llegar al numero de steps máximo */

for (i = 0; i <= steps; i++)

{

XDrawPoint(display,win,gc,round(x),round(y)); /* round(x) -> x+0.5 */

x = x + xs;

y = y + ys;

}

}

El problema con este algoritmo es que se debe redondear números flotantes a enteros y hacer operaciones sobre

números flotantes , lo cual toma tiempo.

Para líneas largas, la acumulación de errores de redondeo en adiciones sucesivas del incremento de punto flotante

pueden provocar que las posiciones del pixel calculadas se desvíen de la trayectoria real de la línea.

Se puede mejorar el desempeño del algoritmo al separar los incrementos m y 1/m en partes enteras y fraccionarias,

de forma que todos los cálculos se reduzcan a operaciones de enteros.