Füll-Werkzeug für Pixelprogramm

[milos]

Hallo,

ich bin dabei für meine 8Bit Game Engine einen kleinen Bildereditor zu basteln mit extras für die Engine. Ich würde nun gerne einige Tools hinzufügen und da habe ich ein Problem beim Füll-Werkzeug. Ich weiss nicht wie ich das Lösen kann.

Ich habe an eine Schleife gedacht die dann wie eine Spirale alles ausfäbrt was er soll, aber beim aufzeichnen hatte ich dann keinen Plan wie ich das wirklich Lösen soll xD

Hoffe einer kann mir helfen ^^

MfG

Edit: Ach ja, hab das Bild in einer 2-Dimensionalen Liste ^^

[BUG]

Floodfill ist vermutlich der Algorithmus, den du suchst.
EDIT: Der englische Wiki-Eintrag ist etwas umfangreicher.

Zitat von milos:

Edit: Ach ja, hab das Bild in einer 2-Dimensionalen Liste ^^

Warum? Das klingt ehrlich gesagt nicht so effizient.

[Popov]

Ich hab mich vor Jahren mit dem Thema beschäftigt wie ich ein Labyrinth berechnen soll. Ich hab mich Wochen damit auseinandergesetzt (ohne fremde Literatur zu Hilfe zu ziehen). Die Lösung war letztendlich simpel und nur paar Zeilen lang. Ich hab mir einen Stack programmiert. Jedes Mal wenn sich die Wege trennten, habe ich die Position auf Stapel gelegt. Ging es irgendwann nicht mehr weiter, nahm ich die letzte Position vom Stapel und machte da weiter. So simpel das Vorgehen war, zuletzt war jede Ecke erfasst und alles war verbunden.

Vorausgesetzt du meinst mit Fill das Gleiche wie ich, sollte das Prinzip ähnlich sein. Jedes mal wenn es zwei Möglichkeiten gibt, Position merken.

[Medium]

Was ziemlich identlich mit dem klassischen FloodFill Algo ist, nur statt rekursiv iterativ mit einem eigenen Stack statt des impliziten Stacks

[Mavarik]

Abgesehen davon, das Du sicherlich nicht einen Stackeintrag pro Pixel machen wirst.
Also immer erst ganze Rasterzeilen füllen.

Mavarik

[Der schöne Günther]

Wie soll das gehen?

Angenommen du fängst am roten Pixel an zu füllen. Wie willst du da "zeilenweise" alles ausfüllen?

[Mavarik]

Zitat von Der schöne Günther:

Wie soll das gehen?

Angenommen du fängst am roten Pixel an zu füllen. Wie willst du da "zeilenweise" alles ausfüllen?

OK! Ein Fill mit Get-/ Setpixel[X,Y] ist viel zu langsam.

Also gehst Du erstmal per Scanline ran. Farbe holen mit Abs(Hintergrund - Diff). Das machst Du horizontal nach links und rechts.
Dann mit einem netten Move aus Deinem Farbrecord/Zeilenspeicher diese Rasterzeile setzen. Rand links und rechts merken. Für Randfill.
Dann entlang der Linie suchen +1/-1 (Y) wenn zu füllen hierfür einen neuen "Stack".

"Im groben". Sorry letzter Fill war noch in Z80 ASM, daher ein bisschen länger her.

Mavarik

[Namenloser]

Zitat von Der schöne Günther:

Wie soll das gehen?

Angenommen du fängst am roten Pixel an zu füllen. Wie willst du da "zeilenweise" alles ausfüllen?

Man muss sich ja nicht jedes einzelne Pixel merken.

Man füllt eine Zeile von links nach rechts, und gleichzeitig prüft man die Zeilen darüber und darunter. Für jeden gefundenen „Streifen“ legt man die Anfangsposition auf den Stack.

Anschließend wiederholt man das ganze für jeden Eintrag auf dem Stack, so lange, bis nichts neues mehr gefunden wird.

[Medium]

Zeilenweise "bulk"-füllen geht leider nur, wenn ein paar Bedingungen erfüllt oder genauere Umstände bekannt sind. Für den allgemeinen Fall ist rekursives Füllen nach wie vor aktuell bei Bitmaps, insbesondere weil es so einfach auch komplizierte Formen erledigen kann. (Mit Löchern und so Schweinerein z.B.)

[Furtbichler]

Die Idee vom FloodFill (aus dem Gedächtnis, Pseudocode):

Delphi-Quellcode:

procedure FloodFill (Bitmap,BackgroundColor,FillColor, X,Y)
begin
  if Bitmap.Inside(x,y) and Bitmap[x,y]=BackgroundColor then begin
    Bitmap[x,y] = FillColor;
    FloodFill(Bitmap, Backgroundcolor, FillColor, x-1 ,y);
    FloodFill(Bitmap, Backgroundcolor, FillColor, x+1 ,y);
    FloodFill(Bitmap, Backgroundcolor, FillColor, x ,y-1);
    FloodFill(Bitmap, Backgroundcolor, FillColor, x ,y+1);
 end;
end

Es ist so mit das ineffizienteste, was man machen kann, weswegen es die triviale Optimierung gibt, am Punkt (x,y) iterativ die ganze horizontale Linie nach links und nach rechts zu laufen, solange der Punkt in der Hintergrundfarbe ist. Dann wird FloodFill für den Punkte darüber und darunter aufgerufen (so ähnlich jedenfalls).

Wenn Du die Kanten des geschlossenen Polygons als Vektorliste hast, kannst Du nocht ausrechnen, welche Fläche 'innen' ist.

Wenn deine 8-Bit Grafiken aber nicht zu groß sind, reicht vermutlich der erste triviale Ansatz.