GDI Objective C 文本 Visual Studio 6 Visual C++ 6.0 Windows XP MFC 中级开发 Visual Studio Windows C++

QuickFill: 一种高效的 Flood Fill 算法

John R. Shaw

4.84/5 (67投票s)

2004年2月3日

13分钟阅读

551317

12077

高效洪水填充算法的设计与实现。

Sample Image

原始图像

Sample Image

填充模式

Sample Image

引言

本文旨在介绍如何设计一种高效的洪水填充算法。

为了展示良好设计的优势，我必须首先：描述洪水填充的基本类型及其各自的优缺点。

注意：高效，我指的是创建一种读取像素最少且内存分配最少的算法。虽然我们现在谈论的是填充位图，但从历史上看，洪水填充是直接读写视频，速度非常慢。因此，减少读写次数是必须的；内存也是有限的，所以减少内存使用量也是一个很大的优点。

什么是QuickFill算法？

QuickFill算法是一种非递归（种子填充）方法，通过扫描线搜索方法和双向链表节点来填充2D图形图像，以减少所需的内存量。扫描线方法与链表的结合使用极大地提高了图像填充的速度，并支持多种填充类型：背景、边框和图案填充。

注意：原始的QuickFill算法是在我的个人DOS图形库中编写的，用于填充视频显示器上的图像。

基本4向递归方法

这是所有洪水填充方法中最基本、最简单的一种。

它的优点：即使是初学者也能轻松实现。

它的缺点：重复采样像素和递归（可能导致堆栈溢出）。

Sample Image

上面的图显示了3x3图像的填充过程。您可以看到：每个像素被访问了2次或更多次，递归深度为10。

// Fill background with given color
void SeedFill_1(int x, int y, COLORREF fill_color)
{
    if( fill_color != GetPixel(x,y) ) { // sample pixel color
        SeedFill_1(x,y,fill_color);
        SeedFill_1(x-1,y,fill_color);
        SeedFill_1(x+1,y,fill_color);
        SeedFill_1(x,y-1,fill_color);
        SeedFill_1(x,y+1,fill_color);
    }
}

// Fill (over write) all pixels that are not the border color
void SeedFill_2(int x, int y, COLORREF fill_color, COLORREF border_color)
{
    if( border_color != GetPixel(x,y) ) { // sample pixel color
        SeedFill_2(x,y,fill_color,border_color);
        SeedFill_2(x-1,y,fill_color,border_color);
        SeedFill_2(x+1,y,fill_color,border_color);
        SeedFill_2(x,y-1,fill_color,border_color);
        SeedFill_2(x,y+1,fill_color,border_color);
    }
}

基本8向递归方法

这与4向方法类似，但效率更低。

它的优点：即使是初学者也能轻松实现。

它的缺点：重复采样像素、递归（可能导致堆栈溢出），并且它会在对角线处“泄漏”。

注意：我称之为异常洪水填充方法。由于它会在对角线处“泄漏”，因此用途非常有限。

Sample Image

上面的图显示了3x3图像的填充过程。您可以看到：每个像素被访问了3次或更多次，递归深度为10。

// Fill background with given color
void SeedFill_1(int x, int y, COLORREF fill_color)
{
    if( fill_color != GetPixel(x,y) ) { // sample pixel color
        SeedFill_1(x,y,fill_color);
        SeedFill_1(x-1,y,fill_color);
        SeedFill_1(x+1,y,fill_color);
        SeedFill_1(x,y-1,fill_color);
        SeedFill_1(x,y+1,fill_color);
        SeedFill_1(x-1,y+1,fill_color);
        SeedFill_1(x+1,y-1,fill_color);
        SeedFill_1(x+1,y+1,fill_color);
        SeedFill_1(x-1,y-1,fill_color);
    }
}

// Fill (over write) all pixels that are not the border color
void SeedFill_2(int x, int y, COLORREF fill_color, COLORREF border_color)
{
    if( border_color != GetPixel(x,y) ) { // sample pixel color
        SeedFill_2(x,y,fill_color,border_color);
        SeedFill_2(x-1,y,fill_color,border_color);
        SeedFill_2(x+1,y,fill_color,border_color);
        SeedFill_2(x,y-1,fill_color,border_color);
        SeedFill_2(x,y+1,fill_color,border_color);
        SeedFill_2(x-1,y+1,fill_color,border_color);
        SeedFill_2(x+1,y-1,fill_color,border_color);
        SeedFill_2(x+1,y+1,fill_color,border_color);
        SeedFill_2(x-1,y-1,fill_color,border_color);
    }
}

递归扫描线方法

递归扫描线方法是一种4向方法，但比单像素递归的4向或8向方法更高效。

它的优点：扫描完整的行。

它的缺点：重复采样某些行和递归（可能导致堆栈溢出）。

Sample Image

上面的图显示了3x3图像的填充过程。您可以看到：每行被访问了1到3次，递归深度为2。

下面的行填充方法可能效率不高，但它减少了像素被重新访问的次数，并减少了递归调用的次数。它还有一个优点是可以优化，也就是说，可以通过优化技术来改进它。

可以应用的一些技术包括

编写直接读写图像数据的扫描和搜索行函数
重写函数以消除递归

// Fill background with given color
extern int nMinX, nMaxX, nMinY, nMaxY;
void LineFill_3(int x1, int x2, int y, 
        COLORREF fill_color, COLORREF seed_color)
{
    int xL,xR;
    if( y < nMinY || nMaxY < y )
        return;
    for( xL = x1; xL >= nMinX; --xL ) { // scan left
        if( GetPixel(xL,y) != seed_color )
            break;
        SetPixel(xL,y,fill_color);
    }
    if( xL < x1 ) {
        LineFill_3(xL, x1, y-1, fill_color, seed_color); // fill child
        LineFill_3(xL, x1, y+1, fill_color, seed_color); // fill child
        ++x1;
    }
    for( xR = x2;  xR <= nMaxX; ++xR ) { // scan right
        if( GetPixel(xR,y) !=  seed_color )
            break;
        SetPixel(xR,y,fill_color);
    }
    if(  xR > x2 ) {
        LineFill_3(x2, xR, y-1, fill_color, seed_color); // fill child
        LineFill_3(x2, xR, y+1, fill_color, seed_color); // fill child
        --x2;
    }
    for( xR = x1; xR <= x2 && xR <= nMaxX; ++xR ) {  // scan between
        if( GetPixel(xR,y) == seed_color )
            SetPixel(xR,y,fill_color);
        else {
            if( x1 < xR ) {
                // fill child
                LineFill_3(x1, xR-1, y-1, fill_color, seed_color);
                // fill child
                LineFill_3(x1, xR-1, y+1, fill_color, seed_color);
                x1 = xR;
            }
            // Note: This function still works if this step is removed.
            for( ; xR <= x2 && xR <= nMaxX; ++xR) { // skip over border
                if( GetPixel(xR,y) == seed_color ) {
                    x1 = xR--;
                    break;
                }
            }
        }
    }
}

void SeedFill_3(int x, int y, COLORREF fill_color)
{
    COLORREF seed_color = GetPixel(x,y);
    if( fill_color != seed_color )
        LineFill_3(x,x,y,fill_color,seed_color);
}

简单的非递归扫描线方法

非递归扫描线方法是一种4向方法，但比递归方法更高效。

它的优点：扫描完整的行，没有递归。

它的缺点：重复采样某些行，以及堆栈大小受限。

下面的行填充方法比递归方法效率低。它还有一个优点是可以优化，也就是说，可以通过优化技术来改进它。

可以应用的一些技术包括

编写直接读写图像数据的扫描和搜索行函数
重写代码以使用链表作为堆栈

第二种所谓的优化技术似乎会降低填充过程的速度。如果它像下面的代码中使用数组堆栈一样使用，那么您是对的。事实是，链表允许我们应用其他优化技术，这些技术可以弥补效率上的轻微损失。例如：我们可以根据行号弹出堆栈中的项目，这减少了堆栈中的项目数量。

注意：由于大多数程序员现在处理位图，而不是直接读写视频，因此上述第一个优化可能是实现真正快速实心洪水填充算法所需要的。

// The following is a rewrite of the seed fill algorithm by Paul Heckbert.
// The original was published in "Graphics Gems", Academic Press, 1990.
//
// I have rewritten it here, so that it matches the other examples
// of seed fill algorithms presented.

extern int nMinX, nMaxX, nMinY, nMaxY;
typedef struct { int x1, x2, y, dy; } LINESEGMENT;

#define MAXDEPTH 10000

#define PUSH(XL, XR, Y, DY) \
    if( sp < stack+MAXDEPTH && Y+(DY) >= nMinX && Y+(DY) <= nMaxY ) \
    { sp->xl = XL; sp->xr = XR; sp->y = Y; sp->dy = DY; ++sp; }

#define POP(XL, XR, Y, DY) \
    { --sp; XL = sp->xl; XR = sp->xr; Y = sp->y+(DY = sp->dy); }

// Fill background with given color
void SeedFill_4(int x, int y, COLORREF new_color)
{
    int left, x1, x2, dy;
    COLORREF old_color;
    LINESEGMENT stack[MAXDEPTH], *sp = stack;

    old_color = GetPixel(x, y);
    if( old_color == new_color )
        return;

    if( x < nMinX || x > nMaxX || y < nMinX || y > nMaxY )
        return;

    PUSH(x, x, y, 1);        /* needed in some cases */
    PUSH(x, x, y+1, -1);    /* seed segment (popped 1st) */

    while( sp > stack ) {
        POP(x1, x2, y, dy);

        for( x = x1; x >= nMinX && GetPixel(x, y) == old_color; --x )
            SetPixel(x, y, new_color);

        if( x >= x1 )
            goto SKIP;

        left = x+1;
        if( left < x1 )
            PUSH(y, left, x1-1, -dy);    /* leak on left? */

        x = x1+1;

        do {
            for( ; x<=nMaxX && GetPixel(x, y) == old_color; ++x )
                SetPixel(x, y, new_color);

            PUSH(left, x-1, y, dy);

            if( x > x2+1 )
                PUSH(x2+1, x-1, y, -dy);    /* leak on right? */

SKIP:        for( ++x; x <= x2 && GetPixel(x, y) != old_color; ++x ) {;}

            left = x;
        } while( x<=x2 );
    }
}

QuickFill算法

终于，我们来到了QuickFill洪水填充方法，这是一种4向方法，但比简单的非递归方法更高效（信不信由你）。

注意：出于本文的目的，我将（主要）描述原始的QuickFill算法，因为包含的代码不使用优化的扫描、搜索和绘图函数（请记住，原始代码直接访问视频）。

它的优点是

支持3种填充类型：背景、边框和图案
优化的扫描、搜索和绘图函数
无递归
使用双向链表，以便根据行号高效地从列表中删除项目
在需要图案填充时，高效地使用列表进行反向行拆分

它的缺点：在实心填充期间，重复采样某些行。

从下面的代码可以看出，这是最复杂的洪水填充方法。它是间接从简单非递归方法中提出的思想演变而来的。

创建原始代码的步骤如下：

根据我能记住的关于扫描线填充的知识，编写了QuickFill函数。
将堆栈数组替换为两个单向链表。
修改了PopLine函数，以便根据行号删除行。
添加了SearchLeft、SearchRight、ScanLeft、ScanRight函数；以便优化搜索和扫描。
添加了PushOpposite函数，该函数反向拆分行，以减少重新访问的行数。这需要将列表更改为双向链表，并且列表需要按x轴排序。此函数背后的原因是消除所有行重新访问，但实际上，它只是减少了访问次数（但付出了代价）。
优化上述所有内容。

注意：在将代码移植到Windows时进行测试时，我发现单次访问代码存在一个很大的漏洞，图案和掩码不能为空，否则代码会一直陷入无限循环（因此有了以下内容）。

为了使此功能对Windows程序员更有用，我添加了代码以支持使用位图图案填充图像。由于PushOpposite仅减少了重新访问的行数，并未阻止重新访问，因此我必须添加另一个链表来跟踪哪些行已被访问。仍然需要PushOpposite函数，因为它仍然减少了重新访问的行数，并且作为一个额外的好处，它减少了放置在访问列表中的项目数量。为了优化访问列表，我决定使用访问块（矩形）而不是访问行，这减少了列表中所需的项目数量，意味着更少的内存分配。

注意：以下是代码1.0版本中的QuickFill函数。

/* Arguments:
 *        Pointer to bitmap to fill, (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,int x,int y,
    COLORREF fill_color,COLORREF border_color/*=CLR_INVALID*/)
{
    COLORREF ThisColor;
    int MaxY,MaxX,dy;
    int ChildLeft,ChildRight;
    int ParentLeft,ParentRight;

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

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

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

    /* Initialize internal info based on fill type */
    if( CLR_INVALID != border_color ) {
        /* Check color at x,y position */
        ThisColor = GetPixel(x,y);
        if( ThisColor == border_color )
            return -1;

        ThisColor = border_color;
        m_bXSortOn = TRUE;
    }
    else {
        /* Check color at x,y position */
        ThisColor = GetPixel(x,y);
        if( ThisColor == fill_color && !m_DibPattern.GetDibPtr() )
            return -1;

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

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

    /* Initialize Line list */
    if( MakeList() )
        return -2;

    /* Initialize maximum coords */
    MaxX = m_DibData.GetWidth()-1;
    MaxY = m_DibData.GetHeight()-1;

    /* Push starting point on stack */
    PushLine(x,x,y,+1);        /* Needed in one special case */
    PushLine(x,x,y+1,-1);

    /* Now start flooding */
    while( m_pLineList ) {
        PopLine(&ParentLeft,&ParentRight,&y,&dy);
        y += dy;
        if( y < 0 || MaxY < y )
            continue;
        if( m_bMemError )
            continue;
        if( m_bXSortOn && IsRevisit(ParentLeft,ParentRight,y) )
            continue;

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

        /* Find ChildLeft end ( ChildLeft>ParentLeft on failure ) */
        ChildLeft = FindLeft(ParentLeft,y,0,ThisColor)+1;
        if( ChildLeft<=ParentLeft ) {
            /* Find ChildRight end ( this should not fail here ) */
            ChildRight = FindRight(ParentLeft,y,MaxX,ThisColor)-1;
            /* Fill line */
            if( ChildLeft == ChildRight )
                SetPixel(ChildRight,y,fill_color);
            else
                DrawHorizontalLine(ChildLeft,ChildRight,y,fill_color);

#ifdef QUICKFILL_SLOW
            if( m_bSlowMode && hWnd ) {
                m_DibData.SetDIBits(pBitmap);
                ::InvalidateRect(hWnd,NULL,FALSE);
                ::UpdateWindow(hWnd);
            }
#endif

            /* Push unvisited lines */
            if( ParentLeft-1<=ChildLeft && 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);
            }
            /* Advance ChildRight end on to border */
            ++ChildRight;
        }
        else ChildRight = ParentLeft;

        /* Fill between */
        while( ChildRight < ParentRight ) {
            /* Skip to new ChildLeft end 
               ( ChildRight>ParentRight on failure ) */
            ChildRight = SkipRight(ChildRight,y,ParentRight,ThisColor);
            /* If new ChildLeft end found */
            if( ChildRight<=ParentRight ) {
                ChildLeft = ChildRight;
                /* Find ChildRight end ( this should not fail here ) */
                ChildRight = FindRight(ChildLeft,y,MaxX,ThisColor)-1;
                /* Fill line */
                if( ChildLeft == ChildRight )
                    SetPixel(ChildRight,y,fill_color);
                else
                    DrawHorizontalLine(ChildLeft,ChildRight,y,fill_color);

#ifdef QUICKFILL_SLOW
                if( m_bSlowMode && hWnd ) {
                    m_DibData.SetDIBits(pBitmap);
                    ::InvalidateRect(hWnd,NULL,FALSE);
                    ::UpdateWindow(hWnd);
                }
#endif

                /* 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);
                }
                /* Advance ChildRight end onto border */
                ++ChildRight;
            }
        }

        /* Push visited line onto visited stack */
        if( m_bXSortOn )
            PushVisitedLine(ParentLeft,ParentRight,y);
    }
    FreeList();
    m_DibData.SetDIBits(pBitmap);
    m_DibData.DeleteObject();
    return( m_bMemError?-2:0 );
}

父/子行关系

Sample Image

基本行推送

注意：在下面的图中，“已扫描”表示当被推送的行从堆栈中弹出时，下一行将被扫描。

Sample Image

反向行拆分

注意：在下面的图中，扫描/推送从顶部开始。

Sample Image

注意：在下面的图中，蓝色（带箭头的）线代表正在被推送的线。

Sample Image

背景

在创建QuickFill算法时，我只见过两种洪水填充类型，并且希望有一种算法能够处理这两种类型。第一种类型使用边框颜色方法，这意味着需要填充的区域必须首先用给定颜色的边框勾勒出来；这种方法是洪水填充中最不理想的。第二种类型使用种子点的颜色，这意味着只填充具有该颜色的像素；这种方法更通用，因为它允许多个不同颜色的图像对象包含在填充区域中。这两种洪水填充类型都使用了水平扫描线方法来解决图像填充问题。

当尝试查找有关如何实现快速洪水填充算法的信息时，我发现几乎没有相关信息。我找到的唯一算法是

许多出版物中提到（并且仍然在提到）的基本递归4向洪水填充，这是填充图像最糟糕（也是最慢）的方法
一种非递归扫描线版本（参考1），比4向版本更快（但对我来说仍然太慢），并且
一种非递归扫描线版本（参考2），它使用两个链表来实现洪水填充算法，更快（但仍然太慢）

前两种方法优点是紧凑且非常慢。另一方面，第三种方法有可能非常快且复杂。

在将这个想法搁置了一段时间后，因为它是我自己的个人图形库，优先级不高，我突然有了灵感。我在当地的咖啡店喝咖啡时，正在思考如何解决这个问题，然后一切都在我脑海中清晰起来。我从简单扫描线算法（参考1）的思想开始，然后使用一个表示LIFO堆栈的节点单向链表（参考2）对其进行扩展。在接下来的九天里，我对算法进行了增量更改，每项更改都旨在提高整体速度。完成后，我得到了一个不仅快，而且比我能找到的每一个实现都快的算法，除了Ted Gruber在Fastgraph库中实现的那个（用汇编编写）。代码完成后五个月，我终于回去添加了单行访问所需的代码，以便QuickFill函数也能处理图案填充。

参考文献

Paul Heckbert 在《Graphics Gems》, Academic Press, 1990 年的种子填充算法
Anton Treuenfels 在《C/C++ Users Journal》2004 年 8 月第 12 卷第 8 期中的高效洪水访问算法

Using the Code

注意：在慢速模式下运行演示程序时，可以按ESC键停止。

CDibData 特定

如果您没有安装Microsoft的Windows SDK，在调试模式下编译时会遇到一些编译错误。原因是BITMAPV5HEADER在Visual C++ 6.0附带的SDK中未定义。由于BITMAPV5HEADER仅用于显示调试信息，因此很容易注释掉相关代码。

// Normal solid filling
#include "QuickFill.h"

// Declare a quickfill variable
QuickFill qf;

// Call quickfill to flood fill image background starting at given point
qf.QuickFill(&bitmap, x, y, fill_color);

// Or call quickfill to flood fill outlined image starting at given point
qf.QuickFill(&bitmap, x, y, fill_color, border_color);

// Pattern filling
#include "QuickFill.h"

// Declare a quickfill variable
QuickFill qf;

// Set bitmap used as pattern
qf.SetPatternBitmap(&patternBitmap);

// If you want to make a color transparent (only applies to patterns)
qf.SetPatternClearColor(transparentColor);
 
// Call quickfill to flood fill image background starting at given point
qf.QuickFill(&bitmap, x, y, fill_color);

// If pattern bitmap no longer needed
// Frees pattern bitmap and invalidates pattern clear color.
qf.SetPatternBitmap();

// Masked filling
#include "QuickFill.h"

// Declare a quickfill variable
QuickFill qf;

// Set mask to use
BYTE diagMask[8] = {
    0x80, 0x80>>1, 0x80>>2, 0x80>>3,
    0x80>>4, 0x80>>5, 0x80>>6, 0x80>>6,
};
qf.SetFillMask(diagMask);

// Call quickfill to flood fill image background starting at given point
qf.QuickFill(&bitmap, x, y, fill_color);

// If mask to longer needed
qf.SetFillMask();

关注点

本文包含的代码依赖于CDibData类来提供对位图像素的直接访问。

我看不出有任何障碍可以重写代码以用于GDI+，我没有这样做的唯一原因是，我现在对GDI+的使用了解不够。此外，我有一个使用GDI编写的个人绘画程序，并希望将此代码添加到其中。

对于那些想要比较各种洪水填充算法的人，我建议如下

添加一些跟踪变量和代码（如QuickFill代码中的那些）
将测试函数或函数设为QuickFill类的私有成员
在QuickFill初始化之后，但在第一次推送之前，调用测试函数。然后，在测试函数调用之后进行清理，并返回而不进入主QuickFill循环。

注意：以上是我测试递归扫描线代码的方式。由于它是凭空写出来的，我需要确保它能正常工作。

如果有人知道如何完全消除访问列表的需要，我将非常感兴趣。当我发现用于减少重新访问的原始方法并未消除它们时，我感到被自己的代码侮辱了。在我编写QuickFill算法时，我可能知道这个问题，只是忘记了（可能性不大）。

问题：如何优化位图的QuickFill算法？

答案：修改CDibData类，使其具有用于ScanLeft、ScanRight、SearchLeft、SearchRight和水平线绘制的优化函数。当然，水平线绘制将是最困难的，因为它必须与DrawHorizontalLine成员函数相同。

历史

版本 1.0

2004年1月：从C（直接视频访问）转换为C++，用于MS Windows位图，并增加了对以下内容的支持：用作填充的图案位图，以及用于在图案和掩码填充期间消除重新访问的访问块列表。

注意：由于原始代码具有直接视频访问，因此它可以利用（使用正确的写入模式）字节块复制和颜色位掩码读取（读取模式1）。这两者都得到了硬件支持（VGA/EGA显示器），并且比直接从位图中读取/写入单个像素更有效。

版本 1.1

2004年2月6日：添加了左优化，消除了部分重新访问
2004年2月8日：添加了反向裁剪优化，消除了部分重新访问
2004年2月15日：发现了PushOpposite的特殊情况并进行了修正
2004年2月19日：将内部扫描、搜索和线绘制例程更改为使用像素颜色值，以提高处理调色板位图时的整体速度（修改了CDibData）
2004年3月5日：（1）将PushVisitedLine从QuickFill移至PushOpposite，这增加了重新访问次数并减小了访问列表的大小（8:1）。（2）将访问列表更改为使用HLINE_NODE，因为不再需要块检查，并且由于自由列表可以被所有人使用，因此分配次数减少了（当然，HLINE_NODE比我们需要的要大，因为它不是仅限访问列表的节点类型）。
2004年3月9日：（1）向QuickFill添加参数，以便用户可以指定要填充的矩形区域。（2）添加了GetInvalidRect函数和相关代码，以便用户可以检索已修改的位图区域的矩形坐标，因为缺少此信息迫使用户重新绘制整个位图。

演示程序更改

“填充掩码”选择选项。
“显示重新访问”选项。当使用图案位图或掩码时，此选项用于显示哪些行被放入了访问列表中。行类型：青色->访问列表中的行，黄色->重新访问的行方向 = -1，蓝色->重新访问的行方向 = +1。
通过鼠标选择填充区域（左键单击并拖动以选择区域）。要填充：在选定区域内单击鼠标左键并释放即可填充。
在位图右侧显示的附加信息中添加了填充的已用时间和重新访问计数。

致谢

Andrew J. McCauley 修改了CDibData调试代码，使其基于WINVER而不是仅基于头类型进行头类型检查。这解决了用户未安装新Windows SDK时出现的编译错误。

许可证

本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。

作者可能使用的许可证列表可以在此处找到。