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:

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:

Zitat von Der schöne Günther (Beitrag 1246494)

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:

Zitat von Der schöne Günther (Beitrag 1246494)

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.

[Medium]

Da es hier ja um einen Bildeditor geht, nicht um Animationen bei denen jedes Frame etwas neu gefüllt werden muss, wird der triviale Ansatz locker reichen. Man sollte nur überlegen, ob man nicht lieber mit Scanline statt Pixels[] da dran geht (vorausgesetzt man arbeitet mit einem TBitmap, was hier glaube ich nichtmals der Fall ist).
Ohne die Zeilen-Optimierung muss man ggf. nur aufpassen, dass man ab gewissen Bildgrößen keinen Stacküberlauf bekommt. Da ginge im Zweifel als Lösung auch noch die iterative Variante mit selbst verwaltetem Stapel.

[Sir Rufo]

Wie wäre es denn mit dieser Funktion?

Delphi-Quellcode:

procedure FloodFill( Canvas : TCanvas; x, y : Integer; NewColor : TColor );
var
  LCurrentColor : TColor;
begin
  Canvas.Brush.Color := NewColor;
  Canvas.Brush.Style := bsSolid;
  LCurrentColor := Canvas.Pixels[x, y];
  Canvas.FloodFill( x, y, LCurrentColor, fsSurface );
end;

...
FloodFill( MyBitmap.Canvas, 23, 54, clRed );
...

TCanvas.FloodFill

[Bjoerk]

Die Rekursion kann man vergessen (bringt regelmäßig Stackoverflow).

BTW, wie würde denn ein Algorithmus für fsBorder aussehen? :gruebel:

fsSurface ist ja dieser:

Delphi-Quellcode:

procedure TFloodFill.FloodFill4(X, Y: integer);
var
  P: TPoint;
  Stack: TPointStack;
begin
  Stack := TPointStack.Create;
  try
    Stack.Push(Point(X, Y));
    while not Stack.Empty do
    begin
      P := Stack.Pop;
      if IsCurrentColor(P.X, P.Y) then // OldColor;
      begin
        FPixels[P.X, P.Y] := FBrushColor; // NewColor;
        Stack.Push(Point(P.X, P.Y + 1));
        Stack.Push(Point(P.X, P.Y - 1));
        Stack.Push(Point(P.X + 1, P.Y));
        Stack.Push(Point(P.X - 1, P.Y));
      end;
    end;
  finally
    Stack.Free;
  end;
end;

[Blup]

Gibt viele nette Sachen im Internet zu dem Thema mit Quellcode und Erklärung:
QuickFill-An-efficient-flood-fill-algorithm

[Medium]

Zitat:

Zitat von Bjoerk (Beitrag 1246602)

Die Rekursion kann man vergessen (bringt regelmäßig Stackoverflow).

So pauschal stimmt das einfach nicht. Fläche klein genug oder Stack groß genug, und schon ist alles gut. (Ja, mit einem eigenen Stack ist man fast immer besser beraten, aber dennoch ist die Aussage faktisch falsch.)

Zitat:

BTW, wie würde denn ein Algorithmus für fsBorder aussehen? :gruebel:

Ich vermute du meinst die Unterscheidung zwischen "fülle diese einfarbige Fläche" und "fülle alles was von einem Rand mit Farbe X umgeben ist". Dann wäre "fsBorder":

Delphi-Quellcode:

procedure TFloodFill.FloodFill4(X, Y: integer);
var
  P: TPoint;
  Stack: TPointStack;
begin
  Stack := TPointStack.Create;
  try
    Stack.Push(Point(X, Y));
    while not Stack.Empty do
    begin
      P := Stack.Pop;
      if not IsBorderColor(P.X, P.Y) then
      begin
        FPixels[P.X, P.Y] := FBrushColor;
        Stack.Push(Point(P.X, P.Y + 1));
        Stack.Push(Point(P.X, P.Y - 1));
        Stack.Push(Point(P.X + 1, P.Y));
        Stack.Push(Point(P.X - 1, P.Y));
      end;
    end;
  finally
    Stack.Free;
  end;
end;

[Popov]

Ich hab gestern meinen alten Labyrinth Code ausgepackt und die Entstehung visualisiert, da ich selbst sehen wollte was da vor sich geht. Es ist ja nicht das Fill Problem, aber ich denke es ist im Grunde ein ähnliches Problem, da sich auch bei Fill die Wege oft trennen. Dabei habe ich auch den Stack visualisiert (rote Punkte), und war letztendlich selbst überrascht, wie viele Werte es dann doch sind. Ist aber auch richtig, denn bei dem Drang nach vorne wird immer dann eine Position auf Stack gelegt, wenn es zu dem Zeitpunkt mehr als eine Möglichkeit gab. Einiges erledigt sich im Laufe der weiteren Berechnung, aber jede Punkt wird noch mal besucht und kontrolliert.

Das Beispiel zeigt eine verzögerte Berechnung eines Labyrinths und wo überall und wie viele Werte auf Stack gelegt wurde. Interessant zu sehen, falls man den Stack bei der Arbeit zusehen möchte.

[Bjoerk]

Ok. Logo. Thanx @ Medium. Bin allerdings schon der Auffassung, daß das hier der Klassiker für einen Stack ist? Hatte gestern Tests mit 200 x 200 Pixel Fläche durchgeführt. Kam bei jedem 3. Durchlauf ein Stackoverflow? Den Stack hochstellen hab ich noch nie gemacht?

[Furtbichler]

Zitat:

Zitat von Bjoerk (Beitrag 1246633)

Ok. Logo. Thanx @ Medium. Bin allerdings schon der Auffassung, daß das hier der Klassiker für einen Stack ist? Hatte gestern Tests mit 200 x 200 Pixel Fläche durchgeführt. Kam bei jedem 3. Durchlauf ein Stackoverflow? Den Stack hochstellen hab ich noch nie gemacht?

Dieses Schwachsinnsfüllen macht man ja auch nicht mit 200x200 pixeln, sondern mit so 10x10 und in der Schule/Uni um mal was über Stacks und Rekursion zu lernen. :shock: