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:
public __gc class QuickFill
static System::Drawing::Image* Fill(System::Drawing::Bitmap* bitmap,
int x, int y,
qf.QuickFill(bitmap, x, y, RGB(fc.R, fc.G, fc.B));
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
Bait and Switch
QuickFill class depends on another nifty class called
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
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
CBitmap a synonym for the .NET Framework
System::Drawing::Bitmap type, which is what my replacement
CDibBitmap class takes as input:
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.
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
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
COLORREF CDibData::GetPixel(int x, int y) const
BYTE* pel = (BYTE*)m_pbmpSrcData->Scan0.ToPointer() +
return RGB(pel, pel, pel) ;
BOOL CDibData::SetPixel(int x, int y, COLORREF clPixel)
BYTE* pel = (BYTE*)m_pbmpSrcData->Scan0.ToPointer() +
pel = GetRValue(clPixel);
pel = GetGValue(clPixel);
pel = GetBValue(clPixel);
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.
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.