Füll-Werkzeug für Pixelprogramm

[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.

[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?

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;

[Medium]

Zitat von Bjoerk:

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?

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;

[Blup]

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