Différence entre l'algorithme de DDA et Bresenham

L'algorithme différentiel numérique (DDA) et l'algorithme de Bresenhams sont les algorithmes de dessin de lignes numériques et sont utilisés dans l'infographie pour dessiner des images. Auparavant, nous utilisons des analyseurs analytiques pour calculer les pixels et ainsi des dessins en ligne étaient rendus possibles. Mais ces méthodes analytiques ne sont pas aussi précises que les méthodes numériques qu'avec l'utilisation de ces algorithmes numériques maintenant et comme avec chaque domaine, nous avons également inventé des méthodes de meilleure qualité en informatique. L'invention de ces algorithmes est un exemple parfait.  Avant de continuer, regardons le concept derrière ces algorithmes. Bien qu'il semble hors de l'étendue de notre discussion, il est essentiel de souligner les différences de base entre les deux. Si vous connaissez vraiment les algorithmes, vous pouvez passer aux différences réelles situées à la fin de cette page.

Qu'est-ce que l'algorithme différentiel numérique (DDA)?

Un DDA est principalement utilisé pour dessiner des lignes en informatique et utilise des valeurs réelles tout en prédisant les valeurs de pixels suivantes. Supposons la valeur de pixel initiale en tant que (x0, y0) (x0, y0) et le pixel de destination comme (x1, y1) (x1, y1). Nous apprendrons à calculer les valeurs de pixels de destination à partir de la valeur des pixels connus (x0, y0) (x0, y0) comme ci-dessous.

• Comment calculer la valeur du point de destination à l'aide de DDA?

Étape 1: Ici, nous avons l'entrée (x0, y0) (x0, y0) et nous devons identifier si la ligne est parallèle à l'axe x ou à l'axe y. Pour constater cela, calculons maintenant la différence entre les valeurs initiales et des pixels de destination.

dx = x1 - x0

dy = y1 - y0

Étape 2: Maintenant, nous avons identifié la différence et nous devons tracer la ligne le long de l'axe des x si «dx» est zéro sinon, nous devons tracer la ligne parallèle à l'axe y. Voici le calcul réel en termes de langage informatique.

if (absolu (dx)> absolu (dy))

Étapes = absolu (dx);

autre

Étapes = absolu (dy);

Étape 3: Maintenant, il est temps d'identifier les coordonnées «x» réelles ou les coordonnées «Y» pour tracer la ligne.

X incrément = étapes dx / (float);

Y incrément = étapes dy / (float);

Étape 4: Cela doit être calculé jusqu'à ce que nous atteignions le pixel de destination. L'algorithme DDA arrête la valeur des pixels à la valeur entière la plus proche tout en faisant le calcul. Voici l'échantillon de code de ce dont nous avons discuté maintenant.

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

x = x + x incrément;

y = y + y incrément;

putPixel (rond (x), rond (y));

Nous avons terminé avec le dessin de la ligne en utilisant le DDA et nous allons passer aux Bresenham maintenant!

Quel est l'algorithme de Bresenham?

Il s'agit également d'un algorithme de dessin de ligne numérique et a été inventé par Bresenham en 1962 et c'est pourquoi il a le même nom. Cet algorithme est plus précis et il a utilisé la soustraction et l'ajout de calcul de la valeur des pixels tout en dessinant la ligne. La précision de l'algorithme de Bresenham est fiable tout en dessinant les courbes et les cercles également. Laissez-nous voir comment cet algorithme fonctionne.

Étape 1: Les algorithmes de Bresenham supposent que la coordonnée de pixel initiale est (x_{A + 1}, y_un).

Étape 2: Il calcule automatiquement la valeur de pixel suivante comme (x_{A + 1}, y_{A + 1}), Ici «a» est la valeur incrémentielle et l'algorithme le calcule en ajoutant ou en soustrayant les équations qu'elle avait formées.

Cet algorithme calcule des valeurs précises sans arrondir et semble également plus facile!

• Exemple numérique de l'algorithme de Bresenham:

Voyons maintenant les points (0,0) et (-8, -4) et tracez-nous une ligne entre ces points en utilisant l'algorithme de Bresenham.

Données données, (x1, y1) = (0, 0) et (x2, y2) = (-8, -4).

Calculons maintenant les valeurs différentielles comme ci-dessous.

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

Par conséquent, la valeur incrémentale pour x = ∆x / x2 = 8 / -8 = -1.

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

Par conséquent, la valeur incrémentielle pour y = ∆y / y2 = 4 / -4 = -1.

Variable de décision = E = 2 * (∆y) - (∆x)

Par conséquent, E = 2 * (4) - (8) = 8-8 = 0

Avec le calcul ci-dessus, tabulons les valeurs résultantes. Les valeurs de la coordonnée y sont ajustées en fonction d'une variable de décision et nous ignorons simplement son calcul ici.

Différences entre l'algorithme de DDA et Bresenham:

• Calcul arithmétique:

Le DDA utilise des valeurs réelles dans ses calculs avec l'utilisation des points flottants. Les valeurs de pixel ou de points suivantes sont déterminées avec des équations différentielles

X incrément = étapes dx / (float)

Y incrément = dy / (float) étapes

Ici, aucune constante fixe n'est utilisée mais dans l'algorithme de Bresenham, des points fixes sont utilisés dans les calculs arithmétiques. L'algorithme de Bresenham utilise l'arithmétique entier, contrairement au DDA.

• Type d'opération utilisé:

La DDA résout les équations différentielles avec les opérations de multiplication et de division. Vous pouvez remarquer la même chose ici, x incrément = dx / (float) étapes. L'algorithme de Bresenham utilise des opérations d'addition et de soustraction et vous pouvez le remarquer ici dans sa prochaine équation de calcul de valeur de pixels (x_{A + 1}, y_{A + 1}). L'arithmétique est plus simple chez Bresenham par rapport au DDA.

• Efficacité:

Comme nous l'avons discuté plus tôt, l'algorithme de Bresenham utilise l'arithmétique plus simple que le DDA et se traduit par des résultats efficaces.

• Vitesse: Comme le DDA utilise des entiers à virgule flottante ainsi que des opérations de multiplication et de division, il est relativement plus lent tandis que l'algorithme de Bresenham utilise uniquement l'arithmétique entier avec des ajouts et des soustractions seul. Cela réduit considérablement le temps pris pour ses calculs et donc plus rapidement que le DDA.
• Précision: Bien que DDA utilise des valeurs de points flottants, la précision de DDA n'est pas aussi meilleure que la Bresenham. Divers facteurs affectent ce concept et, par conséquent, Bresenham est plus précis que le DDA.
• Arrondir: Regardez simplement le calcul du DDA ici.

X incrément = étapes dx / (float)

Vous pouvez remarquer le «flotteur» et donc il n'enlève pas les valeurs tandis que l'algorithme de Bresenham arrête les valeurs de l'entier le plus proche. Par conséquent, les valeurs utilisées sont plus simples dans l'algorithme de Bresenham.

• Qu'est-ce qu'il dessine?

Le DDA est capable de séparer les cercles et les courbes en dehors des lignes de dessin. L'algorithme de Bresenham est également capable de dessiner tous ceux mentionnés ci-dessus et sa précision est vraiment plus élevée que celle du DDA. De même, l'algorithme de Bresenham pourrait proposer des courbes efficaces que celles produites par le DDA. Les algorithmes peuvent également dessiner des triangles et des polygones.

• Qui est cher?

Comme le DDA comprend également d'arrondir, il coûte cher que l'utilisation de l'algorithme de Bresenham.

• Qui est un algorithme optimisé?

Depuis notre discussion ci-dessus, il est très clair que l'algorithme de Bresenham est optimisé en termes de vitesse, de coût et d'utilisation des opérations.

Examinons les différences de forme tabulaire.

Nous avons traité de chaque différence possible entre le DDA et l'algorithme de Bresenham. Cela peut même sembler répétitif, mais il y a une raison valable de mentionner à nouveau ces points et vous saurez quand vous le comprenez complètement. Si vous sentez toujours qu'il existe une ambiguïté, veuillez nous laisser un commentaire. Apprenons ensemble en partageant les connaissances appropriées!