Universelle Füll-Verfahren

Universelle Füllverfahren stützen sich auf die Nachbarschaft eines Pixels. Abbildung 4.1 zeigt zwei Varianten.

Nachbarschaften bei universellen Füllverfahren

Nachbarn zu $\bullet$ im 4-way-stepping

Nachbarn zu $\bullet$ im 8-way-stepping

Ausgehend vom Startpunkt ($x, y$) werden so lange die 4-way-stepping-Nachbarn gefärbt, bis die Umgrenzung erreicht ist.

Vorteil:

beliebige Umrandung möglich

Nachteil:

hoher Rechen- und Speicherbedarf

Obacht:

Gebiete, die nur durch 8-way-stepping erreicht werden können, werden beim Füllen mit 4-way-stepping ``vergessen'', wird hingegen die Nachbarschaft über 8-way-stepping definiert, so ``läuft die Farbe aus''.

Bild 4.1 zeigt beide Effekte.

Probleme bei universellen Füllverfahren

Unerreichtes Gebiet beim 4-way-stepping

Farbauslauf beim 8-way-stepping

Benötigt werden

/** Liefert true, wenn Pixel (x,y) die Vordergrundfarbe hat. */
public boolean getPixel(int x, int y)

und

/** Liefert true, wenn Pixel (x,y) innerhalb des Bildbereichs */
public boolean rangeOk(int x, int y)

/** fuellt eine durch Vordergrundfarbe umrandete Flaeche */
public void boundaryFill(int x, int y, CGCanvas cgc) {

  if (cgc.rangeOk(x,y) &&                        // falls Pixel im Bild
      !cgc.getPixel(x,y)) {                      // und bisher nicht gesetzt
    cgc.setPixel(x,y);                           // setze Vordergrundfarbe

    boundary_fill(x+1, y  , cgc);                // rekursive Aufrufe
    boundary_fill(x,   y+1, cgc);                // nach Schema des 
    boundary_fill(x-1, y  , cgc);                // 4-Way-Stepping
    boundary_fill(x,   y-1, cgc);
  }
}

/** leert eine durch Vordergrundfarbe definierten Flaeche */

public void boundaryEmpty(int x, int y, CGCanvas cgc) { // Saatpixel (x,y)

  if(cgc.rangeOk(x, y) &&                        // falls Pixel im Bild und
     cgc.getPixel(x, y)) {                       // in Vordergrundfarbe

    cgc.del_pixel(x, y);                         // setze Hintergrundfarbe

    boundaryEmpty(x+1, y  , cgc);                // loesche Nachbarpunkte
    boundaryEmpty(x+1, y+1, cgc);                // nach Schema des
    boundaryEmpty(x,   y+1, cgc);                // 8-Way-Stepping
    boundaryEmpty(x-1, y+1, cgc);
    boundaryEmpty(x-1, y  , cgc);
    boundaryEmpty(x-1, y-1, cgc);
    boundaryEmpty(x,   y-1, cgc);
    boundaryEmpty(x+1, y-1, cgc);
  }
}

Der Nachteil der sehr ineffizienten Methode boundaryFill liegt darin, daß für jedes Pixel innerhalb der Begrenzungskurve(n) (mit Ausnahme der Randpixel des inneren Gebiets) der Algorithmus viermal aufgerufen wird. Dadurch werden die Pixel mehrfach auf dem Stapel abgelegt.

Eine Beschleunigung des Verfahrens läßt sich dadurch erreichen, daß auf dem Stapel jeweils Repräsentanten für noch zu füllende Zeilen abgelegt werden, d.h. nach dem Einfärben einer kompletten horizontalen Linie werden von den unmittelbar angrenzenden Zeilen solche Punkte auf den Stapel gelegt, die noch nicht gefüllt worden sind und die unmittelbar links von einer Begrenzung liegen.

Abbildung 4.3: Beschleunigtes universelles Füllen ($\odot$: Saatpixel, $\circ$: Pixel in Hintergundfarbe, $\bullet$: Randpixel, $\otimes$: vom Algorithmus gesetztes Pixel).

/** fuelle durch Vordergrundfarbe umrandete Fl"ache linienweise */
private void fillRowByRow(int x, int y, CGCanvas cgc) {
  int lg;                                      // nicht gesetzte Pixel ganz
  int rg;                                      // links/rechts in dieser Z.
  Punkt hilf;                                  // Hilfpunkt
  int px = x;                                  // lokale Kopie

  while(!cgc.getPixel(x, y)) {                 // Solange Pixel ungesetzt
    cgc.setPixel(x, y);                        // Pixel setzen
    x--;                                       // naechstes Pixel links
  }
  lg = x+1;                                    // 1 zu weit gelaufen

  x = px + 1;                                  // da (px,y) schon gesetzt

  while(!cgc.getPixel(x, y)) {                 // Solange Pixel ungesetzt
    cgc.setPixel(x, y);                        // Pixel merken und setzen
    x++;                                       // naechstes Pixel rechts
  }
  rg = x-1;                                    // 1 zu weit gelaufen

  for(int pos = rg; pos >= lg; pos--) {        // von rechts nach links
    if(!cgc.getPixel(pos, y-1) &&              // Pixel in Reihe ueber 
                                               // dieser nicht gesetzt und
       cgc.getPixel(pos+1, y-1)) {             // dessen rechter Nachbar
                                               // ist gesetzt

      fillRowByRow(pos,y-1, cgc);              // Repraesentant! Neuaufruf
    }
    if(!cgc.getPixel(pos, y+1)) &&             // Pixel in Reihe unter 
                                               // dieser nicht gesetzt:
       cgc.getPixel(pos+1, y+1)) {             // dessen rechter Nachbar
                                               // ist gesetzt
      fillRowByRow(pos,y+1, cgc);              // Repraesentant! Neuaufruf
    }
  }
}