FloodFill function

using System.Collections.Generic;
using UnityEngine;

#region MIT LICENSE

/*
    License: The MIT License (MIT)
    Copyright (C) 2020 Shannon Rowe

    Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
    documentation files (the "Software"), to deal in the Software without restriction, including without limitation
    the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
    and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all copies or substantial portions of
    the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
    TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
    THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
    CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.
*/

#endregion

// This class being static means it can be called from anywhere and doesn't need to be instantiated
// Note that this is a pure C# class, not a MonoBehaviour
public static class ImageFunctions
{
    /// <summary>
    ///     <para>
    ///         To use this, pass it a texture and the from and to colors, and a starting position inside the texture
    ///         where you want the fill to start from, and it will return a filled texture.
    ///         Note that alpha transparency values are ignored and the image assumed to be opaque.
    ///     </para>
    ///     <para>
    ///         For example, say you have a texture that is all white except for an outline pattern that's some other color,
    ///         for example a black outline circle but it's still white inside the outline, and you want to fill that inside
    ///         with red, you would pass fillFromColor as white, fillToColor as red, and startPosition as some point inside
    ///         the circle based on either maths or a mouse click or something.
    ///     </para>
    ///     <para>
    ///         The colorTolerance parameter determines how far to either side of the color's RGB values to process,
    ///         which can be useful when you want to fill an image with a gradient of colors in an approximate range.
    ///         With the default of 0 it will only match to exact colors, but if you set it to say 10 for example,
    ///         and your fillFromColor is something like Red 127/Green 66/Blue 32 then the fill will be applied to
    ///         any color combination in the range Red 117-137/Green 56-76/Blue 22-42.  It will also preserve the
    ///         gradient, so your fillToColor will also be adjusted by up to -10 and +10 depending on how far it is.
    ///         If you want to just have a single to color replace all colors in the from range, however, just set
    ///         preserveGradientsWithTolerance to false
    ///     </para>
    /// </summary>
    public static Texture2D FloodFill (
        Texture2D sourceImage,
        Vector2 startPosition,
        Color32 fillFromColor,
        Color32 fillToColor,
        int colorTolerance = 0,
        bool preserveGradientsWithTolerance = true)
    {
        // Cache these size properties in local variables for a slight performance boost, as it costs
        // less to read from a local variable than to get the property more than once
        int sourceImageWidth = sourceImage.width;
        int sourceImageHeight = sourceImage.height;

        // Now we read in the pixels as colors into an array for processing
        Color32 [] imageColors = sourceImage.GetPixels32 ();

        // Although the image is 2D, the array we read the pixels into is single dimension.
        // We need a way to take the horizontal X position of the point and the vertical Y position of the point
        // and find the one-dimensional index that corresponds to that pixel in the array.
        // In Unity, note also that vertical points usually start at the bottom, so 0,0 would be the bottom left
        // Imagine in the image that each horizontal line has "width" number of pixels, and there are "height"
        // number of these lines in the image, going from the bottom to the the top.
        // So if we multiply the Y value by the width, we get the starting index of the first X pixel on that
        // vertical line.  Say our image is 100*100.  For Y=0, the first pixel is 0, for Y=1 the first pixel is
        // 100, then Y=2 is 200, and so on.  Then we *add* the X position to that to get the final index,
        // so for X=0,Y=2 we get 200, for X=1,Y=2 we get 201, all the way over to X=99,Y=2 is 299, and then it
        // moves on to the next line, so X=0,Y=3 is 300 for the index to that point in the array
        int startIndex = (int) startPosition.y * sourceImageWidth + (int) startPosition.x;

        // We are optionally going to adjust these values, so cache them here
        Color32 minColorRange = fillFromColor;
        Color32 maxColorRange = fillFromColor;

        // When the color tolerance is set to a non zero value, that means we want to look to either side of
        // the from color by that amount.  In Unity, the Color32 struct uses byte values from 0-255 for
        // the Red, Green, Blue, and Alpha values (we are ignoring alpha in this function).
        // So all we do here is change the min (by subtracting tolerance) and max (by adding tolerance)
        // values, and then clamping them with the math functions to make sure they stay between 0 and 255
        if (colorTolerance != 0)
        {
            minColorRange.r = (byte) Mathf.Max (fillFromColor.r - colorTolerance, 0);
            minColorRange.g = (byte) Mathf.Max (fillFromColor.g - colorTolerance, 0);
            minColorRange.b = (byte) Mathf.Max (fillFromColor.b - colorTolerance, 0);
            maxColorRange.r = (byte) Mathf.Min (fillFromColor.r + colorTolerance, 255);
            maxColorRange.g = (byte) Mathf.Min (fillFromColor.g + colorTolerance, 255);
            maxColorRange.b = (byte) Mathf.Min (fillFromColor.b + colorTolerance, 255);
        }

        // This calls a second function to make sure the color that sits on the pixel where the start position was
        // mapped to in the array is actually within the color range we want.
        // So if your from color is white but the pixel under your start position is actually black, it will return
        // an error.  If you have a tolerance value and the pixel is nearly white and within the tolerance, it will pass
        if (!IsColorWithinTolerance (imageColors [startIndex], minColorRange, maxColorRange))
        {
            Debug.Log ("Start location index " + startIndex + " does not contain the old color to be replaced; " +
                       "expected range " + minColorRange + " to " + maxColorRange + " but got " + imageColors [startIndex]);
            return sourceImage;
        }

        // Now we get to the meat of the processing.
        // We want to start from the start position and then progressively look up, down, left, and right by one pixel
        // If that pixel is within our from color range, and has not been previously processed, then we want to add
        // it to our set of pixels to be processed.  We don't need to consider diagonals because, for example, if the
        // pixel above our current pixel is valid, then when that pixel gets assessed, the pixel to its left will be
        // checked, and that pixel corresponds to the diagonally up-and-left pixel of the one we are currently on.
        // In that way, the 4-way flood fill will check every pixel until it finds a border that is no longer valid
        // within the from color range, and when there are no pixels left to check, then it has completed the fill.

        // The best data structure to handle this recording of which pixel indexes are flagged to be checked is a Queue.
        // Queues in C# are first-in-first-out (or FIFO) which means that if I have a Queue of int and I pass in
        // first 1, then 3, then 2 (adding to a queue is called "enqueueing") and then dequeue three times, I will
        // get them back in the order 1, then 3, then 2.
        // This differs to a Stack which is last-in-first-out (LIFO), where "pushing" 1, then 3, then 2 would get
        // "popped" back as 2, then 3, then 1.
        Queue<int> floodQueue = new Queue<int> ();

        // For keeping track of which indexes we have already processed (to avoid doing extra work) a HashSet is the
        // best data structure.  This is much faster for looking up values than say a List, as it doesn't need to
        // store the order of the values.  It also doesn't care about duplicate values, although that isn't important here
        HashSet<int> floodDone = new HashSet<int> ();

        // To kick off the loop, first we add the start index we derived earlier that corresponds to the start position.
        // We add this to the queue as the first index to be flagged for checking, and also the done set since we
        // already know from before that it is within the color range
        floodQueue.Enqueue (startIndex);
        floodDone.Add (startIndex);

        // This while loop will continue until nothing left to check is in the queue.
        // When we first come here, the start index enqueued above is the only item present, but as we keep looking
        // to the sides, then the queue will grow, and will only start to shrink once we begin hitting borders
        // where no new indexes to check are getting added
        while (floodQueue.Count > 0)
        {
            // Dequeue takes the next queued index and removes it from the queue
            int currentIndex = floodQueue.Dequeue ();

            // This is the reverse of the formula earlier on where we calculated the index from the point;
            // in these two lines, we are calculating the X,Y position values of the pixel that correspond
            // to the integer index.  So we divide by width this time to get back to the Y vertical line,
            // and we also use a math floor operation (removes the decimal, so say 1.63 becomes 1), and then
            // calculate the X value in a similar way by removing all the vertical lines worth of indexes from
            // the value until only the X position remains
            int currentY = Mathf.FloorToInt ((float) currentIndex / sourceImageHeight);
            int currentX = currentIndex - currentY * sourceImageHeight;

            if (colorTolerance == 0 || !preserveGradientsWithTolerance)
            {
                // If tolerance is not being used then we can just set the to color straight away
                imageColors [currentIndex] = fillToColor;
            }
            else
            {
                // Otherwise, we want to apply the same gradient difference that was present in the from value
                // For example with tolerance of 10 again, if our from was Red 127/Green 66/Blue 32 and the to
                // color was Red 88/Green 88/Blue 88, and the color of this pixel happens to be Red 127/Green 60/Blue 32
                // (a Green difference of -6, so within the tolerance of +-10) then our new color will be set as
                // a gradient-adjusted value of Red 88/Green 82/Blue 88.
                // Alpha is just set to the same as the original, and not adjusted for gradient, although you could
                // put that in if you wanted
                imageColors [currentIndex].r = (byte) Mathf.Clamp (fillToColor.r + (imageColors [currentIndex].r - fillFromColor.r), 0, 255);
                imageColors [currentIndex].g = (byte) Mathf.Clamp (fillToColor.g + (imageColors [currentIndex].g - fillFromColor.g), 0, 255);
                imageColors [currentIndex].b = (byte) Mathf.Clamp (fillToColor.b + (imageColors [currentIndex].b - fillFromColor.b), 0, 255);
                imageColors [currentIndex].a = fillToColor.a;
            }

            // Now that the current pixel is processed, we want to check the neighbours on all four sides

            // Up - only process if we are on Y=1 or higher, because when Y=0, there is no valid Y-1 to use
            // Remember also the weird convention that Unity starts at 0,0 in bottom left, so technically
            // this is more like a downwards in terms of eyeball visualising of the direction, but that doesn't matter
            if (currentY > 0)
            {
                // To calculate the correct index of the pixel above this one, we just add the unchanged X
                // to the start of the line at Y-1, using the same formula as before
                int testIndex = (currentY - 1) * sourceImageWidth + currentX;

                // If that neighbouring pixel has been previously processed, then skip any further work
                if (!floodDone.Contains (testIndex))
                {
                    // Otherwise check it using the shared function below to see if the new pixel
                    // is within the from tolerance range
                    if (IsColorWithinTolerance (imageColors [testIndex], minColorRange, maxColorRange))
                    {
                        // And if it is, enqueue it for processing in some later iteration of the while loop
                        floodQueue.Enqueue (testIndex);
                    }

                    // Whether or not the pixel was flagged for processing, we are done with checking it, so
                    // add it to the set of indexes not to be processed again
                    floodDone.Add (testIndex);
                }
            }

            // Down - this is the same as before, although this time we only process if we are at least 1
            // away from the last Y row of the image, i.e. height minus 1, since last Y + 1 would not be valid
            if (currentY < sourceImageHeight - 1)
            {
                // All of this is as before, only this time we add a row
                int testIndex = (currentY + 1) * sourceImageWidth + currentX;
                if (!floodDone.Contains (testIndex))
                {
                    if (IsColorWithinTolerance (imageColors [testIndex], minColorRange, maxColorRange))
                    {
                        floodQueue.Enqueue (testIndex);
                    }

                    floodDone.Add (testIndex);
                }
            }

            // Left - similarly to Up, we only check from X=1 or greater, because X=0 - 1 would be invalid
            if (currentX > 0)
            {
                // This time the formula is taking the unchanged Y and adding X - 1 to that to get
                // the index of the pixel to the left
                int testIndex = currentY * sourceImageWidth + (currentX - 1);
                if (!floodDone.Contains (testIndex))
                {
                    if (IsColorWithinTolerance (imageColors [testIndex], minColorRange, maxColorRange))
                    {
                        floodQueue.Enqueue (testIndex);
                    }

                    floodDone.Add (testIndex);
                }
            }

            // Right - again, similar to Down, we check to make sure it's not the last X value on the
            // current Y line, as X=last + 1 would be invalid
            if (currentX < sourceImageWidth - 1)
            {
                int testIndex = currentY * sourceImageWidth + currentX + 1;
                if (!floodDone.Contains (testIndex))
                {
                    if (IsColorWithinTolerance (imageColors [testIndex], minColorRange, maxColorRange))
                    {
                        floodQueue.Enqueue (testIndex);
                    }

                    floodDone.Add (testIndex);
                }
            }
        }

        // Finally, we have exited the while loop as there are no more indexes to check, so we know
        // we have successfully altered all of the color values in the array that matched the flood fill.
        // The last thing to do is copy these back from the array to the actual pixels in the resulting image.
        // First make a copy of the texture with the same size and image format as the original, with mip-maps turned off
        // as those can cause the fill to have weird artifacts, and force the format to RGBA32 so we get
        // the right copied alpha values as well.
        // This first line creates a blank texture of the right settings
        Texture2D result = new Texture2D (sourceImageWidth, sourceImageHeight, TextureFormat.RGBA32, false);

        // And then this line copies the actual changed pixel data from the color array to the new image
        result.SetPixels32 (imageColors);

        // When you "set" something in a texture, you need to do an Apply to "save" the changes
        result.Apply ();

        // Finally, we return the altered texture!
        return result;
    }

    private static bool IsColorWithinTolerance (Color32 checkColor, Color32 minColor, Color32 maxColor)
    {
        // All this does is check to make sure each channel (Red, Green, and Blue) is greater than or equal
        // to the min range value derived earlier (or is an exact match, if tolerance was 0) and less than or
        // equal to the max range value.  If all channels fit within those range values, it will be true
        return checkColor.r >= minColor.r &&
               checkColor.g >= minColor.g &&
               checkColor.b >= minColor.b &&
               checkColor.r <= maxColor.r &&
               checkColor.g <= maxColor.g &&
               checkColor.b <= maxColor.b;
    }
}