Making Flood Fill Algorithm more efficient.

[Xrey274]

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;
}

[Laurent]

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.

[Xrey274]

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?

[Laurent]

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

A little bit.

[Xrey274]

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);
                }
        }
}

[Laurent]

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