FloodFill

Diskussion zum Thema Programmierung unter DOS (Intel x86)
Antworten
Brueggi

FloodFill

Beitrag von Brueggi »

Da mein 4wege-Stack-Floodfill nicht richtig funktioniert und ich mit den ganzen C-Sources nicht viel anfangen kann... Kann mir jemand mal schritt für schritt erklären, wie man ein Scanline-Floodfill schreibt? Ich meine, ich brauche nicht unbedingt Code, sondern nur eine Art Ablauf-Plan. Ich denke mal, dass ein Scanline-floodfill das beste ist, um auch Patternfill anbieten zu können, denn mit dem 4wege-Floodfill geht das nicht wirklich...
Brueggi

Re: FloodFill

Beitrag von Brueggi »

Ich hab jetzt mal mit einem Flodfill-Scanline experimentiert. Das klappt schon besser und beachtet sogar jetzt die Flächen-Grenzen. Nur frag ich mich, wie die ganzen Programmierer das Stack-Problem lösen. Ich habe Platz für 5000 Koordinaten-Paare (=4 Bytes pro Eintrag = 20000 Bytes Stack). Nach 3-4 Scanlines ist der Stack bereits voll...

Ich habe es jetzt so gemacht, dass der Stack einfach immer und immer wieder gefüllt wird - wie eine Art Ringpuffer und dabei keine Rücksicht darauf genommen wird, wo der Lesezeiger gerade ist. Max. 60000 mal darf der Ring-Puffer vollgemacht werden. Jetzt wird die Test-Fläche schon weiter gefüllt - aber trotzdem reicht es nicht aus. Wie löst Ihr das Stack-Problem? Sollte ich nur noch - beispielsweise - 4. Punkt auf den Stack legen?

Ein weiteres PRoblem ist das füllen mit Mustern (im Mono-Modus 640x480x1 Bit): Hier kommt der Fill-Algo total durcheinander und bleibt in der Endlosschleife hängen (da er ständig die Linien drüber drunter prüft und dabei natürlich entsprechend wieder rückwärts wandert, wenn Patterns durchlässig sind).

Gibts hierfür noch ein paar Tips?
Brueggi

Re: FloodFill

Beitrag von Brueggi »

Im Netz habe ich mal geschaut - die Probleme haben wohl alle :-) Bei jedem reicht der Stack nicht. Ich werde mal probieren, nicht mehr jeden Punkt auf den Stack zu legen, sondern nur noch jeden 4. oder jeden 8. - Lustigerweise füllt die Routine - je nach Muster - immer nur nach oben oder nach unten :-)
Brueggi

Re: FloodFill

Beitrag von Brueggi »

Auch wenn das in einem Monolog ausartet... :-)

Ich hab jetzt die Fill-Routine geändert und nur noch jeden 8. Pixel auf den Fill-Stack gelegt. Die Demo-Fläche scheint jetzt zu klappen - leider noch nicht mit allen Patterns. Sobald ein Pattern "durchlässig" ist, hängt die routine in einer Endlos-Schleife :-( Anbei mal ein Test-Video (die Fillroutine im GOS-Videotreiber).

http://lulu423gina.funpic.de/fill2.avi

Das erste Pattern ist Farbe 0 (schwarz), dann folgt Pattern 2 (jeweils ein Punkt schwarz, dann weiß, also dithering), dann sollte Pattern 10 folgen (herz-Muster) - hier sieht man, wie nach wenigen Zeilen die Routine hängt... Aufgrund der Größe des Videos musste ich die Qualität herunterschrauben. Also nicht wundern :-)
Gebastelt hab ich das erstmal in Assembler (noch nicht optimiert) - aufgenommen am 486 SX 25.

Hat jemand eine Idee, wie man sowas lösen kann?
DOSferatu
DOS-Übermensch
Beiträge: 1220
Registriert: Di 25. Sep 2007, 12:05
Kontaktdaten:

Re: FloodFill

Beitrag von DOSferatu »

Ich habe schon öfter Floodfill-Routinen geschrieben. Ich benutze dazu nie den konventionellen Stack, sondern programmiere mir immer einen eigenen. Und ich mache es NICHT mit einer rekursiven selbstaufrufenden Routine. (Rücksprungadresse usw, das würde viel zuviel Speicher belegen)
Der Stack enthält bei mir keine Pixel-Koordinaten - denn man kann sich ja die Tatsache zunutze machen, daß die Punkte der zu füllenden Fläche nebeneinanderliegen.
Also speichere ich einen Punkt nur mit 2 Bit. (Ein Byte kann also 4 aufeinanderfolgende Punkte speichern.) Diese 2 Bit sind die Richtung, in der der Punkt zum nächsten Punkt gehen soll. (hoch,runter,links,rechts) Zu Anfang sind sie auf "hoch" gestellt (es ist eigentlich egal, welche Richtung die erste ist). Wenn ein Punkt "darüber" zu füllen ist, wird ein weiterer "Richtungspunkt" angelegt, wieder mit 00... wenn KEIN Punkt in der gerade angegebenen Richtung zu füllen ist, erhöht man die "Bit-Zahl" und geht in die entsprechende Richtung. Ist die Bit-Zahl = 11 (also dezimal 3), dann wird nicht mehr erhöht (weil dieser Punkt dann alle Richtungen getestet hat), sondern es wird "zurückgegangen" (d.h. im "Stack") zum vorhergehenden Doppelbit - und dieses erhöht.
Die Erklärung zum Muster-füllen:
Wenn man mit einem "Muster" füllen will, darf dieses natürlich nicht Elemente (Farben) des zu füllenden Areals enthalten, da sonst ja unmöglich festgestellt werden kann, was schon gefüllt ist und was nicht.
Ein Trick, dieses Problem zu umgehen, wäre eine "Doppelfüllung": Man legt korrespondierend zum Bild ein zweites virtuelles 1-Bit-Bild an, das man zu Anfang auf 0 setzt und immer, wenn an einer Position ein Pixel des Musters gesetzt wurde, setzt man ihn das Bit (den 1-Bit-Pixel an der gleichen Position im virtuellen Bild) auf 1. Beim Füllen testet man nun jeden Pixel doppelt: 1.) hat er die Farbe/Farben der zu füllenden Fläche? 2.) ist sein korrespondierendes Bit im virtuellen Bitmap-Bild =0? und NUR DANN wird gefüllt (siehe oben).

Erweiterungen zu meiner FloodFillRoutine (die wird in meinem selbstgebauten Malprogramm benutzt) sind:
- Füllen statt in 4 auch in 8 Richtungen (damit können dünne schräge Linien auch gefüllt werden - oder z.B. 1-Pixel-breite "Konturen").
- Erweiterung des Füllstacks durch Festplattenspeicher - der Füllstack wird, wenn er voll ist, auf Festplatte gespeichert und neu initialisiert. Ein Counter zählt die absolute "Stacktiefe" und ist größer als der "Stack" im Speicher. Immer, wenn beim "Züruckgehen" im Speicher-Stack auf 0 gegangen wird und die Stacktiefe noch nicht wieder 0 ist, wird der Stack von Platte geholt und wieder "oben" angefangen... ich bin sicher, es ist verständlich, was gemeint ist.
Auf diese Art können wahnsinnig große Bilder und komplizierte Formen gefüllt werden.
Die Größe der Fläche erfordert übrigens keinen großen Stack, eher kleine fitzelige Formen. Das "komplizierteste" Bild für ein Floodfill ist übrigens ein Bild, das in 1-Pixel breiten Schlangenlinien von oben nach unten, quasi im Zickzack geht (von oben nach unten, wenn das Bild breiter ist als hoch). "Kompliziert" deshalb, weil in diesem Fall der größtmögliche Stack gebraucht wird. Will sagen, wenn die gesamte Bildfläche z.B. 1024x768 ist, benötigt man mit dieser Füllroutine und mit 4-Richtungs-Füllen (2 bit pro Stackdatum) etwas mehr als 0,09375 MB, bzw 98304 Bytes.
Die Koordinaten braucht man also nicht immer wieder irgendwohin übergeben, sondern nur anhand der Bewegungsrichtungen ändern.

Ja, ich mache so einen Kram schon eine Weile, da denkt man sich so einiges aus.
Übrigens verwendet die Routine, die die Zufallslevels von Xpyderz baut, eine Modifikation meiner Floodfills - eine Labyrinthbau-Routine, die mit verschiedenen Parametern versehen, offene, geschlossene, leichte und schwere Levels bauen kann und die "allgemeine Form" in gewissen Grenzen bestimmen (lange oder kurze Wege, etc).

Vielleicht hilft ja dieser von mir hier vorgestellte Kram etwas. Wenn nicht - war es eben nur mal wieder eine Tippübung für mich.
Brueggi

Re: FloodFill

Beitrag von Brueggi »

Also rekursiv mach ich auch nicht - ich nehme auch einen eigenen Stack, der die Koordinaten eines Punktes aufnimmt. Dabei nutze ich den Bereich des Video-Treiber-Segmentes, der den Hintergrund für z. B. Pulldown-Menüs aufnimmt. Ich habe mir auch schon überlegt, das Bild quasi zu puffern und doppelt zu füllen. Aber da muss ich erstmal entsprechend RAM finden. Es ist jetzt schon seeeehhhrr knapp. Zumal ich ja 640*800 Punkte unterstütze, brauche ich da unbedingt ein komplettes 64K-Segment.

Ansonsten sind deine Ideen sehr hilfreich - ob ich das allerdings alles richtig verstehe und korrekt umsetzen kann, das wird sich herausstellen :-) Aber wie heißt es so schön: Ohne Fleiß kein Preis. Vielen Dank für deinen Beitrag!
Brueggi

Re: FloodFill

Beitrag von Brueggi »

So, der Tip mit dem 1-Bit-Bildschirm hat gefunzt :-) War ziemlich tricky das zu machen, da der konventionelle RAM schon bis zum Anschlag gefüllt war. Die Testfläche wird jetzt in jedem Muster gefüllt. Danke nochmals! :-)
Antworten