QA: Where is the DC FloodFill method?
Joao Paulo Figueira (joao.fig@mail.telepac.pt), September 24, 2003.
Question
Where is the DC FloodFill method?
Answer
There is no DC FloodFill method in the Pocket PC GDI, we have to implement it ourselves.
Question
How do I implement the FloodFill method?
Answer
There are a number of options for the FloodFill algorithm. When I was researching for this article, I found
a lot of recursive implementations (or variations thereof). My first approach was to use one of the optimized
variations of the recursive algorithm, that I reproduce below:
<![CDATA[
void CDCFloodFill::Fill(int x, int y, COLORREF crNew)
{
if(x < m_rcClip.left || x >= m_rcClip.right)
return;
if(y < m_rcClip.top || y >= m_rcClip.bottom)
return;
m_crOld = m_dc.GetPixel(x, y);
m_crNew = crNew;
if(m_crOld == m_crNew)
return;
FillN(x, y - 1);
FillS(x, y + 1);
FillE(x + 1, y);
FillW(x - 1, y);
}
void CDCFloodFill::FillN(int x, int y)
{
if(y < m_rcClip.top)
return;
if(m_dc.GetPixel(x, y) == m_crOld)
{
m_dc.SetPixel(x, y, m_crNew);
FillN(x, y - 1);
FillE(x + 1, y);
FillW(x - 1, y);
}
}
void CDCFloodFill::FillS(int x, int y)
{
if(y >= m_rcClip.bottom)
return;
if(m_dc.GetPixel(x, y) == m_crOld)
{
m_dc.SetPixel(x, y, m_crNew);
FillS(x, y + 1);
FillE(x + 1, y);
FillW(x - 1, y);
}
}
void CDCFloodFill::FillW(int x, int y)
{
if(x < m_rcClip.left)
return;
if(m_dc.GetPixel(x, y) == m_crOld)
{
m_dc.SetPixel(x, y, m_crNew);
FillN(x, y - 1);
FillS(x, y + 1);
FillW(x - 1, y);
}
}
void CDCFloodFill::FillE(int x, int y)
{
if(x >= m_rcClip.right)
return;
if(m_dc.GetPixel(x, y) == m_crOld)
{
m_dc.SetPixel(x, y, m_crNew);
FillN(x, y - 1);
FillS(x, y + 1);
FillE(x + 1, y);
}
}
]]>
By reading the code, you get the idea of what is going on (the m_dc and m_rcClip variables are
initialized in the constructor and are a CDC reference and a CRect respectively). The major problem
with this code is that it doesn't work except for the most simple of shapes. The intense recursion will exhaust
the function call stack and your application (and PDA) will crash.
Back to the drawing board, some further research led me to a very brief comment made by Chris Losinger on the
CodeProject where he states that recursion can be removed by implementing an explicit stack. This does seem to
solve the problem of filling big and complex shapes.
Performance
A successful FloodFill algorithm should be fast. Users should not wait too long for an area to be filled. When
experimenting with this code, I found that the GDI is just too slow. Reading and writing pixels is, as it seems,
a very heavy duty job for the GDI, so an alternative solution was needed and found: GAPI. The
difference between the two approaches can be tested in the sample code and, as you will see, they are not
comparable: GAPI is faster by at least one order of magnitude (if not two).
Implementation
The FloodFill implementation presented here uses a C++ class template. This was needed because I wanted to use
the same algorithm in two different raster access methods: GDI and GAPI. The implementation also uses the
STL vector container to simulate a stack (you can find an STL port for the Pocket PC here on the
Libraries section). The CFloodFill implementation is very simple:
<![CDATA[
#include <vector.h> // or just <vector>
template <class TRaster, class TColor>
class CFloodFill
{
public:
CFloodFill(TRaster &dc, CRect rcClip)
: m_dc (dc),
m_rcClip(rcClip)
{
m_rcClip.NormalizeRect();
}
void Fill(CPoint point, TColor crNew)
{
std::deque<CPoint> stack;
CPoint pt,
pn;
TColor crOld;
crOld = m_dc.GetPixel(point);
stack.push_back(point);
while(!stack.empty())
{
pt = stack.back();
stack.pop_back();
m_dc.SetPixel(pt, crNew);
pn = CPoint(pt.x, pt.y+1);
if(CheckPoint(pn, crOld))
stack.push_back(pn);
pn = CPoint(pt.x, pt.y-1);
if(CheckPoint(pn, crOld))
stack.push_back(pn);
pn = CPoint(pt.x+1, pt.y);
if(CheckPoint(pn, crOld))
stack.push_back(pn);
pn = CPoint(pt.x-1, pt.y);
if(CheckPoint(pn, crOld))
stack.push_back(pn);
}
}
protected:
TRaster& m_dc; // Raster device
CRect m_rcClip; // Clipping rect
BOOL CheckPoint(CPoint pt, COLORREF crOld)
{
return m_rcClip.PtInRect(pt) && m_dc.GetPixel(pt) == crOld;
}
};
]]>
This is as simple as it gets. If you want to use this class with a CDC, you have to instantiate it
as:
<![CDATA[
CClientDC dc(this);
CRect rc;
GetClientRect(&rc);
CFloodFill<CDC, COLORREF> flood(dc, rc);
flood.Fill(point, RGB(255, 0, 0));
]]>
What about GAPI? Well, we have to define our own class to wrap GAPI access and publish the corresponding
PutPixel and GetPixel methods. This is done in the CGC class:
<![CDATA[
class CGC
{
public:
CGC();
virtual ~CGC();
int Open(HWND hWnd);
int Close();
BOOL IsOpen() {return m_bOpen; }
BOOL BeginDraw()
{
m_pBuf = (WORD*)GXBeginDraw();
return m_pBuf != NULL;
}
int EndDraw()
{
m_pBuf = NULL;
return GXEndDraw();
}
int Suspend() {return GXSuspend(); }
int Resume() {return GXResume(); }
void SetPixel(int x, int y, WORD cr)
{
*PixelAddr(x, y) = cr;
}
void SetPixel(POINT pt, WORD cr)
{
SetPixel(pt.x, pt.y, cr);
}
WORD GetPixel(int x, int y)
{
return *PixelAddr(x, y);
}
WORD GetPixel(POINT pt)
{
return GetPixel(pt.x, pt.y);
}
WORD ConvertRGB(COLORREF cr);
private:
WORD* m_pBuf;
BOOL m_bOpen;
GXDisplayProperties m_dp;
WORD* PixelAddr(int x, int y)
{
ASSERT(x >= 0 && x < 240);
ASSERT(y >= 0 && x < 320);
ASSERT(m_pBuf);
return m_pBuf + x * (m_dp.cbxPitch >> 1) + y * (m_dp.cbyPitch >> 1);
}
};
]]>
Note that this is not a complete class. For instance, it will only support 16 bit pixel displays (and will
NOT warn you if your display is different). If you want to look more deeply into GAPI, please check
the GAPI section on this site.
Here is the rest of the implementation:
<![CDATA[
CGC::CGC()
: m_bOpen (FALSE),
m_pBuf (NULL)
{
}
CGC::~CGC()
{
Close();
}
int CGC::Open(HWND hWnd)
{
int nRval = 0;
if(m_bOpen)
return -1;
nRval = GXOpenDisplay(hWnd, GX_FULLSCREEN);
if(nRval != 0)
{
m_bOpen = TRUE;
m_dp = GXGetDisplayProperties();
}
return nRval;
}
int CGC::Close()
{
int nRval = 0;
if(m_pBuf)
EndDraw();
if(m_bOpen)
{
nRval = GXCloseDisplay();
m_bOpen = FALSE;
}
return nRval;
}
WORD CGC::ConvertRGB(COLORREF cr)
{
WORD w = 0;
if(m_dp.ffFormat & kfDirect565)
w = (GetRValue(cr) / 8) << 11 | (GetGValue(cr) / 8) << 6 | (GetBValue(cr) / 8);
else if(m_dp.ffFormat & kfDirect555)
w = (GetRValue(cr) / 8) << 11 | (GetGValue(cr) / 8) << 5 | (GetBValue(cr) / 8);
return w;
}
]]>
Note that GAPI doesn't use standard COLORREF objects to encode color. A COLORREF is a DWORD
where GAPI will use the native pixel size (a WORD, in this case) and hence the reason for the second
template argument in CFloodFill.
Now, using the CFloodFill with CGC is straightforward, but needs some small adaptations (see the sample
application):
<![CDATA[
CRect rc;
GetClientRect(&rc);
ClientToScreen(&rc);
ClientToScreen(&point);
if(m_gc.BeginDraw())
{
CFloodFill<CGC, WORD> flood(m_gc, rc);
flood.Fill(point, m_gc.ConvertRGB(RGB(255, 0, 0)));
m_gc.EndDraw();
}
]]>
And that's it.
The Sample Application
The sample application displays an image with intersecting shapes. To fill in a closed shape, tap inside it
with the stylus. The Gx and DC buttons select GAPI and GDI modes, respectively. Note that selecting
the GDI mode will repaint the image without any fills (essentially repaints a bitmap from the resources).
Memory Allocation Considerations
The class uses std::deque to implement a stack instead of std::vector because the former has
much better performance in managing memory than the latter. If you use std::vector to implement the
stack you mey have memory allocation problems due to the way this container behaves.
Warning
You may get some garbage on the screen if using an iPAQ 3850. This seems to be a device problem since it is
also happens with other GAPI software.
Thank You
To Chris Losinger for providing a simple linear algorithm (http://www.codeproject.com/useritems/floodfill.asp#xx375133xx).
To Yaroslav Goncharov for helping sort out some GAPI intrincacies.