In der Computergrafik sind Objekte, die durch Linien und Punkte abgegrenzt sind selten. Vielmehr bekommen die Flächen eine Farbe oder ein Überzug von einer Textur. Ein ausgefülltes Objekt kann durch zwei Techniken entstehen. Zunächst einmal kann es sofort so konstruiert werden, dass es gefüllt erscheint, beispielsweise ergeben viele gleichförmige Linien ein Rechteck. Aber Objekte können nachträglich gefüllt werden. Dazu sind Begrenzungen nötig. Ein einfacher Algorithmus, der sich auf die Informationen des Bildschirmspeichers verlässt ist Seed-Fill. Die Idee von Seed-Fill ist einfach: Wir starten bei einem bekannten Punkt — dem Seed (zu deutsch Korn) — und geben dem Nachbarpixel die gleiche Füllfarbe, wenn dieser nicht die Begrenzungsfarbe besitzt. Der Algorithmus ist schnell rekursiv definiert. Wenn wir auf den Bildschirmspeicher zugreifen, so umschreiben wir dies mit einem Zugriff auf das Feld pixelArray. Und boundaryValue bezeichnet die begrenzende Farbe und fillValue die zu füllende Farbe:
void seedFill( int x, int y )
{
if ( ( pixelArray[x,y] != boundaryValue ) && ( pixelArray[x,y] != fillValue ) ) {
setPixel( x, y, fillValue );
seedFill( x+1, y );
seedFill( x-1, y);
seedFill( x+1, y+1 );
seedFill( x-1, y-1 );
}
}
Die rekursive Implementierung krankt an dem Problem, dass der interne Stack sehr schnell ansteigt. Auch besitzt diese Implementierung den Nachteil, dass für jeden zu setzenden Punkt immer der Bildschirmspeicher ausgelesen wird und mehrere gleiche Punkte auf den Stack kommen und zurückgewiesen werden.
Eine mögliche Verbesserung erhalten wir dadurch, dass wir die direkten Rekursion eliminieren. Dadurch wird dieser Algorithmus aber nicht schneller, da das setzen eines Pixels vier Stack-Operationen nach sich zieht. Außerdem ist eine Implementierung wie die folgende schon deswegen nicht schneller, da bei der Stack-Implementierung der Objekt-Overhead mit sich gezogen wird. Daher dient folgender Algorithmus lediglich zur Anschauung, wie Flood-Fill mit einem Stack umgesetzt werden kann.
void seedFill( int xSeed, int ySeed )
{
Stack s = new Stack();
floodValue = pixelArray[xSeed, ySeed];
s.push( xSeed );
s.push( ySeed );
while ( s.notEmpty() )
{
y = s.pop();
x = s.pop();
setPixel( x, y );
if ( pixelArray[x+1, y] == floodValue ) {
s.push( x+1 ); s.push( y );
}
if ( pixelArray[x-1, y] == floodValue ) {
s.push( x-1 ); s.push( y );
}
if ( pixelArray[x, y+1] == floodValue ) {
s.push( x ); s.push( y+1 );
}
if ( pixelArray[x, y-1] == floodValue ) {
s.push( x ); s.push( y-1 );
}
}
Überlegen wir, wodurch diese Implementierung ineffizient wird. Ein Grund haben wir schon erschlossen: jeder gesetzte Punkt wird mehrmals überprüft. Nehmen wir einen Punkt (x,y) heraus. Dann wird (x+1,y) auf den Stapel gesetzt aber mit diesen Koordinaten wird wiederum (x+1-1,y) überprüft. Eine verbesserte Variante vom Seed-Fill müsste sich daher einfach die Richtung merken und daraufhin die Rückrichtung nicht mehr gehen. Anstelle der Methode seedFill(…) treten nun vier Implementierungen an, für jede Richtung eine Funktion. Zur Demonstration sei seedFillLeft(…) aufgeführt.
seedFillLeft( int x, int y )
{
if ( pixelArray[x, y] != boundaryValue ) {
setPixel( x, y, fillValue );
seedFillLeft( x+1, y );
seedFillUp( x-1, y);
seedFillDown( x+1, y+1 );
}
Wollen wir noch schnellere Füllalgorithmen benutzen, so kommen wir mit diesem Ansatz nicht weiter. Mit einer modifizierten Version des Scan-Line-Algorithmus ist dies aber zu schaffen.