Der Bresenham Linienalgorithmus ist ein Algorithmus, der bestimmt, welche Punkte in einem n-dimensional Raster geplant werden sollten, um eine nahe Annäherung an eine Gerade zwischen zwei gegebenen Punkten zu bilden. Es wird allgemein verwendet, um Linien auf einem Computerschirm zu ziehen, wie es nur Hinzufügung der ganzen Zahl, Subtraktion und Bit-Verschiebung verwendet, von denen alle sehr preiswerte Operationen in Standardcomputerarchitekturen sind. Es ist einer der frühsten im Feld der Computergrafik entwickelten Algorithmen. Eine geringe Erweiterung auf den ursprünglichen Algorithmus befasst sich auch mit Zeichnung von Kreisen.

Während Algorithmen wie der Algorithmus von Wu auch oft in der modernen Computergrafik verwendet werden, weil sie Antialiasing unterstützen können, bedeuten die Geschwindigkeit und Einfachheit des Linienalgorithmus von Bresenham, dass es noch wichtig ist. Der Algorithmus wird in der Hardware wie Verschwörer und in den Grafikchips von modernen Grafikkarten verwendet. Es kann auch in vielen Softwaregrafikbibliotheken gefunden werden. Weil der Algorithmus sehr einfach ist, wird er häufig entweder im firmware oder in der Grafikhardware von modernen Grafikkarten durchgeführt.

Das Etikett "Bresenham" wird heute für eine ganze Familie von Algorithmen der ursprüngliche Algorithmus von sich ausstreckendem oder modifizierendem Bresenham verwendet. Sieh weitere Verweisungen unten.

Geschichte

Der Algorithmus wurde von Jack E. Bresenham 1962 an IBM entwickelt. 2001 hat Bresenham geschrieben:

Eine Beschreibung der Linienzeichnungsroutine wurde für die Präsentation am 1963-ACM nationale Tagung in Denver, Colorado akzeptiert. Es war ein Jahr, in dem keine Verhandlungen, nur die Tagesordnung von Sprechern und Themen in einem Problem von Kommunikationen des ACM veröffentlicht wurden. Eine Person von IBM Systems Journal hat mich gefragt, nachdem ich meine Präsentation gemacht habe, wenn sie das Papier veröffentlichen konnten. Ich habe glücklich zugestimmt, und sie haben es 1965 gedruckt.

Der Algorithmus von Bresenham wurde später modifiziert, um Kreise, der resultierende Algorithmus zu erzeugen, der entweder als "der Kreisalgorithmus von Bresenham" oder als Mittelpunkt-Kreisalgorithmus manchmal bekannte.

Der Algorithmus

Die allgemeine Vereinbarung wird verwendet:

• der spitzenverlassene ist (0,0) solch, dass Pixel Zunahme im Recht und unten den Richtungen koordiniert (z.B, dass das Pixel an (1,1) direkt über dem Pixel an (1,2) ist), und
• dass die Pixel-Zentren Koordinaten der ganzen Zahl haben.

Die Endpunkte der Linie sind die Pixel an (x, y) und (x, y), wo die erste Koordinate des Paares die Säule ist und das zweite die Reihe ist.

Der Algorithmus wird nur für den Oktanten am Anfang präsentiert, in dem das Segment hinuntergeht und nach rechts (xx und yy), und sein horizontaler Vorsprung länger ist als der vertikale Vorsprung (die Linie hat einen negativen Hang, dessen absoluter Wert weniger als 1 ist.)

In diesem Oktanten, für jede Spalte x zwischen und, gibt es genau eine Reihe y (geschätzt durch den Algorithmus), ein Pixel der Linie enthaltend, während jede Reihe dazwischen und vielfache rasterized Pixel enthalten kann.

Der Algorithmus von Bresenham wählt die ganze Zahl y entsprechend dem Pixel-Zentrum, das am idealen (unbedeutenden) y für denselben x am nächsten ist; auf aufeinander folgenden Säulen kann y dasselbe bleiben oder um 1 zunehmen.

Durch die allgemeine Gleichung der Linie durch die Endpunkte wird gegeben:

:

Da wir die Säule, x wissen, wird die Reihe des Pixels, y, durch das Runden dieser Menge zur nächsten ganzen Zahl gegeben:

:

Der Hang hängt von den Endpunkt-Koordinaten nur ab und kann vorgeschätzt werden, und das Ideal y für aufeinander folgende Werte der ganzen Zahl von x kann geschätzt werden, anfangend von und wiederholt den Hang hinzufügend.

In der Praxis kann der Algorithmus, statt vielleicht großer Y-Werte, eines kleinen Fehlerwerts zwischen 0.5 und 0.5 verfolgen: Die vertikale Entfernung zwischen dem rund gemachten und dem genauen y schätzt für den Strom x.

Jedes Mal x wird vergrößert, der Fehler wird durch den Hang vergrößert; wenn es 0.5 zu weit geht, wird der rasterization y um 1 vergrößert (die Linie setzt die folgende niedrigere Reihe des Rasters fort), und der Fehler ist decremented durch 1.0.

Im folgenden Pseudocode plant Probe einen Punkt und gibt absoluten Wert zurück:

Funktionslinie (x0, x1, y0, y1)

interne Nummer deltax: = x1 - x0

interne Nummer deltay: = y1 - y0

echter Fehler: = 0

echter deltaerr: = abs (deltay / deltax)//Nehmen deltax An! = 0 (ist Linie nicht vertikal),

//bemerken Sie, dass diese Abteilung in einem Weg getan werden muss, der den Bruchteil bewahrt

interne Nummer y: = y0

für x von x0 bis x1

Anschlag (x, y)

Fehler: = Fehler + deltaerr

wenn Fehler  0.5 dann

y: = y + 1

Fehler: = Fehler - 1.0

Generalisation

Die Version behandelt oben nur Linien, die nach rechts hinuntersteigen. Wir würden natürlich gern im Stande sein, alle Linien zu ziehen. Der erste Fall erlaubt uns, Linien zu ziehen, die sich noch abwärts, aber Kopf in der entgegengesetzten Richtung neigen. Das ist eine einfache Sache, die anfänglichen Punkte wenn zu tauschen. Heikler bestimmt, wie man Linien zieht, die steigen. Um das zu tun, überprüfen wir wenn y  y; wenn so, wir Schritt y durch-1 statt 1. Letzt müssen wir noch den Algorithmus zur Zeichnung von Linien in allen Richtungen verallgemeinern. Herauf bis jetzt sind uns nur im Stande gewesen, Linien mit einem Hang weniger als ein zu ziehen. Um im Stande zu sein, Linien mit einem steileren Hang zu ziehen, nutzen wir die Tatsache aus, dass eine steile Linie über die Linie y=x widerspiegelt werden kann, um eine Linie mit einem kleinen Hang zu erhalten. Die Wirkung ist, den x und die y Variablen überall, einschließlich der Schaltung der Rahmen zu schalten, um sich zu verschwören. Der Code sieht wie das aus:

Funktionslinie (x0, x1, y0, y1)

steiler boolean: = abs (y1 - y0)> abs (x1 - x0)

wenn steil, dann

Tausch (x0, y0)

Tausch (x1, y1)

wenn x0> x1 dann

Tausch (x0, x1)

Tausch (y0, y1)

interne Nummer deltax: = x1 - x0

interne Nummer deltay: = abs (y1 - y0)

echter Fehler: = 0

echter deltaerr: = deltay / deltax

interne Nummer ystep

interne Nummer y: = y0

wenn y0 und; außerdem können Fehler über viele Schwimmpunkt-Hinzufügungen anwachsen. Das Arbeiten mit ganzen Zahlen wird sowohl schneller als auch genauer sein. Der Trick, den wir verwenden, soll alle Bruchzahlen (einschließlich der unveränderlichen 0.5) im Code oben dadurch multiplizieren, der uns ermöglicht, sie als ganze Zahlen auszudrücken. Das läuft auf ein teilen Inneres die Hauptschleife jedoch hinaus. Um uns damit zu befassen, modifizieren wir, wie initialisiert und verwendet wird, so dass, anstatt an der Null anzufangen und zu 0.5 zusammenzuzählen, es an 0.5 anfängt und zur Null hinzählt. Das neue Programm sieht wie das aus:

Funktionslinie (x0, x1, y0, y1) steiler boolean: = abs (y1 - y0)> abs (x1 - x0) wenn steil, dann Tausch (x0, y0) Tausch (x1, y1) wenn x0> x1 dann Tausch (x0, x1) Tausch (y0, y1) interne Nummer deltax: = x1 - x0 interne Nummer deltay: = abs (y1 - y0)

int Fehler: = deltax / 2

interne Nummer ystep interne Nummer y: = y0

wenn y0

wenn steil, dann Tausch (x0, y0) Tausch (x1, y1)

interne Nummer deltax: = abs (x1 - x0)

interne Nummer deltay: = abs (y1 - y0) int Fehler: = deltax / 2 interne Nummer ystep interne Nummer y: = y0

interne Nummer inc REM hat hinzugefügt

wenn x0 s im initialisation durch das Betrachten der Fehlerberechnung für beide Richtungen gleichzeitig:

Funktionslinie (x0, y0, x1, y1)

dx: = abs (x1-x0)

dy: = abs (y1-y0)

wenn x0

irren Sie sich: = irren sich - dy

x0: = x0 + sx

enden Sie wenn

wenn e2

wo M der Hang ist und b der Y-Abschnitt ist. Das ist eine Funktion nur x, und es würde nützlich sein, diese Gleichung schriftlich als eine Funktion sowohl von x als auch von y zu machen. Das Verwenden algebraischer Manipulation und Anerkennung, dass der Hang der "Anstieg über den geführten" oder dann ist

:

\begin {richten }\aus

y & = mx + b \\

y & = \frac {(\Delta y)} {(\Delta x)} x + b \\

(\Delta x) y & = (\Delta y) x + (\Delta x) b \\

0 & = (\Delta y) x - (\Delta x) y + (\Delta x) b

\end {richten }\aus

</Mathematik>Wenn man

diese letzte Gleichung eine Funktion von x und y dann sein lässt, kann es als geschrieben werden

:

wo die Konstanten sind

Die Linie wird dann für einige Konstanten A, B, und C und überall definiert. Für irgendwelchen nicht auf der Linie dann. Es sollte bemerkt werden, dass alles über diese Form nur ganze Zahlen einschließt, wenn x und y ganze Zahlen sind, da die Konstanten notwendigerweise ganze Zahlen sind.

Als ein Beispiel die Linie dann konnte das als geschrieben werden. Der Punkt (2,2) ist auf der Linie

:

und der Punkt (2,3) ist nicht auf der Linie

:

und keiner ist der Punkt (2,1)

:

Bemerken Sie, dass die Punkte (2,1) und (2,3) auf Gegenseiten der Linie sind und f (x, y) zum positiven oder negativen bewertet. Eine Linie spaltet ein Flugzeug in Hälften und das Halbflugzeug, das einen negativen f hat (x, y) kann das negative Halbflugzeug genannt werden, und die andere Hälfte kann hat das positive Halbflugzeug genannt. Diese Beobachtung ist im Rest der Abstammung sehr wichtig.

Algorithmus

Klar ist der Startpunkt auf der Linie

:

nur weil die Linie definiert wird, um anzufangen und auf Koordinaten der ganzen Zahl zu enden (obwohl es völlig angemessen ist, eine Linie mit Endpunkten der nichtganzen Zahl ziehen zu wollen).

Beachtend, dass der Hang weniger ist als oder gleich einem, stellt sich das Problem jetzt betreffs vor, ob der folgende Punkt an sein sollte oder. Vielleicht intuitiv sollte der Punkt gestützt gewählt werden, auf den an der Linie daran näher ist. Wenn es am ersteren näher ist, dann schließen den ehemaligen Punkt auf der Linie, wenn die Letzteren dann die Letzteren ein. Um darauf zu antworten, denken Sie den Mittelpunkt zwischen diesen zwei Punkten:

:

Wenn der Wert davon dann negativ ist, liegt der Mittelpunkt über der Linie, und wenn der Wert davon dann positiv ist, dass der Mittelpunkt unter der Linie liegt. Wenn der Mittelpunkt unter der Linie liegt, dann sollte gewählt werden, da es näher ist; sonst sollte gewählt werden. Diese Beobachtung ist entscheidend, um zu verstehen! Der Wert der Linienfunktion an diesem Mittelpunkt ist die alleinige Determinante, deren Punkt gewählt werden sollte.

Das Image zum Recht zeigt den blauen Punkt (2,2) gewählt, um auf der Linie mit zwei Kandidat-Punkten im Grün (3,2) und (3,3) zu sein. Der schwarze Punkt (3, 2.5) ist der Mittelpunkt zwischen den zwei Kandidat-Punkten.

Wechselweise kann der Unterschied zwischen Punkten verwendet werden, anstatt f (x, y) an Mittelpunkten zu bewerten. Der Unterschied für die erste Entscheidung ist

:\begin {richten }\aus

D & = f (x_0+1, y_0+1/2) - f (x_0, y_0) \\

& = \left [(x_0+1) + B (y_0+1/2) + C \right] - \left [Ein x_0 + B y_0 + C \right] \\

& = + \frac {1} {2} B

\end {richten }\aus</Mathematik>

Wenn dieser Unterschied, D, positiv ist, dann hat sonst gewählt.

Die Entscheidung für den zweiten Punkt kann als geschrieben werden

::

Wenn der Unterschied positiv ist, dann wird sonst gewählt. Diese Entscheidung kann durch das Ansammeln des Fehlers verallgemeinert werden.

Die ganze Abstammung für den Algorithmus wird getan. Ein Leistungsproblem ist der 1/2 Faktor im Anfangswert von D. Da all dieser über das Zeichen des angesammelten Unterschieds ist, dann kann alles mit 2 ohne Folge multipliziert werden.

Das läuft auf einen Algorithmus hinaus, der nur Arithmetik der ganzen Zahl verwendet.

Anschlag (x0, y0, x1, y1)

dx=x1-x0

dy=y1-y0

D = 2*dy - dx

Anschlag (x0, y0)

y=y0

für x von x0+1 bis x1

wenn D> 0

y = y+1

Anschlag (x, y)

D = D + (2*dy-2*dx)

sonst

Anschlag (x, y)

D = D + (2*dy)

Das Laufen dieses Algorithmus für von (0,1) bis (6,4) Erträge die folgenden Unterschiede mit dx=6 und dy=3:

• D=2*3-6=0
• Anschlag (0,1)
• Schleife von 1 bis 6
• x=1: D0: Anschlag (1,1), D=6
• x=2: D> 0: Y=2, verschwören Sie sich (2,2), D=6 + (6-12) =0
• x=3: D0: Anschlag (3,2), D=6
• x=4: D> 0: Y=3, verschwören Sie sich (4,3), D=6 + (6-12) =0
• x=5: D0: Anschlag (5,3), D=6
• x=6: D> 0: Y=4, verschwören Sie sich (6,4), D=6 + (6-12) =0

Das Ergebnis dieses Anschlags wird nach rechts gezeigt. Das Plotten kann durch das Plotten an der Kreuzung von Linien (blaue Kreise) oder das Ausfüllen von Pixel-Kästen (gelbe Quadrate) angesehen werden. Trotzdem ist das Plotten dasselbe.

Alle Fälle

Jedoch wie oben erwähnt ist das nur für den ersten Oktanten. Das bedeutet, dass es acht mögliche Fälle gibt, um in Betracht zu ziehen.

Ähnliche Algorithmen

Der Bresenham Algorithmus kann so ein bisschen modifizierter DDA interpretiert werden (0.5 verwendend, wie Fehlerschwelle statt 0, der erforderlich ist, um auf Vieleck rasterizing nichtüberzugreifen).

Der Grundsatz, einen zusätzlichen Fehler im Platz von Abteilungsoperationen zu verwenden, hat andere Anwendungen in der Grafik. Es ist möglich, diese Technik zu verwenden, um den U zu berechnen, V Koordinaten während des Rasteransehens der Textur haben Vielecke kartografisch dargestellt. Der voxel heightmap softwaremachende Motoren, die in einigen PC-Spielen auch gesehen sind, hat diesen Grundsatz verwendet.

Bresenham hat auch eine Lauf-Scheibe (im Vergleich mit der Lauf-Länge) rechenbetonter Algorithmus veröffentlicht.

Eine Erweiterung auf den Algorithmus, der dicke Linien behandelt, wurde von Alan Murphy an IBM geschaffen.

Siehe auch

• Digitaldifferenzial Analysator (Grafikalgorithmus), eine einfache und allgemeine Methode für rasterizing Linien und Dreiecke
• Der Linienalgorithmus von Xiaolin Wu, eine ähnlich schnelle Methode, Linien mit dem Antialiasing zu ziehen
• Mittelpunkt-Kreisalgorithmus, ein ähnlicher Algorithmus, um Kreise zu ziehen

Zeichen

• Jack E. Bresenham, "Algorithmus für die Computerkontrolle eines Digitalverschwörers", IBM Systems Journal, Vol. 4, Nr. 1, Januar 1965, Seiten 25-30
• "Der Bresenham linienziehende Algorithmus", durch Colin Flanagan
• Die Grafik von Michael Abrash, die Schwarze Liste eine sehr optimierte Version des Algorithmus in C und Zusammenbau für den Gebrauch in Videospielen mit ganzen Details seiner inneren Tätigkeit Programmiert, die von Michael Abrash, Seiten 654-678 - internationale Standardbuchnummer 978-1-57610-174-2 geschrieben ist

Weiterführende Literatur

• Die These von Patrick-Gilles Maillot eine Erweiterung des Linienzeichnungsalgorithmus von Bresenham, um verborgene 3D-Linieneliminierung durchzuführen; auch veröffentlicht in MICAD '87 Verhandlungen auf dem CAD/NOCKEN und der Computergrafik, der Seite 591 - internationale Standardbuchnummer 2-86601-084-1.
• Linie, die durch die Modifizierung zum Algorithmus von Bresenham, A.S. Murphy, IBM Technical Disclosure Bulletin, Vol Dick wird. 20, Nr. 12, Mai 1978.

Links

• Didaktische Javascript Durchführung
• GEBROCHEN: Analysieren Sie http://tide4javascript.com/?s=Bresenham den Linienalgorithmus von Bresenham in einem Online-Javascript IDE
• Der Bresenham linienziehende Algorithmus durch Colin Flanagan
• Nationales Institut für Standards und Technologieseite auf dem Algorithmus von Bresenham
• Calcomp 563 Zusätzliche Verschwörer-Information
• 3D-Erweiterung
• Bresenham, der 2., bis zu 6D 3D

ist

• Bresenham Algorithmus auf mehreren Programmiersprachen
• Die Schönheit des Algorithmus von Bresenham - Eine einfache Durchführung, um Linien, Kreise, Ellipsen und Bézier zu planen, biegt