计算机图形学--填充

扫描线多边形填充算法

扫描线多边形填充算法（Scanline Polygon Fill Algorithm）是一种计算机图形学中广泛使用的算法，用于将一个封闭的多边形形状涂色填充。它通过扫描线的方式，从上到下将多边形内的像素按照预设的填充颜色来进行填充。本文将详细介绍扫描线多边形填充算法的原理、流程和实现细节。

1.算法原理：

扫描线多边形填充算法基于扫描线的思想，在水平方向上扫描每一行像素，并检测多边形边界与扫描线的交点。通过将扫描线从上到下扫过整个多边形，对于每一行像素，找出与多边形边界交点的水平线段，然后根据填充颜色将像素点进行填充。

2.算法流程：

-找出多边形的最小和最大Y坐标，确定扫描线的范围。

-从最小Y坐标开始，到最大Y坐标结束，逐行进行扫描。

-对于每一行，找出与多边形边界交点的水平线段。

-根据填充颜色，为每个水平线段上的像素点进行填充。

3.算法实现：

-首先，需要根据给定的多边形描述边界的顶点坐标，计算出每条边的斜率、最小和最大Y值以及每条边的X坐标交点。

-然后，对于每一扫描线，找出与多边形边界交点的水平线段，即找出交点的X坐标范围。 -最后，根据填充颜色，将该范围内的像素点进行填充。

4.算法优化：

- 针对复杂多边形，可以使用活性边表（AET，Active Edge Table）来管理边界信息，加快查找交点的速度。

-可以使用桶排序来排序边界事件点，提高扫描速度。

-根据多边形边的特征，对算法进行优化，减少不必要的计算和内存消耗。

5.算法应用：

-扫描线多边形填充算法广泛应用于计算机图形学中的图形渲染、图像处理等领域。

-在游戏开发、CAD绘图、虚拟现实等应用中，扫描线多边形填充算法被用于快速绘制和渲染复杂多边形。

总结：

扫描线多边形填充算法是一种经典的计算机图形学算法，通过扫描线的方式对多边形进行填充。它可以高效地处理各种形状的多边形，包括凸多边形和凹多边形。算法虽然简单，但在实际应用中具有广泛的用途。通过合理的优化和算法细节实现，可以提高算法的效率和性能。

佛山科学技术学院

实 验 报 告

课程名称 计算机图形学基础

实验项目 多边形的区域填充

一、实验目的

1. 通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理

2. 掌握多边形区域填充算法的基本过程

3. 掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。

二、实验内容

用种子填充算法和扫描线填充算法等任意两种算法实现指定多边形的区域填充。

三、实验原理

种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。

四向连通填充算法：

a） 种子像素压入栈中；

b） 如果栈为空，则转e)；否则转c)；

c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；

d） 转b）；

e） 结束。

扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

区域填充的扫描线算法可由下列四个步骤实现：

(1)初始化：堆栈置空。将种子点(x,y)入栈。

(2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。

(3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。

(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。

计算机图形学——区域填充算法（基本光栅图形算法）⼀、区域填充概念

区域：指已经表⽰成点阵形式的填充图形，是象素的集合。

区域填充：将区域内的⼀点（常称【种⼦点】）赋予给定颜⾊，然后将这种颜⾊扩展到整个区域内的过程。

区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种⼦点的颜⾊扩展到区域内的其它点。

1、区域有两种表⽰形式

1）内点表⽰：枚举出区域内部的所有象素，内部所有象素着同⼀个颜⾊，边界像素着与内部象素不同的颜⾊。

2）边界表⽰：枚举出区域外部的所有象素，边界上的所有象素着同⼀个颜⾊，内部像素着与边界象素不同的颜⾊。

2、区域连通

1）四向连通区域：从区域上⼀点出发可通过【上、下、左、右】四个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

2）⼋向连通区域：从区域上⼀点出发可通过【上、下、左、右、左上、右上、左下、右下】⼋个⽅向移动的组合，在不越出区域的前提下，到达区

域内的任意象素。⼆、简单种⼦填充算法基本思想

给定区域G⼀种⼦点（x, y）,⾸先判断该点是否是区域内的⼀点，如果是，则将该点填充为新的颜⾊，然后将该点周围的四个点（四连通）或⼋个点

（⼋连通）作为新的种⼦点进⾏同样的处理，通过这种扩散完成对整个区域的填充。

这⾥给出⼀个四连通的种⼦填充算法（区域填充递归算法），使⽤【栈结构】来实现原理算法原理如下：种⼦像素⼊栈，当【栈⾮空】时重复如下三

步：算法代码

这⾥给出⼋连通的种⼦填充算法的代码：

void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color)

{

if(x0&&y0)

{

if (pixels[y*w+x]==old_color)

{

pixels[y*w+x]== new_color);

flood_fill_8(pixels, x,y+1,old_color,new_color);

flood_fill_8(pixels, x,y-1,old_color,new_color);

图形填充的操作方法

图形填充是一种常见的图形处理操作，其目的是为图形中的封闭区域添加颜色、纹理或渐变等效果，从而使得图形更加生动、美观。图形填充在计算机图形学、计算机辅助设计、游戏开发等领域都有广泛的应用。本文将详细介绍图形填充的操作方法。

图形填充的操作方法可以分为手动填充和自动填充两种。

手动填充是指通过人工操作来为图形中的封闭区域进行填充。主要有以下几种方式：

1. 手绘填充：通过使用绘图工具，如铅笔、画笔等，在图形中逐点进行填充。这种方法适用于填充简单的图形，如小面积的矩形、圆形等。但对于复杂的图形，手绘填充需要耗费大量时间和精力。

2. 区域选择填充：将图形中的封闭区域选中后，再通过图形软件提供的填充工具进行填充。这种方法适用于具有规则边界的图形区域，如矩形、圆形等。一般情况下，填充工具提供了多种填充方式，如纯色填充、渐变填充、纹理填充等。

3. 自由选择填充：对于复杂的图形区域，可以使用自由选择工具选中区域，然后再进行填充。自由选择工具可以根据鼠标轨迹智能选择图形区域边界，提高填充效率和准确性。

手动填充的优点是精确控制填充的细节和效果，但缺点是耗时耗力，对于复杂的图形难以实现。

自动填充是指通过计算机算法来为图形中的封闭区域进行自动填充。主要有以下几种方式：

1. 扫描线填充：扫描线填充是一种基于扫描线的图形填充算法。该算法从图形区域的上边界开始，逐行扫描并填充像素，直到达到下边界。在填充过程中，根据扫描线与图形边界的交点，来确定填充的范围。该算法适用于任意封闭图形的填充，填充效果较为均匀。

2. 边界种子填充：边界种子填充是一种基于种子点的图形填充算法。该算法首先从图形区域的边界上选择一个种子点，然后向四周扩散，逐渐填充整个区域。在填充过程中，需要通过判断像素的颜色是否与边界颜色一致，来确定是否填充该像素。该算法适用于有规则边界的图形区域，填充效果较为快速。

3. 边界种子扫描线填充：边界种子扫描线填充算法是扫描线填充和边界种子填充的结合。该算法首先选取一个种子点，然后通过扫描线填充的方式逐行扫描并填充像素，但在填充过程中需要判断当前像素是否与边界颜色一致，如果一致则继续填充，否则停止填充。该算法适用于有规则边界的图形区域，填充效果较为均匀。