Die Grafik-VDUDer Fill-AlgorithmusDas dickste Plus, das mit dem CPC 664 eingeführt wurde, ist aber sicher der schnelle Rekursion - Selbst-Aufruf einer Prozedur: Füll-AlgorithmusFüll-Algorithmus. CPC-464-Benutzer können da nur neidvoll zusehen. Bei der Erklärung der Rekursion (Kapitel Grundlagen: ProgrammstrukturenProgrammstrukturen) wurde ja schon ein voll funktionsfähiger Basic-Füll-Einzeiler vorgestellt, der nur leider an praktischen Grenzen scheitert. Der im CPC 664/6128 realisierte 'Füller' arbeitet auch ein wenig anders. Nicht rekursiv und er speichert nur 'Der Fill-Algorithmus: interessante Punkteinteressante Punkte'. Um das zu verstehen, muss man sich einmal Gedanken machen, wie so eine Ausmalroutine prinzipiell funktionieren muss. Die Routine bekommt eine Start-Koordinate übergeben, die in einer beliebig umgrenzten Fläche liegt. Aber es gibt rundherum eine Grenze. Man muss also Erklärung der Anschlussbelegung: Testtesten und unterscheiden können, ob ein Punkt 'gesetzt' oder 'nicht gesetzt' ist. Im ersten Fall begrenzt er die Ausmal-Routine, im zweiten Fall muss er gesetzt werden. Außerdem müssen auch die nur diagonal verbundenen Grenz-Punkte als 'dicht' angesehen werden. Der im CPC verwendete Linien-Algorithmus produziert Linien, die sehr oft nur diagonal verbundene Punkte enthält. Daraus ergibt sich die Forderung, dass man sich beim Pixel-Testen nur in den vier Grund-Richtungen, nicht aber diagonal bewegen darf. Füllen mittels IterationNehmen wir einmal an, die Routine würde ein Pixel auf einer bestimmten Position Erklärung der Anschlussbelegung: Testtesten und feststellen, dass es noch nicht gesetzt ist. Was muss sie dann tun? Zunächst einmal muss sie den Punkt einfärben. Dann muss sie aber auch die Nachbarpunkte Erklärung der Anschlussbelegung: Testtesten, ob diese auch nicht gesetzt sind. Davon gibt es vier Stück. Da man die nicht gleichzeitig untersuchen kann, muss man Die Grafik-VDU: Die Koordinatendie Koordinaten dieser Punkte speichern. Oder man löst das Problem rekursiv, wie im Basic-Einzeiler. Aber auch jetzt ist der Speicherbedarf enorm: Ein Punkt hat vier Nachbarn, die zusammen haben 16 (dass dadurch einige mehrfach abgedeckt werden, ist einem Algorithmus nur schwer klar zu machen), die haben 64 potentielle Nachbarn, dann 256, 1024, 4096, etc.. Das greift rasend um sich, bis es endlich durch die Umrandung gestoppt wird. Was passiert, wenn der getestete Punkt gesetzt ist? Dann wird die Rekursion oder das explodierende Abspeichern von 'Weitersuch-Stellen' einfach abgebrochen und 'genau nichts' getan. Das folgende Bild erstellt in Zeile 100 bis 250 eine Demo-Grafik und ruft das Grundlagen: UnterprogrammeUnterprogramm ab Zeile 260 auf, um die Fläche auszufüllen. 100 Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 2: 290 IF z1=z2 THEN RETURN ' Erklärung der Anschlussbelegung: TestTest auf Ende 300 Die verwendeten Abkürzungen bedeuten: x:x=Die verwendeten Abkürzungen bedeuten: x:x(z1):y=y(z1):z1=(z1+1)Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 2: Zum Speichern der Weitersuch-Stellen wird ein Ringspeicher benutzt, der in Zeile 270 definiert und in Zeile 280 mit dem ersten (Start-) Wert gefüllt wird. Normalerweise benutzt man einen Stack. Der hat aber den Nachteil, dass 'Karteileichen', also vielfach eingetragene und anderweitig bereits bearbeitete Punkte fast beliebig lange in seinen Tiefen schlummern können, bis der Stack ganz zum Schluss geleert wird. Solchermassen realisierte Paint-Routinen erkennt man daran, dass sie beim Ausmalen regelmäßig Pausen einlegen, weil der Speicher voll ist, um alle Karteileichen zu entfernen. Bei der Queue kommen aber regelmäßig alle Einträge dran. Dadurch werden ganz automatisch tote Punkte entfernt. interessante PunkteDer CPC 664/6128-Füller arbeitet aber noch ein wenig anders: Er speichert nur 'Der Fill-Algorithmus: interessante Punkteinteressante' Punkte. Was unterscheidet einen 'interessanten' von einem 'unwichtigen' Punkt? Dazu die folgenden Bilder. In den 3*3-Feldern ist jeweils der mittlere Punkt gesetzt Datenbreite: Wordsworden: 1) 2) 3) 4) +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | # | # | # | | # | | | | # | | # | | # | # | # | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | # | # | # | | # | # | | | | # | | | # | # | | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | | # | | | # | | | | # | | # | | # | | | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ Der Algorithmus soll so funktionieren, dass nicht der gerade gesetzte Punkt gespeichert wird, sondern die vier umliegenden, noch zu testenden Punkte. Welche Punkte müssen in Bild 1) in den Speicher aufgenommen werden? Keiner, weil ja alle Nachbarn bereits gesetzt sind. In Bild 2) kommen die Punkte (o)LOW KERNEL JUMPBLOCK: 000B: LOW KL LOW PCHL Unter diesem Gesichtspunkt betrachtet, müssen in 3) aber alle vier Nachbar-Punkte gespeichert werden, weil alle Eckpunkte bereits gesetzt sind, und die Nachbarn voneinander trennen. In Beispiel 4) muss wieder nur ein Punkt weiter betrachtet werden, weil (r) und (u) über den Eckpunkt verbunden sind. Füllen mit Iteration und interessanten PunktenDas folgende Programm macht dabei noch zwei weitere Vereinfachungen. Zum Einen werden nur Verzweigungen in die Tabelle aufgenommen. Also nur, wenn zwei Pfade weiter verfolgt werden müssen, wird der eine zwischengespeichert. Mit dem anderen wird direkt weitergemacht. Zum Anderen wird die aktuelle Zugrichtung festgehalten. Dabei dreht der Algorithmus wenn möglich nach jedem Punkt einmal nach links. Dadurch müssen nicht mehr alle Nachbarpunkte untersucht werden: +---+---+---+ In diesem Beispiel zog der Algorithmus von (u) in die Mitte (und | ? | ? | ? | drehte die Zugrichtung nach links). Wenn man jetzt von der Mitte +---+---+---+ aus die Nachbarpunkte untersucht, weiß man sicher, dass (u) | ? | # | ? | gesetzt ist. Dadurch müssen (ul), (u) und (ur) nicht mehr +---+---+---+ untersucht werden. | * | # | * | +---+---+---+ 260 DIM Die verwendeten Abkürzungen bedeuten: x:x(200),y(200),dx(200),dy(200) 270 dx=2:dy=0:zg=0 280 IF Erklärung der Anschlussbelegung: TestTEST(Die verwendeten Abkürzungen bedeuten: x:x,y) THEN 450 290 PLOT Die verwendeten Abkürzungen bedeuten: x:x,y:z=dy:dy=dx:dx=-z ' Plot und drehe nach links. 300 IF Erklärung der Anschlussbelegung: TestTEST(Die verwendeten Abkürzungen bedeuten: x:x+dx,y+dy)=0 THEN 390 ' Punkt frei? dann nach links weitermachen. 310 z=dx:dx=dy:dy=-z ' sonst wieder nach rechts drehen. 320 IF Erklärung der Anschlussbelegung: TestTEST(Die verwendeten Abkürzungen bedeuten: x:x+dx,y+dy)=0 THEN 360 ' Punkt frei? dann geradeaus weitermachen. 330 z=dx:dx=dy:dy=-z ' sonst nochmal nach rechts drehen. 340 Die verwendeten Abkürzungen bedeuten: x:x=Die verwendeten Abkürzungen bedeuten: x:x+dx:y=y+dy ' vorwärts gehen (insgesamt nach rechts) 350 GOTO 280 ' und weiter. Verzweigungen nicht möglich! 355 ' Punkt rechts auf Verzweigung Erklärung der Anschlussbelegung: Testtesten, nach vorne schreiten und weiter: 360 IF Erklärung der Anschlussbelegung: TestTEST(Die verwendeten Abkürzungen bedeuten: x:x+dy,y-dx)=0 ' Erklärung der Anschlussbelegung: TestTest auf Verzweigung: THEN IF TESTR(dx,dy) ' rechts frei aber rechts vorne gesetzt? THEN GOSUB 380 ' Wenn ja, eintragen 370 Die verwendeten Abkürzungen bedeuten: x:x=Die verwendeten Abkürzungen bedeuten: x:x+dx:y=y+dy:GOTO 290 ' Schritt nach vorne und weiter 380 Einleitung: Sound Zwar entspricht dieses Programm auch noch nicht dem CPC-Algorithmus, es zeigt aber ein Beispiel, wo nur noch Verzweigungs-Punkte ('interesting points' im Amstrad-Jargon) in die Tabelle eingetragen werden. Die Füll-Routine ist so gestaltet, dass man jedes PUSH und POP auf dem Verzweigungs-Stapel mitbekommt: PUSH = hoher Ton, POP = tiefer Ton. Die Routine setzt einen Punkt, dreht sich nach links und testet, ob sie in dieser Richtung weiter machen kann. Wenn nicht, dreht sie wieder zurück nach rechts (und zeigt so wieder in die ursprüngliche Richtung), checkt diese Richtung ab und dreht sogar eventuell noch einmal nach rechts. Im letzten Fall kann keine Verzweigung vorliegen. Von hinten kommt sie ja, links und vorne sind dicht (weshalb sie ja überhaupt nur bis rechts drehen musste), allenfalls nach rechts kann es noch weitergehen. Geht die Routine geradeaus, muss nur nach rechts auf eine Verzweigung getestet werden, nach links ist der Weg versperrt (sonst würde sie ja da weiter machen). Eine Verzweigung liegt vor, wenn es nach rechts weitergeht, die Verbindung nach vorne aber durch ein gesetztes Pixel rechts vorne unterbrochen ist. Ist aber schon der Weg nach links frei, so müssen erst noch die Verzweigungen nach vorne und nach rechts überprüft werden. Vektor-DrehungZum Verständnis der Routine ist noch die Kodierung der 'Richtung' zu erklären. Diese setzt sich aus dx und dy zusammen. Einer der beiden Werte ist Real: NullNull, der andere kann den Wert -2 oder +2 haben. Damit sind die vier Grund-Richtungen darstellbar: dx=0,dy=+2
/\
||
dx=-2,dy=0 <--++--> dx=+2:dy=0
||
\/
dx=0,dy=-2
Zum Drehen dieses Richtungsvektors in 90-Grad-Schritten werden folgende Formeln benutzt: vorwärts: dy=+dy und dx=+dx
nach links: dy=+dx und dx=-dy (in Einleitung: BASIC
Entsprechend kann man, ohne die 'Richtung' zu ändern, mit den folgenden Kombinationen in alle vier Richtungen Erklärung der Anschlussbelegung: Testtesten: vorwärts: Erklärung der Anschlussbelegung: TestTEST (Die verwendeten Abkürzungen bedeuten: x:x+dx,y+dy) nach links: Erklärung der Anschlussbelegung: TestTEST (x-dy,y+dx) nach rechts: Erklärung der Anschlussbelegung: TestTEST (Die verwendeten Abkürzungen bedeuten: x:x+dy,y-dx) rückwärts: Erklärung der Anschlussbelegung: TestTEST (x-dx,y-dy) Diese Angaben sind ein Spezialfall für eine Formel, mit der man Vektoren drehen kann. Normalerweise würde man einen Vektor der Länge 'l' wie folgt mit Sinus und Cosinus in eine bestimmte Richtung 'w' drehen, wobei die Null-Richtung nach oben zeigen soll (wie in Einleitung: LOGO dx = l*sin(w) dy = l*cos(w) um ihn um den Winkel dw zu drehen, würde man dann wohl so vorgehen: dx = l*sin(w+dw) dy = l*cos(w+dw) Speziell bei Anwendungen, bei denen der Vektor aber immer um einen konstanten Betrag gedreht wird (Bei Rekursion - Selbst-Aufruf einer Prozedur: Füll-AlgorithmusFüll-Algorithmus immer um 90 Grad, oder beim Zeichnen von Kreise zum Beispiel!), ist es sinnvoll, auf folgende trigonometrische Gleichungen zurückzugreifen: d.Die verwendeten Abkürzungen bedeuten: x:x = dx*cos(dw) - dy*sin(dw)
d.y = dy*cos(dw) + dx*sin(dw)
Wobei d.Die verwendeten Abkürzungen bedeuten: x:x und d.y die Komponenten des neuen Vektors sind, dx und dy die des alten. Für diese Formel braucht man dann SIN(dw) und COS(dw) nur noch einmal zu berechnen bzw. bei 90 Grad sind SIN(90)=1 und COS(90)=0 |