Lode 的计算机图形学教程

泛洪填充

目录

返回索引

简介

泛洪填充的目的是将一片相连像素区域全部填充为同一颜色。它就是许多绘图程序中的"油漆桶"工具。下面是一个示例：左侧为原始图像。对大形状内部执行泛洪填充后，算法将形状内所有像素设置为新颜色，而边框及外部像素保持不变。



泛洪填充算法有时也称为种子填充：你种下一粒种子（即起始像素），如果周围像素颜色符合条件，则递归地在原始种子周围不断种下更多种子。每粒新种子负责为其所在位置的像素着色，并检测周围需要着色的新像素。

泛洪填充算法有很多种，本文讨论其中 3 种（4 向、8 向和基于扫描线），每种各有两个版本：递归版本和使用栈的版本。所有这些算法都是某种形式的深度优先搜索（但基于扫描线的版本更为专用）。

还有一种称为边界填充的算法，它与泛洪填充非常相似，但会以特定颜色的像素作为边界来填充区域。边界填充的算法与泛洪填充非常类似，区别仅在于种植新种子时的判断条件。

你可以在此处下载本教程的完整源代码。

测试程序

为了测试不同的泛洪填充算法，我们需要一个可以绘制形状并进行填充的测试程序。该测试程序是"绘图"教程中所述绘图程序的简化版。它还包含一个基准测试，可以对比两种不同的泛洪填充算法，并显示各自填充某区域 50 次所花费的毫秒数。

由于泛洪填充需要读取像素，我们使用一个缓冲区（称为 screenBuffer[h][w]）来存储像素，而不是直接对屏幕进行读写操作。这里所有颜色均使用整数值表示，而不使用 ColorRGB 结构体。

此处给出的代码包含完整的测试程序，但不含泛洪填充算法（将在本教程后续部分说明）以及 paint_drawLine 函数——该函数与 QuickCG.cpp 中的 drawLine 函数完全相同，只是将输出目标改为 screenBuffer 而非直接写入屏幕。包含所有这些函数的完整源代码可在此处下载：floodfill.cpp。

以下是我们将要实现的所有 floodFill 函数的声明、部分函数使用的栈、辅助函数以及图形缓冲区的初始化代码。

此处定义的栈容量相当大（166777216），你可以轻松将其调小。只有在大分辨率屏幕上测试性能较差的泛洪填充函数时，才需要这么大的栈。最优的泛洪填充算法根本不需要很大的栈，除非你在极高分辨率下工作。

//the floodfill algorithms
void floodFill4(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor);
void floodFill8(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor);
void floodFill4Stack(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor);
void floodFill8Stack(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor);
void floodFillScanline(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor);
void floodFillScanlineStack(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor);

//the auxiliary functions
bool paint_drawLine(int x1, int y1, int x2, int y2, ColorRGB color);
void clearScreenBuffer(ColorRGB color);

//the graphics buffer
#define screenW 256
#define screenH 256
//pixel (x, y) is at index y * screenW + x, the memory structure is per horizontal scanline.
std::vector screenBuffer(screenH * screenW);

以下是测试程序的主函数，它支持 3 种不同的鼠标操作： 基准测试代码会对你选择的 2 种泛洪填充算法各执行 50 次，记录各自耗时，显示结果，然后等待你按下任意键。按空格键启动基准测试，它将在当前鼠标位置执行泛洪填充。

int main(int argc, char *argv[])
{
  screen(screenW, screenH, 0, "Flood Fill");
  clearScreenBuffer(RGB_White);
  int mouseX, mouseY;
  int oldMouseX, oldMouseY;
  bool LMB, RMB;

  while(!done())
  {
    oldMouseX = mouseX;
    oldMouseY = mouseY;
    getMouseState(mouseX, mouseY, LMB, RMB);

    //3 different mouse input actions
    if(LMB) paint_drawLine(oldMouseX, oldMouseY, mouseX, mouseY, RGB_Black);
    if(RMB)
    {
      Uint32 color = RGBtoINT(ColorRGB((mouseX % 3 + 1) * 64, (mouseY % 8) * 32, (mouseX + mouseY) % 256));
      floodFillScanlineStack(screenBuffer.data(), w, h,
                        mouseX, mouseY, color, screenBuffer[mouseY * w + mouseX]);
    }
    if(RMB && LMB) clearScreenBuffer(RGB_White);

    //benchmark
    readKeys();
    if(keyPressed(SDLK_SPACE))
    {
      float startTime = getTime();
      for(int i = 0; i < 300; i++)
      {
        floodFill4Stack(screenBuffer.data(), w, h,
                        mouseX, mouseY, RGBtoINT(ColorRGB(i%256,255,i%256)), screenBuffer[mouseY * w + mouseX]);
      }
      float endTime = getTime();

      float startTime2 = getTime();
      for(int i = 0; i < 300; i++)
      {
        floodFillScanlineStack(screenBuffer.data(), w, h,
                           mouseX, mouseY, RGBtoINT(ColorRGB(i%256,255,i%256)), screenBuffer[mouseY * w + mouseX]);
      }
      float endTime2 = getTime();

      drawBuffer(&screenBuffer[0]);
      fprint(endTime - startTime, 3, 0, 0, RGB_Black, 1, RGB_White);
      fprint(endTime2 - startTime2, 3, 0, 8, RGB_Black, 1, RGB_White);
      print("press c to continue", 0, 16, RGB_Black, 1, RGB_White);  // any key works, but "space" tends to re-trigger the benchmark
      redraw();
      sleep();
    }

    //redraw the screen each frame
    drawBuffer(&screenBuffer[0]);
    redraw();
  }
  return 0;
}

以下是栈操作函数，仅被 3 个 floodFill 函数使用。栈是一种内存结构，你可以将新值压入栈顶，或弹出栈顶值来读取它。你只能访问栈顶的值，而读取栈顶值时必须弹出它，即同时将其移除。

为简单起见，我们将两个坐标分别存入栈中，因此每次压栈和弹栈各操作两个值。
pop 函数以引用方式接收 x 和 y，从而可以修改参数中传入的 x 和 y。若成功从栈顶取到值，pop 函数返回 true；若栈为空则返回 false。

我们使用 C++ 的 std::vector 数据结构作为栈，因为它内置了对栈操作的支持。 
void push(std::vector<int>& stack, int x, int y)
{
  // C++'s std::vector can act as a stack and manage memory for us
  stack.push_back(x);
  stack.push_back(y);
}

bool pop(std::vector<int>& stack, int& x, int& y)
{
  if(stack.size() < 2) return false; // it's empty
  y = stack.back();
  stack.pop_back();
  x = stack.back();
  stack.pop_back();
  return true;
}

以下是辅助函数之一 clearScreenBuffer，它将整个 screenBuffer 设置为指定颜色。另一个函数 paint_drawLine 不在此处给出，因为它篇幅较长，且与 quickCG.cpp 中的 drawLine 函数几乎相同，区别仅在于它将 screenBuffer 的像素设置为指定颜色，而不使用 pset。

void clearScreenBuffer(ColorRGB color)
{
  for(int y = 0; y < h; y++)
  for(int x = 0; x < w; x++)
  {
    screenBuffer[y * w + x] = RGBtoINT(color);
  }
}

除了这些函数之外，测试程序当然还需要你定义 6 个 floodFill 函数，这些函数将在下文给出。

4 向递归方法（floodFill4）

这是最简单的算法，但也是最慢的。此外，由于它使用递归函数，在填充较大区域时递归栈可能溢出，导致程序崩溃。

调用函数时需传入以下参数：起始位置（即你点击以启动泛洪填充的位置）、oldColor（被覆盖区域的颜色）以及 newColor（这些像素应获得的新颜色）。递归过程如下：在起始位置"种下一粒种子"。每粒种子将其所在位置的像素设置为新颜色，然后在其 4 个邻居处各种下一粒新种子。每粒新种子同样会绘制一个像素并继续种下更多种子，但前提是满足以下条件：
这个算法非常容易编写：

//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor)
{
  if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x] == oldColor && screenBuffer[y][x] != newColor)
  {
    screenBuffer[y * w + x] = newColor; //set color before starting recursion!

    floodFill4(screenBuffer, w, h, x + 1, y    , newColor, oldColor);
    floodFill4(screenBuffer, w, h, x - 1, y    , newColor, oldColor);
    floodFill4(screenBuffer, w, h, x    , y + 1, newColor, oldColor);
    floodFill4(screenBuffer, w, h, x    , y - 1, newColor, oldColor);
  }
}

该函数会不断递归调用自身，直到所有像素都被填充。调用各邻居的 floodFill4 函数的顺序并不重要。在上面的示例中，它首先尝试右侧邻居，因此算法会先向右绘制一条线，直到遇到边界。然后最后调用的 floodFill4 函数返回到倒数第二个，后者检测左侧邻居。由于左侧已经绘制过，它接着检测下方邻居。下方尚未绘制，如果不是边界，算法就会继续在那里向右检测，如此循环……

请注意颜色用整数表示，而不使用速度较慢的 ColorRGB 结构体。

此截图显示了 floodFill4 算法仍在执行中的状态：


8 向递归方法（floodFill8）

该算法与前一个非常相似，区别在于它检测的不是 4 个邻居，而是 8 个。这意味着此版本的泛洪填充算法会穿透宽度为 1 像素的斜边：



两个红色像素互为邻居，因此算法会穿过斜向黑线继续填充。代码与 4 向版本非常相似：

//Recursive 8-way floodfill, crashes if recursion stack is full
void floodFill8(Uint32* screenBuffer, int w, int h,
                int x, int y, Uint32 newColor, Uint32 oldColor)
{
  if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x] == oldColor && screenBuffer[y][x] != newColor)
  {
    screenBuffer[y * w + x] = newColor; //set color before starting recursion!

    floodFill8(screenBuffer, w, h, x + 1, y    , newColor, oldColor);
    floodFill8(screenBuffer, w, h, x - 1, y    , newColor, oldColor);
    floodFill8(screenBuffer, w, h, x    , y + 1, newColor, oldColor);
    floodFill8(screenBuffer, w, h, x    , y - 1, newColor, oldColor);
    floodFill8(screenBuffer, w, h, x + 1, y + 1, newColor, oldColor);
    floodFill8(screenBuffer, w, h, x - 1, y - 1, newColor, oldColor);
    floodFill8(screenBuffer, w, h, x - 1, y + 1, newColor, oldColor);
    floodFill8(screenBuffer, w, h, x + 1, y - 1, newColor, oldColor);
  }
}

与 4 向版本不同，8 向版本可以填充细线，例如形状的边缘：



floodFill4 算法（即绘图程序中油漆桶工具的工作方式）只会为黑色曲线的少数几个像素着色，仅通过角点接触的像素在该情况下不被视为邻居。

但是，你不能使用 floodFill8 来填充形状内部，因为它会从侧面漏出。

带栈的 4 向方法（floodFill4Stack）

该算法与递归版本的功能完全相同，只是它使用一个 while 循环，循环直到栈为空，并将新位置压入栈中，而不是发起新的递归调用。因此唯一的区别在于我们现在使用自己的栈操作，而不是递归函数所使用的调用栈。这意味着我们可以控制栈的大小，并在栈溢出时正确地停止泛洪填充算法，而不是让程序直接崩溃。实现上还有一些其他细微差异。

栈操作函数已在"测试程序"章节中描述。

//4-way floodfill using our own stack routines
void floodFill4Stack(Uint32* screenBuffer, int w, int h,
                     int x, int y, Uint32 newColor, Uint32 oldColor)
{
  if(newColor == oldColor) return; //avoid infinite loop

  static const int dx[4] = {0, 1, 0, -1}; // relative neighbor x coordinates
  static const int dy[4] = {-1, 0, 1, 0}; // relative neighbor y coordinates

  std::vector<int> stack;
  push(stack, x, y);
  while(pop(stack, x, y))
  {
    screenBuffer[y * w + x] = newColor;
    for(int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx >= 0 && nx < w && ny >= 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
        push(stack, nx, ny);
      }
    }
  }
}

该算法比递归版本稍快，至少更加健壮。

带栈的 8 向方法（floodFill8Stack）

这是前一个函数的 8 向版本，区别仅在于需要额外检测 4 个邻居坐标：

//8-way floodfill using stack instead of recursion
void floodFill8Stack(int x, int y, int newColor, int oldColor)
{
  if(newColor == oldColor) return; //avoid infinite loop

  static const int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}; // relative neighbor x coordinates
  static const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // relative neighbor y coordinates

  std::vector stack;
  push(stack, x, y);
  while(pop(stack, x, y))
  {
    screenBuffer[y][x] = newColor;
    for(int i = 0; i < 8; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx >= 0 && nx < w && ny >= 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
        push(stack, nx, ny);
      }
    }
  }
}

递归扫描线泛洪填充算法（floodFillScanline）

该算法基于以下步骤：
与原始的 floodFill4 和 floodFill8 算法一样，该算法也是递归的，但现在每次递归会填充整条扫描线而不是单个像素，因此所需的递归次数和栈深度大幅减少。下面给出的实现首先绘制当前扫描线，然后检测上方和下方的扫描线，并通过再次递归调用自身来种下新种子。

该算法给出与 floodFill4 算法相同的结果，而非 floodFill8 的结果。如有需要，你可以修改它，让其同时检测上下方各向左和向右偏移一个像素的扫描段，从而实现类似 floodFill8 的效果。

//stack friendly and fast floodfill algorithm, using recursive function calls
void floodFillScanline(int x, int y, int newColor, int oldColor)
{
  if(oldColor == newColor) return;
  if(screenBuffer[y * w + x] != oldColor) return;

  int x1;

  //draw current scanline from start position to the right
  x1 = x;
  while(x1 < w && screenBuffer[y * w + x1] == oldColor)
  {
    screenBuffer[y * w + x1] = newColor;
    x1++;
  }

  //draw current scanline from start position to the left
  x1 = x - 1;
  while(x1 >= 0 && screenBuffer[y * w + x1] == oldColor)
  {
    screenBuffer[y * w + x1] = newColor;
    x1--;
  }

  //test for new scanlines above
  x1 = x;
  while(x1 < w && screenBuffer[y * w + x1] == newColor)
  {
    if(y > 0 && screenBuffer[(y - 1) * w + x1] == oldColor)
    {
      floodFillScanline(screenBuffer, w, h, x1, y - 1, newColor, oldColor);
    }
    x1++;
  }
  x1 = x - 1;
  while(x1 >= 0 && screenBuffer[y * w + x1] == newColor)
  {
    if(y > 0 && screenBuffer[(y - 1) * w + x1] == oldColor)
    {
      floodFillScanline(screenBuffer, w, h, x1, y - 1, newColor, oldColor);
    }
    x1--;
  }

  //test for new scanlines below
  x1 = x;
  while(x1 < w && screenBuffer[y * w + x1] == newColor)
  {
    if(y < h - 1 && screenBuffer[(y + 1) * w + x1] == oldColor)
    {
      floodFillScanline(screenBuffer, w, h, x1, y + 1, newColor, oldColor);
    }
    x1++;
  }
  x1 = x - 1;
  while(x1 >= 0 && screenBuffer[y * w + x1] == newColor)
  {
    if(y < h - 1 && screenBuffer[(y + 1) * w + x1] == oldColor)
    {
      floodFillScanline(screenBuffer, w, h, x1, y + 1, newColor, oldColor);
    }
    x1--;
  }
}

此截图显示了扫描线泛洪填充算法正在执行中的状态：



请注意，由于我们的内存缓冲区按扫描线组织，处理水平扫描线（如本文所做）比处理垂直条带更快。这是因为 CPU 会缓存二维 screenBuffer 数组的部分内容，处理水平线时只改变数组的 x 坐标，相关数据在内存结构中排列更加紧密；而沿 y 方向变化时，数据间距更大，所需内容未全部命中缓存的概率更高，从而导致速度变慢。

带栈的扫描线泛洪填充算法（floodFillScanlineStack）

这与前一个算法非常相似，区别同样在于使用自定义栈操作代替递归。该实现还使用了两个布尔变量 "spanAbove" 和 "spanBelow"，用于记录上方或下方检测到的像素是属于新的扫描段，还是已经压入栈的扫描段。在递归实现中不需要这两个变量，因为那里上下方的扫描段会先被绘制，使其所有像素已获得 newColor，从而其余像素不会再被检测到。

//The scanline floodfill algorithm using stack instead of recursion, more robust
void floodFillScanlineStack(int x, int y, int newColor, int oldColor)
{
  if(oldColor == newColor) return;

  int x1;
  bool spanAbove, spanBelow;

  std::vector<int> stack;
  push(stack, x, y);
  while(pop(stack, x, y))
  {
    x1 = x;
    while(x1 >= 0 && screenBuffer[y * w + x1] == oldColor) x1--;
    x1++;
    spanAbove = spanBelow = 0;
    while(x1 < w && screenBuffer[y * w + x1] == oldColor)
    {
      screenBuffer[y * w + x1] = newColor;
      if(!spanAbove && y > 0 && screenBuffer[(y - 1) * w + x1] == oldColor)
      {
        push(stack, x1, y - 1);
        spanAbove = 1;
      }
      else if(spanAbove && y > 0 && screenBuffer[(y - 1) * w + x1] != oldColor)
      {
        spanAbove = 0;
      }
      if(!spanBelow && y < h - 1 && screenBuffer[(y + 1) * w + x1] == oldColor)
      {
        push(stack, x1, y + 1);
        spanBelow = 1;
      }
      else if(spanBelow && y < h - 1 && screenBuffer[(y + 1) * w + x1] != oldColor)
      {
        spanBelow = 0;
      }
      x1++;
    }
  }
}

以下是 floodFill4Stack 与 floodFillScanlineStack 函数之间的基准测试结果：在 2004 年的 Athlon 1700 CPU 上，floodFill4Stack 填充该形状 50 次耗时 239 毫秒，而 floodFillScanlineStack 仅耗时 34 毫秒。



最后编辑：2018 年

版权所有（c）2004-2018 Lode Vandevenne。保留所有权利。