QuickFill: An Efficient Flood Fill Algorithm

// 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);
}