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 [(x_inicio, y_inicio), (x_fin, y_fin)] por cálculo para cada x_i las ecuaciones x_i = x_i−1+1, y_i = y_i−1 + Δy/Δx, donde Δx = x_fin − x_inicio y Δy = y_fin − y_inicio.

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

• Wikilibros alberga un libro o manual sobre Implementaciones del analizador diferencial digital.

• Datos: Q2247908