Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm creating a sprite and animation editor like this one. I'm having performance issues with my flood-fill algorithm.

Basically, I open an image with the different modules that are part of a frame of an animation. When I double-click a module I run a depth-first search algorithm that checks all the pixels of that part of the image that are surrounded by transparency. From that I get the rectangle of said module (the position and size). With large images, when I double-click that part of the image the application freezes.

How can I improve my algorithm?

Right now what I do is maintain an array of already-checked pixels and a list of pixels to check. I start with the pixel that I double-clicked and check if the surrounding pixels have transparency. If they do not, I check for the surrounding pixels of those pixels and so on until all the surrounding pixels are transparent. Then I can get the minimum and maximum position in the X-axis and Y-axis and use that to construct the bounding rectangle of the frame.

This is my code:

private Rectangle widthSearch(int posX, int posY)
{
    Rectangle result = new Rectangle();
    int leftX, topY, rightX, botY;
    leftX = rightX = posX;
    topY = botY = posY;

    List<Point> closedList = new List<Point>();
    List<Point> toProcessList = new List<Point>();

    Point processingNode;
    Color colorAux;
    int alphaAux;
    int offsetX = 0;
    int offsetY = 0;

    toProcessList.Add(new Point(posX, posY));

    int[] dx = { 1, 1, 0, -1, -1, -1, 0, 1 };
    int[] dy = { 0, -1, -1, -1, 0, 1, 1, 1 };

    while (toProcessList.Count > 0)
    {
        processingNode = toProcessList.ElementAt(0);
        closedList.Add(processingNode);
        toProcessList.Remove(toProcessList.ElementAt(0));                

        for (int i = 0; i < dx.Count(); i++)
        {
            offsetX = dx[i];
            offsetY = dy[i];
            try{
                if (!closedListContains(closedList, processingNode.X + offsetX, processingNode.Y + offsetY) && !closedListContains(toProcessList, processingNode.X + offsetX, processingNode.Y + offsetY))
                {
                    colorAux = bmp.GetPixel(processingNode.X + offsetX, processingNode.Y + offsetY);
                    alphaAux = (colorAux.ToArgb() >> 24) & 0xFF;
                    if (alphaAux > 0)
                    {
                        toProcessList.Add(new Point(processingNode.X + offsetX, processingNode.Y + offsetY));
                    }
                }
            }
            catch (Exception e)
            {
                Console.Write(">>>>>>>>\n" + e + "\n>>>>>>>>>");
            }
        }
    }

    for (int i = 0; i < closedList.Count(); i++)
    {
        if (closedList.ElementAt(i).X > rightX)
            rightX = (int)closedList.ElementAt(i).X;
        if (closedList.ElementAt(i).X < leftX)
            leftX = (int)closedList.ElementAt(i).X;
        if (closedList.ElementAt(i).Y < topY)
            topY = (int)closedList.ElementAt(i).Y;
        if (closedList.ElementAt(i).Y > botY)
            botY = (int)closedList.ElementAt(i).Y;
    }

    result.X = leftX;
    result.Y = topY;
    result.Width = rightX - leftX;
    result.Height = botY - topY;

    return result;
}

private Boolean closedListContains(List<Point> closedList, int posX, int posY)
{
    Point pointer = new Point(posX, posY);
    for (int i = 0; i < closedList.Count(); i++)
    {
        if (closedList.ElementAt(i).Equals(pointer))
            return true;
    }
    return false;
}

I only call the widthSearch() method when I double-click a PictureBox. It is not inside a loop.

share|improve this question
2  
That sounds like a flood fill algorithm. –  UnderscoreZero Dec 23 '13 at 18:56
    
You need flood fill check this en.wikipedia.org/wiki/Flood_fill. –  concept3d Dec 23 '13 at 20:17
    
are you calling widthSearch recursively ? can you show us more of the code? How are you calling it, I suspect it's called inside a loop ? please provide more details. –  concept3d Dec 24 '13 at 13:08
add comment

1 Answer

up vote 4 down vote accepted

I suspect you are using an inefficient implementation of the flood fill algorithm especially that the application freezes when applied on large images.

By looking quickly at your code I can identify few problems

It seems your code has a Big O( N^2 * K ) and might even be O(N^3), which translates to your code like this:

toProcessList.Count // Looping through that O(N)
closedListContains  // That's O(N), also called twice.
dx.Count            // This is K

Keep in mind that I didn't do exact analysis, and this is only a rough estimate. Three nested loops isn't really fast (unless you have a very small data set) This will be the biggest speed improvement.

I also suspect that widthSearch is being called inside a loop. Which makes things even worse. But I don't have enought info about.

Second the chosen data structure (List) is not ideal, to be more clear:

  • Your closedListContains implementation clearly runs in O(N) time.
  • You also have two expensive operations which you are using liberally. List<T>::RemoveAt is O(N) unless it was from the end of the list. List<T>::Add I suspect this is O(N). Actually according to the documentation:

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

Now my suggestions for improvement

  • Use some kind of Dictionary for closedPoints instead of Lists where Searching is faster (or any other data structure with fast search but I think dictionaries will perform better here).
  • Use a stack/linked list or any data structure where Adding/Removing could be faster (static array could also be great if you know the maximum size previously).

(the above points depend on the size of data and the underlying implementation of data structure).

  • Other enhancements could be done by making iterating over the image more cache friendly especially when accessing it using GetPixel. But I won't go that path unless I am done with the above and did't get a decent result.
share|improve this answer
    
Typically you'd use something like a BitSet rather than a Dictionary, unless the image is extremely huge –  BlueRaja - Danny Pflughoeft Dec 24 '13 at 17:36
    
@BlueRaja-DannyPflughoeft that's why I said "the above depends on the data and the underlying implementation" –  concept3d Dec 24 '13 at 17:38
    
I haven't done the math but this feels like O(N^4) to me. You are treating the Contains call as O(N) but it's filled by a O(N^2) loop and thus it might itself be an O(N^2) call. –  Loren Pechtel Dec 24 '13 at 18:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.