www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Grafik: Fill-Funktion


Autor: LCD User (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: LCD User (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@kbuchegg
Danke!

Autor: LCD User (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lupin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Rahul (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...).

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.