4. Resourcensparender Flood-fill Algorithmus

Resourcensparender Flood-fill Algorithmus

  • M

    Ich weiß nicht, ob ich hier im richtigen Forum bin, aber da es sich ja um Grafik handelt, frag ich einfach mal hier.

    Ich brauche für mein aktuelles Projekt einen Flood-fill Algorithmus, der möglichst wenig Speicher benötigt. Das Projekt ist nicht für einen PC, daher sind die Speicher/Resourcen sehr spärlich. Eine rekursive Implementierung ist deshalb auch nicht möglich.

    Die iterative Lösung aus der Wikipedia habe ich bereits ausprobiert und so umgeschrieben, dass nur nöch nicht gefüllte Felder auf dem Stack abgelegt werden, statt allen, trotzdem benötige ich ca 8KB Stack, was hardwarebedingt das absulute Limit und daher inaktzeptabel ist.

    Es geht außerdem nicht um die Geschwindigkeit der Funktion, Hauptsache ist wenig Speicherbedarf. Die Bildschirmgröße ist 128 * 64 Pixel.

    Mich würde es freuen, wenn sich jemand der vllt schon Erfahrung bzgl des Themas hat oder mir anderweitig weiterhelfen kann, melden würde.

    MGOS

    0
  • R
    Mod 

    a) du gehst vom start punkt nach links und dann nach rechts
b) du pruefst pro pixel, ob der pixel darueber und darunter  "frei" ist
   falls "ja", pruefst du ob deren nachfolger nicht "frei" ist,
   falls "ja", legst du den oberen bzw unteren pixel in deinen buffer
c) fall du einen punkt im buffer hast, waehle diesen als startpunkt und gehe zu a)
    0
  • M

    Danke für die schnelle Antwort, doch deine Lösung kann ich irgendwie nicht nachvollziehen.
    sagen wir , wir haben eine 5x5 pxl große Fläche und fangen in der Mitte an:

    X = Schwarzen Feld
. = aktuelles Feld
? = Prüfen

+-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
| | | | | |   | | |
+-+-+-+-+-+   | | |
| |.|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Gehe nach links
| | | | | |
+-+-+-+-+-+

+-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
| |?| | | |   | | |
+-+-+-+-+-+   | | |
| |.|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Prüfe den oberen ob frei -> Ja
| | | | | |
+-+-+-+-+-+

+-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
|?| |?| | |   | | |
+-+-+-+-+-+   | | |
| |.|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Prüfe ob die Nachfolger nicht frei sind -> Nein
| | | | | |   D.h. es kommt nichts in den Buffer.
+-+-+-+-+-+
    0
  • W

    Wie sind denn die Daten bei dir gespeichert? Wenn du die gefüllten Pixel z.B. in einen gleich großen Puffer zwischenspeicherst (sodass der Algorithmus "weiß", welche Pixel neu markiert sind und welche die alte Begrenzung darstellen), dann hätte ich auch einen Algorithmus für dich (mit ansonstem konstanten Speicherbedarf, vermutlich < 100 Byte).

    0
  • M

    Also so einen Speicher für neu gefüllte könnte ich anlegen, das wäre bei meiner Bildschirmgröße nur 1k, also vollkommen OK.

    0
  • W

    Ich gehe mal davon aus, dass die Füllung bei dir nur über angrenzende und nicht aneckende Pixel gehen soll.

    Mein Algorithmus ist: Ausgehend vom Ausgangspunkt wird die Zeile im Puffer soweit aufgefüllt, bis im Original ein schwarzes (= true) pixel kommt. Dann wird die Zeile weiter unten ausgehend von dieser Pixelreihe aufgefüllt, dann die weiter unten bis in einer Zeile kein Pixel mehr ausgefüllt wird. Dann werden die Zeilen wieder nach oben durchgegangen, dann wieder nach unten usw. bis sicher ist, dass alles ausgefüllt ist. Hier der Auszug aus meinem Code:

    Hier werden die nicht erreichbaren Regionen im Puffer ausgefüllt. Das ist aber nicht weiter schlimm, du musst bloß entsprechend den Puffer mit false statt mit true initialisieren und dann die entsprechenden Pixel auf true setzen. Natürlich musst du auch die Vergleiche auf der dest_map entsprechend umkehren.

    pos_x und pos_y geben die Pixelposition des Ausgangspixels an.

    bool DataMap::EraseReachableSection(DataMap source_map, DataMap dest_map, size_t y_pos, size_t x_start, size_t length) //private
{
    bool has_changed = false;

    //1. set the section in the dest map to the section in the source map

    for(size_t i = x_start; i < x_start + length; ++i)
    {
        if(source_map.GetBit(i, y_pos) != dest_map.GetBit(i, y_pos))
        {
            has_changed = true;
            dest_map.SetBit(i, y_pos, false); //can't be true because a true bit in the source map will never be erased
        }
    }

    //2. expand the section if necessary
    //2.1 expand to the left

    if(source_map.GetBit(x_start, y_pos) == false)
    {
        for(int i = static_cast<int>(x_start) - 1; i >= 0 && source_map.GetBit(i, y_pos) == false; --i)
        {
            if(dest_map.GetBit(i, y_pos) == true)
            {
                has_changed = true;
                dest_map.SetBit(i, y_pos, false);
            }
        }
    }

    //2.2 expand to the right
    if(source_map.GetBit(x_start + length - 1, y_pos) == false)
    {
        for(size_t i = x_start + length; i < source_map.GetYSize() && source_map.GetBit(i, y_pos) == false; ++i)
        {
            if(dest_map.GetBit(i, y_pos) == true)
            {
                has_changed = true;
                dest_map.SetBit(i, y_pos, false);
            }
        }
    }

    return has_changed;
}

bool DataMap::ExpandReachableSection(DataMap source_map, DataMap dest_map, int source_y, int dest_y) //private
{
    size_t x_pos = 0;
    bool has_changed = false;

    while(true)
    {
        while(x_pos < source_map.GetXSize() && dest_map.GetBit(x_pos, source_y) == true) ++x_pos;

        if(x_pos == source_map.GetXSize()) break;

        size_t x_start_pos = x_pos;

        while(x_pos < source_map.GetXSize() && dest_map.GetBit(x_pos, source_y) == false) ++x_pos;

        if(EraseReachableSection(source_map, dest_map, dest_y, x_start_pos, x_pos - x_start_pos)) has_changed = true;

        if(x_pos == source_map.GetXSize()) break;
    }

    return has_changed;
}

void DataMap::FillUnreachableRegions(size_t pos_x, size_t pos_y)
{
    if(GetBit(pos_x, pos_y) == true) return;

    if(transformation_buffer.CanResize()) transformation_buffer.ResizeUninitialized(storage.GetBitSize());
    StorageManager(transformation_buffer).Reset(true);  //fill it per default and set all regions reachable by the position to false
    DataMap buffer_map(transformation_buffer, GetXSize());

    int direction = 1;
    int line = pos_y;
    int first_change_line_in_negative_direction = pos_y;
    int first_change_line_in_positive_direction = pos_y;

    EraseReachableSection(*this, buffer_map, line, pos_x, 1);

    bool last_has_changed_result = true;

    while(true)
    {
        bool need_to_go_on_in_direction = false;
        bool is_at_the_border_of_the_map = false;
        bool has_a_changed_value_in_direction = false;

        if(direction == 1)
        {
            if(first_change_line_in_positive_direction <= line) has_a_changed_value_in_direction = true;
        }
        else
        {
            if(first_change_line_in_negative_direction >= line) has_a_changed_value_in_direction = true;
        }

        if(direction == 1)
        {
            if(first_change_line_in_negative_direction >= line) need_to_go_on_in_direction = true;
            if(line + 1 >= static_cast<S32>(GetYSize())) is_at_the_border_of_the_map = true;
        }
        else
        {
            if(first_change_line_in_positive_direction <= line) need_to_go_on_in_direction = true;
            if(line <= 0) is_at_the_border_of_the_map = true;
        }

        if((last_has_changed_result == true || need_to_go_on_in_direction) && !is_at_the_border_of_the_map)  //process next line
        {
            last_has_changed_result = ExpandReachableSection(*this, buffer_map, line, line + direction);
            if(last_has_changed_result == true)
            {
                if(direction == 1)
                {
                    if(!has_a_changed_value_in_direction) first_change_line_in_positive_direction = line;
                }
                else
                {
                    if(!has_a_changed_value_in_direction) first_change_line_in_negative_direction = line;
                }
            }
        }
        else if(last_has_changed_result == true || has_a_changed_value_in_direction) //change direction
        {
            direction = -direction;

            if(direction == 1)
            {
                first_change_line_in_positive_direction = GetYSize();
            }
            else
            {
                first_change_line_in_negative_direction = -1;
            }
        }
        else break; //finished

        line += direction;
    }

    CopyFrom(buffer_map);
}
    0
  • M

    Vielen Dank, wxSkip

    Das muss ich mir mal in Ruhe ansehen... das ist ganz schön viel.

    0
  • R
    Mod

    MGOS schrieb:

    Danke für die schnelle Antwort, doch deine Lösung kann ich irgendwie nicht nachvollziehen.
    sagen wir , wir haben eine 5x5 pxl große Fläche und fangen in der Mitte an:

    X = Schwarzen Feld
. = aktuelles Feld
? = Prüfen

+-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
| | | | | |   | | |
+-+-+-+-+-+   | | |
| |.|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Gehe nach links
| | | | | |
+-+-+-+-+-+

+-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
| |?| | | |   | | |
+-+-+-+-+-+   | | |
| |.|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Prüfe den oberen ob frei -> Ja
| | | | | |
+-+-+-+-+-+

+-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
|?| |?| | |   | | |
+-+-+-+-+-+   | | |
| |.|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Prüfe ob die Nachfolger nicht frei sind -> Nein
| | | | | |   D.h. es kommt nichts in den Buffer.
+-+-+-+-+-+

    sorry, hab mich nicht ganz richtig ausgedrueckt bei a). du gehst pixelweise soweit nach links/rechts wie moeglich, deine ascii art fortfuehrend waere das:

    +-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
| | | | | |   | | |
+-+-+-+-+-+   | | |
|.|X|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Gehe nach links
| | | | | |
+-+-+-+-+-+

+-+-+-+-+-+   Buffer:     
| | | | | |   | | |
+-+-+-+-+-+   | | |
|?| | | | |   | | |
+-+-+-+-+-+   | | |
|.|X|X| | |   | | |
+-+-+-+-+-+   | | |
| | | | | |
+-+-+-+-+-+   Prüfe den oberen ob frei -> Ja
| | | | | |
+-+-+-+-+-+
  A B C D E
 +-+-+-+-+-+   Buffer:     
 | | | | | |0  |A|1|
 +-+-+-+-+-+   |A|3|
?| | | | | |1  | | |
 +-+-+-+-+-+   | | |
 |.|X|X| | |2  | | |
 +-+-+-+-+-+   | | |
?| | | | | |3
 +-+-+-+-+-+   Prüfe ob die Nachfolger nicht frei sind -> JA
 | | | | | |4   
 +-+-+-+-+-+
    0
  • M

    Ich habe jetzt eine aktzeptabel schnelle Lösung gefunden, die mit festgelegtem speicher arbeitet. Es gibt einen begrenzten Stack für eine iterative Füllung, falls der Stack nicht ausreicht, weil die Form zu groß bzw. zu komplex ist, lagert die Funktion dein Speicher auf einen weiteren Buffer aus, auf dem die Pixel mittels einer Suchroutine abgerufen werden können. Das ist zwar langsam, aber so ist sichergestellt, dass kein zusätzlicher speicher benötigt wird. In der Praxis zeigt sich die Funktion als äußerst schnell, da wenn der Stack wieder Platz hat, die Pixel wieder auf den Stack verschoben werden, der deutlicher effizienter ausgelesen werden kann. das ganze kann man sich also ähnlich wie bei der Speicherauslagerung vom Ram auf dei Festplatte / Flash am PC vorstellen.

    Trotzdem vielen Dank an alle, die mir Lösungsvorschläge gepostet haben, ihr wart eine große Hilfe.

    0
  • K

    Wahrscheinlich haette es auch ein Scanline-Algorithmus getan.

    0
  • M

    Möglich, ich habe mir das auch überlegt, jedoch als zu kompliziert eingestuft. Scanline Algorithmen kann man am besten umsetzten, wenn man ein vorgebenes Polygon hat. Hier muus eine beliebige Fläche gefüllt werden. Das wäre wahrscheinlich auch mit einem Scanline Algorithmus möglich, aber weit aufwändiger als das, was ich im Moment nehme.
    Aber wenn du Spaß, daran hast, kannst du dich ja mal an einem Scanline Algorithmus versuchen 😉

    0
Anmelden zum Antworten