Analizador diferencial digital

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

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
    Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.