Analizador diferencial digital (algoritmo gráfico)

En gráficos por computadora , un analizador diferencial digital ( ADD ) es un hardware o software que se utiliza para interpolación de variables en un intervalo entre un punto inicial y un punto final. Los ADD se utilizan para rasterizar líneas, triángulos y polígonos. Pueden extenderse a funciones no lineales, como mapeo de texturas con corrección de perspectiva , curvas cuadráticas y recorrido de vóxeles .

En su implementación más simple para casos lineales como las líneas , el algoritmo DDA interpola valores en un intervalo calculando para cada x _i las ecuaciones x _i = x _i−1 + 1, y _i = y _i−1 + m, donde m es la pendiente de la línea. Esta pendiente se puede expresar en DDA de la siguiente manera:

${\displaystyle m={\frac {y_{\rm {fin}}-y_{\rm {inicio}}}{x_{\rm {fin}}-x_{\rm {inicio}}}}}$

De hecho, cualesquiera dos puntos consecutivos que se encuentren en este segmento de línea deberían satisfacer la ecuación.

El método DDA puede implementarse con aritmética de punto flotante o entera . La implementación nativa de punto flotante requiere una suma y una operación de redondeo por cada valor interpolado (por ejemplo, coordenada x, y, profundidad, componente de color, etc.) y resultado de salida. Este proceso solo es eficiente si se dispone de una unidad de punto flotante (FPU) con operaciones rápidas de suma y redondeo.

La operación con números enteros de punto fijo requiere dos sumas por ciclo de salida y, en caso de desbordamiento de la parte fraccionaria, un incremento y una resta adicionales . La probabilidad de desbordamiento de la parte fraccionaria es proporcional a la relación m entre los valores inicial y final interpolados.

Las DDA son idóneas para su implementación en hardware y pueden configurarse en paralelo para maximizar el rendimiento.

Un algoritmo DDA lineal comienza calculando el menor de los valores de dy o dx para un incremento unitario del otro. A continuación, se muestrea una línea a intervalos unitarios en una coordenada y se determinan los valores enteros correspondientes más cercanos a la trayectoria de la línea en la otra coordenada.

Considerando una línea con pendiente positiva, si la pendiente es menor o igual a 1, tomamos muestras a intervalos unitarios de x (dx=1) y calculamos valores sucesivos de y como

${\displaystyle y_{k+1}=y_{k}+m}$

${\displaystyle x_{k+1}=x_{k}+1}$

El subíndice k toma valores enteros que comienzan en 0 para el primer punto y aumentan en 1 hasta llegar al punto final. El valor de y se redondea al entero más cercano para que corresponda a un píxel de la pantalla.

Para líneas con pendiente mayor que 1, invertimos el papel de x e y, es decir, tomamos muestras en dy=1 y calculamos valores de x consecutivos como

${\displaystyle x_{k+1}=x_{k}+{\frac {1}{m}}}$

${\displaystyle y_{k+1}=y_{k}+1}$

Se realizan cálculos similares para determinar las posiciones de los píxeles a lo largo de una línea con pendiente negativa. Por lo tanto, si el valor absoluto de la pendiente es menor que 1, establecemos dx=1 si${\displaystyle x_{\rm {inicio}}<x_{\rm {fin}}}$es decir, el punto extremo inicial está a la izquierda.

Programa de algoritmo DDA en C++ :

#include <graphics.h>#include <iostream.h>#include <math.h>#include <dos.h>#incluir <conio.h>void main (){flotar x ,flotar y ,flotante x1 , y1 ,flotante x2 , y2 , dx , dy , paso ;int i , gd = DETECTAR , gm ;initgraph ( & gd , & gm , "C: \\ TURBOC3 \\ BGI" );cout << "Ingrese el valor de x1 e y1: " ;cin >> x1 >> y1 ;cout << "Ingrese el valor de x2 e y2: " ;cin >> x2 >> y2 ;dx = ( x2 - x1 );dy = ( y2 - y1 );si ( abs ( dx ) >= abs ( dy ))paso = abs ( dx );demáspaso = abs ( dy );dx = dx / paso ;dy = dy / paso ;x = x1 ;y = y1 ;i = 0 ;mientras ( i <= paso ) {putpixel ( round ( x ), round ( y ), 5 );x = x + dx ;y = y + dy ;i = i + 1 ;retraso ( 100 );}obtener ();closegraph ();}

• El algoritmo de líneas de Bresenham es un algoritmo para la representación de líneas.
• Algoritmo de error incremental
• El algoritmo de líneas de Xiaolin Wu es un algoritmo para suavizado de líneas.

http://www.museth.org/Ken/Publications_files/Museth_SIG14.pdf

• Alan Watt: Gráficos 3D por computadora , 3.ª edición, 2000, pág.  184 (Rasterización de bordes). ISBN 0-201-39855-9