Click here to Skip to main content
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
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
// QuickFill.cpp
//
// Author : John R. Shaw (shawj2@earthlink.net)
// Date   : Jan. 26 2004
//
// Copyright (C) 2004 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
//
//----------------------------------------------------------------------------
// Version 1.0
//----------------------------------------------------------------------------
// Jan. ??, 2004 : Converted from C (direct video access) to C++ for use with
//                 MS Windows bitmaps and support for: pattern bitmaps to be
//                 used as fill and visit-block-list to eliminate
//                 revisiting durring pattern & mask fills.
//
// Note: Since the origanal code had direct video access it could take
// advantage (with the correct write mode) of byte block copping and color-
// bit-mask reading (read mode 1). Both of which where hardware supported and
// much more efficeint than reading/writing pixels directly from/to a bitmap.
//
//----------------------------------------------------------------------------
// Version 1.1
//----------------------------------------------------------------------------
// Feb.  6, 2004 : Added left optimization, eliminates some revisits.
// Feb.  8, 2004 : Added reverse clip optimization, eliminates some revisits.
// Feb. 15, 2004 : Found PushOpposite() special case and corrected it.
// Feb. 19, 2004 : Changed internal scan, search and line drawing routines
//                 to use pixel color values, in order to increase overall
//                 speed while working with palettized bitmaps.
// Mar.  5, 2004 : 1) Moved PushVisitedLine() from QuickFill() to
//                 PushOpposite(), this increases the number of revisits and
//                 reduces the size of the visit-list (8:1).
//                 2) Changed visit-list to use HLINE_NODE, since block
//                 checking is no longer required and the number of
//                 allocations are reduce because the free-list can now be
//                 used by all. (of course HLINE_NODE is larger than we need,
//                 since it is not a visit-list specific node type)
// Mar.  9, 2004 : 1) Added argument to QuickFill() so that user can specify
//                 the rectangular area to be filled.
//                 2) Added the GetInvalidRect() function and associated code
//                 so that user can retrieve the rectangular coordinates of
//                 the bitmap area that has been modified, since lack of this
//                 information forces user to redraw whole bitmap.
//
//----------------------------------------------------------------------------
//
#include "stdafx.h"
#include "QuickFill.h"

const BYTE _SolidMask[8] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
const BYTE   _BitMask[8] = {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};

//----------------------------------------------------------------------------
// Optimization / testing defines
//----------------------------------------------------------------------------

#ifdef QUICKFILL_SLOW
#define UPDATE_DISPLAY() \
if( m_bSlowMode && ::IsWindow(hWnd) ) { \
	m_DibData.SetDIBits(pBitmap); \
	::InvalidateRect(hWnd,NULL,FALSE); \
	::UpdateWindow(hWnd); \
}
#else
#define UPDATE_DISPLAY()
#endif // QUICKFILL_SLOW

//----------------------------------------------------------------------------
// Public methods
//----------------------------------------------------------------------------

/* Arguments:
 *		Pointer to bitmap to fill, pointer rectangular area it fill (or NULL)
 *		(x,y) coordinates of seed point, color used for solid or masked fills,
 *		border color used if area to be filled is outlined (or CLR_INVALID).
 *
 * Returns:
 *		 0 = Success.
 *		-1 = Invalid seed point.
 *		-2 = Memory allocation error.
 *		-3 = Invalid bitmap or unknown error.
 */
int CQuickFill::QuickFill(
	CBitmap* pBitmap,LPRECT pRect,int x,int y,
	COLORREF fill_color,COLORREF border_color/*=CLR_INVALID*/)
{
	DWORD ThisColorValue, FillValue, BorderValue;
	int MinY,MinX,MaxY,MaxX,dy;
	int ChildLeft,ChildRight;
	int ParentLeft,ParentRight;

#ifdef QUICKFILL_SLOW
	HWND hWnd = NULL;
	if( m_bSlowMode )
		hWnd = ::GetActiveWindow();
#endif

	// Create dib data object
	if( !m_DibData.CreateDIB(pBitmap) )
		return -3;

	FillValue   = m_DibData.RGBtoValue(fill_color);
	BorderValue = m_DibData.RGBtoValue(border_color);

	/* Initialize global variables */
#ifdef QUICKFILL_TEST
	m_CurStackSize = m_MaxStackSize = m_VisitSize = 0U;
	m_nRevisitCount = m_CurrentLine = m_Direction = 0;
#endif
	m_bXSortOn = m_bMemError = FALSE;
	m_LastY = -1;

	/* Get seed pixel */
	ThisColorValue = GetPixel(x,y);
	
	/* Initialize internal info based on fill type */
	if( CLR_INVALID != BorderValue ) {
		/* Check color at x,y position */
		if( ThisColorValue == BorderValue ) {
			m_DibData.DeleteObject();
			return -1;
		}

		ThisColorValue = BorderValue;
		m_bXSortOn = TRUE;
	}
	else {
		/* Check color at x,y position */
		if( ThisColorValue == FillValue && !m_DibPattern.GetDibPtr() ) {
			m_DibData.DeleteObject();
			return -1;
		}

		if( m_DibPattern.GetDibPtr() || memcmp(m_FillMask,_SolidMask,8) )
			m_bXSortOn = TRUE;
	}

	/* Using macros because we can not use pointers to non-static
	 * member functions.
	 * This makes the code less efficient, but solves the problem.
	 */
#define FindLeft(x,y,xmin,color) \
	((CLR_INVALID != BorderValue) \
	? SearchLeft(x,y,xmin,color) : ScanLeft(x,y,xmin,color))
#define FindRight(x,y,xmax,color) \
	((CLR_INVALID != BorderValue) \
	? SearchRight(x,y,xmax,color) : ScanRight(x,y,xmax,color))
#define SkipRight(x,y,xmax,color) \
	((CLR_INVALID != BorderValue) \
	? ScanRight(x,y,xmax,color) : SearchRight(x,y,xmax,color))

	/* Initialize Line list */
	if( MakeList() ) {
		m_DibData.DeleteObject();
		return -2;
	}

    /* Initialize coords */
	MaxX = m_DibData.GetWidth()  - 1;
	MaxY = m_DibData.GetHeight() - 1;
	MinX = MinY = 0;
	if( pRect )
	{
		if( 0 < pRect->left && pRect->left < MaxX )
			MinX = pRect->left;
		if( 0 < pRect->right && pRect->right < MaxX )
			MaxX = pRect->right;
		if( 0 < pRect->top && pRect->top < MaxY )
			MinY = pRect->top;
		if( 0 < pRect->bottom && pRect->bottom < MaxY )
			MaxY = pRect->bottom;
	}

	if( x < MinX || MaxX < x || y < MinY || MaxY < y ) {
		m_DibData.DeleteObject();
		return -1;
	}

	/* Initialize invalid rectangle */
	m_rcInvalid.left = m_rcInvalid.right  = x;
	m_rcInvalid.top  = m_rcInvalid.bottom = y;

	/* Push starting point on stack.
	 * Durring testing calling FindLeft() & FindRight() here reduced the number
	 * of revisits by 1 and the number of items on the visit list by 2.
	 */
	ChildLeft  = FindLeft(x,y,MinX,ThisColorValue)+1;
	ChildRight = FindRight(x,y,MaxX,ThisColorValue)-1;
	PushLine(ChildLeft,ChildRight,y,+1); /* Needed in one special case */
	PushLine(ChildLeft,ChildRight,++y,-1);

	/* Now start flooding */
	while( m_pLineList ) {
		PopLine(&ParentLeft,&ParentRight,&y,&dy);
		y += dy;
#ifdef QUICKFILL_TEST
		m_CurrentLine = y;
		m_Direction = dy;
#endif
		if( y < MinY || MaxY < y ) {
			continue;
		}
		if( m_bMemError ) {
			continue;
		}
		if( m_bXSortOn && IsRevisit(ParentLeft,ParentRight,y) ) {
			continue;
		}

		/* This slows things down a little but provides needed information */
		if( ParentLeft < m_rcInvalid.left )
			m_rcInvalid.left = ParentLeft;
		else if( ParentRight > m_rcInvalid.right )
			m_rcInvalid.right = ParentRight;
		if( y < m_rcInvalid.top )
			m_rcInvalid.top = y;
		else if( y > m_rcInvalid.bottom )
			m_rcInvalid.bottom = y;

#ifdef QUICKFILL_SLOW
		if( m_bSlowMode ) {
			if( ::GetAsyncKeyState(VK_ESCAPE) < 0 )
				break;
		}
#endif

		/* Find ChildLeft end ( ChildLeft>ParentLeft on failure ) */
		ChildLeft = FindLeft(ParentLeft,y,MinX,ThisColorValue)+1;
		if( ChildLeft<=ParentLeft ) {
			/* Find ChildRight end ( this should not fail here ) */
			ChildRight = FindRight(ParentLeft+1,y,MaxX,ThisColorValue)-1;

			/* Fill line */
			if( ChildLeft == ChildRight )
				SetPixel(ChildRight,y,FillValue);
			else
				DrawHorizontalLine(ChildLeft,ChildRight,y,FillValue);

			UPDATE_DISPLAY();

			/* Push unvisited lines */
			if( ParentLeft-1<=ChildLeft && ChildRight<=ParentRight+1 ) {
				/* No reverse clipping required
				 *
				 * Example: Going down
				 * +-------------+
				 * |xxxxxxxxxxxxx|
				 * +---+xxxxx+---+
				 * |   |xxxxx|	 |   <- Parent Line (CASE 1)
				 * |   |xxxxx|	 |   <- Child Line
				 * |   |xxxxx|   |
				 * |  ++xxxxx++  |   <- Parent Line (CASE 2)
				 * |  |xxxxxxx|  |   <- Child Line
				 * +--+-------+--+
				 */
				PushLine(ChildLeft,ChildRight,y,dy);
			}
			else {
				if( m_bXSortOn ) {
					PushOpposite(ParentLeft,ParentRight,ChildLeft,ChildRight,y,dy);
				}
#ifndef QUICKFILL_NO_REVERSE_CLIP_OPT // Reduces total number of pixels visited
				else if( ChildLeft == ParentLeft ) {
					/* Reverse clip left
					 *
					 * Example: Going up
					 * +-----------------+
					 * |xxxxxxxxxxxxxxxxx|   <- Child Line
					 * |xxx+----+   +----+   <- Parent Line
					 * |xxx|    |   |    |
					 * +---+----+---+----+
					 */
					PushLine(ParentRight+2,ChildRight,y,-dy);
				}
				else if( ChildRight == ParentRight ) {
					/* Reverse clip right
					 *
					 * Example: Going up
					 * +-----------------+
					 * |xxxxxxxxxxxxxxxxx|   <- Child Line
					 * +----+   +----+xxx|   <- Parent Line
					 * |    |   |    |xxx|
					 * +----+---+----+---+
					 */
					PushLine(ChildLeft,ParentLeft-2,y,-dy);
				}
#endif
				else {
					/* Normal reverse push
					 *
					 * Example: Going up
					 * +-------------------+
					 * |xxxxxxxxxxxxxxxxxxx| <- Child Line
					 * +   +---+xxx+---+   | <- Parent Line
					 * |   |   |xxx|   |   |
					 * +---+---+---+---+---+
					 */
					PushLine(ChildLeft,ChildRight,y,-dy);
				}
				PushLine(ChildLeft,ChildRight,y,dy);
			}
			/* Addvance ChildRight end on to border */
			++ChildRight;
		}
		else ChildRight = ParentLeft;

		/* Fill betweens */
		while( ChildRight < ParentRight ) {
			/* Skip to new ChildLeft end ( ChildRight>ParentRight on failure ) */
			ChildRight = SkipRight(ChildRight+1,y,ParentRight,ThisColorValue);
			/* If new ChildLeft end found */
			if( ChildRight<=ParentRight ) {
				ChildLeft = ChildRight;

				/* Find ChildRight end ( this should not fail here ) */
				ChildRight = FindRight(ChildLeft+1,y,MaxX,ThisColorValue)-1;

				/* Fill line */
				if( ChildLeft == ChildRight )
					SetPixel(ChildRight,y,FillValue);
				else
					DrawHorizontalLine(ChildLeft,ChildRight,y,FillValue);

				UPDATE_DISPLAY();

				/* Push unvisited lines */
				if( ChildRight <= ParentRight+1 ) {
					PushLine(ChildLeft,ChildRight,y,dy);
				}
				else {
					if( m_bXSortOn ) {
						PushOpposite(ParentLeft,ParentRight,ChildLeft,ChildRight,y,dy);
					}
					else
						PushLine(ChildLeft,ChildRight,y,-dy);
					PushLine(ChildLeft,ChildRight,y,dy);
				}
				/* Addvance ChildRight end onto border */
				++ChildRight;
			}
		}
	}

#ifdef QUICKFILL_TEST
	if( m_bShowRevisits && m_nRevisitCount ) // only if revisit occured
	{
		HLINE_NODE*	pNext = m_pVisitList;
		while( pNext ) {
			m_DibData.DrawLineH(pNext->x1,pNext->x2,pNext->y,DWORD(pNext->dy));
			pNext = pNext->pNext;
		}
	}
#endif // QUICKFILL_TEST
	/**/

	FreeList();
	m_DibData.SetDIBits(pBitmap);
	m_DibData.DeleteObject();

	return( m_bMemError?-2:0 );
}

// Argument: FillMask[8] or NULL
void CQuickFill::SetFillMask(BYTE* pMask/*=NULL*/)
{
	if( !pMask )
		memcpy(m_FillMask,_SolidMask,8);
	else
		memcpy(m_FillMask,pMask,8);
}

// Argument: Pointer to bitmap or NULL.
// Returns: Nonzero on success.
BOOL CQuickFill::SetPatternBitmap(CBitmap* pBitmap/*=NULL*/,COLORREF clrClear/*=CLR_INVALID*/)
{
	m_DibPattern.DeleteObject();
	m_xPatMod = m_yPatMod = 0;
	m_clrPatClear = CLR_INVALID;
	if( pBitmap ) {
		if( !m_DibPattern.CreateDIB(pBitmap) )
			return FALSE;
		m_xPatMod = m_DibPattern.GetWidth()-1;
		m_yPatMod = m_DibPattern.GetHeight()-1;
		m_clrPatClear = clrClear;
	}
	return TRUE;
}

// Argument: Handle to bitmap or NULL.
// Returns: Nonzero on success.
BOOL CQuickFill::SetPatternBitmap(HBITMAP hBitmap,COLORREF clrClear/*=CLR_INVALID*/)
{
	m_DibPattern.DeleteObject();
	m_xPatMod = m_yPatMod = 0;
	m_clrPatClear = CLR_INVALID;
	if( hBitmap ) {
		if( !m_DibPattern.CreateDIB(hBitmap) )
			return FALSE;
		m_xPatMod = m_DibPattern.GetWidth()-1;
		m_yPatMod = m_DibPattern.GetHeight()-1;
		m_clrPatClear = clrClear;
	}
	return TRUE;
}

// Argument: Path/Name of bitmap file.
// Returns: Nonzero on success.
BOOL CQuickFill::SetPatternBitmap(LPCTSTR lpszPathName,COLORREF clrClear/*=CLR_INVALID*/)
{
	m_DibPattern.DeleteObject();
	m_xPatMod = m_yPatMod = 0;
	m_clrPatClear = CLR_INVALID;
	if( lpszPathName ) {
		if( !m_DibPattern.LoadDIB(lpszPathName) )
			return FALSE;
		m_xPatMod = m_DibPattern.GetWidth()-1;
		m_yPatMod = m_DibPattern.GetHeight()-1;
		m_clrPatClear = clrClear;
	}
	return TRUE;
}

// Argument: Transparent color used with pattern bitmaps.
// Returns: Previous color.
COLORREF CQuickFill::SetPatternClearColor(COLORREF clrClear/*=CLR_INVALID*/)
{
	COLORREF color = m_clrPatClear;
	m_clrPatClear = clrClear;
	return color;
}

// Returns: Nonzero if pattern bitmap is being used.
BOOL CQuickFill::HasPattern()
{
	return( m_xPatMod && m_yPatMod );
}

// Returns: Nonzero if fill masks are being used.
BOOL CQuickFill::HasMask()
{
	return( memcmp(m_FillMask,_SolidMask,8) );
}

//----------------------------------------------------------------------------
// Public Constructor/Destructor methods
//----------------------------------------------------------------------------

CQuickFill::CQuickFill()
{
	m_pVisitList = NULL;
	m_pLineList = NULL;		// List of lines to be visited.
	m_pFreeList = NULL;		// List of free nodes.
	m_bXSortOn = FALSE;		// X-Sorting flag (single visit indicator).
	m_bMemError = FALSE;	// Memory error flag.
	memset(&m_rcInvalid,0,sizeof(m_rcInvalid));
#ifdef QUICKFILL_SLOW
	m_bSlowMode = FALSE;	// Update active window and allow user to ESC
#endif
#ifdef QUICKFILL_TEST
	m_CurStackSize = 0U;	// Current number of nodes in line list.
	m_MaxStackSize = 0U;	// Greatest number of nodes added to line list.
	m_VisitSize = 0U;		// Number of nodes in the visited list
	m_CurrentLine  = 0;		// Current line being visited
	m_Direction = 0;		// Curent direction of travel
	m_nRevisitCount = 0;
	m_bShowRevisits = FALSE;
#endif
	memset(m_FillMask,0xFF,8);		// Current fill mask
	m_xPatMod = m_yPatMod = 0;		// Pattern modulus values
	m_clrPatClear = CLR_INVALID;	// Transparent color, pattern fills only
}

CQuickFill::~CQuickFill()
{
	// Safety only
	FreeList();
	m_DibData.DeleteObject();
}

//----------------------------------------------------------------------------
// Protected scanning and drawing methods
//----------------------------------------------------------------------------

// Arguments: x, y coordinates of pixel to examine.
// Returns: Color of pixel or CLR_INVALID on failure.
DWORD CQuickFill::GetPixel(int x, int y)
{
	return m_DibData.GetPixelValue(x,y);
}

// Arguments: x, y coordinates and new color of pixel.
BOOL CQuickFill::SetPixel(int x, int y, DWORD dwValue)
{
	if( _BitMask[x&7] & m_FillMask[y&7] ) {
		if( m_xPatMod && m_yPatMod ) {
			dwValue = DWORD(m_DibPattern.GetPixel(x%m_xPatMod,y%m_yPatMod));
			if( m_clrPatClear != CLR_INVALID ) {
				 if( COLORREF(dwValue) == m_clrPatClear ) {
					return FALSE;
				}
			}
			return m_DibData.SetPixel(x,y,COLORREF(dwValue));
		}
		else {
			return m_DibData.SetPixelValue(x,y,dwValue);
		}
	}
	return FALSE;
}

// Arguments: Coordinates of horizontal line and new color of line.
void CQuickFill::DrawHorizontalLine(int x1, int x2, int y, DWORD dwValue)
{
	// If doing solid fill
	if( !m_bXSortOn ) {
		m_DibData.DrawLineH(x1,x2,y,dwValue);
	}
	else {
		// Slow but neccessary for patterns and masks
		for( ; x1 <= x2; ++x1 )
			SetPixel(x1,y,dwValue);
	}
}

/*	ScanLeft()
 *	xmin > result -> failure
 */
int CQuickFill::ScanLeft(int x,int y,int xmin,DWORD dwValue)
{
	return m_DibData.ScanLeft(x,y,xmin,dwValue);
}

/*	SearchLeft()
 *	xmin > result -> failure
 */
int CQuickFill::SearchLeft(int x,int y,int xmin,DWORD dwValue)
{
	return m_DibData.SearchLeft(x,y,xmin,dwValue);
}

/*	ScanRight()
 *	xmax < result -> failure
 */
int CQuickFill::ScanRight(int x,int y,int xmax,DWORD dwValue)
{
	return m_DibData.ScanRight(x,y,xmax,dwValue);
}

/*	SearchRight()
 *	xmax < result -> failure
 */
int CQuickFill::SearchRight(int x,int y,int xmax,DWORD dwValue)
{
	return m_DibData.SearchRight(x,y,xmax,dwValue);
}

//----------------------------------------------------------------------------
// Private methods
//----------------------------------------------------------------------------

/* Initialize Line list */
int CQuickFill::MakeList(void)
{
	m_pFreeList = (HLINE_NODE*)calloc(1,sizeof(HLINE_NODE));
	return( m_pFreeList?0:1 );
}

/* Frees the list of free nodes */
void CQuickFill::FreeList(void)
{
	HLINE_NODE *pNext;
	while( m_pFreeList ) {
		pNext = m_pFreeList->pNext;
	  	free(m_pFreeList);
	  	m_pFreeList = pNext;
	}

	while( m_pLineList ) {
		pNext = m_pLineList->pNext;
	  	free(m_pLineList);
	  	m_pLineList = pNext;
	}
	
	while( m_pVisitList ) {
		pNext = m_pVisitList->pNext;
	  	free(m_pVisitList);
	  	m_pVisitList = pNext;
	}

}

/* Push a node onto the line list */
void CQuickFill::PushLine(int x1,int x2,int y,int dy)
{
	HLINE_NODE *pNew = m_pFreeList;
	if( pNew )
		m_pFreeList = m_pFreeList->pNext;
	else
		pNew = (HLINE_NODE*)calloc(1,sizeof(HLINE_NODE));
	/* Add to start of list */
	if( pNew ) {
		pNew->x1 = x1;
		pNew->x2 = x2;
		pNew->y  = y;
		pNew->dy = dy;
		
		if( m_bXSortOn ) {
			/* This is for the single line visiting code.
			 * The code runs about 18% slower but you can
			 * use fill patterns with it.
			 * Since the basic algorithym scans lines from
			 * left to right it is required that the list
			 * be sorted from left to right.
			 */
			HLINE_NODE *pThis,*pPrev=(HLINE_NODE*)0;
			for( pThis=m_pLineList;pThis;pThis=pThis->pNext ) {
				if( x1 <= pThis->x1 )
					break;
				pPrev = pThis;
			}
			if( pPrev ) {
				pNew->pNext = pPrev->pNext;
				pNew->pPrev = pPrev;
				pPrev->pNext = pNew;
				if( pNew->pNext )
					pNew->pNext->pPrev = pNew;
			}
			else {
				pNew->pNext = m_pLineList;
				pNew->pPrev = (HLINE_NODE*)0;
				if( pNew->pNext )
					pNew->pNext->pPrev = pNew;
				m_pLineList = pNew;
			}
		}
		else {
			pNew->pNext = m_pLineList;
			m_pLineList = pNew;
		}
#ifdef QUICKFILL_TEST
		++m_CurStackSize;
		if( m_CurStackSize > m_MaxStackSize )
			m_MaxStackSize = m_CurStackSize;
#endif
	}
	else m_bMemError = 1;
}

/* Pop a node off the line list */
void CQuickFill::PopLine(int *x1,int *x2,int *y,int *dy)
{
	if( m_pLineList ) {
		HLINE_NODE *pThis,*pPrev;
		/* Search lines on stack for same line as last line.
		 * This smooths out the flooding of the graphics object
		 * and reduces the size of the stack.
		 */
		pPrev = m_pLineList;
		for( pThis=m_pLineList->pNext;pThis;pThis=pThis->pNext ) {
			if( pThis->y == m_LastY )
				break;
			pPrev = pThis;
		}
		/* If pThis found - remove it from list */
		if( pThis ) {
			pPrev->pNext = pThis->pNext;
			if( pPrev->pNext )
				pPrev->pNext->pPrev = pPrev;
			*x1 = pThis->x1;
			*x2 = pThis->x2;
			*y  = pThis->y;
			*dy = pThis->dy;
		}
		/* Remove from start of list */
		else {
			*x1 = m_pLineList->x1;
			*x2 = m_pLineList->x2;
			*y  = m_pLineList->y;
			*dy = m_pLineList->dy;
			pThis = m_pLineList;
			m_pLineList = m_pLineList->pNext;
			if( m_pLineList )
				m_pLineList->pPrev = (HLINE_NODE*)0;
		}

		pThis->pNext = m_pFreeList;
		m_pFreeList = pThis;
#ifdef QUICKFILL_TEST
		--m_CurStackSize;
#endif
		m_LastY = *y;
	}
}

/***** Single Visit Code *******************************************/

/* Jan 24, 2004
 * Testing showed a gapping hole in the push opposite code, that
 * would cause QuickFill to get stuck. The cause of this was the
 * fact that push opposite just reduced the number of revisits but
 * did not stop them.
 */

/* Adds line to visited block list */
void CQuickFill::PushVisitedLine(int x1,int x2,int y)
{
	HLINE_NODE *pNew = m_pFreeList;
	if( pNew )
		m_pFreeList = m_pFreeList->pNext;
	else
		pNew = (HLINE_NODE*)calloc(1,sizeof(HLINE_NODE));
	/* Add to start of list */
	if( pNew ) {
		pNew->x1 = x1;
		pNew->x2 = x2;
		pNew->y  = y;
#ifdef QUICKFILL_TEST
		pNew->dy  = (int)m_DibData.RGBtoValue(RGB(0,255,255));
#endif
		pNew->pNext = m_pVisitList;
		m_pVisitList = pNew;
#ifdef QUICKFILL_TEST
		++m_VisitSize;
#endif
	}
	else m_bMemError = 1;
}

/* Checks if line has already been visited */
BOOL CQuickFill::IsRevisit(int x1,int x2,int y)
{
	HLINE_NODE* pNext = m_pVisitList;
	while( pNext ) {
		if( pNext->y == y && pNext->x1 <= x1 && x2 <= pNext->x2 ) {
#ifdef QUICKFILL_TEST
			if( !m_pFreeList ) // do to where IsRevisit() is called
				pNext->dy = (int)m_DibData.RGBtoValue(RGB(0,255,0));
			else {
				int nColor;
				if( m_pFreeList->dy < 0 )
					nColor = (int)m_DibData.RGBtoValue(RGB(255,255,0));
				else
					nColor = (int)m_DibData.RGBtoValue(RGB(0,0,255));
				// tack on end for drawing
				while( pNext->pNext )
					pNext = pNext->pNext;
				HLINE_NODE *pNew = m_pFreeList;
				m_pFreeList = m_pFreeList->pNext;
				pNew->x1 = x1;
				pNew->x2 = x2;
				pNew->y  = y;
				pNew->dy = nColor;
				pNew->pNext = NULL;
				pNext->pNext = pNew;
			}
			++m_nRevisitCount;
#endif
			break;
		}
		pNext = pNext->pNext;
	}
	return( pNext != NULL );
}

/* Find next line segment on parent line.
 * Note: This function is designed to be
 *		called until NULL is returned.
 */
CQuickFill::HLINE_NODE* CQuickFill::FindNextLine(int x1,int x2,int y)
{
	static HLINE_NODE *pFindNext=(HLINE_NODE*)0;
	HLINE_NODE *pThis;
	if( !pFindNext )
		pFindNext = m_pLineList;
	for( pThis=pFindNext;pThis;pThis=pThis->pNext ) {
		if( (pThis->y+pThis->dy) == y ) {
			if( x1 < pThis->x1 && pThis->x1 <= x2 ) {
				pFindNext = pThis->pNext;
				return pThis;
			}
		}
	}
	return( pFindNext=(HLINE_NODE*)0 );
}

/* Removes pThis from line list */
void CQuickFill::PopThis(HLINE_NODE *pThis)
{
	if( m_pLineList ) {
		/* If pThis is not start of list */
		if( pThis->pPrev ) {
			HLINE_NODE *pPrev = pThis->pPrev;
			pPrev->pNext = pThis->pNext;
			if( pPrev->pNext )
				pPrev->pNext->pPrev = pPrev;
		}
		/* Remove pThis from start of list */
		else {
			m_pLineList = m_pLineList->pNext;
			if( m_pLineList )
				m_pLineList->pPrev = (HLINE_NODE*)0;
		}
		pThis->pNext = m_pFreeList;
		m_pFreeList = pThis;
#ifdef QUICKFILL_TEST
		--m_CurStackSize;
#endif
	}
}

/* Push unvisited lines onto the stack
 *
 * +-----------------------------------+
 * |                                   |
 * +---+   +---+   +---+   +---+   +---+
 * |   |   |   |   |   |   |   |   |   |
 * |   |(..+---+...+---+...+---+..)|   | <- Pushed Up
 * |   |xxxxxxxxxxxxxSxxxxxxxxxxxxx|   | <- Drawn
 * +---+(-------------------------)+---+ <- Pushed Down
 *
 * +-----------------------------------+
 * |                                   |
 * +---+   +---+   +---+   +---+   +---+
 * |   |(.)|   |(.)|   |(.)|   |(.)|   | <- Pushed Up
 * |   |xxx+...+xxx+...+xxx+...+xxx|   | <- Drawn
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 *
 * +-----------------------------------+
 * |                                   |
 * +---+(.)+---+(.)+---+(.)+---+(.)+---+ <- Pushed Up
 * |   |xxx|   |xxx|   |xxx|   |xxx|   | <- Drawn
 * |   |xxx+---+xxx+---+xxx+---+xxx|   |
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 *
 * +-----------------------------------+
 * |    (.)     (.)     (.)     (.)    | <- Pushed Up
 * +---+xxx+---+xxx+---+xxx+---+xxx+---+ <- Drawn
 * |   |xxx|   |xxx|   |xxx|   |xxx|   |
 * |   |xxx+---+xxx+---+xxx+---+xxx|   |
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 *
 * +(---------------------------------)+ <- Pushed Up
 * |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| <- Drawn
 * +(-)+xxx+(-)+xxx+(-)+xxx+(-)+xxx+(-)+ <- Pushed Down (PushOpposite)
 * |   |xxx|   |xxx|   |xxx|   |xxx|   |
 * |   |xxx+---+xxx+---+xxx+---+xxx|   |
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 */
void CQuickFill::PushOpposite(int OldX1,int OldX2,int x1,int x2,int y,int dy)
{
	/* Find next line on parent line */
	HLINE_NODE *pFind = FindNextLine(x1,x2,y);
	if( !pFind ) {
		/* push cliped left ends */
		if( x1 < --OldX1 )
			PushLine(x1,--OldX1,y,-dy);
		if( x2 > ++OldX2 )
			PushLine(++OldX2,x2,y,-dy);
	}
	else {
		/* push cliped left */
		if( x1 < --OldX1 )
			PushLine(x1,--OldX1,y,-dy);
		/* set test value for right cliping */
		OldX1 = x2+1;
		do {
			/* push valid line only */
			if( ++OldX2 < pFind->x1-2 )
				PushLine(++OldX2,pFind->x1-2,y,-dy);
			OldX2 = pFind->x2;
			/* clip right end if needed */
			if( OldX2 > OldX1 ) {
				pFind->x1 = ++OldX1;
			}
			else /* pop previously visited line */
				PopThis(pFind);
			pFind = FindNextLine(x1,x2,y);
		} while( pFind );

		/* Special Cases
		 *
		 * S = Seed point
		 * x = Filled point
		 * o = Unfilled point
		 *
		 * CASE 1:                CASE 2: Indirectly solved by
		 *                                the solution to case 1.
		 * +-----------------+    +-----------------+
		 * |xxxxxxxxxxxxxxxxx|    |xxxxxxxxxxxxxxxxx|
		 * |x+-----+x+-----+x|    |x+-----+x+-----+x|
		 * |x|xxxxx|x|x|x|x|x|    |x|xxxxx|x|x|x|x|x|
		 * |x|x|x|x|x|x|x|x|x|    |x|x|x|x|x|x|x|x|x|
		 * |x|x|x|x|x|x|x|x|x|    |x|x|x|x|x|x|x|x|x|
		 * |x|x|x|x|x|x|x|x|x|    |x|x|x|x|x|x|x|x|x|
		 * |xxxxxxxxxxxxxxx|x|    |xxxxxxxSxxxxxxx|x|
		 * |x|x|x|x|x|o|o|o|x|    |x|x|x|o|x|x|x|x|x|
		 * |x|x|x|x|x|o|o|o|x|    |x|x|x|o|x|x|x|x|x|
		 * |x|x|x|x|x|o|o|o|x|    |x|x|x|o|x|x|x|x|x|
		 * |x|xxxxx|x|o|o|o|x|    |x|xxxxx|x|x|x|x|x|
		 * |x+-----+x+-----+x|    |x+-----+x+-----+x|
		 * |xxxxxxxxxxxxxxxxS|    |xxxxxxxxxxxxxxxxx|
		 * +-----------------+    +-----------------+
		 *
		 */
		if( ++OldX2 < x2 )
			PushLine(OldX2,x2,y,-dy);
	}
	PushVisitedLine(x1,x2,y);
}

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.150123.1 | Last Updated 13 Mar 2004
Article Copyright 2004 by John R. Shaw
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid