Analizador Diferencial Digital (algoritmo gráfico)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Plantilla:Acerca de

Introducción[editar]

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, triangulos y polígonos. En la implementación más simple del algoritmo DDA interpola valores en intervalo [(xinicio, yinicio), (xfin, yfin)] por calculo para cada xi las ecuaciones xi = xi−1+1, yi = yi−1 + Δy/Δx, donde Δx = xfin − xinicio y Δy = yfin − yinicio.

Algoritmo[editar]

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,...

Implementación en Java[editar]

  public void DDA(int x0, int y0, int x1, int y1, Graphics g)
    {
        int dx = x1 - x0;
        int dy = y1 - y0;
 
        g.drawLine( x0, y0, x1, y1);
        if (Math.abs(dx) > Math.abs(dy)) {          // pendiente < 1
            float m = (float) dy / (float) dx;
            float b = y0 - m*x0;
            if(dx<0)
                dx =  -1;
            else
                dx =  1;
            while (x0 != x1) {
                x0 += dx;
                y0 = Math.round(m*x0 + b);
                g.drawLine( x0, y0, x1, y1);
            }
        } else
        if (dy != 0) {                              // slope >= 1
            float m = (float) dx / (float) dy;      // compute slope
            float b = x0 - m*y0;
            if(dy<0)
                dy =  -1;
            else
                dy =  1;
            while (y0 != y1) {
                y0 += dy;
                x0 = Math.round(m*y0 + b);
                g.drawLine( x0, y0, x0, y0);
            }
        }
    }

Rendimiento[editar]

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 esta 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 sustraccion. 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[editar]

Referencias[editar]

Apuntes de Informática Gráfica Uned por Omega.


Publicaciones[editar]

  • Alan Watt: 3D Computer Graphics, 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9