Bresenham-Algorithmus (in Arbeit): Unterschied zwischen den Versionen
(→Bresenham-Algortihmus für Geraden) |
(→Bresenham-Algortihmus für Geraden) |
||
Zeile 113: | Zeile 113: | ||
<math>= \begin{pmatrix} n_x \\ n_y \end{pmatrix} \cdot \begin{pmatrix} p_x + 1 + p_x + 1 \\ p_y + p_y + 1 \end{pmatrix} </math><br><br> | <math>= \begin{pmatrix} n_x \\ n_y \end{pmatrix} \cdot \begin{pmatrix} p_x + 1 + p_x + 1 \\ p_y + p_y + 1 \end{pmatrix} </math><br><br> | ||
<math>= \begin{pmatrix} n_x \\ n_y \end{pmatrix} \cdot \begin{pmatrix} 2 \cdot p_x + 2 \\ 2 \cdot p_y + 1 \end{pmatrix} </math><br><br> | <math>= \begin{pmatrix} n_x \\ n_y \end{pmatrix} \cdot \begin{pmatrix} 2 \cdot p_x + 2 \\ 2 \cdot p_y + 1 \end{pmatrix} </math><br><br> | ||
− | <math>= - ( n_x \cdot 2 \cdot p_x \ + 2 \cdot n_x + n_y \cdot 2 \cdot p_y + n_y ) </math> | + | <math>= - ( n_x \cdot 2 \cdot p_x \ + 2 \cdot n_x + n_y \cdot 2 \cdot p_y + n_y ) =: d </math> |
+ | |||
+ | Nun entscheidet das Vorzeichen von <math> d </math> welcher Punkt angesteuert wird: | ||
+ | Für <math> d >= 0 </math> der Punkt <math> S </math><br><br> | ||
+ | Für <math> d < 0 </math> der Punkt <math> T </math><br><BR> | ||
+ | |||
Version vom 7. März 2013, 16:26 Uhr
Inhaltsverzeichnis |
Allgemeines zum Bresenham Algorithmus
Motivation des Algorithmus
Der Bresenham-Algorihtmus, ist ein Verfahren um Graden bzw. Kreise möglichst "gut" auf Anzeigegeräten zu zeichnen. Hier heisst "gut", dass die Abweichung zwischen dem gezeichneten und dem gedachten Objekt möglichst gering ist.
Das Problem beim Darstellen einer Strecke auf einem Anzeigegerät ist, dass das erzeugte Bild nur durch endlich viele Punkte aufgebaut ist. Dadurch entstehen "Lücken" beim zeichnen. Da unser Auge nur eine endliche Auflösung verarbeiten kann, scheint uns ein Bild auf dem Monitor nicht durch einzelne Punkte aufgebaut zu sein, sondern es entstehen für uns geometrische Formen, die wir mit unserer Vorstellung von mathematischen Objekten in Einklang bringen können.
Eine Gerade wie wir sie auf dem Bildschirm wahrnehmen.
Hier sieht man dieselbe Gerade um das 8fache vergrößert.
Effektivität des Algorithmus
Dieser Algorithmus ist auch in heutiger Zeit, in seiner Geschwindigkeit und Einfachheit ungeschlagen, da die Rechenoperationen sich auf Addition und die Multiplikation mit zwei beschränken lässt. Dadurch kann dieser Rechenalgorithmus direkt in die Hardware der Grafikkarten implementiert werden.
Obwohl in den Rechentermen Potenzen auftreten, kann man diese umgehen.
Hierfür betrachten wir den Ausdruck:
die zweite Binomische Formel liefert:
durch rekursives Anwenden dieser Formel lassen sich Potenzen solange vereinfachen bis die Basis Eins erreicht ist und damit die Potenz verschwindet.
Multiplikation mit zwei
Eine Multiplikation mit der Zwei ist für einen Computer eine elementare Rechenoperation, da die sogenannte Shift Operation (Verrückungsoperation) durchgeführt werden kann.
Wir erinnern uns an die Darstellung von Zahlen im Binärsystem.
Wertigkeit der Stelle | 2^7 = 128 | 2^6 = 64 | 2^5 = 32 | 2^4 = 16 | 2^3 = 8 | 2^2 = 4 | 2^1 = 2 | 2^0 = 1 |
---|---|---|---|---|---|---|---|---|
Binärzahl | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
Hier wird die Zahl (im Dezimalsystem) dargestellt
Multiplizerien wir nun mit zwei, so folgt:
Also die Zahl 154 (Dezimal) in Binärdarstellung:
Wertigkeit der Stelle | 2^7 = 128 | 2^6 = 64 | 2^5 = 32 | 2^4 = 16 | 2^3 = 8 | 2^2 = 4 | 2^1 = 2 | 2^0 = 1 |
---|---|---|---|---|---|---|---|---|
Binärzahl | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
Vergleichen wir nun die Darstellung der Zahl 77 mit der Darstellung der Zahl 154, so fällt auf, dass durch die Multiplikation mit Zwei jedes Bit um eine Stelle nach links verschoben wurde.
Skizzen
Bresenham-Algortihmus für Geraden
Wir wollen uns nun mit der folgenden Problemstellung beschäftigen, wir wollen eine Gerade, welche in Hesseform gegeben ist, mit einem Plotter (z.B. Monitor) zeichnen lassen. Wir wollen für den ersten Teil nur Geraden mit einer Steigung betrachten.
Sei die Gerade gegeben. Hierbei ist
der normierte Normalenvektor,
ein gegebener Ortsvektor eines Punktes der Geraden.
Wir geben den Startpunkt der Geraden auf unserem Plotter die Koordinaten (0,0), d.h. jede Gerade, die wir zeichnen erhält damit ein eigenes Koordinatensystem.
Den ersten Punkt den wir zeichnen ist natürlich der Punkt , denn dies haben wir so festgelegt. Nun müssen wir für den nächsten Punkt entscheiden, ob wir nur ein Pixel (allgemein: einen Plotterschritt) nach rechts zum Punkt
gehen oder ein Pixel nach rechts und nach oben zum Punkt
. Um dies zu entscheiden müssen wir die Abstände, die die jeweiligen Punkte zu der idealen Geraden haben, vergleichen. Der Punkt mit dem kleineren Abstand wird dann angesteuert.
Hierfür betrachten wir die Differenz der Abstände .
Nun gehen wir nicht mehr von dem ersten Punkt (Ursprung) aus, sondern von einem allgemeinen Punkt
, dementsprechend lautet dann der Punkt
und der Punkt
(*)Achtung:
Wie wir unter dem Punkt Hesseform gesehen haben, kommt es bei den Abständen der Punkte auf die Lage der Punkte im Bezug zur Geraden und dem Ursprung an. Da der Punkt nicht zwischen Gerade und Ursprung liegt hat, ist der Abstand
positiv, analog ist der Abstand
negativ.
Also folgt mit (*):
Nun entscheidet das Vorzeichen von welcher Punkt angesteuert wird:
Für
der Punkt
Für der Punkt
Skizze