En gráficos por ordenador, una implementación de hardware o software de un 'analizador diferencial digital (DDA)''' se usa para la interpolación lineal de variables sobre un intervalo entre un punto de comienzo y un punto de fin. Los DDAs se usan para rastreo de líneas, triángulos y polígonos. En la implementación más simple del algoritmo DDA interpola valores en intervalo [(xinicio, yinicio), (xfin, yfin)] por cálculo para cada xi las ecuaciones xi = xi−1+1, yi = yi−1 + Δy/Δx, donde Δx = xfin − xinicio y Δy = yfin − yinicio.

Algoritmo Si m>=0 (pendiente positiva) Si m<=1 de izquierda a derecha * muestreo de x (Δx =1) * yk+1 = redondeo(yk + m) k=1,2,... de derecha a izquierda * muestreo de x (Δx =-1) * yk+1 = redondeo(yk - m) k=1,2,... Si m > 1 (para evitar la aparición de agujeros) de izquierda a derecha * muestreo de y (Δy =1) * xk+1 = redondeo(xk + 1/m) k=1,2,... de derecha a izquierda * muestreo de y (Δy =-1) * xk+1 = redondeo(xk - m) k=1,2,... Si m<0 (pendiente negativa) Si |m|<1 de izquierda a derecha * muestreo de x (Δx =1) * yk+1 = redondeo(yk + m) k=1,2,... de derecha a izquierda * muestreo de x (Δx =-1) * yk+1 = redondeo(yk - m) k=1,2,... Si |m| > 1 (para evitar la aparición de agujeros) de izquierda a derecha * muestreo de y (Δy =1) * xk+1 = redondeo(xk + 1/m) k=1,2,... de derecha a izquierda * muestreo de y (Δy =-1) * xk+1 = redondeo(xk - m) k=1,2,...

Rendimiento El método DDA puede ser implementado usando aritmética de coma flotante o entero. La implementación nativa en coma flotante requiere una suma y un redondeo para cada valor interpolado (Ej. coordenada x, y, profundidad, componente de color etc.) y resultado de salida. Este proceso es solo eficiente cuando una FPU con operaciones de suma y redondeo rápido está disponible.

La operación en coma fija entero requiere dos sumas para cada ciclo de salida, y en caso de rebose de la parte fraccional, un incremento adicionar y sustracción. La probabilidad de que rebose la parte fraccional es proporcional al radio m de los valores inicio/fin interpolados.

Los DDAs son muy usados para implementaciones hardware y pueden ser pipelined para maximizar el rendimiento.

Véase también Algoritmo de Bresenham es un algoritmo para el trazado de líneas. Algoritmo de Xiaolin Wu es un algoritmo para antialiasing de líneas. Algoritmo del punto medio para circunferencias es un algoritmo para el trazado de cónicas.

Referencias Apuntes de Informática Gráfica Uned por Omega.

Publicaciones Alan Watt: 3D Computer Graphics'', 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9

Enlaces externos

Categoría:Algoritmos de computación gráfica Categoría:Algoritmos geométricos Categoría:Infografía