Allgemein

10 Unterschied zwischen Bresenhams und DDA-Strichzeichnungsalgorithmus

In der Computergrafik müssen wir fortlaufende Grafikobjekte mit diskreten Pixeln darstellen. Dieser Vorgang wird als Scankonvertierung bezeichnet. Jedes Grafiksystem muss die Grundelemente wie Linien, Kreise und Ellipsen in eine Sammlung von Pixeln umwandeln.

Linienzeichnungsalgorithmen werden verwendet, um eine Linie in diskreten grafischen Medien zu zeichnen. In der Computergrafik gibt es drei Strichzeichnungsalgorithmen.

DDA-Algorithmus (Digital Differential Analyzer)
Mittelpunktalgorithmus
Bresenhams Linienalgorithmus

Contents

Bresenhams Strichzeichnungsalgorithmus

Der Linienalgorithmus von Bresenham ist ein optimistischer und inkrementeller Scan-Umwandlungs-Linienzeichnungsalgorithmus , der alle Zwischenpunkte über das Intervall zwischen Start- und Endpunkt berechnet und vollständig mit ganzen Zahlen und der ganzzahligen Arithmetik implementiert ist. Es verwendet nur Addition und Subtraktion und vermeidet schwere Operationen wie Multiplikation und Division.

Der Bresenham-Linienzeichnungsalgorithmus bestimmt die Punkte eines n-dimensionalen Rasters, die ausgewählt werden sollten, um eine enge Annäherung an eine gerade Linie zwischen zwei Punkten zu bilden.

Es wird häufig zum Zeichnen von Linienprimitiven in einem Bitmap-Bild (z. B. auf einem Computerbildschirm) verwendet, da es nur ganzzahlige Addition, Subtraktion und Bitverschiebung verwendet, die alle sehr billige Operationen in häufig verwendeten Computerbefehlssätzen wie x86_64 sind. Es ist ein inkrementeller Fehleralgorithmus. Es ist einer der frühesten Algorithmen, die auf dem Gebiet der Computergrafik entwickelt wurden. Eine Erweiterung des ursprünglichen Algorithmus kann zum Zeichnen von Kreisen verwendet werden.

Bresenhams Algorithmus

Schritt 1: Algorithmus starten

Schritt 2: Deklariere die Variablen x ₁ ,x ₂ ,y ₁ ,y ₂ ,d,i ₁ ,i ₂ ,dx,dy

Schritt 3: Geben Sie den Wert von x ₁ ,y ₁ ,x ₂ ,y ₂
ein, wobei x ₁ ,y ₁ die Koordinaten des Startpunkts
und x ₂ ,y ₂ die Koordinaten des Endpunkts sind

Schritt 4: Berechnen von dx = x ₂ – x ₁
Berechnen von dy = y ₂ – y ₁
Berechnen von i ₁ =2*dy
Berechnen von i ₂ =2*(dy-dx)
Berechnen von d=i ₁ –dx

Schritt 5: Betrachte (x, y) als Startpunkt und x _Ende als maximal möglichen Wert von x.
Wenn dx < 0
Dann x = x ₂
y = y ₂
x _Ende = x ₁
Wenn dx > 0
Dann x = x ₁
y = y ₁
x _Ende = x ₂

Schritt 6: Punkt bei (x,y)-Koordinaten erzeugen.

Schritt 7: Überprüfen Sie, ob eine ganze Zeile generiert wird.
Wenn x > = x _Ende
Stop.

Schritt 8: Koordinaten des nächsten Pixels berechnen
Wenn d < 0
Dann d = d + i ₁
Wenn d ≥ 0
Dann d = d + i ₂
Erhöhe y = y + 1

Schritt 9: Erhöhe x = x + 1

Schritt 10: Zeichnen Sie einen Punkt mit den letzten (x, y) Koordinaten

Schritt 11: Gehen Sie zu Schritt 7

Schritt 12: Ende des Algorithmus

DDA-Strichzeichnungsalgorithmus

DDA steht für Digital Differential Analyzer. Dies ist ein inkrementeller Linienalgorithmus, die Berechnung jedes Schrittes basiert auf den Ergebnissen der vorherigen Schritte. Der DDA-Algorithmus nimmt Einheitsschritte entlang einer Koordinate und berechnet die entsprechenden Werte entlang der anderen Koordinate .

DDAs werden zur Rasterung von Linien, Dreiecken und Polygonen verwendet. Sie können auf nichtlineare Funktionen erweitert werden, wie z. B. perspektivisch korrektes Textur-Mapping, quadratische Kurven und durchlaufende Voxel.

Ein linearer DDA beginnt mit der Berechnung des kleineren Werts von dy oder dx für ein Einheitsinkrement des anderen. Eine Linie wird dann in Einheitsintervallen in einer Koordinate abgetastet, und entsprechende ganzzahlige Werte, die dem Linienpfad am nächsten liegen, werden für die andere Koordinate bestimmt.

DDA-Algorithmus

Schritt 1: Algorithmus starten

Schritt 2: Deklarieren Sie x ₁ ,y ₁ ,x ₂ ,y ₂ ,dx,dy,x,y als ganzzahlige Variablen.

Schritt 3: Geben Sie den Wert von x ₁ ,y ₁ ,x ₂ ,y ₂ ein .

Schritt 4: Berechnen Sie dx = x ₂ – x ₁

Schritt 5: Berechnen Sie dy = y ₂ – y ₁

Schritt 6: Wenn ABS (dx) > ABS (dy)
dann Schritt = abs (dx)
Else

Schritt 7: x _inc =dx/Schritt
y _inc =dy/Schritt
zuweisen x = x ₁
zuweisen y = y ₁

Schritt 8: Pixel setzen (x, y)

Schritt 9: x = x + x _inc
y = y + y _inc
Pixel setzen (Round (x), Round (y))

Schritt 10: Wiederholen Sie Schritt 9, bis x = x ₂

Schritt 11: Algorithmus beenden

Lesen Sie auch: Unterschied zwischen deterministischen und nicht deterministischen Algorithmen

DDA vs. Bresenham-Algorithmus

GRUNDLAGE DES VERGLEICHS	DDA-ALGORITHMUS	BRESENHAMS ALGORITHMUS
Beschreibung	DDA steht für Digital Differential Analyzer.	——-
Operationen	DDA-Algorithmen verwenden Multiplikation und Division in ihren Operationen.	Bresenhams Algorithmus verwendet bei seinen Operationen nur Subtraktion und Addition.
Funktionalität	Der DDA-Algorithmus ist nicht so genau und effizient wie der von Bresenham.	Der Bresenham-Algorithmus ist genauer und effizienter als der DDA-Algorithmus.
Arithmetik	Der DDA-Algorithmus verwendet Fließkommazahlen, dh reelle Arithmetik.	Bresenhams Algorithmus verwendet Festkommazahlen, dh ganzzahlige Arithmetik.
Abrunden	Der DDA-Algorithmus rundet die Koordinaten auf die ganze Zahl ab, die der Linie am nächsten liegt.	Der Algorithmus von Bresenham rundet nicht ab, sondern nimmt den inkrementellen Wert bei seiner Operation.
Zeichnung	Der DDA-Algorithmus kann Kreise und Kurven mit geringerer Genauigkeit zeichnen.	Bresenhams Algorithmus kann Kreise und Kurven viel genauer zeichnen.
Geschwindigkeit	Der DDA-Algorithmus ist langsamer als der Bresenham-Algorithmus, da er echte arithmetische Gleitkommaoperationen verwendet.	Der Bresenham-Algorithmus ist schneller als der DDA-Algorithmus, da er ganzzahlige Arithmetik verwendet.
Komplexität	Beim DDA-Algorithmus ist die Komplexität der Berechnung komplexer.	Bei Bresenhams Algorithmus ist die Komplexität der Berechnung einfach.
Kosten	Der DDA-Algorithmus ist teurer als der Bresenham-Algorithmus.	Der Bresenham-Algorithmus ist billiger als der DDA-Algorithmus.

Lesen Sie auch : Unterschied zwischen Prims und Kruskals Algorithmus

Was Sie über DDA und Bresenhams wissen müssen

Der Bresenham-Algorithmus wurde 1962 von JEBresenham entwickelt und ist viel genauer und viel effizienter als DDA.
Es scannt die Koordinaten, aber anstatt sie zu runden, berücksichtigt es den Inkrementwert durch Addieren oder Subtrahieren und kann daher zum Zeichnen von Kreisen und Kurven verwendet werden.
Wenn also eine Linie zwischen zwei Punkten x und y gezogen werden soll, dann sind die nächsten Koordinaten (xa+1, ya) und (xa+1, ya+1), wobei a der Inkrementwert der nächsten Koordinaten und die Differenz zwischen diesen ist zwei werden durch Subtrahieren oder Addieren der von ihnen gebildeten Gleichungen berechnet.
Der DDA-Algorithmus ist beim Strichzeichnen eher langsam als der Bresenhams-Algorithmus, da er echte Arithmetik (Gleitkommaoperationen) verwendet.
DDA verwendet Gleitkommazahlen, während der Bresenham-Algorithmus Festkommazahlen verwendet.
DDA rundet die Koordinaten auf die nächste ganze Zahl ab, der Bresenham-Algorithmus jedoch nicht.
Der Bresenham-Algorithmus ist viel genauer und effizienter als DDA.
Der Bresenham-Algorithmus kann Kreise und Kurven viel genauer zeichnen als DDA.
DDA verwendet Multiplikation und Division von Gleichungen, aber der Bresenham-Algorithmus verwendet nur Subtraktion und Addition.
Der Bresenhams-Algorithmus ist beim Strichzeichnen schneller als der DDA-Algorithmus, da er in seinen Berechnungen nur Additionen und Subtraktionen durchführt und nur ganzzahlige Arithmetik verwendet, sodass er erheblich schneller läuft.
Der Bresenhm-Algorithmus rundet nicht ab, sondern nimmt den inkrementellen Wert bei seiner Operation.

Lesen Sie auch: Unterschied zwischen RSA- und DSA-Algorithmus

osky