ASM86FAQ - Algorithmen
DWord -> DezStr (Zahlenkonvertierung)
Markus Krieger 2:2454/420.6: Topic in Arbeit
DWord -> HexStr (Zahlenkonvertierung)
Markus Krieger 2:2454/420.6: Topic in Arbeit
DWord -> BinStr (Zahlenkonvertierung)
Markus Krieger 2:2454/420.6:
Ein DWord besteht aus 32 Bit. Will man nun diesen Wert in einen Binärstring umformen, benötigt man für die Speicherung des Strings dementsprechend 32 Bytes.
Für eine Umformung in einen Binärstring eignen sich die sogenannten Schiebe- befehle (man braucht sie nicht unbedingt, doch da dies hier eine Assembler FAQ ist, gehe ich besonders darauf ein).
Ein Schiebebefehl schiebt alle Bits in einer Speicherzelle nach links oder rechts. So kann man, wenn man z.B. die Bitfolge 11001010 hat, diese um ein Bit nach links oder rechts schieben:
urspruenglich 11001010 daraus wird nach einer Verschiebung nach links 10010100 bzw. nach rechts 01100101
Man sieht allerdings, daß bei einer Verschiebung unter Umständen eine 1 weg- fällt bzw. auf der anderen Seite wieder auftaucht (ist abhängig vom verwen- deten Schiebebefehl). Benutzt man z.B. auf einem PC den Befehl SHL, wird das herausfallende Bit im CF (Bit 0 im eFLAGS-Register) gespeichert.
Abhängig vom Inhalt des CF könnte man folglich nach jedem Schiebevorgang das CF prüfen und sein Programm entsprechend verzweigen lassen, um eine 0 oder 1 in seinen String zu schreiben.
Um eine vollständige Umformung zu erhalten, muß der Vorgang 32mal wiederholt werden, ein DWord hat ja schließlich 32 Bit. Natürlich darf man auch nicht vergessen, immer die Schreibposition im ASCII-String jeweils um eine Stelle zu erhöhen... ;)
Nochmal kurz:
1. Man setzt einen Zähler auf 32 (Anzahl der Durchläufe) 2. Man führt einen Schiebebefehl nach links aus 3. In einem Register landet das Bit, welches nach links herausgeschoben worden ist 4. Je nach Zustand dieses Bits ASCII-0 oder 1 in den String schreiben 5. Die Schreibposition des nächsten Zeichens im String um eins erhöhen 6. Den Zähler um eins vermindern 7. Wenn der Zähler = 0 ist, ist die Umformung abgeschlossen, ansonsten weiter bei 2.
DezStr -> DWord (Zahlenkonvertierung)
Markus Krieger 2:2454/420.6: Topic in Arbeit
HexStr -> DWord (Zahlenkonvertierung)
Markus Krieger 2:2454/420.6: Topic in Arbeit
BinStr -> DWord (Zahlenkonvertierung)
Markus Krieger 2:2454/420.6:
Ein DWord besteht aus 32 Bit. Ein umzuformender Binärstring muss also auch eine Länge von 32 Zeichen haben. Diese 32 Zeichen sind in einem ASCII-String gespeichert, der ja nur aus Kombinationen von "0" und "1" bestehen kann.
Anders als für die Umwandlung DWord -> BinStr (vergl. ALG0003) benötigt man hier die Rotationsbefehle, da man mit dem Schiebebefehlen nur Bits auslesen und nicht setzen kann. Man benötigt bei einem 80x86 den Befehl RCL. Dieser Befehl schiebt die vorhandenen Bits um eine Position nach links. Das höchst- wertigste Bit (links) landet im Carryflag (CF). Der vorherige Inhalt des CF wird an die niederwertigste Position (rechts) geschrieben.
Die Umwandlung findet nun folgendermaßen statt:
a. Es wird ein Zähler auf 32 gesetzt
b. Es wird ein Zeiger auf das erste Byte des umzuformenden Strings gesetzt (enthält entweder "0" oder "1")
Jetzt beginnt die eigentliche Umwandlung:
1. Das Zeichen an der Zeigerposition wird eingelesen.
2. Abhängig vom Zeichen wird das CF gesetzt (gesetzt für eine 1).
(ich persönlich würde das so machen: von dem im Register stehenden ASCII- Wert für "0" oder "1" wird der Wert für "0" abgezogen. Im Register steht nun entweder eine 0b (b fuer binär) oder eine 1b. Ist es eine 0, ist das ZF gesetzt. Genau entgegengesetzt muss das CF gesetzt sein.)
3. Mit dem Rotations-Befehl (in diesem Falle RCL, s.o.) wird der Inhalt des CF an die rechte Position im DWord geschrieben und der Inhalt um eine Po- sition nach links verschoben.
4. Die Zeigerposition wird um eins erhöht.
5. Der Zähler wird um eins vermindert.
6. Wenn der Zähler noch nicht 0 ist, wieder zu 1.
InsertionSort (Sortierung)
Michael Klose 2:2446/301.7: Topic in Arbeit.
BubbleSort (Sortierung)
Michael Klose 2:2446/301.7: Topic in Arbeit.
QuickSort (Sortierung)
Michael Klose 2:2446/301.7: Topic in Arbeit.
MergeSort (Sortierung)
Michael Klose 2:2446/301.7: Topic in Arbeit.
HeapSort (Sortierung)
Michael Klose 2:2446/301.7: Topic in Arbeit.
ShellSort (Sortierung)
Michael Klose 2:2446/301.7: Topic in Arbeit.
BucketSort (Sortierung)
Michael Klose 2:2446/301.7: Topic in Arbeit.
Boyer-Moore (Suche)
Frederik Heber 2:2476/830.26:
Dieser Algorithmus ist besonders schön, da er sehr wenig Vergleiche braucht und damit extrem schnell ist.
Der Witz an ihm ist, ist daß wir nicht mehr jeden Buchstaben einzeln ver- gleichen, sondern wortweise immer nur den letzten Buchstaben. Man spart sich so einiges an IFs bzw. CMPs.
Aber am besten versteht man ihn wohl an einem Beispiel.
Unser Text, in dem wir einen String suchen wollen, waere dieser Satz (<g>).
Und darin suchen wir nun das Wort "String".
Der Trick ist nun, daß wir uns ein 256-Char (Byte) großes Array anlegen und es mit der Länge des Wortes (6) initialisieren. Anschließend gehen wir nun unseren Suchstring durch und schreiben an die Stelle im Array, dessen ASCII- Wert dem Zeichen entspricht, die Zahl (Länge-Pos) rein, wobei Pos die Posi- tion des Zeichens in unserem Suchstring ist und bei 1 beginnt.
Der ASCII-Wert von 'S' ist 83. Also schreiben wir bei Array[83] (6-1) rein. 't' wäre 116. Also kommt bei Array[116] (6-2) hinein ... und schließlich bei 'g': Array[103] (6-6).
Jetzt fangen wir beim 6. Zeichen (nicht beim ersten) an und vergleichen es mit dem letzten (6.) Zeichen des Suchstrings.
' ' == 'g' ? Nicht wahr!
Also nehmen wir array[' '] und addieren es auf unseren Zähler (der uns das Vergleichs-Char im Suchtext anzeigt) drauf.
' ' == 'g' ? s.o. 'm' == 'g' ? s.o. 'e' == 'g' ? s.o. 'S' == 'g' ? Nicht wahr, s.o.
Es fällt aber auf, daß wir nicht mehr 6 weitergehen, sondern dieses Mal nur 5 Schritte (Array['S'] = 6-1).
'g'=='g' ? Jo.
Nun triumphieren wir nicht gleich, sondern gehen mit Zeiger eins zurück und vergleichen, ob dort auch ein 'n' steht, wie wir es erwarten. Trifft zu. Und so weiter mit i,r,t,S. Falls das letzte auch richtig ist, haben wir unseren String gefunden.
Das Ganze nochmal etwas visueller:
Unser' 'Text, in dem wir einen String suchen wollen, waere dieser Satz (<g>). Strin'g'
Unser Text,' 'in dem wir einen String suchen wollen, waere dieser Satz (<g>). Strin'g'
Unser Text, in de'm' wir einen String suchen wollen, waere dieser Satz (<g>). Strin'g'
Unser Text, in dem wir 'e'inen String suchen wollen, waere dieser Satz (<g>). Strin'g'
Unser Text, in dem wir einen 'S'tring suchen wollen, waere dieser Satz (<g>). Strin'g'
Unser Text, in dem wir einen Strin'g' suchen wollen, waere dieser Satz (<g>). Strin'g'
Unser Text, in dem wir einen Stri'n'g suchen wollen, waere dieser Satz (<g>). Stri'n'g . . . Unser Text, in dem wir einen 'S'tring suchen wollen, waere dieser Satz (<g>). 'S'tring
fertig.
Was wäre, wenn da ein 'g' schon vorher im Satz gewesen wäre? Dann hätte er den vorherigen Buchstaben mit dem 'n' verglichen. Wäre wohl fehlgeschlagen. Er würde um 6-Pos(n)+1 weitergehen und weiterfahren.
Was wäre, wenn zwei gleiche Buchstaben im Suchstring vorkommen? Also wenn wir "essen" suchen. Was schreiben wir bei Array['e'] rein? Auf jeden Fall den kleineren Wert, also das 'e' möglichst weit am Ende des Wortes, in die- sem Fall also eine 5-4=1 und nicht eine 5-1=4 !
Nun der Algorithmus in einer C-Umsetzung. Bei mir schafft dieser ein Mbyte Text in einer Sekunde nach einem beliebigen Text zu durchsuchen (wird etwas langsamer, je größer der Suchstring, da ja dann mehr Doppelbuchstaben vor- kommen) auf einem 486DX40.
search : Suchstring text : Suchtext chars : Ist das Array mit Sprüngen aus len-Pos(em) len : Länge des Suchstrings em : Ist der "Zeiger" auf unser Suchstringfeld i : Ist der "Zeiger" auf unser Suchtextfeld stelle : Merkt sich bei Treffer ('g'=='g'), wo wir waren, um später an die Stelle zurückgehen zu können und so leichter weiterzukommen. Ist im Prinzip unnötig. S.o.: len-pos+1 tut es auch. groesse: Ist die Größe von text
{ printf("Suchstring: "); scanf("%s",search); len=strlen(search); em=len-1; /* zeigt auf unser Sucharray /* for(l=0;l<256;l++) chars[l]=len; for(l=0;l<len;l++) chars[(unsigned char)(search[l])]=em-l; i=em; /* zeigt auf unseren Suchtext */
do { if (search[em]!=text[i]) { i+=chars[(unsigned char)text[i]]; if (em<len-1) i=stelle+1; em=len-1; } else { if (em==0) printf("Suchstring gefunden !"); else { if (em==len-1) stelle=i; em--; i--; } } } while (i<groesse); }
Sehen wir uns den Code mal an.
1. Suchstring abfragen 2. Länge bestimmen und Zeiger setzen 3. Das Array mit den Sprüngen einsetzen (man sieht, daß man sich bei zwei- malig vorkommendem 'e' keine Sorgen machen muß, da die alte Position au- tomatisch von der möglichst nahe bei len liegenden überschrieben wird). 4. i auf Länge des Suchstrings und los geht der Spass. 5. Ist es gleich? Wenn nicht, erhöhen wir i um die Zahl aus dem Sprungarray (Der Rest ist zur Rückstellung, falls wir vorher auf ein 'g' trafen, der Buchstabe davor aber kein 'n' war ... <g>) 6. Falls es gleich ist, dann schauen wir, ob wir schon beim ersten Buchsta- ben des Suchstrings und damit am Ende angekommen sind. Falls nicht, wird em dekrementiert (Stichwort: nicht nur 'g'=='g', sondern auch 'n'=='n', usw.). Außerdem merken wir uns die Stelle des 'g', damit wir später ein- facher weiterspringen können. 7. und zu 5, falls wir noch nicht am Ende des Sucharrays sind.
Lempel-Ziv (Komprimierung)
Norman Rudolph 2:2410/235.2: Topic in Arbeit.
Lempel-Ziv-Welch (Komprimierung)
Norman Rudolph 2:2410/235.2: Topic in Arbeit.
Bresenham Line (Grafik)
Frederik Heber 2:2476/830.26: Topic in Arbeit.
Bresenham Circle (Grafik)
Michael Klose 2:2446/301.7:
Vorwort: --------
Dieses Topic der FAQ beschreibt den Bresenham Kreisalgorithmus in einer ziemlich mathematischen Weise, so daß man nachvollziehen kann, warum er denn überhaupt funktioniert.
Der Herr Bresenham hat einen ziemlich genialen Algorithmus entwickelt, um mit möglichst wenig Rechenaufwand Kreise auf dem Bildschirm zu zaubern. Es wird nur mit ganzen Zahlen gerechnet, und es werden keine Multiplikations- oder Divisionsbefehle benutzt. Addition, Subtraktion und Schiebeoperationen sind die einzigen benötigten Operationen.
Wer nur wissen möchte, wie der Algorithmus lautet, und sich für die Herlei- tung nicht interessiert, braucht sie sich ja auch nicht angucken - im Endef- fekt ist ja nur wichtig, was hinten rauskommt. Ich habe mich damals dafür interessiert, wie er überhaupt funktionieren kann, das erkennt man am Ender- gebnis ja nicht gerade. :-)
Dennoch habe ich versucht, die Herleitung so verständlich wie möglich zu machen, so daß jeder mitkommen kann. Um den Bresenham-Algorithmus zu verste- hen, muss man ein paar Kenntnisse in Termumformung haben, ein bißchen Pytha- goras, aber das reicht in Prinzip schon. Pythagoras habe ich aber auch ver- sucht noch mal kurz zu erläutern.
So, ich wünsche noch viel Spass!
Michael Klose
Internet: mklose@uni-duisburg.de Fido : 2:2446/301.7
Wie zeichnet man einen Kreis? -----------------------------
Möchte man einen Algorithmus programmäßig umsetzen, so fragt man sich meist- ens, wie würde man es denn auf Papier machen? Ich weiß nicht, ob es andere auch so machen, aber das ist wenigstens meine Art.
Ich überlege immer Schritt für Schritt, wie ich es denn ueberhaupt mache. Meistens sind die Sachen für uns aber so logisch, daß man gar nicht nach- denkt, wie man es denn gemacht hat (Beispiel: Sortierung von Karten).
So, jetzt wie zeichnet man einen Kreis? Man nimmt einen Zirkel, presst die Spitze in das Papier rein, und zieht mit ihm einen Kreis. Hier dran kann man die ersten beiden Eigenschaften eines Kreises festhalten:
* Er besitzt einen konstanten Mittelpunkt
* Alle 'Punkte' des Kreises haben einen festen (den gleichen) Abstand von diesem Mittelpunkt.
Mit diesen beiden Eigenschaften alleine, lässt sich am Computer leider nur schwer ein Kreis zeichnen, zumindest nicht, wenn die einzige Möglichkeit darin besteht, ihm zu sagen, daß er an Position x,y ein Punkt setzen soll. Unser Problem ist, wie bringen wir es ihm bei?
Ein ganz wichtiger Punkt ist die Symmetrie - er hilft uns das Problem zumin- dest auf einen kleinen Teil des Kreises zu reduzieren. Wenn man sich einen Kreis genauer betrachtet, kann man sehen, daß man im Prinzip nur ein 1/8 des Kreises berechnen muß, der Rest folgt aus der Symmetrie:
W2 W1 \ | / \ P1|P / \ | / \ *|* / \ | / P2 * \ | / *P7 \|/ \|/ ----*---- x ----*---- /|\ /|\ / | \ P3 * / | \ *P6 / | \ / *|* \ / | \ / P4|P5 \ y
Dieses Kreuz zeigt alle Spiegelachsen, die x und die y Achse, sowie die bei- den Winkelhalbierenden. In der Zeichnung rechts sieht man, daß wenn man P berechnet hat, man somit gleichzeitig an 8 weitere Punkte des Kreises kommt: P wurde immer gegen den Uhrzeigersinn gespiegelt - zuerst an der y-Achse, dadurch wurde Punkt P1 gewonnen, dann wurde P1 an W2 gespiegelt, hieraus wurde P2 gewonnen, etc...
Man kann aber auch sehen, daß P3 z.B. P6 entspricht, wenn man ihm auf der y Achse spiegelt.
In Koordinaten ausgedrückt, ergibt sich somit:
P: ( +x, +y ) P1: ( -x, +y ) P2: ( -y, +x ) P3: ( -y, -x ) P4: ( -x, -y ) P5: ( +x, -y ) P6: ( +y, -x ) P7: ( +y, +x )
Was wir jetzt gewonnen haben, ist folgendes: Wenn man alle x,y Werte für 1/8 des Kreises kennt, so kennt man auch alle weitere Punkte des Kreises.
Berechnungsverfahren für x,y ----------------------------
Das Problem ist jetzt, wie kommt man an die x,y Werte? Das ist eine gute Frage! :-)
Naja, betrachten wir noch mal den Kreis: Man kann durch einfaches hingucken erkennen, daß es für jeden x-Wert mindestens einen y-Wert geben muß (wenn x nicht außerhalb des Kreises ist).
Zusätzlich kennt man folgende Koordinaten (ebenfalls ermittelt durch hingu- cken):
( 0, R ) ( R, 0 ) ( -R, 0 ) ( 0, -R )
Das ist schon eine ganze Menge.
Wenn wir schon alle Eigenarten des Kreises aufzählen, dann sollte man noch erwähnen, daß er 360º (Grad) hat, so, jetzt sind wir fast vollständig.
Nehmen wir mal einen x-beliebigen Kreispunkt:
| | | y-Wert |----------------------------*P | ----- | | r ------ | | -----) | | ------ ) _| |----- Alpha ) |o| -----------------------------++------------------------------------- | x-Wert | | |
Eingezeichnet ist der Punkt P, der x-Wert, der y-Wert und der Winkel Alpha. Wie man sieht, spannt der Koordinatenursprung (0,0), der Punkt P und der Punkt (x,0) ein rechtwinkliges Dreieck ein. Rechtwinklig ist ganz wichtig!!! Der Rechte Winkel ist eingezeichnet.
Der Satz des Pythagoras -----------------------
Wer ihn kennt, kann direkt zum nächsten Abschnitt gehen.
Zur Erinnerung: Die Kurzform lautet aý + bý = cý, wobei c die Hyphothenuse und a und b die Katheten sind.
Viele verstehen jetzt Bahnhof: Es ist ganz einfach:
a,b : Katheten c : Hypothenuse B * ----- | c ------ | -----) |a ------ ) _| ----- Alpha ) |o| A +-----------------------------C b
Das Dreieck hat 3 Grundseiten: a, b und c. In einem Rechtwinkligen Dreieck bezeichnet man die Grundseiten, die den rechten Winkel (90º) einschließen, als Katheten (hier a,b) und die verbliebene Seite c als Hypothenuse.
Betrachtet man den Winkel Alpha, so ist a ja die Kathete gegenüber, deswegen bezeichnet man a (in Bezug auf den Winkel Alpha), als Gegenkathete - b ist die sogenannte Ankathete, weil sie direkt AN dem Winkel Alpha liegt.
Der Herr Pythagoras hat irgendwie herausgefunden, daß das aý + bý = cý ist, so einfach!
Wo ich schon dabei bin, hat jetzt mit dem eigentlichen Thema nichts zu tun, aber was tut man nicht für die Bildung :-) - komme ich mal auf Sinus und Co- sinus:
Es gilt:
Sinus Alpha ist gleich der Länge der Gegenkathete dividiert durch die Länge der Hyphotenuse:
sin(Alpha) = a/c
Cosinus Alpha ist gleich der Länge der Ankathete dividiert durch die Länge der Hyphotenuse:
cos(Alpha) = b/c
Dann gibt es noch Tangens Alpha:
tan(Alpha) = Gegenkathete/Ankathete.
Warum ich das erwähne? Weil man häufig Lösungen für einen Kreis sieht, die einfach für Alpha eine FOR Schleife von 0 bis 360 Grad laufen lassen, und so die Punkte x,y berechnen:
Es gilt ja:
sin(Alpha) = a/c
Umgeformt ergibt das:
a = c * sin(Alpha)
Die Hypothenuse ist aber gerade unser Radius. Also gilt:
y = r * (sin Alpha)
Weiterhin gilt:
cos(Alpha) = b/c
oder umgeformt:
b = c * cos(Alpha)
oder hier bei uns im speziellen Fall:
x = r * cos(Alpha)
Somit hat man die Punkte x und y:
(r * cos(Alpha), r * sin(Alpha))
r ist konstant (Radius), und Alpha wird aus der FOR-Schleife entnommen.
So kann man also ohne Probleme einen Kreis zeichnen. Warum macht man es dann nicht? Erstens geht es hier um den Bresenham Algorithmus, und 2. muss man bedenken, daß Sinus und Cosinus aufwendig zu berechnen und zudem auch noch Fließkommazahlen sind (also keine Ganzzahlen, sondern Zahlen mit Brüchen).
Mit Fließkommazahlen kann der Rechner nicht so schnell umgehen, wie mit gan- zen Zahlen. Um es einfach auszudrücken: die Methode einen Kreis mit Sinus und Cosinus zu berechnen, ist verdammt langsam!!
Anwendung des Satzes des Pythagoras -----------------------------------
Betrachten wir noch einmal unser Diagramm:
| | | y-Wert |----------------------------*P | ----- | | r ------ | | -----) | | ------ ) _| |----- Alpha ) |o| -----------------------------++------------------------------------- | x-Wert | | |
Wir haben gesagt, daß es zu jedem x ein y geben muss. X tun wir nun in eine FOR-Schleife und lassen x von 0 bis r laufen. Wenn wir alle y Werte berech- net haben, haben wir ein ¬ Kreis. Es reicht zwar, wie wir schon gesehen ha- ben, 1/8 des Kreises zu berechnen, um einen Kreis zu zeichnen, für das Ver- ständnis gehe ich aber hier von einem 1/4 Kreis aus.
Schauen wir uns jetzt mal das rechtwinklige Dreieck genauer an:
x und y sind die Längen der Katheten, der Radius ist die Länge der Hyphote- nuse. Warum r? Weil es eine Eigenschaft des Kreises ist, daß die Länge der Verbindungslinie zwischen einem beliebigen Kreispunkt und dem Kreismittel- punkt konstant ist, und dieses der Radius des Kreises ist.
Man erinnere sich an den Zirkel - der Mittelpunkt ist fest, und die Blei- stiftspitze stellt den Punkt dar. Der Abstand zwischen Kreismittelpunkt (Na- del) und Bleistiftspitze (Punkt) bleibt immer konstant.
Also, Pythagoras war: aý + bý = cý
Hier ist a = y, b = x und c = r, also:
yý + xý = rý
Umgeformt:
yý = rý - xý
Um jetzt von yý zu y zu kommen, muß man auf beiden Seiten die Wurzel ziehen.
Also gilt:
y = Wurzel von (rý - xý)
Jetzt hat man eine Methode gefunden, um einen 1/4 Kreis zu zeichnen - damit auch den gesamten. Rý muß nur einmal ausgerechnet werden, da der Radius sich ja nicht ändert. Xý jedoch muß man für jedes x der Schleife neu berechnen, ebenso die entstehende Wurzel.
Es gibt raffinierte Verfahren, um die Wurzel einer Zahl zu ziehen. Program- miert man diese selber, und benutzt man dabei nur ganze Zahlen, so hat man schon eine verdammt schnelle Kreisroutine.
Es geht aber noch schneller, und zwar mit dem Bresenham Algorithmus.
Grundideen des Bresenham Algorithmus ------------------------------------
Bresenham hat sich folgendes überlegt:
Hat man einen Punkt des Kreises (z.B. (0,y)), so muß auf einem Computerbild- schirm der nächste Punkt entweder den gleichen, oder einen um eins unter- schiedlichen y Wert haben. Folgende Zeichnung macht dieses ungefähr für ei- nen 1/4 Kreis deutlich:
*** ** * *
Bresenham geht jetzt Punkt zu Punkt hin und sagt, welcher Fehler ist denn jetzt größer? Wenn ich auf der aktuellen y Position bleibe, oder wenn ich einen niedriger gehe?
Das kann man ausrechnen:
y sei jetzt die Position auf dem Bildschirm, yr sei der tatsächliche y-Wert für diesen x-Wert. yr kann man ja aus x errechnen (z.B. mit Pythagoras), es gilt:
yr = Wurzel (rý - xý)
Man prüft jetzt, ob y oder y-1 naeher an yr liegt.
---------------------------------- [Einschub: Ausrechnen von Fehlern]
Wie vergleicht man, welche Zahlen näher zusammen liegen?
Nehmen wir ein einfaches Beispiel: Liegt 7 oder 4 näher an 5? Für Menschen ist das ganz klar: 4 - aber wie kommen wir darauf?
Die Zahl, womit wir vergleichen, ist 5. Jetzt ziehen wir einmal die eine Zahl von 5 ab, und einmal die andere, und betrachten dann die resultieren- den Beträge, also das Ergebnis ohne Vorzeichen:
5 - 7 = -2 5 - 4 = 1
Logisch: 1 ist kleiner als 2, also liegt 4 näher an 5 dran.
Man betrachtet bei dieser Methode den sogenannten Fehler den man macht, wenn man 4 bzw. 7 statt 5 nimmt. Ist der Fehler kleiner, so liegt die Zahl näher dran.
Das Problem sind die Vorzeichen: Aber wir können uns da was schönes aus der Mathematik zunutze machen: ist der Betrag von a größer als der Betrag von b, so ist auch aý größer als bý. Das ist eine mathematische Tatsache!! Nochmal:
Aus |a| < |b| folgt aý < bý
Also hier:
(5-7)ý = (-2)ý = 4 (5-4)ý = ( 1)ý = 1
Wie vorhin: Auch hier ist 1 ist kleiner als 4, also liegt 4 näher an 5.
[Ende des Einschubs] --------------------
yr war der tatsächliche y Wert.
Nach Pythagoras gilt:
yrý = rý - xý bzw. yr = Wurzel (rý - xý)
Wir betrachten jetzt zwei Fehler: Fehler1 ist, wenn wir bei der jetzigen y Position bleiben, und Fehler2 ist der Fehler, den man macht, wenn man den nächsten Punkt um einen Pixel niedriger zeichnet (y-1).
Verwendet man Quadrate, ist yr auch immer eine ganze Zahl. Das ist wichtig für die spätere Implementierung!!!
Fehler1 = yý . yrý bzw. yrý eingesetzt:
Fehler1 = yý - rý + xý
Für Fehler2 gilt:
Fehler2 = yrý - (y-1)ý
mit yrý eingesetzt:
Fehler2 = rý - xý - yý -+ 2y - 1
Wir ziehen hier umgekehrt ab, weil wir zum Vergleichen einen positiven Wert haben möchten. Es ist einfacher als später den Betrag zu ziehen, oder gar die Gleichungen zu quadrieren!!!
------------------------------ [Einschub: Binomische Formeln]
Für die Berechnung von (y-1)ý wurde eine binomische Formel benutzt.
Es gibt folgende binomische Formeln:
(a + b)ý = aý + 2ab + bý (a - b)ý = aý - 2ab - bý (a+b)(a-b) = aý - bý
Das ist einfach ein Sachverhalt, der gilt. Man kann ihn auswendig lernen. Nachvollziehen kann man das leicht an einem Beispiel. Will man z.B. 92 zum Quadrat im Kopf ausrechnen, so kann man folgendes machen:
(90 + 2)ý = 90ý + 2*90*2 + 2ý = 8100 + 360 + 4 = 8464
Stimmt hoffentlich, ich habe es nicht nachgerechnet!!!!
[Ende des Einschubs] --------------------
Wo waren wir?
Fehler1 = yý . yrý bzw. yrý eingesetzt:
Fehler1 = yý - rý + xý
Fuer Fehler2 gilt:
Fehler2 = yrý - (y-1)ý mit yrý eingesetzt:
Fehler2 = rý - xý - yý + 2y - 1
Ist Fehler1 kleiner als Fehler2, so bleibt man bei y, sonst geht man einen y Wert runter.
Diese beiden Fehler kann man auch zusammenfassen in einen Gesamtfehler. Dazu muß man wissen, daß man 2 Werte auch vergleichen kann, indem man sie vonein- ander abzieht. Kommt 0 raus, so sind sie gleich. Kommt ein größerer Wert als 0 raus, so ist der erste Fehler größer als der zweite. Kommt aber ein Wert kleiner als 0 raus, so ist der zweite Fehler größer als der erste.
Fehler = Fehler1 - Fehler2
Fehler ist jetzt der Gesamtfehler.
Ist Fehler < 0, so ist der zweite Fehler größer, das heißt wir machen einen größeren Fehler, wenn wir einen Wert runter gehen, also bleiben wir besser bei y.
Ist umgekehrt Fehler > 0, so sind wir besser beraten, wenn wir einen Wert runter gehen.
Für Fehler = 0 kann man tun was man will. Ich bleibe hier bei y.
Rechnen wir mal den Fehler aus:
Fehler = Fehler1 - Fehler2
Fehler = (yý - rý + xý) - (rý - xý - yý + 2y - 1)
also
Fehler = yý - rý + xý - rý + xý + yý - 2y + 1 <=> Fehler = 2yý - 2y + 2xý -2rý + 1
Wenn wir diese Formel in ein Programm implementieren, lassen sich schon ganz schöne Geschwindigkeiten erreichen, auf alle Fälle besser, als wenn die Wur- zel gezogen würde, wie schon mal oben besprochen! Unser Verfahren wird also immer besser!!
Es wird aber noch besser (versprochen!).
Gucken wir uns mal an, was für einen Wert der Fehler für x=0 annimmt. Es ist aber auch bekannt, daß bei x=0 der y Wert gleich dem Radius ist.
Nochmal: Bei x = 0 gilt:
y = r
Fehler = 2yý - 2y + 2xý -2rý + 1
mit y = r, x = 0 eingesetzt:
Fehler = 2rý - 2r + 0 - 2rý + 1 = -2r + 1
Also gilt für den Fehler bei x = 0:
Fehler = -2r + 1
Betrachten wir nochmal den Fehler, den wir für jedes x berechnen müssen. Ein ziemlich komplizierter Ausdruck:
Fehler = 2yý - 2y + 2xý -2rý + 1
Der Fehler besteht in Prinzip aus 3 Teilen:
* Einen konstanten Anteil (alle reine Zahlen und der Radius, der bleibt beim gesamten Kreis konstant)
* Einen Teil, der sich ändern könnte, wenn wir entscheiden den Wert zu verringern (alles, was mit y zusammenhängt)
* Einen Teil, der immer dazukommt, also alles was mit x zusammenhängt.
Ziel ist es, von x-Wert zu x-Wert nur noch die Änderungen des Fehlers zu be- rechnen, um ihn nicht jedesmal neu berechnen zu müssen. Ziel ist es irgend etwas zu finden, was so aus sieht:
NeuerFehler = AlterFehler + irgendwas
Es geht um dieses irgendwas.
Der konstante Anteil ist, wenn wir schon einen Fehler haben, schon drin, man braucht ihn also nie mehr aufzuaddieren.
Der Teil, der von y abhängig ist, der ändert sich nur, wenn das y verringert wird, sonst bleibt er ebenfalls konstant. Aber wie ändert er sich?
Alles was mit y im Fehler zu tun hat lautet:
2yý - 2y
Es gilt:
NeuerFehler = AlterFehler + irgendwas
NUR bezogen auf y gilt also:
NeuerFehler = AlterFehler + NeuerFehler - AlterFehler
Zur Erinnerung:
NeuerFehler = AlterFehler + irgendwas
ist unser Ziel.
Rechnet man das aus, so kommt man auf die Gleichung:
NeuerFehler = NeuerFehler
Betrachtet man die Gleichung aber genau, sieht man, daß dieses 'irgendwas' ja genau NeuerFehler - AlterFehler sein muss.
Der neue Fehler ist ja 2(y-1)ý - 2(y-1), jetzt nur bezogen auf alles, was mit y zu tun hat. Es muss also folgendes zu AlterFehler dazuaddiert werden, um auf NeuerFehler zu kommen:
NeuerFehler = AlterFehler + 2(y-1)ý - 2(y-1) - [2yý - 2y] <=> NeuerFehler = AlterFehler + 2(yý -2y +1) - 2y + 2 - 2yý + 2y <=> NeuerFehler = AlterFehler + 2yý - 4y + 2 -2y + 2 -2yý + 2y <=> NeuerFehler = AlterFehler - 4y + 4
Zum programmtechnischen: Etwas mit 4 zu multiplizieren kann man auch dadurch machen, daß man die Zahl um 2 Bits nach links shiftet.
Bleibt nur die Änderung, die jedesmal durchgeführt werden muss. Ziel ist es, genau wie eben ein 'irgendwas' zu finden, welches folgendes erfüllt:
NeuerFehler = AlterFehler + irgendwas
Es gilt:
NeuerFehler = AlterFehler + NeuerFehler - AlterFehler
Beim Fehler muß jedesmal 2xý berechnet werden. Bei x+1 ist der Fehler dann 2(x+1)ý, jetzt nur bezogen auf den x abhängigen Teil. Wie man unten sieht, heben sich die Quadrate nochmal schön auf!
Es gilt:
NeuerFehler = AlterFehler + 2(x+1)ý - 2xý = 2xý + 4x + 2 - 2xý = 4x + 2
Jetzt noch mal alles in Ruhe als Pascalprogramm...
Berechnung eines 1/8 Kreis nach Bresenham: ------------------------------------------
Ich schreibe den Algorithmus mal als Pseudo-Pascalcode auf:
VAR x, y, r, Fehler: Integer;
...
Fehler := -2*r + 1;
FOR x := 1 TO r div 2 DO BEGIN Plotpixel(x,y); IF Fehler > 0 THEN BEGIN y := y - 1; Fehler := Fehler - 4*y + 4; END; Fehler := Fehler + 4*x + 2; END;
Das ist es!! Mehr nicht!
Um jetzt einen vollen Kreis zu zeichnen, muss man statt der einen Koordina- te zusätzlich noch die 7 anderen einsetzen. Zur Erinnerung, alle 8 waren:
( +x, +y ) ( -x, +y ) ( -y, +x ) ( -y, -x ) ( -x, -y ) ( +x, -y ) ( +y, -x ) ( +y, +x )
Ich bin jetzt einfach immer von 0,0 ausgegangen. Um jetzt den Kreismittel- punkt woanders als bei (0,0) zu haben, muss man einfach zum x-Wert der Punk- te den x-Wert des Kreismittelpunkts addieren, und zum y Wert den y.Wert des Kreismittelpunkts.
Bemerkungen -----------
Wir haben eine Methode kennengelernt, die mit nur einem Shiftoperator (*4 ist das gleiche wie 2 mal nach links schieben) und Addition bzw. Subtraktion auskommt.
In der Wirklichkeit ist dieses nicht immer der Fall. Meistens muss man den y Wert noch mit einer Korrekturkonstante multiplizieren, um kein Ei (Ellipse) statt eines Kreises zu bekommen. Diese Korrekturkonstante nennt man Aspekt- ratio.
Diese Aspektratio kann man ausrechnen:
Ich mache dieses mal für 320x200; für 640x480, 800x600 oder 1024x768 braucht man dieses z.B. nicht, weil da die Aspektratio = 1 ist (kann man ausrechnen)
Um die Aspektratio auszurechnen, muß man wissen, daß fast alle Monitore und Fernsehgeräte im Verhältnis 4:3 gebaut sind, also das Verhältnis Breite zur Höhe muß 4:3 betragen. Dieses gilt nicht immer. In der Zeitungsindustrie werden oft Monitore verwendet, die ein Verhältnis 3:4 haben, damit man das gesamte DIN A4 Blatt besser sehen kann. Außerdem wird sich in den nächsten paar Jahren im Fernsehbereich die 16:9 Norm durchsetzen, vielleicht auch bald für Computermonitore.
Zurueck zur Berechnung. Man kann folgende Formel aufstellen:
Breite/Höhe = 4/3 = a * xPixel / yPixel
a ist dann die Aspektratio:
Es gilt dann:
a = 4*yPixel / (3*xPixel)
Für 320x200 gilt:
a = (4*200) / (3*320) a = 5/6
Um also statt einem 'Ei' einen richtigen Kreis zu bekommen, muß man für den Modus 320x200 seinen errechneten y-Wert mit 5/6 multiplizieren. Besser ist, erst mit 5 zu multiplizieren, und dann mit 6 zu teilen, als mit Fließkomma- zahlen zu rechnen. Mit y-Wert ist der reale y-Wert gemeint, und nicht die errechnete Variable y im Bresenham Kreisverfahren.
Das untenstehende Programm entspricht direkt dem oberen, nur mit ein paar Zusätzen: Es berücksichtigt die Aspektratio, einen anderen Kreismittelpunkt als 0,0 (Kreismittelpunkt wird durch die Koordinaten (xm,ym) angegeben), und es zeichnet einen vollständigen Kreis.
y1 und y2 geben die verschiedenen möglichen y-Werte an - also einmal x und einmal y. Schaut man sich z.B. diese beiden der 8 Punkte an, dann sieht man sofort, was ich meine:
( +x, +y ) ( +y, +x )
Berücksichtigt man die Aspektratio, so lauten die Koordinaten:
(+x, +y*5/6) (+y, +x*5/6)
Also muß einmal y und einmal x mit 5/6 multipliziert werden. Damit man nicht bei allen 8 Punkten immer wieder mit 5/6 multiplizieren muß, habe ich die beiden Variablen y1 und y2 eingeführt.
VAR xm,ym,r : Integer; Fehler : Integer; y1,y2 : Integer;
...
Fehler := -2*r + 1;
FOR x := 1 TO r div 2 DO BEGIN
y1 := (y * 5) div 6; y2 := (x * 5) div 6;
Plotpixel(xm+x,ym+y1); Plotpixel(xm-x,ym+y1); Plotpixel(xm-y,ym+y2); Plotpixel(xm-y,ym-y2); Plotpixel(xm-x,ym-y1); Plotpixel(xm+x,ym-y1); Plotpixel(xm+y,ym-y2); Plotpixel(xm+y,ym+y2);
IF Fehler > 0 THEN BEGIN y := y - 1; Fehler := Fehler - 4*y + 4; END; Fehler := Fehler + 4*x + 2; END;
Falls es wirklich auf Geschwindigkeit ankommt, so koennte man sogar eine Ta- belle für die verschiedenen Aspektratios anlegen.
Anwendungen für den Bresenham Kreisalgorithmus ----------------------------------------------
Den Algorithmus kann man verwenden um:
* Einen Kreis zu zeichnen
* Eine Ellipse zu zeichnen (hier absichtlich eine falsche Aspektratio einsetzen)
* Gefüllte Kreise (statt Punkte einfach Verbindungslinien zeichnen). Evtl. hilft es, vorher ein möglichst großes Quadrat (bzw. Rechteck) schon vor- zuzeichnen.
* Ein 'Kugel' zu zeichnen. Hierzu einfach von 0 bis r Kreise zeichnen, je- weils in einer anderen Farbabstufung.
* Einen Sinusscroller zu emulieren (einen positiven Halbkreis gefolgt von einem negativen, dann einen Positiven, etc...).
In einer Demo dürfte AFAIK niemand den Unterschied zu einer echten Si- nuskurve merken können (weil es im Prinzip eine ist). Um die 'Frequenz' zu ändern, einfach den x-Wert mit einem Wert multiplizieren (am besten als Bruch, so geht es meist schneller), um die 'Amplitude' zu ändern, einfach den realen y-Wert mit einem anderen Wert multiplizieren (im Prinzip also die Aspektratio erhöhen).
Auf den letzen Punkt hatte ich die Idee erst gerade vor ca. 5 Minuten. Viel- leicht ist das die Methode, die schon überall verwendet wird, und ich es erst jetzt begriffen habe! :-)
Bresenham Lines kann man nach einer ganz ähnlichen Methode zeichnen lassen, die Herleitungsmethode ist die gleiche. Vielleicht bespreche ich das Topic in einer zukünftigen Version dieser FAQ.
CRC (Prüfsummenbildung)
Topic noch zu vergeben.
CRC32 (Prüfsummenbildung)
Topic noch zu vergeben.
Huffman (Komprimierung)
Norman Rudolph 2:2410/235.2: Topic in Arbeit.