En gráficos por computadora , un analizador diferencial digital ( DDA ) es un hardware o software que se utiliza para la interpolación de variables en un intervalo entre el punto inicial y el final. Los DDA se utilizan para rasterizar líneas, triángulos y polígonos. Pueden extenderse a funciones no lineales, como el mapeo de texturas de perspectiva correcta , curvas cuadráticas y vóxeles transversales .
En su implementación más simple para casos lineales como líneas , el algoritmo DDA interpola valores en el intervalo calculando para cada x i las ecuaciones x i = x i − 1 + 1, y i = y i − 1 + m, donde m es el pendiente de la línea. Esta pendiente se puede expresar en DDA de la siguiente manera:
De hecho, cualesquiera dos puntos consecutivos (x, y) que se encuentren en este segmento de línea deberían satisfacer la ecuación.
Actuación
El método DDA se puede implementar usando aritmética de punto flotante o entero . La implementación nativa de punto flotante requiere una operación de suma y una de redondeo por valor interpolado (por ejemplo, coordenada x, y, profundidad, componente de color, etc.) y resultado de salida. Este proceso solo es eficiente cuando está disponible una FPU con operación rápida de suma y redondeo.
La operación de entero de punto fijo requiere dos sumas por ciclo de salida y, en caso de desbordamiento de una parte fraccional, un incremento y una resta adicionales. La probabilidad de desbordamientos de partes fraccionarias es proporcional a la relación m de los valores inicial / final interpolados.
Los DDA son adecuados para la implementación de hardware y se pueden canalizar para maximizar el rendimiento.
Algoritmo
Una DDA lineal comienza calculando el menor 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 para la otra coordenada.
Considerando una línea con pendiente positiva, si la pendiente es menor o igual a 1, tomamos muestras en intervalos de unidad x (dx = 1) y calculamos valores de y sucesivos como
El subíndice k toma valores enteros a partir de 0, para el primer punto y aumenta en 1 hasta que se alcanza el punto final. El valor y se redondea al número entero más cercano para que corresponda a un píxel de la pantalla.
Para rectas con pendiente mayor que 1, invertimos el papel de xey, es decir, tomamos muestras en dy = 1 y calculamos valores x consecutivos como
Se llevan a cabo 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 es decir, el punto extremo inicial está a la izquierda.
Programa
Programa de algoritmo DDA en Turbo C ++:
#include #include #include #include #include vacío principal ( ){ flotar x , flotar y , flotar x1 , y1 , flotar x2 , y2 , dx , dy , paso ; int i , gd = DETECTAR , gm ; initgraph ( & gd , & gm , "C: \\ TURBOC3 \\ BGI" ); cout << "Introduzca el valor de x1 e y1:" ; cin >> x1 >> y1 ; cout << "Introduzca el valor de x2 e y2:" ; cin >> x2 >> y2 ; dx = ( x2 - x1 ); dy = ( y2 - y1 ); si ( abs ( dx ) > = abs ( dy )) paso = abs ( dx ); demás paso = abs ( dy ); dx = dx / paso ; dy = dy / paso ; x = x1 ; y = y1 ; i = 1 ; while ( i <= paso ) { putpixel ( x , y , 5 ); x = x + dx ; y = y + dy ; i = i + 1 ; retraso ( 100 ); } getch (); closegraph ();}
Ver también
- El algoritmo de línea de Bresenham es un algoritmo para la representación de líneas.
- algoritmo de error incremental
- El algoritmo de línea de Xiaolin Wu es un algoritmo para suavizado de líneas
Referencias
http://www.museth.org/Ken/Publications_files/Museth_SIG14.pdf
- Alan Watt: 3D Computer Graphics , tercera edición 2000, p. 184 (Rasterización de bordes). ISBN 0-201-39855-9