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 cliclo 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