SFML community forums

Help => General => Topic started by: Xrey274 on February 12, 2020, 02:50:01 pm

Title: Making Flood Fill Algorithm more efficient.
Post by: Xrey274 on February 12, 2020, 02:50:01 pm

I am working on a Flood Fill Algorithm. Unfortunately I have been having performance issues with said algorithm. It hammers the CPU. It's constantly at 100%(or at least one of the cores is, since the app is single threaded). This is what I have come up with so far:

sf::Image BucketTool::rgbFill(sf::Image& canvas_image, sf::Vector2f origin, sf::Color discriminator)
{
        if(origin.x < 0 || origin.x >= canvas_image.getSize().x || origin.y < 0 || origin.y >= canvas_image.getSize().y)
        {
        return canvas_image;
        }

        if(canvas_image.getPixel(origin.x, origin.y) != discriminator)
        {
                return canvas_image;
        }

        canvas_image.setPixel(origin.x, origin.y, sf::Color::Black);

        ///std::cout<<origin.x<<" "<<origin.y<<std::endl;

        rgbFill(canvas_image, sf::Vector2f(origin.x + 1, origin.y), discriminator);
        rgbFill(canvas_image, sf::Vector2f(origin.x - 1, origin.y), discriminator);
        rgbFill(canvas_image, sf::Vector2f(origin.x, origin.y + 1), discriminator);
        rgbFill(canvas_image, sf::Vector2f(origin.x, origin.y - 1), discriminator);

        canvas_image.setPixel(origin.x, origin.y, sf::Color::Black);
        canvas_image.saveToFile("example.png");

        return canvas_image;
}

Title: Re: Making Flood Fill Algorithm more efficient.
Post by: Laurent on February 12, 2020, 08:39:00 pm

1. Don't return a copy of the image at every call. You don't even need to return anything, since you modify the input image directly.

2. Don't save the image to a file at every call!! Split your function in two: one that recurses, and one that wraps the other, that performs inits and post-processing (those things that should only happen once).

3. Don't write the same pixel twice.

4. Once you've written a proper version, if it's still too slow, you can consider bypassing getPixel/setPixel by directly accessing the pixel array.

Title: Re: Making Flood Fill Algorithm more efficient.
Post by: Xrey274 on February 12, 2020, 09:28:47 pm

Thanks for the input! Worth mentioning that the function called to save the image(also the second setPixel call) was actually there for testing and is not part of the code itself(commented out). Otherwise I agree completely. One question though - Is get/setPixel slower than directly modifying the pixel array?

Title: Re: Making Flood Fill Algorithm more efficient.
Post by: Laurent on February 13, 2020, 07:54:49 am

Quote

Is get/setPixel slower than directly modifying the pixel array?

A little bit.

Title: Re: Making Flood Fill Algorithm more efficient.
Post by: Xrey274 on March 01, 2020, 07:55:31 pm

I have modified the function a bit, and it works(sometimes), but if all recursive directions are enabled is segfaults. If two of them are commented out while the rest are not, it works perfectly fine. Possibly connected with running out of memory?

void BucketTool::rgbFill(sf::Image& canvas_image, sf::Vector2i origin, sf::Color discriminator)
{
        if(canvas_image.getPixel(origin.x, origin.y) == discriminator)
        {
                if(!(origin.x < 0 || origin.x >= canvas_image.getSize().x || origin.y < 0 || origin.y >= canvas_image.getSize().y))
                {
                        //std::cout << origin.x << " " << origin.y << std::endl;
                        canvas_image.setPixel(origin.x, origin.y, sf::Color::Black);

                        rgbFill(canvas_image, sf::Vector2i(origin.x + 1, origin.y), discriminator); //if two of there are commented out it works fine
                        rgbFill(canvas_image, sf::Vector2i(origin.x - 1, origin.y), discriminator);
                        rgbFill(canvas_image, sf::Vector2i(origin.x, origin.y + 1), discriminator);
                        rgbFill(canvas_image, sf::Vector2i(origin.x, origin.y - 1), discriminator);
                }
        }
}

Title: Re: Making Flood Fill Algorithm more efficient.
Post by: Laurent on March 01, 2020, 08:01:26 pm

Use your debugger. A possible explanation for this kind of recursive function is a stack overflow.