Grafik: Fill-Funktion

[LCD User (Gast)]

Hallo Leute,

ich benutze ein Farb-Grafikdisplay und möchte gerne eine
"Fill-Routine" realiseren, d.h. ich übergebe der Funktion eine
Position (X,Y) und eine Fill-Farbe:
  void vLCD_Fill(int iX, int iY, byte bFillColor);

Die Routine soll nun die aktuelle Farbe dieses Pixels ermitteln und
dann alle Pixel innerhalb eines Bereiches (Begrenzung = andere Farbe),
die die gleiche Farbe haben, durch die Fill-Farbe ersetzen.

Kurz gesagt, eine Fill-Funktion, wie sie in jedem Grafik-Programm zur
Verfügung steht.

Frage:
Kenn jemand einen schnellen Algorithmus dafür? Ist bei näherer
Betrachtung (komplizierte Geometrien) gar nicht so ohne!

[Karl H. (kbuchegg)]

http://en.wikipedia.org/wiki/Flood_fill

[LCD User (Gast)]

@kbuchegg
Danke!

[LCD User (Gast)]

Habe mir mal den Algoritmus angesehen. Ist für meine Mikrocontroller
Anwendung nicht geeignet, da Aufgrund der vielen Rekursionen ein
Stack-Überlauf auftreten würde.

Gibt es noch andere Algorithmen?

[Karl H. (kbuchegg)]

1. So viele Rekursionen sind das auch wieder nicht.
2. Auf der Site ist auch eine entrekursivierte Fassung angegeben.
3. Die entrekursivierte Fassung braucht eine Queue. Auch hier:
   So viele Einträge kommen da nicht zustande
4. Das Prinzip ist simpel:
    Fang mit dem gegebenen Pixel an.
    Geh soweit nach links bzw. rechts und setzte Pixel wie du
    kannst.
    Für jedes gesetzte Pixel, schau nach ob drüber/drunter
    ebenfalls ein Pixel gesetzt werden muss. Wenn ja:
     fülle soweit du kannst nach rechts/links
5. Google ist dein Freund.
   Es gibt viele unterschiedliche Implementierungen des Flood Fill.

[Lupin (Gast)]

karl heinz so wie du es beschrieben hast geht es leider nicht. Wenn der
strahl gestoppt wird, dann geht er von dort aus zwar noch hoch/runter
aber pixel die noch weiter in strahlrichtung entfernt liegen werden
nicht behandelt.

Um Rekursion kommt man kaum herum. Das ist gar nicht mal so ein
einfaches Thema und ich kann auch keine perfekte Lösung anbieten.

[Karl H. (kbuchegg)]

Genau da kommt die Queue ins Spiel.
OK. Ich hab das Prinzip da oben auf die Schnelle eingehackt.
Das ist natuerlich nicht vollständig.
Ich weiss ja nicht wie der OP das sieht. Aber ich hatte
immer einen Heidenspass bei der Implementierung von Grafik-
Basisfunktionen. Da kann man so richtig schön kreativ sein.

[Rahul (Gast)]

Karl-Heinz Lösung funktioniert bei Körpern, die eine gleichmässige
Oberfläche (Kreise/Elipsen, Rechtecke, Dreiecke) haben. Sterne kann man
damit z.B. noch nicht komplett füllen.
Wenn man noch die grössten Grenzen (Eckpunkte des grösste Rechtecks)
feststellt, hätte man IMHO zumindest noch einen Anhaltspunkt, was noch
nicht angemalt sein müsste. Ich hab mir den Algorithmus noch nicht
genauer angeguckt (nur die Gifs...).

[Hagen (Gast)]

>>Habe mir mal den Algoritmus angesehen.
>>Ist für meine Mikrocontroller Anwendung nicht geeignet, da Aufgrund
>> der vielen Rekursionen ein Stack-Überlauf auftreten würde.

Hast du das ausgerechnet ?
Wie groß ist das Display in Pixeln und wieviel Speicher hast du in der
MCU ?

Du wirst nämlich, ob du es willst oder nicht immer zusätzlichen
Speicher benötigen für ein Floodfill. Sei es als Stack oder als Queue.
Minimal benötigst du ca. Sqrt(Display Width * Height)  2 
Sizeof(Point) an Speicher. Point stellt eine X,Y Koordinate dar. Das
setzt aber schon einen besseren Floodfill Algo. vorraus als der aus dem
Wiki. Ich beziehe mich auf einen Linien-basierten Floodfill. Dabei wird
als erster Schritt der zu füllende Bereich in Linien mit Start
Koordinate + Anzahl zerlegt und diese Liste dann nach Start Koordinate
sortiert. Als zweiter Schritt wird diese Liste von Linien gezeichnet.

Gruß Hagen