Protocolos y formatos

Diferencia entre DDA y el algoritmo de Bresenham

Diferencia entre DDA y el algoritmo de Bresenham

El algoritmo diferencial digital (DDA) y el algoritmo de Bresenhams son los algoritmos de dibujo de líneas digitales y se utilizan en gráficos de computadora para dibujar imágenes. Anteriormente, estábamos utilizando analizadores analíticos para calcular los píxeles y, por lo tanto, los dibujos de línea eran posibles. Pero estos métodos analíticos no son tan precisos como los métodos digitales que con el uso de estos algoritmos digitales ahora y como con cada campo, hemos estado inventando métodos de mayor calidad en gráficos por computadora también. La invención de estos algoritmos es un ejemplo perfecto.  Antes de continuar, veamos el concepto detrás de estos algoritmos. Aunque parece estar fuera del alcance de nuestra discusión, es esencial señalar las diferencias básicas entre los dos. Si está realmente familiarizado con los algoritmos, puede saltar a las diferencias reales ubicadas al final de esta página.

¿Qué es el algoritmo diferencial digital (DDA)??

Un DDA se usa principalmente para dibujar líneas en gráficos por computadora y usa valores reales al tiempo que predice los próximos valores de píxeles. Supongamos el valor de píxel inicial como (x0, y0) (x0, y0) y el píxel de destino como (x1, y1) (x1, y1). Aprenderemos a calcular los valores de píxeles de destino del valor de píxel conocido (x0, y0) (x0, y0) como se muestra a continuación.

  • Cómo calcular el valor del punto de destino usando DDA?

Paso 1: Aquí tenemos la entrada (x0, y0) (x0, y0) y debemos identificar si la línea se ejecuta paralela al eje x o al eje Y. Para encontrar eso, calculemos ahora la diferencia entre los valores de píxel inicial y de destino.

dx = x1 - x0

dy = y1 - y0

Paso 2: Ahora, hemos identificado la diferencia y debemos dibujar la línea a lo largo del eje x si 'dx' es cero de lo contrario, debemos dibujar la línea paralela al eje y. Aquí está el cálculo real en términos del lenguaje de la computadora.

if (absoluto (dx)> absoluto (dy))

Pasos = absoluto (dx);

demás

Pasos = absoluto (dy);

Paso 3: Ahora, es hora de identificar la coordenada 'x' real o los valores de píxeles de las coordenadas 'Y' para dibujar la línea.

X increment = dx / (flotante) pasos;

Y incremento = dy / (flotante) pasos;

Etapa 4: Esto debe calcularse hasta que llegamos al Píxel de destino. El algoritmo DDA redondea el valor de píxel al valor entero más cercano mientras realiza el cálculo. Aquí está la muestra de código de lo que hemos discutido ahora.

Para (int v = 0; v < Steps; v++)

x = x + x incremento;

y = y + y incremento;

putpixel (redondo (x), redondo (y));

Hemos terminado dibujando la línea usando el DDA y pasemos a la Bresenham ahora!

¿Qué es el algoritmo de Bresenham??

También es un algoritmo de dibujo de línea digital y fue inventado por Bresenham en el año 1962 y es por eso que tiene el mismo nombre. Este algoritmo es más preciso y utilizó sutracción y adición para calcular el valor de píxel mientras dibuja la línea. La precisión del algoritmo de Bresenham también es confiable, mientras que las curvas y los círculos. Miremos cómo funciona este algoritmo.

Paso 1: Los algoritmos de Bresenham suponen la coordenada de píxeles inicial como (xA+1, Ya).

Paso 2: Calcula automáticamente el siguiente valor de píxel como (xA+1, YA+1), Aquí 'a' es el valor incremental y el algoritmo lo calcula agregando o restando las ecuaciones que había formado.

Este algoritmo calcula valores precisos sin redondeo y también se ve más fácil!

  • Ejemplo numérico del algoritmo de Bresenham:

Consideremos ahora los puntos (0,0) y (-8, -4) y trazemos una línea entre estos puntos usando el algoritmo de Bresenham.

Datos dados, (x1, y1) = (0, 0) y (x2, y2) = (-8, -4).

Ahora calculemos los valores diferenciales como se muestra a continuación.

∆x = x2-x1 = -8-0 = 8

Por lo tanto, el valor incremental para x = ∆x / x2 = 8 / -8 = -1.

∆y = y2-y1 = -4-0 = 4

Por lo tanto, el valor incremental para y = ∆y / y2 = 4 / -4 = -1.

Variable de decisión = e = 2*(∆y)-(∆x)

Por lo tanto, E = 2*(4)-(8) = 8-8 = 0

Con el cálculo anterior, tabulemos los valores resultantes. Los valores de la coordenada y se ajustan en función de una variable de decisión y estamos ignorando su cálculo aquí.

Píxel X Y                                              Decisión variable
(0,0) 0 0 0
(-1,0) -1 0 Un valor
(-2, -1) -2 -1 0
(-3, -1) -3 -1 Un valor
(-4, -2) -4 -2 0
(-5, -2) -5 -2 Un valor
(-6, -3) -6 -3 0
(-7, -3) -7 -3 Un valor
(-8, -4) -8 -4 0

Diferencias entre el algoritmo de DDA y Bresenham:

  • Cálculo aritmético:

El DDA usa valores reales en sus cálculos con el uso de puntos flotantes. El siguiente píxel o valores de puntos se determinan con ecuaciones diferenciales

X increment = dx / (float) pasos

Y incremento = dy / (flotante) pasos

Aquí no se usan constantes fijas, pero en el algoritmo de Bresenham se utilizan puntos fijos en cálculos aritméticos. El algoritmo de Bresenham usa aritmética entera, a diferencia del DDA.

  • Tipo de operación utilizada:

El DDA resuelve las ecuaciones diferenciales con operaciones de multiplicación y división. Puede notar lo mismo aquí, x increment = dx / (flotante) pasos. El algoritmo de Bresenham utiliza operaciones de adición y sustracción y puede notar lo mismo aquí en su siguiente ecuación de cálculo de valor de píxeles (xA+1, YA+1). La aritmética es más simple en la de Bresenham en comparación con el DDA.

  • Eficiencia:

Como hemos discutido anteriormente, el algoritmo de Bresenham utiliza aritmética más simple que el DDA y resulta en resultados eficientes.

  • Velocidad: Como DDA utiliza enteros de punto flotante junto con operaciones de multiplicación y división, es relativamente más lento, mientras que el algoritmo de Bresenham usa aritmética de enteros solo junto con adiciones y restos solo. Esto reduce considerablemente el tiempo tardado para sus cálculos y, por lo tanto, es más rápido que el DDA.
  • Exactitud: Aunque DDA usa valores de puntos flotantes, la precisión de DDA no es tan mejor como la de Bresenham. Una variedad de factores afectan este concepto y, por lo tanto, el de Bresenham es más preciso que el DDA.
  • Redondeando: Solo mira el cálculo del DDA aquí.

X increment = dx / (float) pasos

Puede notar el 'flotador' y, por lo tanto, no redondea los valores, mientras que el algoritmo de Bresenham redondea los valores al número entero más cercano. Por lo tanto, los valores utilizados son más simples en el algoritmo de Bresenham.

  • Que dibuja?

El DDA es capaz de dibujar círculos y curvas aparte de las líneas de dibujo. El algoritmo de Bresenham también es capaz de dibujar todos los mencionados anteriormente y su precisión es realmente más alta que la del DDA. Del mismo modo, el algoritmo de Bresenham podría encontrar curvas eficientes que la producida por el DDA. Ambos algoritmos también pueden dibujar triángulos y polígonos.

  • Que es caro?

Como DDA también incluye redondear, es costoso que el uso del algoritmo de Bresenham.

  • Que es un algoritmo optimizado?

De nuestra discusión anterior, está muy claro que el algoritmo de Bresenham es optimizado en términos de velocidad, costo y uso de operaciones.

Veamos las diferencias en forma tabular.

S.No Diferencias en Algoritmo diferencial digital Algoritmo de Bresenham
1. Por qué el nombre? Solo porque fue la implementación digital de las ecuaciones, tiene el nombre. Fue inventado por J.mi. Bresenham en el año 1962 y, por lo tanto, el nombre.
2. Cálculos Implica cálculos más duros. Los cálculos utilizados son realmente más simples.
3. Tipos de operaciones utilizadas Usó multiplicaciones y divisiones. Las ecuaciones diferenciales de muestra utilizadas aquí son pasos xincrement = dx / (float),

Yincrement = dy / (float) pasos.

 Utiliza adiciones y subtracciones. El cálculo de la muestra aquí se puede denotar como (xA+1, YA+1).
4. Valores de cálculo aritmético Utiliza valores de punto flotante. Utiliza solo los valores enteros.
5. Eficiencia Resultados aritméticos complejos en menor eficiencia. Resultados aritméticos más simples en más eficiencia.
6. Velocidad El uso de multiplicaciones y operaciones de división lleva mucho tiempo para sus procesos de cálculo. El uso de las operaciones de suma y sustracción lleva menos tiempo que el DDA.
7. Exactitud Es menor en precisión. Es más preciso.
8. Redondeando Utiliza valores reales y nunca redondea los valores. Redondea los valores a los valores enteros más cercanos.
9. Capacidad de dibujo Es capaz de dibujar líneas, círculos y curvas, pero con menor precisión. Incluso podemos dibujar triángulos y polígonos con este algoritmo. Es capaz de dibujar líneas, círculos y curvas con mayor eficiencia. Los triángulos y los polígonos también son posibles para ser dibujados con este algoritmo.
10. Costo de los cálculos Es costoso, ya que implica redondear también. El uso del algoritmo de Bresenham es más barato que el DDA.
11. Algoritmo optimizado No es un algoritmo optimizado Es un algoritmo optimizado.

Hemos tratado con todas las diferencias posibles entre el DDA y el algoritmo de Bresenham. Incluso puede parecer repetitivo, pero hay una razón válida para mencionar esos puntos nuevamente y llegarías a saber cuándo lo entiendes por completo. Si todavía siente que existe una ambigüedad, déjenos un comentario. Aprendamos juntos compartiendo el conocimiento adecuado!