Saatkorn-Methode

Gegeben sei ein inneres Pixel.

Man unterscheidet zwei Nachbarschaftsbeziehungen

Je nachdem werden entweder vier oder acht rekursive Aufrufe gestartet. Wurde der Rand des Objektes mit einem Bresenham-Algorithmus gezeichnet, sollte man die Vierer-Methode verwenden.

GetPixel(x,y) liefert Farbe für entsprechendes Pixel zurück.

SeedFill() füllt solange wie ``unter'' dem Pixel nicht die Füllfarbe und nicht die Randfarbe gefunden wird.

 
SeedFill_4(
  int x,
  int y,
  int fill_col,
  int boundary_col
) {
  int current_col(GetPixel(x,y));

  if( current_col!=fill_col &&
      current_col!=boundary_col ) {
    SetPixel(x,y,fill_col);
    SeedFill_4(x+1,y,fill_col,boundary_col);
    SeedFill_4(x,y+1,fill_col,boundary_col);
    SeedFill_4(x-1,y,fill_col,boundary_col);
    SeedFill_4(x,y-1,fill_col,boundary_col);
  }
}

FloodFill() füllt solange wie ``unter'' dem Pixel die Startfarbe gefunden wird.

 
FloodFill_4(
  int x,
  int y,
  int fill_col,
  int start_col
) {
  int current_col(GetPixel(x,y));

  if( current_col==start_col ) {
    SetPixel(x,y,fill_col);
    FloodFill_4(x+1,y,fill_col,start_col);
    FloodFill_4(x,y+1,fill_col,start_col);
    FloodFill_4(x-1,y,fill_col,start_col);
    FloodFill_4(x,y-1,fill_col,start_col);
  }
}

Natürlich sollte FloodFill() nur aufgerufen werden, wenn start_col!=fill_col, da die Rekursion sonst nicht terminiert.

Die Anzahl der rekursiven Aufrufe ist recht hoch, deshalb folgende Verbesserungen:

• selbstverwaltete Kellerstruktur anstelle der rekursiven Aufrufe
• bestimmen von Zeilenabschnitten, die gesetzt werden sollen (Übung)

Statt einfach ein Pixel auf eine Füllfarbe zu setzen, kann man auch andere Operationen durchführen, z.B. den $(x,y)$-Wert eines zu setzenden Pixels erst dazu zu benutzen, in einer Textur oder einem Füllmuster den entsprechenden Farbwert zu suchen. Hierzu kommen wir im Abschnitt Texturen zurück. Wichtig ist jedoch, dass man beachtet, dass die Rekursion durch die richtigen Abbruchbedingungen (bei Texturen hat man ja keine einheitliche Füllfarbe mehr) terminiert wird.