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

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

und

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

/** 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).

private void fillRowByRow(int x, int y,        // beginnend bei (x,y)
                          CGCanvas cgc) {      // fuelle eine durch die Vorder- 
                                               // grundfarbe definierte Flaeche 
                                               // linienweise

  int lg;                                      // linker Rand 
  int rg;                                      // rechter Rand 
  int px = x;                                  // Startpunkt 

  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 setzen
    x++;                                       // naechstes Pixel rechts
  }
  rg = x-1;                                    // 1 zu weit gelaufen

  for(x = rg; x >= lg; x--) {                  // von rechts nach links
  
    if(!cgc.getPixel(x, y-1)                   // falls Pixel drueber
                                               // nicht gesetzt: 
      fillRowByRow(x, y-1, cgc);               // Repraesentant! Neuaufruf
    
    if(!cgc.getPixel(x, y+1))                  // falls Pixel drunter 
                                               // nicht gesetzt:
      fillRowByRow(x, y+1, cgc);              // Repraesentant! Neuaufruf
  }
}