Click here to Skip to main content
Click here to Skip to main content
Articles » Multimedia » GDI+ » General » Downloads
 
Add your own
alternative version

Queue-Linear Flood Fill: A Fast Flood Fill Algorithm

, 15 Nov 2006
A super-fast flood fill algorithm and implementation, plus helpful optimization tips for image processing.
largepic.zip
poppy.JPG
queuelinearfloodfill_demo.zip
poppy_sm.jpg
peaches_sm.jpg
hills_sm.jpg
FloodFill2.exe
queuelinearfloodfill_src.zip
FloodFill2
bin
Release
hills_sm.jpg
peaches_sm.jpg
poppy_sm.jpg
Properties
Settings.settings
Resources
NoAction.bmp
OpenFolder.bmp
Save.bmp
snail.png
Thumbs.db
FloodFill2.exe
using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;
using System.Collections.ObjectModel;
using System.Diagnostics;

namespace PictureBoxScroll
{
    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()).
        /// </summary>
        public int PixelFormatSize
        {
            get { return pixelFormatSize; }
        }

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

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

        /// <summary>
        /// Gets an array that contains the bitmap bit buffer.
        /// </summary>
        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"/>.
        /// </summary>
        public EditableBitmap Owner
        {
            get { return owner; }
        }


        /// <summary>
        /// Gets a safe pointer to the buffer containing the bitmap bits.
        /// </summary>
        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.
        /// </summary>
        /// <param name="source">The bitmap to copy from.</param>
        /// <param name="format">The PixelFormat for the new bitmap.</param>
        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.
        /// </summary>
        /// <param name="source"></param>
        /// <param name="format"></param>
        /// <param name="newWidth"></param>
        /// <param name="newHeight"></param>
        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.
        /// </summary>
        /// <param name="source"></param>
        public EditableBitmap(Bitmap source) : this(source,source.PixelFormat)
        {

        }

        /// <summary>
        /// Creates a new, blank EditableBitmap with the specified width, height, and pixel format.
        /// </summary>
        /// <param name="width"></param>
        /// <param name="height"></param>
        /// <param name="format"></param>
        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"/>.
        /// </summary>
        /// <param name="source"></param>
        /// <param name="viewArea"></param>
        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"/>.
        /// </summary>
        /// <param name="viewArea">The area that should form the bounds of the view.</param>
        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.
        /// </summary>
        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();
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

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.

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