Click here to Skip to main content
15,860,972 members
Articles / Multimedia / GDI+
Article

QuickFill .NET: An efficient flood fill algorithm, Adapted for GDI+

Rate me:
Please Sign up or sign in to vote.
4.69/5 (12 votes)
25 Feb 20046 min read 71.1K   627   25   6
The purpose of this article is to show one way of adapting John R. Shaw’s excellent QuickFill algorithm, such that it will work with GDI+ and the .NET Framework.

Sample Image - QuickFillNET.png

Introduction

The purpose of this article is to show one way of adapting John R. Shaw’s excellent QuickFill algorithm, such that it will work with GDI+ and the .NET Framework.

Let me begin by admitting that I did not take much time to fully understand John’s algorithm. When I read that the strengths of the recursive flood-fill algorithms were that they are "simple to implement by even a beginner programmer", I decided it might be detrimental to my psyche if I discovered I couldn’t grep the advanced programmer version. So I rated the article a '5' and moved on.

I came back to the article a couple of times to read the comments. One comment raised an issue that I’d thought of myself: how to use the algorithm for GDI+ applications. GDI+ doesn’t have a flood-fill capability, which makes it pretty useless for us beginning programmers needing such functionality.

So I set out to make Johns code work with GDI+ and the .NET Framework. This sample does not adapt John’s algorithm to work with the native Win32 GDI+ API, although that could certainly be done.

How it Works

First and foremost, I didn’t want to mess with John’s code. I was afraid that if I even looked at that fine algorithm the wrong way, it would break, and I wouldn’t be able to fix it. But I wanted it to work in .NET.

Visual C++ .NET allows us to compile C++ code to MSIL. Throw the /clr switch and the compiler generates a .NET assembly, which can then be consumed by any .NET language. This doesn’t do a heck of a lot of good though unless you also create some CLR data types that expose functionality. /clr doesn’t magically turn a C++ data type into a CLR data type.

The best way to expose existing C++ functionality to .NET is to wrap it inside a new CLR class and expose a new interface. This is what I have done, and I’ve done it at a most basic level. I have not exposed all of the public functionality of John’s CQuickFill class – rather I’ve exposed the primary feature – the QuickFill() method (renamed by me as Fill). I also started to expose the ability to flood-fill with a bitmap pattern, but haven’t got that fully working yet.

My CLR class is called QuickFill, and it has a few overloaded static methods that you can call. Unlike John’s class, mine doesn’t have to be instantiated to use. Here’s a snippit of what the code looks like:

MC++
public __gc class QuickFill
{
private:
 
    // static members only; a user never constructs this class
    QuickFill()
    {
    }
 
public:
 
    static System::Drawing::Image* Fill(System::Drawing::Bitmap* bitmap, 
                                        int x, int y, 
                                        System::Drawing::Color fc)
    {
        CQuickFill qf;
        qf.QuickFill(bitmap, x, y, RGB(fc.R, fc.G, fc.B));
 
        return static_cast<Image*>(bitmap);
    }
};

My QuickFill class is a CLR data type (it is decorated with __gc). Because it is not intended to be instantiated, it hides its constructor. The Fill method (not QuickFill, because that name would collide with the name of the class, and the compiler would complain about the constructor returning a value…) simply instantiates John’s CQuickFill class and calls its QuickFill method. Voila, magic, simply great.

But that’s not the whole story. Where’s the support for GDI+? How on earth am I passing a .NET Framework Bitmap object directly into John’s code, which expects a MFC CBitmap object?

Bait and Switch

John’s QuickFill class depends on another nifty class called CDibBitmap. CDibBitmap is an abstraction of the Win32 DIB (Device Independent Bitmap), and enables simplified access and control of raw bitmap data. QuickFill embeds two CDibBitmap objects – one for the bitmap we’re filling, and another that is used to store a secondary pattern bitmap, for pattern-filling. CDibBitmap is derived from CObject, a MFC class, and it uses several MFC support classes including CBitmap.

I didn’t want to involve MFC in this experiment. MFC is a great, but perhaps it is a bit heavy-weight for this application. I mean, if we’re creating a lightweight flood-fill component for use with the .NET Framework, why would we want to bring along the heavyweight MFC library? Perhaps if we were bringing a bunch of more complex MFC-based code forward, but not today.

I noticed a couple things about CQuickFill. The only use of MFC was the CBitmap it accepted as a parameter to the QuickFill method, and here the method was simply passed on to CDibBitmap. John apparently provided support for CBitmap as a convenience feature for the consumer application (which could likely be a MFC application).

With this knowledge I began to devise a plan. First, I would write my own CDibBitmap that would implement the same interface as the original so that it could continue to be used by CQuickFill. Second, I would strip out the MFC code. This is easier done than said: with the original CDibBitmap out of the picture, the only remaining MFC code is the CBitmap parameter to the QuickFill method. A simple typedef makes CBitmap a synonym for the .NET Framework System::Drawing::Bitmap type, which is what my replacement CDibBitmap class takes as input:

MC++
// We're not using MFC; Substitute the .NET Framework Bitmap class (GDI+) 
// for CBitmap
typedef System::Drawing::Bitmap CBitmap;

Of course, if I hadn’t been so determined not to even touch John’s code, I could have gone in an altered his sources to correct this issue. Another benefit: if John makes any minor changes to his class, I won’t have to reapply any changes to my copy.

The new CDibBitmap class needs to implement an identical interface to the old CDibBitmap, and it needs to act upon a GDI+ Bitmap. The original CDibBitmap class specifies and implements a slew of members – way more than I was willing to implement. Fortunately the consuming CQuickFill class only calls about 10 of them – and they’re relatively simple to implement. The most interesting aspect of this implementation is how we enable fast read and write access to the pixel data. The GDI+ Bitmap class exposes a method LockBits() that returns a pointer to an array of raw bitmap data, in a layout determined by the requested bit-depth format. This is similar in function to the GDI API GetDIBits(), which is what the original CDibBitmap class used. In my implementation, I call LockBits() in the CDibData::CreateDIB() method and store the returned pointer, which is "unlocked" by a call to UnlockBits() in CDibData::SetDIBits(). I also had to implement a small hack to ensure that the corresponding UnlockBits() call is made even if the client never explicitly calls CDibBitmap::SetDIBits(). In this case the client is CQuickFill, and its logic is built around GetDIBits(), which doesn’t require a corresponding "unlock" method.

With direct memory access to the raw bitmap data, it is simple to implement the other core methods in CDibData(), namely GetPixel() and SetPixel():

MC++
COLORREF CDibData::GetPixel(int x, int y) const
{
      BYTE* pel = (BYTE*)m_pbmpSrcData->Scan0.ToPointer() +
                             (y*m_pbmpSrcData->Stride)+(x*4);
 
      return RGB(pel[2], pel[1], pel[0]) ;
}
 
BOOL CDibData::SetPixel(int x, int y, COLORREF clPixel)
{
      BYTE* pel = (BYTE*)m_pbmpSrcData->Scan0.ToPointer() +
                             (y*m_pbmpSrcData->Stride)+(x*4);
 
      pel[2] = GetRValue(clPixel);
      pel[1] = GetGValue(clPixel);
      pel[0] = GetBValue(clPixel);
 
      return TRUE;
}

Note that these assume that the data is in 32bpp format, which it is because that’s what was specified in the earlier call to LockBits(). Note too the flagrant lack of error checking. Use this code at your own risk.

Conclusion

I intend this as an example of how it is possible to take existing C++ code and use it in a .NET application (in the sample, a C# Windows Form application). In the real world, you might wish to be a bit more robust in your solution.

Also note that this sample implements the loader-lock workaround, as discussed in http://support.microsoft.com/?id=814472. This workaround necessitates that the component be initialized and de-initialized by the client.

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


Written By
Web Developer
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey18-Feb-12 0:15
professionalManoj Kumar Choubey18-Feb-12 0:15 
GeneralLove This Pin
John R. Shaw2-Mar-04 21:45
John R. Shaw2-Mar-04 21:45 
GeneralRe: Love This Pin
Nick Hodapp8-Mar-04 17:35
sitebuilderNick Hodapp8-Mar-04 17:35 
GeneralWhy Floodfill is a bad idea Pin
ector27-Feb-04 13:18
ector27-Feb-04 13:18 
GeneralRe: Why Floodfill is a bad idea Pin
Stephane Rodriguez.27-Feb-04 22:13
Stephane Rodriguez.27-Feb-04 22:13 
GeneralRe: Why Floodfill is a bad idea Pin
Joe Beda29-Feb-04 17:19
Joe Beda29-Feb-04 17:19 

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.