Click here to Skip to main content
12,943,528 members (45,789 online)
Click here to Skip to main content
Add your own
alternative version

Stats

288K views
7.4K downloads
57 bookmarked
Posted 15 Nov 2006

Queue-Linear Flood Fill: A Fast Flood Fill Algorithm

, 15 Nov 2006
Rate this:
Please Sign up or sign in to vote.
A super-fast flood fill algorithm and implementation, plus helpful optimization tips for image processing.
[Images in the demo are copyrighted by the author of the article - please do not publish or redistribute outside of CodeProject without permission.]

Sample Image - queuelinearfloodfill.png

Introduction

In a previous article I wrote several years ago, Floodfill Algorithms in C# and GDI+, I presented several different flood fill algorithms, and described the differences between them. In this article, I present a single, highly optimized flood fill algorithm, which I call the Queue-Linear algorithm.

This algorithm combines the strengths of both the Queue and Linear algorithms, but has none of the weaknesses. It is very fast, and at the same time, does not succumb to stack overflows, no matter how big the bitmap being processed is. In my tests, my optimized implementation filled an area covering most of a 12.5 megapixel bitmap in about 750ms on a 1.67 GHZ Athlon processor, faster than any other flood fill implementation that I have seen in action.

The Algorithm

The Queue-Linear algorithm is implemented in two parts. The first part, contained in the FloodFill() method in the sample code, prepares all necessary data, and then calls the second part, contained in the QueueLinearFloodFill4() method, for the first time, passing it the coordinates of the starting point.

Figure 1

The QueueLinearFloodFill4() method finds the furthest extent of the flood fill area to the left and right of the x coordinate passed to it, on the scanline specified by the y coordinate. As it checks to the left and right, it fills the area it has checked. It then adds this horizontal range to a queue of ranges to branch up and down from, and returns.

Figure 2

After the FloodFill() method calls LinearFill() for the first time, it enters a loop. The code in the loop dequeues the next flood fill range off the queue, and moves from left to right along the horizontal range, checking each pixel directly above and below the range. For each pixel that matches the starting color closely enough, it calls LinearFill(), which builds a flood fill range starting from that pixel and adds it to the queue, as detailed previously. This process is repeated until the queue is empty.

Since this implementation does not restrict the fill to pixels that exactly match the starting pixel, but instead fills all pixels that are within an adjustable tolerance range, we cannot assume that if a pixel exactly matches the start color, that pixel has already been processed. Therefore, we must keep track of which pixels have already been processed, and treat those pixels as if they are not within the tolerance range, to prevent an endless loop. The best way to do this is via a one-dimensional boolean array, whose length is equal to the number of pixels in the bitmap. (A bit array could be used; however, it would cause a significant decrease in speed.)

Implementation

Just as with the previous article, the sample application for this article allows you to open a bitmap, adjust the fill tolerance, set the fill color, fill anywhere in the bitmap, and save the resulting bitmap to a file. You can also watch the fill occurring in real time. I have not implemented 8-directional fill in this article's sample, but it would be simple to add should you desire it.

There are two flood filler classes in this sample. UnsafeQueueLinearFloodFiller uses the LockBits() method and pointers to perform the image manipulation, and QueueLinearFloodFiller uses the method detailed in my article, Fast Pointerless Image Manipulation in .NET. This allows you to compare the speed of the two methods. Switch between methods via the combo box on the top left corner of the form.

The Code

The following is the code for the algorithm. The FloodFill() method fills an area starting from a given point. The LinearFill() method is used by the FloodFill() method to get the furthest extent of the color area on a given horizontal scanline, filling as it goes, and then add the horizontal range to the queue.

/// <summary>
/// Fills the specified point on the bitmap with the currently selected 
/// fill color.
/// </summary>
/// <param name="pt">The starting point for the fill.</param>
public override void FloodFill(System.Drawing.Point pt)
{
    //***Prepare for fill.
    PrepareForFloodFill(pt);

    ranges = new FloodFillRangeQueue(((bitmapWidth+bitmapHeight)/2)*5;
    //***Get starting color.
    int x = pt.X; int y = pt.Y;
    int idx = CoordsToByteIndex(ref x, ref y);
    startColor = new byte[] { bitmap.Bits[idx], bitmap.Bits[idx + 1], 
                        bitmap.Bits[idx + 2] };

    bool[] pixelsChecked=this.pixelsChecked;

    //***Do first call to floodfill.
    LinearFill(ref x, ref y);

    //***Call floodfill routine while floodfill ranges still exist 
    //on the queue
    while (ranges.Count > 0)
    {
        //**Get Next Range Off the Queue
        FloodFillRange range = ranges.Dequeue();

        //**Check Above and Below Each Pixel in the Floodfill Range
        int downPxIdx = (bitmapWidth * (range.Y + 1)) + range.StartX;
                    //CoordsToPixelIndex(lFillLoc,y+1);
        int upPxIdx = (bitmapWidth * (range.Y - 1)) + range.StartX;
                    //CoordsToPixelIndex(lFillLoc, y - 1);
        int upY=range.Y - 1;//so we can pass the y coord by ref
        int downY = range.Y + 1;
        int tempIdx;
        for (int i = range.StartX; i <= range.EndX; i++)
        {
            //*Start Fill Upwards
            //if we're not above the top of the bitmap and the pixel 
        //above this one is within the color tolerance
            tempIdx = CoordsToByteIndex(ref i, ref upY);
            if (range.Y > 0 && (!pixelsChecked[upPxIdx]) && 
                    CheckPixel(ref tempIdx))
                LinearFill(ref i, ref upY);

            //*Start Fill Downwards
            //if we're not below the bottom of the bitmap and 
        //the pixel below this one is
            //within the color tolerance
            tempIdx = CoordsToByteIndex(ref i, ref downY);
            if (range.Y < (bitmapHeight - 1) && (!pixelsChecked[downPxIdx]) 
                        && CheckPixel(ref tempIdx))
                LinearFill(ref i, ref downY);
            downPxIdx++;
            upPxIdx++;
        }

    }
}

/// <summary>
/// Finds the furthermost left and right boundaries of the fill area
/// on a given y coordinate, starting from a given x coordinate, 
/// filling as it goes.
/// Adds the resulting horizontal range to the queue of floodfill ranges,
/// to be processed in the main loop.
/// </summary>
/// <param name="x">The x coordinate to start from.</param>
/// <param name="y">The y coordinate to check at.</param>
void LinearFill(ref int x, ref int y)
{
   //cache some bitmap and fill info in local variables for 
   //a little extra speed
   byte[] bitmapBits=this.bitmapBits;
   bool[] pixelsChecked=this.pixelsChecked;
   byte[] byteFillColor= this.byteFillColor;
   int bitmapPixelFormatSize=this.bitmapPixelFormatSize;
   int bitmapWidth=this.bitmapWidth;

    //***Find Left Edge of Color Area
    int lFillLoc = x; //the location to check/fill on the left
    int idx = CoordsToByteIndex(ref x, ref y); 
                //the byte index of the current location
    int pxIdx = (bitmapWidth * y) + x;//CoordsToPixelIndex(x,y);
    while (true)
    {
        //**fill with the color
        bitmapBits[idx] = byteFillColor[0];
        bitmapBits[idx+1] = byteFillColor[1];
        bitmapBits[idx+2] = byteFillColor[2];
        //**indicate that this pixel has already been checked and filled
        pixelsChecked[pxIdx] = true;
        //**screen update for 'slow' fill
        if (slow) UpdateScreen(ref lFillLoc, ref y);
        //**de-increment
        lFillLoc--;     //de-increment counter
        pxIdx--;        //de-increment pixel index
        idx -= bitmapPixelFormatSize;//de-increment byte index
        //**exit loop if we're at edge of bitmap or color area
        if (lFillLoc <= 0 || (pixelsChecked[pxIdx]) || !CheckPixel(ref idx))
            break;

    }
    lFillLoc++;

    //***Find Right Edge of Color Area
    int rFillLoc = x; //the location to check/fill on the left
    idx = CoordsToByteIndex(ref x, ref y);
    pxIdx = (bitmapWidth * y) + x;
    while (true)
    {
        //**fill with the color
        bitmapBits[idx] = byteFillColor[0];
        bitmapBits[idx + 1] = byteFillColor[1];
        bitmapBits[idx + 2] = byteFillColor[2];
        //**indicate that this pixel has already been checked and filled
        pixelsChecked[pxIdx] = true;
        //**screen update for 'slow' fill
        if (slow) UpdateScreen(ref rFillLoc, ref y);
        //**increment
        rFillLoc++;     //increment counter
        pxIdx++;        //increment pixel index
        idx += bitmapPixelFormatSize;//increment byte index
        //**exit loop if we're at edge of bitmap or color area
        if (rFillLoc >= bitmapWidth || pixelsChecked[pxIdx] || 
                        !CheckPixel(ref idx))
            break;

    }
    rFillLoc--;

   //add range to queue
   FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
   ranges.Enqueue(ref r);
}

Optimization

I have implemented many optimizations in my code to increase performance. These optimizations are useful in other image processing routines as well, so I will discuss some of them here.

Cache bitmap properties

Most properties on the Bitmap class directly or indirectly call the GDI+ API via P/Invoke. If you need to reference these properties often in a performance-critical operation, your code will take a serious performance hit. Therefore, you should cache these properties at the beginning of the operation, and reference the cached version only during the operation.

Store non-call-specific data at class level

Reduced stack space means better performance, so this can be very helpful if your class will not be accessed by multiple threads simultaneously.

Pass value-type arguments to methods by reference where possible

When you repeatedly call a method with value-type parameters passed 'byval', space is allocated for those parameters and the parameters are copied on each call. When I was experimenting with my old 'linear' flood fill algorithm, I found that by passing all possible parameters by reference, I gained a 15% speed increase.

Use a profiler to help you pinpoint bottlenecks

A profiler can catch many things that you may not recognize as bottlenecks. For example, I had originally used a struct with properties to store the tolerance values for the flood filler, but when I checked my code with VS.NET 2005's built-in profiler, I discovered that it caused a 10% performance decrease compared to a simple byte array. A profiler can also save you time in a different way – by helping you to not waste time optimizing in places where it isn't really needed.

Pay attention to the performance implications of everything you do

Sadly, since .NET frees you up from many low-level aspects of programming, many .NET developers do not pay enough attention to the performance and memory aspects of their code. .NET is plenty fast enough for performance-critical code in most cases, as long as developers pay attention to how they code. So even if you don't have to think about the performance implications of what your code does, do it anyway – it's worth it! This article is a good read to start with.

Notes

To see the highest performance in the demo, use the release configuration, not the debug configuration. The "binaries" download contains binaries built with the release configuration.

You haven't properly seen the flood fill algorithm in action until you try it out with a large bitmap. A large bitmap is not included in the download in order to reduce download speed, but you can try it with a picture from a good-quality digital camera if you have one available.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

J. Dunlap
Web Developer
United States United States
My main goal as a developer is to improve the way software is designed, and how it interacts with the user. I like designing software best, but I also like coding and documentation. I especially like to work with user interfaces and graphics.

I have extensive knowledge of the .NET Framework, and like to delve into its internals. I specialize in working with VG.net and MyXaml. I also like to work with ASP.NET, AJAX, and DHTML.

You may also be interested in...

Comments and Discussions

 
GeneralThanks, great article and algorithm, adding a Java port Pin
Ozone7719-Jun-08 19:14
memberOzone7719-Jun-08 19:14 
GeneralRe: Thanks, great article and algorithm, adding a Java port Pin
Joel R. Becker18-Apr-09 5:48
memberJoel R. Becker18-Apr-09 5:48 
QuestionNice work Pin
bulupe12-Sep-07 5:48
memberbulupe12-Sep-07 5:48 
GeneralSomething to consider for the unmanaged code Pin
reinux26-Aug-07 13:05
memberreinux26-Aug-07 13:05 
GeneralA Little Bug Pin
hankhuf7-Aug-07 11:30
memberhankhuf7-Aug-07 11:30 
GeneralRe: A Little Bug Pin
GuavamanX14-Feb-14 21:07
memberGuavamanX14-Feb-14 21:07 
GeneralAwesome Article! Pin
STLMike13-Jul-07 22:17
memberSTLMike13-Jul-07 22:17 
GeneralRe: Awesome Article! Pin
ttxT14-Oct-07 18:41
memberttxT14-Oct-07 18:41 
I've adapted the code a bit to wrap in a single unit (hope the author doesn't mind!), I think it will do what you want.

To use:

Bitmap bitmap = new Bitmap("MyBitmap.bmp");
FloodFiller ff = new FloodFiller();
bitmap = ff.FloodFillBitmap(bitmap, new Point(58, 51), Color.Red);


Bruce

----------------------------

using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Drawing.Imaging;
using System.Collections.ObjectModel;

namespace FloodFillClasses
{

public class FloodFiller
{
protected AbstractFloodFiller ff;

public Bitmap FloodFillBitmap(Bitmap bm, Point p, Color c)
{
if ((bm == null) || (p == null)) return null;

ff = new QueueLinearFloodFiller(ff);

ff.FillColor = c;
ff.Tolerance[0] = (byte)5;
ff.Tolerance[1] = (byte)5;
ff.Tolerance[2] = (byte)5;

ff.Bitmap = new EditableBitmap(bm, PixelFormat.Format32bppArgb);
ff.FloodFill(p);
return ff.Bitmap.Bitmap;

}

}

/// <summary>
///
///
/// <param name="x">
/// <param name="y">
public delegate void UpdateScreenDelegate(ref int x, ref int y);

/// <summary>
/// The base class that the flood fill algorithms inherit from. Implements the
/// basic flood filler functionality that is the same across all algorithms.
///
public abstract class AbstractFloodFiller
{

protected EditableBitmap bitmap;
protected byte[] tolerance = new byte[] { 25, 25, 25 };
protected Color fillColor = Color.Magenta;
protected bool fillDiagonally = false;
protected bool slow = false;

//cached bitmap properties
protected int bitmapWidth = 0;
protected int bitmapHeight = 0;
protected int bitmapStride = 0;
protected int bitmapPixelFormatSize = 0;
protected byte[] bitmapBits = null;

//internal int timeBenchmark = 0;
internal Stopwatch watch = new Stopwatch();
internal UpdateScreenDelegate UpdateScreen;

//internal, initialized per fill
//protected BitArray pixelsChecked;
protected bool[] pixelsChecked;
protected byte[] byteFillColor;
protected byte[] startColor;
//protected int stride;

public AbstractFloodFiller()
{

}

public AbstractFloodFiller(AbstractFloodFiller configSource)
{
if (configSource != null)
{
this.Bitmap = configSource.Bitmap;
this.FillColor = configSource.FillColor;
this.FillDiagonally = configSource.FillDiagonally;
this.Slow = configSource.Slow;
this.Tolerance = configSource.Tolerance;
}
}

public bool Slow
{
get { return slow; }
set { slow = value; }
}

public Color FillColor
{
get { return fillColor; }
set { fillColor = value; }
}

public bool FillDiagonally
{
get { return fillDiagonally; }
set { fillDiagonally = value; }
}

public byte[] Tolerance
{
get { return tolerance; }
set { tolerance = value; }
}

public EditableBitmap Bitmap
{
get { return bitmap; }
set
{
bitmap = value;
}
}

public abstract void FloodFill(Point pt);

protected void PrepareForFloodFill(Point pt)
{
//cache data in member variables to decrease overhead of property calls
//this is especially important with Width and Height, as they call
//GdipGetImageWidth() and GdipGetImageHeight() respectively in gdiplus.dll -
//which means major overhead.
byteFillColor = new byte[] { fillColor.B, fillColor.G, fillColor.R };
bitmapStride = bitmap.Stride;
bitmapPixelFormatSize = bitmap.PixelFormatSize;
bitmapBits = bitmap.Bits;
bitmapWidth = bitmap.Bitmap.Width;
bitmapHeight = bitmap.Bitmap.Height;

pixelsChecked = new bool[bitmapBits.Length / bitmapPixelFormatSize];
}
}

/// <summary>A queue of FloodFillRanges.
public class FloodFillRangeQueue
{
FloodFillRange[] array;
int size;
int head;

/// <summary>
/// Returns the number of items currently in the queue.
///
public int Count
{
get { return size; }
}

public FloodFillRangeQueue()
: this(10000)
{

}

public FloodFillRangeQueue(int initialSize)
{
array = new FloodFillRange[initialSize];
head = 0;
size = 0;
}

/// <summary>Gets the <see cref="FloodFillRange"/> at the beginning of the queue.
public FloodFillRange First
{
get { return array[head]; }
}

/// <summary>Adds a <see cref="FloodFillRange"/> to the end of the queue.
public void Enqueue(ref FloodFillRange r)
{
if (size + head == array.Length)
{
FloodFillRange[] newArray = new FloodFillRange[2 * array.Length];
Array.Copy(array, head, newArray, 0, size);
array = newArray;
head = 0;
}
array[head + (size++)] = r;
}

/// <summary>Removes and returns the <see cref="FloodFillRange"/> at the beginning of the queue.
public FloodFillRange Dequeue()
{
FloodFillRange range = new FloodFillRange();
if (size > 0)
{
range = array[head];
array[head] = new FloodFillRange();
head++;//advance head position
size--;//update size to exclude dequeued item
}
return range;
}

/// <summary>Remove all FloodFillRanges from the queue.
/*public void Clear()
{
if (size > 0)
Array.Clear(array, 0, size);
size = 0;
}*/

}

/// <summary>
/// Implements the QueueLinear flood fill algorithm using array-based pixel manipulation.
///
public class QueueLinearFloodFiller : AbstractFloodFiller
{

//Queue of floodfill ranges. We use our own class to increase performance.
//To use .NET Queue class, change this to:
//<floodfillrange> ranges = new Queue<floodfillrange>();
FloodFillRangeQueue ranges = new FloodFillRangeQueue();

public QueueLinearFloodFiller(AbstractFloodFiller configSource) : base(configSource) { }

/// <summary>
/// Fills the specified point on the bitmap with the currently selected fill color.
///
/// <param name="pt">The starting point for the fill.
public override void FloodFill(System.Drawing.Point pt)
{
watch.Reset();
watch.Start();

//***Prepare for fill.
PrepareForFloodFill(pt);

ranges = new FloodFillRangeQueue(((bitmapWidth + bitmapHeight) / 2) * 5);//new Queue<floodfillrange>();

//***Get starting color.
int x = pt.X; int y = pt.Y;
int idx = CoordsToByteIndex(ref x, ref y);
startColor = new byte[] { bitmap.Bits[idx], bitmap.Bits[idx + 1], bitmap.Bits[idx + 2] };

bool[] pixelsChecked = this.pixelsChecked;

//***Do first call to floodfill.
LinearFill(ref x, ref y);

//***Call floodfill routine while floodfill ranges still exist on the queue
while (ranges.Count > 0)
{
//**Get Next Range Off the Queue
FloodFillRange range = ranges.Dequeue();

//**Check Above and Below Each Pixel in the Floodfill Range
int downPxIdx = (bitmapWidth * (range.Y + 1)) + range.StartX;//CoordsToPixelIndex(lFillLoc,y+1);
int upPxIdx = (bitmapWidth * (range.Y - 1)) + range.StartX;//CoordsToPixelIndex(lFillLoc, y - 1);
int upY = range.Y - 1;//so we can pass the y coord by ref
int downY = range.Y + 1;
int tempIdx;
for (int i = range.StartX; i <= range.EndX; i++)
{
//*Start Fill Upwards
//if we're not above the top of the bitmap and the pixel above this one is within the color tolerance
tempIdx = CoordsToByteIndex(ref i, ref upY);
if (range.Y > 0 && (!pixelsChecked[upPxIdx]) && CheckPixel(ref tempIdx))
LinearFill(ref i, ref upY);

//*Start Fill Downwards
//if we're not below the bottom of the bitmap and the pixel below this one is within the color tolerance
tempIdx = CoordsToByteIndex(ref i, ref downY);
if (range.Y < (bitmapHeight - 1) && (!pixelsChecked[downPxIdx]) && CheckPixel(ref tempIdx))
LinearFill(ref i, ref downY);
downPxIdx++;
upPxIdx++;
}

}

watch.Stop();
}

/// <summary>
/// Finds the furthermost left and right boundaries of the fill area
/// on a given y coordinate, starting from a given x coordinate, filling as it goes.
/// Adds the resulting horizontal range to the queue of floodfill ranges,
/// to be processed in the main loop.
///
/// <param name="x">The x coordinate to start from.
/// <param name="y">The y coordinate to check at.
void LinearFill(ref int x, ref int y)
{

//cache some bitmap and fill info in local variables for a little extra speed
byte[] bitmapBits = this.bitmapBits;
bool[] pixelsChecked = this.pixelsChecked;
byte[] byteFillColor = this.byteFillColor;
int bitmapPixelFormatSize = this.bitmapPixelFormatSize;
int bitmapWidth = this.bitmapWidth;

//***Find Left Edge of Color Area
int lFillLoc = x; //the location to check/fill on the left
int idx = CoordsToByteIndex(ref x, ref y); //the byte index of the current location
int pxIdx = (bitmapWidth * y) + x;//CoordsToPixelIndex(x,y);
while (true)
{
//**fill with the color
bitmapBits[idx] = byteFillColor[0];
bitmapBits[idx + 1] = byteFillColor[1];
bitmapBits[idx + 2] = byteFillColor[2];
//**indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
//**screen update for 'slow' fill
if (slow) UpdateScreen(ref lFillLoc, ref y);
//**de-increment
lFillLoc--; //de-increment counter
pxIdx--; //de-increment pixel index
idx -= bitmapPixelFormatSize;//de-increment byte index
//**exit loop if we're at edge of bitmap or color area
if (lFillLoc <= 0 || (pixelsChecked[pxIdx]) || !CheckPixel(ref idx))
break;

}
lFillLoc++;

//***Find Right Edge of Color Area
int rFillLoc = x; //the location to check/fill on the left
idx = CoordsToByteIndex(ref x, ref y);
pxIdx = (bitmapWidth * y) + x;
while (true)
{
//**fill with the color
bitmapBits[idx] = byteFillColor[0];
bitmapBits[idx + 1] = byteFillColor[1];
bitmapBits[idx + 2] = byteFillColor[2];
//**indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
//**screen update for 'slow' fill
if (slow) UpdateScreen(ref rFillLoc, ref y);
//**increment
rFillLoc++; //increment counter
pxIdx++; //increment pixel index
idx += bitmapPixelFormatSize;//increment byte index
//**exit loop if we're at edge of bitmap or color area
if (rFillLoc >= bitmapWidth || pixelsChecked[pxIdx] || !CheckPixel(ref idx))
break;

}
rFillLoc--;

//add range to queue
FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
ranges.Enqueue(ref r);
}

///<summary>Sees if a pixel is within the color tolerance range.
///<param name="px">The byte index of the pixel to check, passed by reference to increase performance.
protected bool CheckPixel(ref int px)
{
//tried a 'for' loop but it adds an 8% overhead to the floodfill process
/*bool ret = true;
for (byte i = 0; i < 3; i++)
{
ret &= (bitmap.Bits[px] >= (startColor[i] - tolerance[i])) && bitmap.Bits[px] <= (startColor[i] + tolerance[i]);
px++;
}
return ret;*/

return (bitmapBits[px] >= (startColor[0] - tolerance[0])) && bitmapBits[px] <= (startColor[0] + tolerance[0]) &&
(bitmapBits[px + 1] >= (startColor[1] - tolerance[1])) && bitmapBits[px + 1] <= (startColor[1] + tolerance[1]) &&
(bitmapBits[px + 2] >= (startColor[2] - tolerance[2])) && bitmapBits[px + 2] <= (startColor[2] + tolerance[2]);
}

///<summary>Calculates and returns the byte index for the pixel (x,y).
///<param name="x">The x coordinate of the pixel whose byte index should be returned.
///<param name="y">The y coordinate of the pixel whose byte index should be returned.
protected int CoordsToByteIndex(ref int x, ref int y)
{
return (bitmapStride * y) + (x * bitmapPixelFormatSize);
}

/// <summary>
/// Returns the linear index for a pixel, given its x and y coordinates.
///
/// <param name="x">The x coordinate of the pixel.
/// <param name="y">The y coordinate of the pixel.
/// <returns>
protected int CoordsToPixelIndex(int x, int y)
{
return (bitmapWidth * y) + x;
}

}

/// <summary>
/// Represents a linear range to be filled and branched from.
///
public struct FloodFillRange
{
public int StartX;
public int EndX;
public int Y;

public FloodFillRange(int startX, int endX, int y)
{
StartX = startX;
EndX = endX;
Y = y;
}
}

public class EditableBitmap : IDisposable
{
Bitmap bitmap;
int stride;
int pixelFormatSize;

SharedPinnedByteArray byteArray;

/// <summary>
/// Gets the pixel format size in bytes (not bits, as with Image.GetPixelFormatSize()).
///
public int PixelFormatSize
{
get { return pixelFormatSize; }
}

/// <summary>
/// Gets the stride of the bitmap.
///
public int Stride
{
get { return stride; }
}

/// <summary>
/// Gets the underlying <see cref="System.Drawing.Bitmap"/>
/// that this EditableBitmap wraps.
///
public Bitmap Bitmap
{
get { return bitmap; }
set { bitmap = value; }
}

/// <summary>
/// Gets an array that contains the bitmap bit buffer.
///
public byte[] Bits
{
get { return byteArray.bits; }
}

private EditableBitmap owner;

/// <summary>
/// The <see cref="EditableBitmap"/> that this <see cref="EditableBitmap"/> is a view on.
/// This property's value will be null if this EditableBitmap is not a view on another
/// <see cref="EditableBitmap"/>.
///
public EditableBitmap Owner
{
get { return owner; }
}


/// <summary>
/// Gets a safe pointer to the buffer containing the bitmap bits.
///
public IntPtr BitPtr
{
get
{
return byteArray.bitPtr;
}
}

/// <summary>
/// Creates a new EditableBitmap with the specified pixel format,
/// and copies the bitmap passed in onto the buffer.
///
/// <param name="source">The bitmap to copy from.
/// <param name="format">The PixelFormat for the new bitmap.
public EditableBitmap(Bitmap source, PixelFormat format)
: this(source.Width, source.Height, format)
{
//NOTE: This ONLY preserves the first frame of the image.
//It does NOT copy EXIF properties, multiple frames, etc.
//In places where preserving them is necessary, it must
//be done manually.
Graphics g = Graphics.FromImage(bitmap);
g.DrawImageUnscaledAndClipped(source, new Rectangle(0, 0, source.Width, source.Height));
g.Dispose();
}

/// <summary>
/// Creates a new EditableBitmap with the specified pixel format and size,
/// and copies the bitmap passed in onto the buffer. The source bitmap is stretched to
/// fit the new size.
///
/// <param name="source">
/// <param name="format">
/// <param name="newWidth">
/// <param name="newHeight">
public EditableBitmap(Bitmap source, PixelFormat format, int newWidth, int newHeight)
: this(newWidth, newHeight, format)
{
//NOTE: This ONLY preserves the first frame of the image.
//It does NOT copy EXIF properties, multiple frames, etc.
//In places where preserving them is necessary, it must
//be done manually.
Graphics g = Graphics.FromImage(bitmap);
g.DrawImage(source, 0, 0, newWidth, newHeight);
g.Dispose();
}

/// <summary>
/// Creates a new EditableBitmap containing a copy of the specified source bitmap.
///
/// <param name="source">
public EditableBitmap(Bitmap source)
: this(source, source.PixelFormat)
{

}

/// <summary>
/// Creates a new, blank EditableBitmap with the specified width, height, and pixel format.
///
/// <param name="width">
/// <param name="height">
/// <param name="format">
public EditableBitmap(int width, int height, PixelFormat format)
{
pixelFormatSize = Image.GetPixelFormatSize(format) / 8;
stride = width * pixelFormatSize;
int padding = (stride % 4);
stride += padding == 0 ? 0 : 4 - padding;//pad out to multiple of 4
byteArray = new SharedPinnedByteArray(stride * height);
bitmap = new Bitmap(width, height, stride, format, byteArray.bitPtr);
}

#region View Support

/// <summary>
/// Creates an <see cref="EditableBitmap"/> as a view on a section of an existing <see cref="EditableBitmap"/>.
///
/// <param name="source">
/// <param name="viewArea">
protected EditableBitmap(EditableBitmap source, Rectangle viewArea)
{
owner = source;
pixelFormatSize = source.pixelFormatSize;
byteArray = source.byteArray;
byteArray.AddReference();
stride = source.stride;

try
{
startOffset = source.startOffset + (stride * viewArea.Y) + (viewArea.X * pixelFormatSize);
bitmap = new Bitmap(viewArea.Width, viewArea.Height, stride, source.Bitmap.PixelFormat,
(IntPtr)(((int)byteArray.bitPtr) + startOffset));
}
finally
{
if (bitmap == null)
byteArray.ReleaseReference();
}

}

/// <summary>
/// Creates an <see cref="EditableBitmap"/> as a view on a section of an existing <see cref="EditableBitmap"/>.
///
/// <param name="viewArea">The area that should form the bounds of the view.
public EditableBitmap CreateView(Rectangle viewArea)
{
if (disposed)
throw new ObjectDisposedException("this");
return new EditableBitmap(this, viewArea);
}

private int startOffset;

/// <summary>
/// If this <see cref="EditableBitmap"/> is a view on another <see cref="EditableBitmap"/> instance,
/// this property gets the index where the pixels that are within the view's pixel area start.
///
public int StartOffset
{
get { return startOffset; }
}

#endregion


private bool disposed;

public bool Disposed
{
get { return disposed; }
}


#region IDisposable Members

public void Dispose()
{
Dispose(true);
}

#endregion

protected void Dispose(bool disposing)
{
if (disposed)
return;

bitmap.Dispose();
byteArray.ReleaseReference();
disposed = true;

//Set managed object refs to null if explicitly disposing, so that they can be cleaned up by the GC.
if (disposing)
{
owner = null;
bitmap = null;
}
}

~EditableBitmap()
{
Dispose(false);
}
}

internal class SharedPinnedByteArray
{
internal byte[] bits;
internal GCHandle handle;
internal IntPtr bitPtr;

int refCount;

public SharedPinnedByteArray(int length)
{
bits = new byte[length];
// if not pinned the GC can move around the array
handle = GCHandle.Alloc(bits, GCHandleType.Pinned);
bitPtr = Marshal.UnsafeAddrOfPinnedArrayElement(bits, 0);
refCount++;
}

internal void AddReference()
{
refCount++;
}

internal void ReleaseReference()
{
refCount--;
if (refCount <= 0)
Destroy();
}

bool destroyed;
private void Destroy()
{
if (!destroyed)
{
handle.Free();
bits = null;
destroyed = true;
}
}

~SharedPinnedByteArray()
{
Destroy();
}
}


}
GeneralControl the Threashold Pin
fcis20076-Feb-07 6:22
memberfcis20076-Feb-07 6:22 
GeneralLicense Pin
Jonas Beckeman23-Jan-07 22:31
memberJonas Beckeman23-Jan-07 22:31 
GeneralVery nice! Thanks a lot!! Pin
eliran121-Nov-06 4:03
membereliran121-Nov-06 4:03 
GeneralI'm awestruck Pin
reinux15-Nov-06 23:03
memberreinux15-Nov-06 23:03 
GeneralRe: I'm awestruck Pin
J. Dunlap16-Nov-06 3:44
memberJ. Dunlap16-Nov-06 3:44 
GeneralRe: I'm awestruck Pin
reinux16-Nov-06 9:09
memberreinux16-Nov-06 9:09 
GeneralRe: I'm awestruck Pin
J. Dunlap16-Nov-06 21:47
memberJ. Dunlap16-Nov-06 21:47 
AnswerI'm less impressed Pin
Kodieropa16-Aug-07 5:23
memberKodieropa16-Aug-07 5:23 
GeneralRe: I'm less impressed Pin
reinux26-Aug-07 13:00
memberreinux26-Aug-07 13:00 
AnswerDifferent hardware [modified] Pin
Kodieropa30-Aug-07 10:20
memberKodieropa30-Aug-07 10:20 
GeneralRe: Different hardware Pin
reinux30-Aug-07 17:32
memberreinux30-Aug-07 17:32 
GeneralRe: I'm awestruck Pin
Frank Hileman16-Nov-06 4:42
memberFrank Hileman16-Nov-06 4:42 
GeneralRe: I'm awestruck Pin
J. Dunlap16-Nov-06 4:55
memberJ. Dunlap16-Nov-06 4:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170518.1 | Last Updated 15 Nov 2006
Article Copyright 2006 by J. Dunlap
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid