计算机图形学（三）_图元的属性_13_ 不规则边界区域的填充方法_不规则图形填充算法

十三：不规则边界区域的填充方法
        区域填充的另一种方法是 从区域的一个内部点开始，由内向外逐点绘制直到边界 。这对如绘画程序生成的有不规则边界的填充区域是很有用的技术。一般来说，这些方法要求输人待填充区域中的一个起始位置，以及关于边界或内部的颜色信息。

        我们可以使用单一颜色或一个颜色图案来填充不规则区域。对于图案填充来说，如9节讨论的那样重叠一个颜色掩模。在处理区域中的每一个像素时，其颜色由对应的重叠掩模中的值来确定。

13.1边界填充算法

        假如边界是以单一颜色指定的，则填充算法可逐个像素地向外处理，直至遇到边界颜色。这种方法称为边界填充算法(boundary-fill algorithm )，用于比较容易地指定内点交互式绘画软件。艺术家或设计师可以使用图形板或其他交互设备来勾勒图形的轮廓，从颜色菜单中选择一个填充色，指定一种边界色，并选择一个内部点。然后在图形的内部涂上填充色。内边界和外边界可以一起用来定义边界填充的区域，图4.26给出了指定颜色范围的例子。

         基本上，边界填充算法从一个内点(x,y）开始检测相邻位置的颜色。如果检测位置不是该边界颜色，就将它改为填充颜色，并再检测其相邻位置。 这个过程延续到检测完区域边界颜色范围内的所有像素为止。
         图4.27 给出了从一个当前检测位置处理相邻像素的两种方法。在图4.27(a)中，检测四个邻点。即当前像素右面、左面、上面和下面的像素位置。使用这种方法填充的区域 称为4_连通(4-connected)区域。图4.27(b)中的第二种方法用于填充更复杂的图形。这里要测试的相邻位置包括四个对角像素。使用这种方法填充的区域 称为8_连通(8-connected )区域。8_连通区域边界填充算法将正确填充图4.28中定义的区域内部，4_连通区域边界填充算法只完成如图所示的部分填充。

        下列过程给出了使用由参数fillColor指定的单一颜色及由参数borderColor指定的边界颜色来填充4一连通区域的递归方法。我们可以将它扩充成填允8一连通区域，只要增加四条测试诸如(x±1,y±1)等对角位置的语句。

void boundaryFill4(int x, int y, int fillColor, int borderColor){
int interiorColor;
 
/*Set current color to fillColor, then perform following operations*/
getPixel (x, y, interiorColor);
if ((interiorColor != borderColor) && (interiorColor != fillColor)) {
   setPixel (x, y); // Set color of pixel to fillColor.
   boundaryFill4 (x + 1, y, fillColor, borderColor);
   boundaryFill4 (x - 1, y, fillColor, borderColor);
   boundaryFill4 (x, y + 1, fillColor, borderColor);
   boundaryFill4 (x, y - 1, fillColor, borderColor);
  }
}

        假如有些内部像素已经以填充颜色显示，则递归式的边界填充算法也许不能正确地填充区域。这是因为算法既按边界颜色又按填充颜色来检测下一个像素。 遇到一个具有填充颜色的像素将导致该递归分支终止，从而留下一些尚未填充的内部像素。 为了避免这种情况，可在应用边界填充程序前，将那些初始颜色改为填充颜色的内部像素的颜色。
         此外，由于 这个程序需要大量堆栈空间来存储相邻点，因而通常使用更有效的方法。这些方法沿扫描线填充水平像素区段，从而代替处理4_连通或8_连通相邻点。然后， 仅需将每个水平像素区段的起始位置放进堆栈，而不需将所有当前位置周围的未处理相邻位置都放进堆栈。如果使用这种方法，将从初始内部点开始，首先填充该像素所在扫描行的连续像素区段，然后将相邻扫描线上各段的起始位置放进堆栈，这些水平段分别由像素(显示为区域边界颜色)包围，接着逐步从堆栈顶部取出一个开始点，并重复上述过程。
        图4.29给出了如何使用逼近法对4_连通区域填充像素区段的例子。在这个例子中，从起始扫描线开始向顶部边界顺序地处理。在处理完所有上面的扫描线以后，再向下逐行填充剩余的像素段，直到底部边界。沿着每条扫描线，从左向右将每个水平区段的最左边像素位置放进堆栈，如图4.29所示。在图4.29(a)中，填充完初始区段以后，接下来的一条扫描线(向下和向上)上的段起始位置

1和2进栈；在图4.29(b)中，从堆栈中取出位置2并生成填充区段，然后将下一个扫描线上单个区段的起始像素(位置3)放进堆栈。在处理完位置3后，填充过的区段和进栈的位置如图4.29(c)所示。图4.29(d)给出了在处理指定区域右上角的所有区段后的已填充像素。接着处理位置5，并且对区域的左上角填充，然后取出位置4继续对较低的扫描线进行处理。

13.2泛滥填充算法
        有时，我们要对一个不是用单一颜色边界定义的区域进行填充(或重新涂色)。图4.30给出了由多个不同颜色区域围成的区域。可以通过替换指定的内部颜色而不是搜索边界颜色值来对该区域涂色。这个方法称为泛滥填充算法(flood-fill algorithm )。从指定的内部点(x，y)开始，将期望的填充颜色赋给所有当前设置为给定内部颜色的像素。假如所要涂色的区域具有多种内部颜色，可以重新设置像素值，从而使所有的内部点具有相同的颜色。然后使用4_连通或8_连通方法，逐步连通各像素位置，一直到所有内部点都已被涂色。下列过程从输入位置开始，递归地填充一个4_连通区域。

void boundaryFill4(int x, int y, int fillColor, int interiorColor){
int color;
 
/*Set current color to fillColor, then perform following operations. */
getPixel (x, y, color);
if ((color != interiorColor){
   setPixel (x, y); // Set color of pixel to fillColor.
   boundaryFill4 (x + 1, y, fillColor, interiorColor);
   boundaryFill4 (x - 1, y, fillColor, interiorColor);
   boundaryFill4 (x, y + 1, fillColor, interiorColor);
   boundaryFill4 (x, y - 1, fillColor, interiorColor);
  }
}

    我们可以像边界填充算法中讨论的那样修改上面的过程，通过填充水平像素区段。来减少对堆栈的存储要求。在这种方法中，仅存储具有值interiorColor的像素区段的起始位置。这种修改后的泛滥填充算法的步骤与图4.29所示的边界填充相同，从每个区间的第一个位置开始替代像素值直至遇interiorColor以外的值。