FloodFillScanlineReplace with MaxDiff freezes

Mar 13, 2014 at 1:43 PM
Edited Mar 13, 2014 at 1:56 PM
I've been trying to use the FloodFillScanlineReplace function, which has 2 overloads. One with "maxDiff" as an argument.

When this argument is used with any value, it has the potential to freeze a Windows 8.1 app. It simply freezes and starts using about 20 - 30% CPU on an Intel Core i7 mobile processor, and stays like that forever.

Using the function without the maxDiff works just fine, but this of course lacks functionality that I'm seeking.

This code seems to be able to reproduce the problem every time
var bitmap = new WriteableBitmap(1600, 900);
bitmap.FillRectangle(0, 0, bitmap.PixelWidth, bitmap.PixelHeight, Colors.White);
FloodFillBitmap(bitmap, 800, 450, new Color { R = 0, G = 0, B = 0, A = 255 }, 128);
FloodFillBitmap(bitmap, 800, 450, new Color { R = 255, G = 138, B = 64, A = 255 }, 128);
FloodFillBitmap(bitmap, 800, 450, new Color { R = 255, G = 215, B = 46, A = 255 }, 128);

public static void FloodFillBitmap(WriteableBitmap bitmap, int x, int y, Color color, byte treshhold)
{
    // Correct X and Y coordinates
    if (x > bitmap.PixelWidth)
        x = bitmap.PixelWidth;
    else if (x < 0)
        x = 0;

    if (y > bitmap.PixelHeight)
        y = bitmap.PixelHeight;
    else if (y < 0)
        y = 0;

    try
    {
        var currentColor = bitmap.GetPixel(x, y).AsInt();

        if (currentColor == color.AsInt())
            return;

        // No crash
        //bitmap.FloodFillScanlineReplace(x, y, currentColor, color.AsInt());
        // Crash
        bitmap.FloodFillScanlineReplace(x, y, currentColor, color.AsInt(), treshhold);
              
    }
    catch (Exception)
    {
            
    }
}
Test environment: Windows 8.1 Pro 64-bit, Intel Core i7-2630QM @ 2.00GHz, 8 GB SODIMM DDR3 1600MHz RAM, 1600x900 screen resolution, Visual Studio 2013 Ultimate.
Coordinator
Mar 13, 2014 at 3:43 PM
Thanks, I'll take a look.
Mar 17, 2014 at 8:07 AM
Hey xyzzer, any luck with finding the cause/solution?

Thanks in advance.
Coordinator
Mar 17, 2014 at 4:09 PM
I spent a while trying to debug it, but it seemed like it might take more time.
Mar 17, 2014 at 4:11 PM
I understand.

Thanks for taking the time :)
May 9, 2014 at 12:14 AM
Hi there, it's been a while, and I was wondering if you had any success yet with this issue. I've asked a few of my programmer friends, but as none of us really have an understanding of the kind of algorithms, we've had no luck on solving the issue.
I have however discovered that the stack seems to keep being filled infinitely, causing the freeze and the constant loop.

Thanks in advance.
Coordinator
May 9, 2014 at 12:49 AM
No, not yet, sorry. Last time I got to just about that same point - finding the stack being filled indefinitely. I'll see if I can figure it out today again though.
May 9, 2014 at 7:33 AM
Seems like I've found a temporary solution. I'm directly attacking the issue of the stack being filled infinitely by adding a list of points that have already been scanned, and skipping the current point it is at if it's in this list:
public static void CustomFloodFillScanlineReplace(
            this WriteableBitmap target, int x, int y, int oldColor, int fillColor, byte maxDiff)
        {
            var pixels = target.PixelBuffer.GetPixels();

            var width = target.PixelWidth;
            var height = target.PixelHeight;

            if (pixels[x + width * y] == fillColor)
            {
                return;
            }

            var stack = new Stack<Pnt>();
            var scannedPoints = new List<Pnt>(); // Added this line

            stack.Push(new Pnt { X = x, Y = y });

            while (stack.Count > 0)
            {
                var pnt = stack.Pop();
                x = pnt.X;
                y = pnt.Y;

                if (scannedPoints.Contains(pnt)) continue; // Added this line
                scannedPoints.Add(pnt); // Added this line

                var y1 = y;

                // Find first unfilled point in line
                while (
                    y1 >= 0 &&
                    pixels[x + width * y1].MaxDiff(oldColor) < maxDiff)
                //pixels[x + width * y1] == oldColor)
                {
                    y1--;
                }

                y1++;
                var spanLeft = false;
                var spanRight = false;


                while (
                    y1 < height &&
                    pixels[x + width * y1].MaxDiff(oldColor) < maxDiff)
                {
                    pixels[x + width * y1] = fillColor;

                    if (!spanLeft &&
                        x > 0 &&
                        pixels[x - 1 + width * y1].MaxDiff(oldColor) < maxDiff)
                    {
                        stack.Push(new Pnt { X = x - 1, Y = y1 });

                        spanLeft = true;
                    }
                    else if (
                        spanLeft &&
                        x > 0 &&
                        pixels[x - 1 + width * y1].MaxDiff(oldColor) >= maxDiff)
                    {
                        spanLeft = false;
                    }

                    if (!spanRight &&
                        x < width - 1 &&
                        pixels[x + 1 + width * y1].MaxDiff(oldColor) < maxDiff)
                    {
                        stack.Push(new Pnt { X = x + 1, Y = y1 });
                        spanRight = true;
                    }
                    else if (
                        spanRight &&
                        x < width - 1 &&
                        pixels[x + 1 + width * y1].MaxDiff(oldColor) >= maxDiff)
                    {
                        spanRight = false;
                    }

                    y1++;
                }
            }
        }
I've quickly tested it, also using my own example that crashed it before, and so far, it seems to work. But in the end, there's an internal problem, but at least there seems to be a solution for now :)
Coordinator
May 9, 2014 at 3:40 PM
No time last night. Maybe over the weekend.
May 9, 2014 at 3:46 PM
Don't worry about it. We've got a solution right now for our app, and we'll update it in the store whenever a better solution becomes available.
I'm already extremely glad with this toolkit, it's so useful!