Diferencia entre DDA y 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 por computadora para dibujar imágenes. Anteriormente, usábamos analizadores analíticos para calcular los píxeles y, por lo tanto, eran posibles los dibujos lineales. Pero estos métodos de análisis no son tan precisos como los métodos digitales que usamos ahora usando estos algoritmos digitales y, como en todos los campos, también estamos ideando métodos más avanzados en gráficos por computadora. La invención de este algoritmo es un ejemplo perfecto. Antes de continuar, veamos el concepto detrás de estos algoritmos. Aunque parece más allá del alcance de nuestra discusión, es necesario señalar las diferencias básicas entre los dos. Si está realmente familiarizado con los algoritmos, puede saltar a las diferencias reales que se encuentran al final de esta página.
¿Qué es un algoritmo diferencial digital (DDA)?
DDA se usa principalmente para dibujar líneas en gráficos de computadora y usa valores reales cuando predice los siguientes valores de píxeles. Tomamos el valor del píxel inicial como (X0, Y0) (X0, Y0) y el píxel de destino como (X1, Y1) (X1, Y1). Aprenderemos cómo calcular los valores de píxel de destino a partir 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 corre paralela al eje x o al eje y. Para encontrar eso, ahora calculemos la diferencia entre los valores de píxel de inicio 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 de lenguaje informático.
si (total(dx) > total(dy))
Grados = absoluto(dx);
otro
Grados = absoluto (dy);
Paso 3: Ahora es el momento de identificar la coordenada ‘x’ real o los valores de píxel de la coordenada ‘y’ para dibujar la línea.
Incremento X = dx / (flotante) grados;
Y incremento = dy / (flotante) grados;
Paso 4: Esto debe calcularse hasta llegar al píxel de destino. El algoritmo DDA redondea el valor del píxel al valor entero más cercano al realizar el cálculo. Aquí está el ejemplo de código que hemos discutido ahora.
Para (int v=0; v < Grados; v++)
{
x = x + incremento de X;
y = y + incremento de Y;
putpixel (Redondo(x), Redondo(y));
}
¡Estamos listos para trazar la línea usando el DDA y pasemos ahora a Bresenham!
¿Qué es el algoritmo de Bresenham?
También es un algoritmo de dibujo lineal digital y fue creado por Bresenham en 1962 y es por eso que recibió el mismo nombre. Este algoritmo es más preciso y usa restas y sumas para calcular el valor de píxel mientras dibuja la línea. La precisión del algoritmo de Bresenham es confiable al dibujar curvas y círculos también. Veamos cómo funciona este algoritmo.
Paso 1: Los algoritmos de Bresenham asumen la coordenada de píxel 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 sumando o restando las ecuaciones que creó.
¡Este algoritmo calcula valores exactos sin ningún redondeo y también parece más fácil!
- Ejemplo numérico del algoritmo de Bresenham:
Consideremos ahora los puntos (0,0) y (-8, -4) y dibujemos una línea entre estos puntos usando el algoritmo de Bresenham.
Dados los datos, (x1, y1) = (0, 0) y (x2, y2) = (-8,-4).
Calculemos ahora los valores diferenciales como se muestra a continuación.
∆x=x2-x1=-8-0=8
Por tanto, el valor incremental de 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 determinante=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 simplemente estamos ignorando su cálculo aquí.
píxeles | X | y | Decisión variable |
(0,0) | 0 | 0 | 0 |
(-1,0) | -1 | 0 | Es valioso |
(-2,-1) | -2 | -1 | 0 |
(-3,-1) | -3 | -1 | Es valioso |
(-4,-2) | -4 | -2 | 0 |
(-5,-2) | -5 | -2 | Es valioso |
(-6,-3) | -6 | -3 | 0 |
(-7,-3) | -7 | -3 | Es valioso |
(-8,-4) | -8 | -4 | 0 |
Diferencias entre DDA y el Algoritmo de Bresenham:
- Cálculo Numérico:
La DDA utiliza valores reales en sus cálculos con el uso de puntos flotantes. Los siguientes valores de píxeles o puntos se determinan con ecuaciones diferenciales
Incremento X = dx / (flotante) grados
Incremento Y = dy / (flotante) grados
Aquí no se utilizan constantes fijas, pero en el algoritmo de Bresenham se utilizan puntos fijos en los cálculos aritméticos. El algoritmo de Bresenham utiliza aritmética de enteros, 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í, incremente X grados = dx / (flotante). El algoritmo de Bresenham usa operaciones de suma y resta y lo mismo se puede observar aquí en su primera ecuación para calcular otro valor de píxel (xa+1, ya+1). La aritmética es más simple en Bresenham en comparación con el DDA.
- Eficiencia:
Como discutimos anteriormente, el algoritmo de Bresenham usa una aritmética más simple que el DDA y produce resultados eficientes.
- Velocidad: Debido a que DDA usa números enteros de coma flotante junto con operaciones de multiplicación y división, es mucho más lento, mientras que el algoritmo de Bresenham usa solo aritmética de números enteros, así como solo sumas y restas. Esto reduce en gran medida el tiempo de cálculo y, por lo tanto, es más rápido que el DDA.
- Precisión: Aunque DDA usa valores de coma flotante, la precisión de DDA no es tan buena como la de Bresenham. Varios factores influyen en este concepto y, por lo tanto, el de Bresenham es más preciso que el DDA.
- Recuperación: Ver el cálculo de DDA aquí.
Incremento X = dx / (flotante) grados
Es posible que observe el ‘flotante’, por lo que no redondea los valores, pero el algoritmo de Bresenham redondea los valores al número entero más cercano. Por tanto, los valores utilizados en el algoritmo de Bresenham son más sencillos.
- ¿Qué dibuja?
El DDA puede dibujar círculos y curvas en lugar de líneas. El algoritmo de Bresenham también puede dibujar todos los mencionados anteriormente y su precisión es en realidad mayor que la DDA. De manera similar, el algoritmo de Bresenham puede tener mejores curvas que las que produce el DDA. Ambos algoritmos también pueden dibujar triángulos y polígonos.
- ¿Cuál es caro?
Debido a que el DDA también incluye el redondeo, es más costoso que usar el algoritmo de Bresenham.
- ¿Cuál es un algoritmo optimizado?
De la discusión anterior, queda muy claro que el algoritmo de Bresenham está optimizado en términos de velocidad, costo y utilización de las operaciones.
Veamos las diferencias en la forma de la tabla.
S.No | Diferencias yo | Algoritmo diferencial digital | Algoritmo de Bresenham |
1. | ¿Por qué el nombre? | Solo porque era una función digital de las ecuaciones, recibió el nombre. | JE Bresenham lo inventó en 1962 y de ahí el nombre. |
2. | Cálculos | Implica cálculos más intensivos. | Los cálculos utilizados son en realidad más simples. |
3. | Tipos de operaciones utilizadas | Usó multiplicaciones y divisiones. Las ecuaciones diferenciales de muestra utilizadas aquí son pasos de incremento X = dx / (flotante), Yincremento = dy / (flotante) grados. | Utiliza sumas y restas. El ejemplo de cálculo aquí se puede expresar como (xa+1, ya+1). |
4. | Valores de cálculo aritmético | Utiliza valores de coma flotante. | Sólo utiliza los valores enteros. |
5. | Eficiencia | La aritmética compleja da como resultado una menor eficiencia. | Una aritmética más simple conduce a una mayor eficiencia. |
6. | Velocidad | El uso de operaciones de multiplicación y división toma mucho tiempo para sus procesos de cálculo. | El uso de operaciones de suma y resta lleva menos tiempo que el DDA. |
7. | Precisión | Es menos en precisión. | Es más preciso. |
8. | Salvación | Utiliza valores reales y nunca completa los valores. | Redondea los valores a los valores enteros más cercanos. |
9. | Habilidad de dibujo | Es capaz de dibujar líneas, círculos y curvas pero con menos 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. Con este algoritmo también se pueden dibujar triángulos y polígonos. |
10 | Costo de los cálculos | Es caro porque implica también la salvación. | Usar el algoritmo de Bresenham es más económico que el DDA. |
11 | Algoritmo de optimización | No es un algoritmo de optimización. | Es un algoritmo de optimización. |
Hemos tratado todas las posibles diferencias entre el DDA y el algoritmo de Bresenham. Incluso puede parecer repetitivo, pero hay alguna razón válida para repetir esos puntos y se le informará cuando lo comprenda por completo. Si aún siente que hay ambigüedad, por favor déjenos un comentario. ¡Aprendamos juntos compartiendo la información relevante!