Click here to Skip to main content
11,483,586 members (69,286 online)
Click here to Skip to main content
Articles » Multimedia » GDI » General » Downloads
Add your own
alternative version

QuickFill: An efficient flood fill algorithm.

, 12 Mar 2004 307.1K 9K 98
Design and implimentation of efficient flood fill algorithms.
quickfilldemo_demo.zip
QuickFillDemo.exe
quickfilldemo_src.zip
CDibData
Doxygen.dat
CQuantize
QuickFill
test.bmp
QuickFillDemo
Debug
QuickFillDemo.clw
QuickFillDemo.dsp
QuickFillDemo.dsw
Release
res
bitmap1.bmp
bmp00001.bmp
bmp00002.bmp
bmp00003.bmp
bmp00004.bmp
checker.bmp
checker2.bmp
circle.bmp
clubs.bmp
cross.bmp
dchecker.bmp
diamon.bmp
dimonds.bmp
hart.bmp
it.bmp
ldiag.bmp
ne.bmp
nw.bmp
QuickFillDemo.ico
QuickFillDemoDoc.ico
rdiag.bmp
schecker.bmp
scircle.bmp
se.bmp
spades.bmp
square.bmp
sw.bmp
x.bmp
xsquare.bmp
// CDibData.h
//
// Author : John R. Shaw (shawj2@earthlink.net)
// Date   : Oct 14 2003
//
// Copyright (C) 2003 John R. Shaw
// All rights reserved.
//
// This code may be used in compiled form in any way you desire. This
// file may be redistributed unmodified by any means PROVIDING it is 
// not sold for profit without the authors written consent, and 
// providing that this notice and the authors name is included. If 
// the source code in this file is used in any commercial application 
// then a simple email would be nice.
//
// Warranties and Disclaimers:
// THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND
// INCLUDING, BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
// IN NO EVENT WILL JOHN R. SHAW BE LIABLE FOR ANY DIRECT,
// INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES,
// INCLUDING DAMAGES FOR LOSS OF PROFITS, LOSS OR INACCURACY OF DATA,
// INCURRED BY ANY PERSON FROM SUCH PERSON'S USAGE OF THIS SOFTWARE
// EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
//
// Please email bug reports, bug fixes, enhancements, requests and
// comments to: shawj2@earthlink.net
//

#ifndef __CDIBDATA_H__
#define __CDIBDATA_H__

/////////////////////////////////////////////////////////////////////////////
//! class CDibData

class CDibData;

class CDibData : public CObject
{
	DECLARE_DYNAMIC(CDibData)

	friend CDibData;

	HANDLE m_hDib;				//!< Handle to DIB object
	LPBYTE m_pDib;				//!< Pointer to DIB
	LPBYTE m_pBits;				//!< Pointer to image bits in DIB
	LPBYTE* m_pLine;			//!< DIB line pointer array
	LPRGBQUAD m_pColorTable;	//!< Pointer to color table in DIB
	WORD  m_wBitsPerPixel;		//!< Number of bits-per-pixel
	DWORD m_dwColorTableSize;	//!< Number of color table entries
	DWORD m_dwBitfields[3];		//!< DIB bitfields (16 & 24 bit images)
	WORD  m_wRShift[3];			//!< Right shift values (16 & 24 bit images)
	WORD  m_wLShift[3];			//!< Left  shift values (16 & 24 bit images)

protected:
	void SetDefaultBitfields(WORD wBitsColor);
	HANDLE CreateBitmapInfo(CBitmap* pbmpSrc, BOOL* pbFinished);
	void FixImageData();
	CDibData* CreateEmptyDIB(WORD wBitsPerPixel);
	UINT GetOptimalColors(LPRGBQUAD pColors, UINT cColors, UINT nColorBits);
	HBITMAP CreateDIBitmap();

public:
	// Constructors/Destructors
	CDibData(const CDibData&);
	CDibData();
	~CDibData();

	// Attach/Detach
	BOOL Attach(HANDLE hDib);
	HANDLE Detach();

	// DIB deletion
	BOOL DeleteObject();

	// Bitmap update
	BOOL SetDIBits(CBitmap* pbmpDest);
	BOOL SetDIBits(HBITMAP hBitmap);

	// Pixel set/get
	DWORD GetPixelValue(int x, int y) const;
	BOOL SetPixelValue(int x, int y, DWORD dwValue);

	COLORREF GetPixel(int x, int y) const;
	BOOL SetPixel(int x, int y, COLORREF clPixel);

	BOOL CopyPixelValue(int xDest, int yDest,
		CDibData& dibSrc, int xSrc, int ySrc);
	BOOL CopyPixel(int xDest, int yDest,
		CDibData& dibSrc, int xSrc, int ySrc);

	// Palette/Color table
	BOOL GetPaletteEntries(
		UINT uStartIndex, UINT cEntries, LPRGBQUAD pColors) const;
	BOOL SetPaletteEntries(
		UINT uStartIndex, UINT cEntries, const LPRGBQUAD pColors);
	UINT GetNearestPaletteIndex(const LPRGBQUAD pColors) const;
	UINT GetNearestPaletteIndex(COLORREF clrSrc) const;

	// DIB creation/initialization
	BOOL CreateDIB(CBitmap* pbmpSrc, BOOL bCompress = FALSE);
	BOOL CreateDIB(HBITMAP hBitmap, BOOL bCompress = FALSE);
	HBITMAP LoadDIB(LPCTSTR lpszPathName);

	// DIB storing
	BOOL SaveDIB(LPCTSTR lpszPathName,
		CBitmap* pbmpSrc = NULL, BOOL bCompress = FALSE);

	// Create converted copy of DIB
	CDibData* GetConvertedDIB(WORD wBitsPerPixel, BOOL bOptimize = FALSE);

	/////////////////////////////////////////////////////////////////////////
	// Direct DIB access
	LPBYTE GetDibPtr() const;			//!< Pointer to DIB
	DWORD GetDibSize() const;			//!< Total size of DIB
	LPBITMAPINFOHEADER GetHeaderPtr() const;//!< Pointer to DIB header
	DWORD GetHeaderSize() const;		//!< Size of header
	LONG  GetWidth() const;				//!< Width of image
	LONG  GetHeight() const;			//!< Height of image (may be negative)
	WORD  GetPlanes() const;			//!< Number of planes (=1)
	WORD  GetBitCount() const;			//!< Bits per plane
	DWORD GetCompression() const;		//!< BI_RGB, BI_RLE8, BI_RLE4, BI_BITFIELDS
	DWORD GetSizeImage() const;			//!< Image size (may be 0)
	LONG  GetXPelsPerMeter() const;
	LONG  GetYPelsPerMeter() const;
	DWORD GetClrUsed() const;			//!< Colors used, 0 to 256
	DWORD GetClrImportant() const;		//!< Important colors, 0 to 256

	WORD  GetBitsPerPixel() const;		//!< 1, 2, 4, 8, 16, 24, 32
	DWORD GetByteWidth() const;			//!< Bytes per scan line
	DWORD GetMaxImageSize() const;		//!< Maximum possible image size

	WORD  GetSizeOfBitFields() const;	//!< Bit field size or 0
	LPDWORD GetBitFeildsPtr();			//!< Pointer to bit fields or NULL

	WORD  GetMaxColors() const;			//!< Maximum colors, 0 to 256
	DWORD GetUsedColors() const;		//!< Used or maximum colors, 0 to 256

	DWORD GetSizeOfColorTable() const;	//!< Size of color table in bytes
	DWORD GetColorTableOffset() const;	//!< Offset to color table or 0
	LPRGBQUAD GetColorTablePtr() const;	//!< Pointer to color table or NULL

	DWORD GetImageOffset() const;		//!< Offset to image data
	LPBYTE GetImagePtr() const;			//!< Pointer to image data

	/////////////////////////////////////////////////////////////////////////////
	// Special Functions
	/////////////////////////////////////////////////////////////////////////////

	// Color conversion
	DWORD RGBtoValue(COLORREF ColorRef) const;
	COLORREF ValueToRGB(DWORD dwValue) const;

	// Line drawing
	BOOL DrawLineH(int x1, int x2, int y, DWORD dwValue);

	// Line scanning functions
	int ScanRight(int x, int y, int xmax, DWORD dwValue);
	int SearchRight(int x, int y, int xmax, DWORD dwValue);
	int ScanLeft(int x, int y, int xmin, DWORD dwValue);
	int SearchLeft(int x, int y, int xmin, DWORD dwValue);

	// Convert to DIB compatible with source DIB
	CDibData* GetCompatibleDIB(CDibData& dibSrc);

	/////////////////////////////////////////////////////////////////////////////
	// Debug: Helpers
	/////////////////////////////////////////////////////////////////////////////
#ifdef _DEBUG
	friend void DumpDibFileHeader(const LPBITMAPINFOHEADER pbmfh);
	friend void DumpDibInfoHeader(const LPBYTE pDib);
	friend void DumpDibBitfields(const LPBYTE pDib);
	friend void DumpDibColorTable(const LPBYTE pDib);
	friend void DumpDib(const LPBYTE pDib);
	friend void DumpDibFile(LPCTSTR lpszPathName,BOOL bPixels);
#endif
};

/////////////////////////////////////////////////////////////////////////////
// class CDibData inline functions

//! Copy pixel value from source bitmap to this bitmap.
inline BOOL CDibData::
CopyPixelValue(int xDest, int yDest,
	CDibData& dibSrc, int xSrc, int ySrc)
{ return SetPixelValue(xDest, yDest, dibSrc.GetPixelValue(xSrc, ySrc)); }

//! Copy pixel color from source bitmap to this bitmap.
inline BOOL CDibData::
CopyPixel(int xDest, int yDest,
	CDibData& dibSrc, int xSrc, int ySrc)
{ return SetPixel(xDest, yDest, dibSrc.GetPixel(xSrc, ySrc)); }

inline LPBYTE CDibData::GetDibPtr() const
{ return m_pDib; }
inline LPBITMAPINFOHEADER CDibData::GetHeaderPtr() const
{ ASSERT(m_pDib != NULL); return((LPBITMAPINFOHEADER)m_pDib); }
inline DWORD CDibData::GetHeaderSize() const
{ return(GetHeaderPtr()->biSize); }
inline LONG  CDibData::GetWidth() const
{ return(GetHeaderPtr()->biWidth); }
inline LONG  CDibData::GetHeight() const
{ return(GetHeaderPtr()->biHeight); }
inline WORD  CDibData::GetPlanes() const
{ return(GetHeaderPtr()->biPlanes); }
inline WORD  CDibData::GetBitCount() const
{ return(GetHeaderPtr()->biBitCount); }
inline DWORD CDibData::GetCompression() const
{ return(GetHeaderPtr()->biCompression); }
inline DWORD CDibData::GetSizeImage() const
{ return(GetHeaderPtr()->biSizeImage); }
inline LONG  CDibData::GetXPelsPerMeter() const
{ return(GetHeaderPtr()->biXPelsPerMeter); }
inline LONG  CDibData::GetYPelsPerMeter() const
{ return(GetHeaderPtr()->biYPelsPerMeter); }
inline DWORD CDibData::GetClrUsed() const
{ return(GetHeaderPtr()->biClrUsed); }
inline DWORD CDibData::GetClrImportant() const
{ return(GetHeaderPtr()->biClrImportant); }

inline WORD  CDibData::GetBitsPerPixel() const
{ return WORD(GetPlanes() * GetBitCount()); }

inline DWORD CDibData::GetByteWidth() const
{ return(((GetWidth() * GetBitsPerPixel() + 31) & ~31) >> 3); }

inline DWORD CDibData::GetMaxImageSize() const
{ return(GetByteWidth() * abs(GetHeight())); }

inline WORD  CDibData::GetSizeOfBitFields() const
{ return WORD((GetCompression() == BI_BITFIELDS) ? sizeof(m_dwBitfields) : 0); }

inline LPDWORD CDibData::GetBitFeildsPtr()
{ return(LPDWORD)(GetSizeOfBitFields() ? (m_pDib + GetHeaderSize()) : NULL); }

inline WORD CDibData::GetMaxColors() const
{ return WORD((GetBitsPerPixel() <= 8) ? (1 << GetBitsPerPixel()) : 0); }

inline DWORD CDibData::GetUsedColors() const
{ return(GetClrUsed() ? GetClrUsed() : GetMaxColors()); }

inline DWORD CDibData::GetSizeOfColorTable() const
{ return(GetUsedColors() * sizeof(RGBQUAD)); }

inline DWORD CDibData::GetColorTableOffset() const
{ return(GetHeaderSize() + GetSizeOfBitFields()); }

inline LPRGBQUAD CDibData::GetColorTablePtr() const
{ return(LPRGBQUAD)(GetUsedColors() ? (m_pDib + GetColorTableOffset()) : NULL); }

inline DWORD CDibData::GetImageOffset() const
{ return(GetColorTableOffset() + GetSizeOfColorTable()); }

inline LPBYTE CDibData::GetImagePtr() const
{ return(m_pDib + GetImageOffset()); }

inline DWORD CDibData::GetDibSize() const
{
	if( GetSizeImage() )
		return GetImageOffset() + GetSizeImage();
	return GetImageOffset() + GetMaxImageSize();
}

/////////////////////////////////////////////////////////////////////////////
//! Debug: Helpers

#ifdef _DEBUG

// Dib dump helpers
void DumpDibFileHeader(const LPBITMAPINFOHEADER pbmfh);
void DumpDibInfoHeader(const LPBYTE pDib);
void DumpDibBitfields(const LPBYTE pDib);
void DumpDibColorTable(const LPBYTE pDib);
void DumpDib(const LPBYTE pDib);
void DumpDibFile(LPCTSTR lpszPathName,BOOL bPixels);

#define DEBUG_TRACE_FHEADER(pbmfh)   DumpDibFileHeader(pbmfh)
#define DEBUG_TRACE_IHEADER(pDib)    DumpDibInfoHeader(pDib)
#define DEBUG_TRACE_BITFIELDS(pDib)  DumpDibBitfields(pDib)
#define DEBUG_TRACE_COLORTABLE(pDib) DumpDibColorTable(pDib)
#define DEBUG_TRACE_DIB(pDib)        DumpDib(pDib)
#define DEBUG_TRACE_DIBFILE(lpszPathName,bPixels) \
	DumpDibFile(lpszPathName,bPixels)

// Allocation helpers
HANDLE DibAlloc(DWORD dwLen);
LPBYTE DibLock(HANDLE hDib);
BOOL   DibUnlock(HANDLE hDib);
HANDLE DibFree(HANDLE hDib);

#else

// Dib dump helpers
#define DEBUG_TRACE_FHEADER(pbmfh)   ((void)0)
#define DEBUG_TRACE_IHEADER(pDib)    ((void)0)
#define DEBUG_TRACE_BITFIELDS(pDib)  ((void)0)
#define DEBUG_TRACE_COLORTABLE(pDib) ((void)0)
#define DEBUG_TRACE_DIB(pDib)        ((void)0)
#define DEBUG_TRACE_DIBFILE(lpszPathName, bPixels) ((void)0)

// Allocation helpers
#define DibAlloc(dwLen) ::GlobalAlloc(GHND, dwLen)
#define DibLock(hDib)   (LPBYTE)::GlobalLock(hDib)
#define DibUnlock(hDib) ::GlobalUnlock(hDib)
#define DibFree(hDib)   ::GlobalFree(hDib)

#endif // _DEBUG

#endif // __CDIBDATA_H__

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

John R. Shaw
Software Developer
United States United States
I am a senior software engineer who has been designing and developing software for many years, mostly in C/C++. You might say that I think in code; which is why I am passionate about my first rule of coding: “First do no harm”. So if I get carried away in my explanations, please realize that it is just part of my personality. I enjoy learning new things and, when I have the time, passing that knowledge onto others.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150520.1 | Last Updated 13 Mar 2004
Article Copyright 2004 by John R. Shaw
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid