Der Flood-Fill-Algorithmus
Bresenhams Linienalgorithmus und der Midpoint-Circle-Algorithmus zeichnen Umrisse. Flood Fill ist der nĂ€chste Schritt: Gegeben ein geschlossener Umriss und ein Pixel darin, fĂ€rbe jedes Pixel ein, das von dort aus erreichbar ist, ohne den Umriss zu ĂŒberqueren â das Farbeimer-Werkzeug aus jedem Bildbearbeitungsprogramm.
Die Idee
Man beginnt beim Startpixel. Ist es leer, wird es gefĂŒllt, und dasselbe passiert mit seinen Nachbarn. Die FĂŒllung breitet sich nach auĂen aus, bis sie auf allen Seiten an die Begrenzung stöĂt und nicht mehr weiterkommt. Direkt hingeschrieben ist das eine rekursive Funktion mit vier Zeilen:
void flood_fill(int x, int y) {
if (!inside(x, y) || grid[y][x] != EMPTY) return;
grid[y][x] = FILLED;
flood_fill(x + 1, y);
flood_fill(x - 1, y);
flood_fill(x, y + 1);
flood_fill(x, y - 1);
}
Das ist korrekt, hat aber ein ernstes Problem: Die Rekursionstiefe wĂ€chst mit der GröĂe der FlĂ€che, nicht etwa mit ihrer Breite oder Höhe. Im Beispiel unten erreicht eine FlĂ€che von gerade einmal 455 Zellen schon eine Rekursionstiefe von 250. Auf einem leeren Quadrat liegt die Tiefe bei etwa der HĂ€lfte der Pixelzahl: Eine FlĂ€che von 1000Ă1000 Pixeln verschachtelt rund 500.000 Aufrufe â weit mehr, als ein unter Linux ĂŒblicher 8-MB-Thread-Stack fasst, und das Programm stĂŒrzt mit einem Segmentation Fault ab.
Ein expliziter Stack
Die Lösung: Die Liste der noch zu besuchenden Zellen kommt in eine eigene Datenstruktur statt auf den Aufruf-Stack. Die Logik bleibt dieselbe â Zelle nehmen, fĂŒllen, Nachbarn vormerken â, aber die âTo-doâ-Liste liegt jetzt in einem gewöhnlichen Array, das so groĂ sein kann wie nötig. Wird eine Zelle schon beim Ablegen markiert (und nicht erst beim FĂŒllen), landet jede Zelle höchstens einmal auf dem Stack; ein Array mit einem Eintrag pro Zelle reicht also immer aus.
Implementierung
#include "plot.hpp"
// false: 4-way flood fill, one cell per step
// true: scanline fill, one whole horizontal span per step
const bool SCANLINE = false;
const int CELL = 16;
const int W = 640 / CELL; // 40 columns
const int H = 480 / CELL; // 30 rows
enum { EMPTY, WALL, QUEUED, FILLED };
int grid[H][W];
// Explicit stack instead of recursion. Every cell is pushed at most once
// (it is marked QUEUED right away), so W * H entries are always enough.
int stackX[W * H];
int stackY[W * H];
int top = -1;
bool done = false;
int tick = 0;
bool inside(int x, int y) {
return x >= 0 && x < W && y >= 0 && y < H;
}
void wall(int x, int y) {
if (inside(x, y)) grid[y][x] = WALL;
}
// The boundary: the midpoint circle algorithm, plotting grid cells
// instead of pixels.
void midpoint_circle(int cx, int cy, int r) {
int x = 0, y = r, d = 1 - r;
while (x <= y) {
wall(cx + x, cy + y); wall(cx - x, cy + y);
wall(cx + x, cy - y); wall(cx - x, cy - y);
wall(cx + y, cy + x); wall(cx - y, cy + x);
wall(cx + y, cy - x); wall(cx - y, cy - x);
x++;
if (d < 0) {
d += 2 * x + 1;
} else {
y--;
d += 2 * x - 2 * y + 1;
}
}
}
void push(int x, int y) {
if (inside(x, y) && grid[y][x] == EMPTY) {
grid[y][x] = QUEUED;
top++;
stackX[top] = x;
stackY[top] = y;
}
}
// 4-way flood fill: take one cell off the stack, fill it, and push its
// four neighbors.
void step_four_way() {
int x = stackX[top];
int y = stackY[top];
top--;
grid[y][x] = FILLED;
push(x + 1, y);
push(x - 1, y);
push(x, y + 1);
push(x, y - 1);
}
bool fillable(int x, int y) {
return inside(x, y) && (grid[y][x] == EMPTY || grid[y][x] == QUEUED);
}
// Scanline fill: take one seed off the stack, extend it left and right
// as far as possible, fill that whole span, then push one new seed for
// every separate empty run directly above and below it.
void step_scanline() {
int x = stackX[top];
int y = stackY[top];
top--;
int left = x, right = x;
while (fillable(left - 1, y)) left--;
while (fillable(right + 1, y)) right++;
for (int i = left; i <= right; i++) grid[y][i] = FILLED;
for (int dy = -1; dy <= 1; dy += 2) {
bool inRun = false;
for (int i = left; i <= right; i++) {
bool empty = inside(i, y + dy) && grid[y + dy][i] == EMPTY;
if (empty && !inRun) push(i, y + dy);
inRun = empty;
}
}
}
void setup() {
PlotCanvas(640, 480);
midpoint_circle(20, 15, 13);
for (int x = 10; x <= 30; x++) {
if (x < 18 || x > 21) wall(x, 11); // a wall with a gap
}
for (int y = 17; y <= 21; y++) {
for (int x = 23; x <= 27; x++) wall(x, y); // a solid block
}
push(14, 15); // the seed cell
}
void frame() {
// 4-way fill: two cells per frame. Scanline: one span every 6 frames,
// since each step fills a lot more at once.
if (!done && ++tick >= (SCANLINE ? 6 : 1)) {
tick = 0;
for (int n = 0; n < (SCANLINE ? 1 : 2) && top >= 0; n++) {
if (SCANLINE) step_scanline();
else step_four_way();
}
if (top < 0) done = true;
}
PlotBackground(250, 250, 250);
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
int c = grid[y][x];
if (c == EMPTY) continue;
if (c == WALL) PlotColor(30, 100, 200); // boundary
else if (c == QUEUED) PlotColor(220, 60, 60); // waiting on the stack
else PlotColor(70, 170, 90); // filled
PlotFilledRectangle(x * CELL + 1, y * CELL + 1,
x * CELL + CELL - 1, y * CELL + CELL - 1);
}
}
}
Die Begrenzung ist ein Kreis, gezeichnet mit dem Midpoint-Circle- Algorithmus â diesmal auf einem Raster aus 16Ă16 Pixel groĂen Zellen statt auf einzelnen Pixeln â, dazu eine Wand mit LĂŒcke und ein massiver Block, damit die FĂŒllung ihren Weg um Hindernisse herum finden muss. Die Farben zeigen den Zustand jeder Zelle: Blau ist die Begrenzung, rote Zellen warten auf dem Stack, grĂŒne Zellen sind gefĂŒllt.
Mit SCANLINE = false nimmt step_four_way pro Schritt eine Zelle vom
Stack, fĂŒllt sie und legt ihre vier Nachbarn ab. Weil der Stack immer mit
der zuletzt abgelegten Zelle weitermacht, lĂ€uft die FĂŒllung in langen
Streifen davon â eine Tiefensuche â und hinterlĂ€sst eine Spur roter
Zellen, die erst spĂ€ter abgearbeitet werden. FĂŒr diese Form wĂ€chst der
Stack auf 166 EintrÀge.
Scanline-Fill
Die meisten dieser Push-Operationen sind verschwendet: Der linke und rechte Nachbar einer Zelle werden ohnehin fast immer als NĂ€chstes gefĂŒllt. Scanline-Fill nutzt das aus. Jeder Schritt nimmt einen Startpunkt vom Stack und
- lÀuft von dort nach links und rechts, bis er auf die Begrenzung trifft,
- fĂŒllt diesen ganzen waagrechten Abschnitt auf einmal,
- schaut sich die Zeilen direkt darĂŒber und darunter an und legt fĂŒr jeden zusammenhĂ€ngenden Bereich leerer Zellen dort genau einen neuen Startpunkt ab.
Ăndere im Code oben SCANLINE auf true und klicke auf âCompile & Runâ,
um den Unterschied zu sehen: Die FlĂ€che fĂŒllt sich jetzt Zeile fĂŒr Zeile,
und es warten nie mehr als eine Handvoll roter Startpunkte. FĂŒr dieselbe
Form braucht Scanline-Fill 34 statt 455 Schritte und einen Stack von
höchstens 4 statt 166 EintrĂ€gen â und fĂŒllt dabei exakt dieselben 455
Zellen.
4er- oder 8er-Nachbarschaft?
Die Beispiele oben betrachten nur die vier direkten Nachbarn â links, rechts, oben, unten â als verbunden. Ein 8-Wege-Fill zĂ€hlt auch die vier diagonalen Nachbarn dazu. Das klingt nach einer harmlosen Erweiterung, Ă€ndert aber, welche Umrisse als geschlossen gelten.
Ein Kreis aus dem Midpoint-Circle-Algorithmus hĂ€ngt ĂŒberall dort nur
diagonal zusammen, wo er gleichzeitig in x und y um ein Pixel springt.
Ein 4-Wege-Fill kann sich nicht zwischen zwei Pixeln hindurchzwÀngen, die
sich nur an einer Ecke berĂŒhren â fĂŒr ihn ist der Umriss geschlossen. Ein
8-Wege-Fill kann das und lÀuft direkt hindurch: Bei der Beispielform
entkommt er aus dem Kreis und fĂŒllt 1086 statt 455 Zellen. Ein 4-Wege-Fill
gehört also zu 8-fach verbundenen Umrissen, wie sie Bresenham und der
Midpoint-Circle-Algorithmus erzeugen, und ein 8-Wege-Fill funktioniert nur
innerhalb von Umrissen, die 4-fach verbunden sind.
Fazit
Flood Fill ist eine verkleidete Graphensuche: Die Zellen sind Knoten, benachbarte leere Zellen sind verbunden, und FĂŒllen heiĂt, alles zu besuchen, was vom Startpunkt aus erreichbar ist. Die rekursive Variante ist die kĂŒrzeste Art, das hinzuschreiben, der explizite Stack macht sie fĂŒr jede GröĂe sicher, und Scanline-Fill macht sie schnell, indem ganze Pixelreihen auf einmal statt Pixel fĂŒr Pixel abgearbeitet werden.