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 1 ,x 2 ,y 1 ,y 2 ,d,i 1 ,i 2 ,dx,dy
Schritt 3: Geben Sie den Wert von x 1 ,y 1 ,x 2 ,y 2
ein, wobei x 1 ,y 1 die Koordinaten des Startpunkts
und x 2 ,y 2 die Koordinaten des Endpunkts sind
Schritt 4: Berechnen von dx = x 2 – x 1
Berechnen von dy = y 2 – y 1
Berechnen von i 1 =2*dy
Berechnen von i 2 =2*(dy-dx)
Berechnen von d=i 1 –dx
Schritt 5: Betrachte (x, y) als Startpunkt und x Ende als maximal möglichen Wert von x.
Wenn dx < 0
Dann x = x 2
y = y 2
x Ende = x 1
Wenn dx > 0
Dann x = x 1
y = y 1
x Ende = x 2
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 1
Wenn d ≥ 0
Dann d = d + i 2
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 1 ,y 1 ,x 2 ,y 2 ,dx,dy,x,y als ganzzahlige Variablen.
Schritt 3: Geben Sie den Wert von x 1 ,y 1 ,x 2 ,y 2 ein .
Schritt 4: Berechnen Sie dx = x 2 – x 1
Schritt 5: Berechnen Sie dy = y 2 – y 1
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 1
zuweisen y = y 1
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 2
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