第三章二维图形基础物体的形状和颜色可用象素矩阵或直线线段和多边形填充区域等基本几何结构来描述。点和直线段是最简单的几何成分，其它可供构造图形的输出图元有圆及其它圆锥曲线、二次曲面、样条曲线和曲面、多边形填充区域以及字符串等。而二维图形的生成是三维图形生成的基础，研究计算机生成图形需先从二维图形的生成开始。下面将讨论一些基本二维图元生成技术和算法，以光栅图形系统的扫描转换方法为基础。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

3.1直线生成算法最基本的图形显示方式是直线方式。实际上，无论什么复杂图形，它们无非是由直线段和曲线段组成。而对于曲线及各种复杂的图形，可以将其离散成许多小直线段，连接各直线来逼近欲生成的曲线或其它复杂图形，所以一般图形都可以看成是由直线段组成。因此，直线段生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速度。在光栅显示器上显示图形是将线段上所有象素点亮的过程。如果已知直线段两个端点，可以有很多种不同的数学方法来决定应改变在两端点之间的那些象素的亮度值才能显示出两点间的直线。在绘图仪上绘直线段，主要决定X、Y方向上的位移量，这些算法之间主要区别是判别和生成x、y增量的过程和方法的不同。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

在PC机中，点亮屏幕上一个点是由BIOS控制完成的，各种程序语言中都有描点语句。例如C语言为putpixel(x,y,color)。
1. 点的生成点是图形中最基本的图素，直线、曲线以及其它的图元都是点的集合。在几何学中，一个点既没有大小，也没有维数，点只是表示坐标系统中一个位置。在计算机图形学中，点是用数值坐标来表示的。在直角坐标系中点由（x,y) 两个数值组成的坐标表示，在三维坐标系中点是由（x,y,z)三个数值组成的坐标表示。在输出设备上输出一个点，就要把应用程序中的坐标信息转换成所用输出设备的相应位置。对于一个CRT监视器来说，输出一个点就是要在指定的屏幕位置上打开电子束，使该位置上的荧光点亮。在PC机中，点亮屏幕上一个点是由BIOS控制完成的，各种程序语言中都有描点语句。例如C语言为putpixel(x,y,color)。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

2. DDA直线生成算法（digital differential analyzer)
直线是点的集合，在几何学中直线被定义为两个点之间的最短距离。也就是说一条直线是指所有在它上面的点的集合。直线是一维的，即它们具有长度但没有面积。直线可以向一个方向及其相反的方向无限伸长，这不是计算机图形学中所需要的，在图形学中研究的对象是直线段。已知线段的起点坐标（x1,y1），终点坐标（x2,y2)，这两点就确定了一条线段。一般来讲，任何图形输出设备都能准确地画出水平线X和垂直线Y,或对角线，但要画出一条准确斜线不是件容易的事。在光栅系统中，线段通过象素绘制，水平和垂直方向的台阶大小受象素的间隔限制。这就是说，必须在离散位置上对线段取样，并且在每个取样位置上决定距线段最近的象素，画一条直线实际上就计算出来一系列与该线靠近的象素。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

其中，m表示直线的斜率，b是y轴截距。给定线段的两个端点（x1,y1）和（x2,y2)，可以计算斜率m和截距b:
直线的点斜式方程为： y﹦m·x﹢b 其中，m表示直线的斜率，b是y轴截距。给定线段的两个端点（x1,y1）和（x2,y2)，可以计算斜率m和截距b: m﹦(y2﹣y1)/(x2﹣x1) b﹦y1﹣m·x1 对任何沿直线给定的x的增量△x，对应的y增量△y： △y﹦m·△x 同样，对应于y的增量△y，x的增量△x为： △x﹦(1/m)△y 2019/4/25 计算机图形学演示稿纪玉波制作(C)

对于|m|＞1的线段，可通过计算由Y方向的增量△y引起的改变来生成直线： xk+1﹦xk﹢△x﹦xk﹢m·△y
DDA直线生成算法是一种基于上述直线方程的线段扫描转换算法。在一个坐标轴上以单位间隔增量，决定另一个坐标轴上最靠近线段路径的对应整数值。为了使产生的直线光滑，应使X、Y两方向上每一步的增量都不大于一个单位，因此当|m|≤1时，应该使用x做自变量，而当|m|＞1时应该使用y做自变量。也就是说应该选定x2﹣x1和y2﹣y1中绝对值较大者作为步进的控制量。假定x2﹣x1的绝对值大于y2﹣y1的绝对值，取x为一个象素单位长，即x 每次递增一个象素，然后利用下式计算相应的y值： yk+1﹦yk﹢△y﹦yk﹢m·△x 对于|m|＞1的线段，可通过计算由Y方向的增量△y引起的改变来生成直线： xk+1﹦xk﹢△x﹦xk﹢m·△y 2019/4/25 计算机图形学演示稿纪玉波制作(C)

DDA直线生成算法的伪语言描述如下： begin
if abs(x2﹣x1)≥abs(y2﹣y1) then lenght﹦abs(x2﹣x1) else lenght﹦abs(y2﹣y1) endif △x﹦(x2﹣x1)/lenght △y﹦(y2﹣y1)/lenght x﹦x1 y﹦y1 k﹦1 while(k≤lenght) putpixel(x,y) x﹦x﹢△x y﹦y﹢△y k﹦k﹢1 endwhile end DDA方法计算象素位置要比直接使用代数方程快。它利用光栅特性消除了代数方程中的乘法，而在X和Y方向使用合适的增量来逐步沿线段的路径计算各象素位置。但浮点增量的连续迭加中取整误差的积累会使长线段所计算的象素位置偏离实际线段，而且算法中的取整操作和浮点运算仍然十分耗时。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

DDA直线绘制演示 DDA直线绘制的C++实现 void DDA直线绘制(HDC hdc) { x=x1; int k; y=y1;
double x1=50,y1=50,x2=300,y2=350; double x,y,deltx,delty,length; if (fabs(x2-x1)>=fabs(y2-y1)) length=fabs(x2-x1); else length=fabs(y2-y1); deltx=(x2-x1)/length; delty=(y2-y1)/length; x=x1; y=y1; k=1; while(k<=length) { SetPixel(hdc,x,y,RGB(0,0,0)); x=x+deltx; y=y+delty; k=k+1; Sleep(50); } DDA直线绘制演示 2019/4/25 计算机图形学演示稿纪玉波制作(C)

3 Bresenham直线生成算法 Bresenham直线生成算法是由Bresenham提出的一种精确而有效的光栅线段生成算法，算法的目标是选择表示直线的最佳光栅位置。为此，算法根据直线的斜率确定选择变量在X方向上或在Y方向上每次递增一个单位，另一变量的增量为0或1，它取决于实际直线与最近网格点位置的距离，这一距离称为误差。算法的构思巧妙，使得每次只需检查误差项的符号即可确定所选象素。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

以第一象限的直线为例。假设斜率m在0～1之间。如下图所示。若通过（0,0）的直线的斜率m＞l／2，它与x﹦1直线的交点离y﹦l直线较y﹦0直线近，光栅点（1,1）比（1,0）更逼近于该直线，因此应该取象素点（1,1）。如果斜率m＜l／2，则应取象素点（1,0）。当斜率m﹦l／2时，差值相同，可以任选（1,1）或（1,0）象素点。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

通常，所选象素点与实际的直线位置之间存在差值。当斜率m在0～1之间时，x每增加一单位，y 应该增加m，记e为y方向上的误差。当选取实际直线位置上方的象素点时，误差为e﹦m﹣1；当选取实际直线位置下方的象素点时，误差为e﹦m。为了简化判断，可首先令误差项的初值为e0﹦-1/2，这样只要判断e的符号即可。第一步，当 e1﹦m﹢e0≥0，选取上面的象素点（1,1）；当e1﹦m﹢e0＜0,选取下面的象素点（1,0）。e1作为累计误差项供下一步判断继续使用。设第k步的误差为ek，选取上面象素点后的积累误差为： ek+1﹦ek﹢（m﹣1）选取下面的象素点后的积累误差为： ek+1﹦ek﹢m 2019/4/25 计算机图形学演示稿纪玉波制作(C)

根据上述思想的Bresenham直线生成算法描述如下： begin
x﹦x1 y﹦y1 x﹦x2-x1 y﹦y2-y1 m﹦y/x e﹦-1/2 for k﹦1 to x putpixel(x,y) e﹦e﹢m if(e≥0) y﹦y﹢1 e﹦e﹣1 endif x﹦x﹢1 next k endfor end 此Bresenham算法在计算直线斜率和误差项时要用到浮点算术运算和除法，如果采用整数算术运算和避免除法，可以加快算法的速度。实际上，误差项e的数值大小与算法的执行没有什么关系，相关的只是e的符号，因此作简单变换，即可得到整数算法。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

将e乘以2x记为E﹦2xe，则E同e有相同的符号，取代e判断E的符号确定象素点的过程仍然正确。此时上述算法中各误差项的表示式做如下变动：
积累误差 ek+1﹦ek﹢m修改为： Ek+1﹦2xek+1 ﹦2x(ek﹢y/x） ﹦2xek﹢2y ﹦Ek﹢2y；如果选取上面的象素点，积累误差还要减去1，修改为： Ek+1﹦2x（ek+1﹣1） ﹦E k+1﹣2x 2019/4/25 计算机图形学演示稿纪玉波制作(C)

由于x、y是整数，因此算法全部运算都只使用整数，修改后的Bresenham直线生成算法描述如下： begin
x﹦x1 y﹦y1 x﹦x2﹣x1 y﹦y2﹣y1 E﹦-x for k﹦1 To x putpixel(x,y) E﹦E﹢2y If (E≥0) y﹦y﹢1 E﹦E﹣2x endif x﹦x﹢1 next k endfor end 对于斜率值大于1的线段，只要交换x和y之间的规则，即沿Y方向以单位步长增加并计算最接近线段路径的x连续值。考虑到XY平面各种八分和四分区域间的对称性，Bresenham算法对任意斜率的线段具有通用性。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

Bresenham算法直线绘制例子：考虑绘制从点（0，0）到（8，4）的线段。初值计算：x=0 y=0 Δx=8 Δy=4
( 循环计算过程部分： e﹦-x for k﹦1 To x putpixel(x,y) e﹦e﹢2y If (e≥0) y﹦y﹢1 e﹦e﹣2x endif x﹦x﹢1 ) 2019/4/25 计算机图形学演示稿纪玉波制作(C)

Bresenham直线绘制演示 Bresenham直线绘制的C++实现 void Bresenham直线绘制(HDC hdc) {
int k; double x1=50,y1=50,x2=300,y2=300; double x,y,deltx,delty,E; x=x1; y=y1; deltx=x2-x1; delty=y2-y1; E=-deltx; for(k=1;k<=deltx;++k) { SetPixel(hdc,x,y,RGB(0,0,0)); E=E+2*delty; if(E>=0) y=y+1; E=E-2*deltx; }; x=x+1; Sleep(50); } Bresenham直线绘制演示 2019/4/25 计算机图形学演示稿纪玉波制作(C)

3.2 二次曲线绘制算法二次曲线是指那些能用二次函数 Ax2﹢Bxy﹢Cy2﹢Dx﹢Ey﹢F﹦0
来表示的曲线，包括圆、椭圆、抛物线、双曲线等。由于图形输出设备的基本动作是显示象素点或者是画以步长为单位的直线段，所以，从图形显示器和绘图机上输出的图形，一般除了水平线和垂直线以外，其他的各种线段，包括直线和曲线，都是由很多的点和短直线构成的锯齿形线条组成的。也就是说，需要把曲线离散化，把它们分割成很多短直线段，用这些短直线段组成的折线来逼近曲线。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

圆是图形中经常使用的元素，圆被定义为所有离一中心位置（xc,yc）距离为给定值R的点集，其函数方程为：
3.2.1 圆的参数方程生成算法圆是图形中经常使用的元素，圆被定义为所有离一中心位置（xc,yc）距离为给定值R的点集，其函数方程为： (x﹣xc)2﹢(y﹣yc)2﹦R2 利用这个方程，我们可以沿X轴从xc﹣R 到xc﹢R以单位步长计算对应的y值来得到圆周上每点的位置, 但这并非是生成圆的好方法。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

圆的方程绘制方法演示圆的方程绘制方法C++实现 void 圆的方程绘制(HDC hdc) {
double xc=300,yc=200,R=150; double x,y; y=yc; for(x=xc-R;x<=450;x++) y=sqrt(R*R-(x-xc)*(x-xc))+yc; SetPixel(hdc,x,y,RGB(0,0,0)); y=-sqrt(R*R-(x-xc)*(x-xc))+yc; Sleep(50); } 圆的方程绘制方法演示 2019/4/25 计算机图形学演示稿纪玉波制作(C)

这一方法包括乘法和平方根运算，计算量较大，所画象素位置间的间距也是不一致的。下面介绍两种生成速度较快的算法。先介绍圆的参数生成方法。
2019/4/25 计算机图形学演示稿纪玉波制作(C)

假定园心在(xc,yc)点，将圆用参数方程表示：
0≤θ≤2 将 离散化 0≤k≤n 使用上述离散化方程，可以得到如下算法： begin for k﹦0 to n x﹦xc﹢Rcos(2.k/n) y﹦yc﹢Rsin(2.k/n) putpixel(x,y) next k endfor end 2019/4/25 计算机图形学演示稿纪玉波制作(C)

使用上述方法可沿圆周等距点绘制出圆来。算法中，n取的值越大，计算的点越多，但执行时间越长。此算法的缺点是含有三角函数，计算量大。
为了避免三角函数运算，考虑下图,如果已经计算出圆上一点（xk,yk）,则增加一个角度 后，下一点（xk+1,yk+1）的坐标值可以用上一个点表示出。 xk+1﹦Rcos(﹢) ﹦R(coscos ﹣sinsin) ﹦R.coscos﹣Rsinsin ﹦xkcos﹣yksin yk+1﹦Rsin(﹢) ﹦R(sincos﹢cossin) ﹦Rcoscos﹣Rsinsin ﹦ykcos﹢xksin 2019/4/25 计算机图形学演示稿纪玉波制作(C)

习惯上用 表示一个较小的量，用它替代,式子改写为： xk+1=xk﹣yk yk+1=yk﹢xk
当 足够小时有： cos≈1 sin≈ 如是方程式可以改写为： xk+1=xk﹣yk yk+1=yk﹢xk 习惯上用 表示一个较小的量，用它替代,式子改写为： xk+1=xk﹣yk yk+1=yk﹢xk 2019/4/25 计算机图形学演示稿纪玉波制作(C)

利用前式，圆的参数方程生成算法可以描述如下： begin x﹦xc﹢R y﹦yc ﹦0 for ≤2 putpixel(x,y)
x﹦x﹣y y﹦y﹢x ﹦﹢ endfor end 此圆的生成算法中仍包含浮点数和乘法运算，影响速度。上述算法中， 选取的值越小，计算的点越多，但执行时间越长。为了在光栅系统上得到连续的边界，可选取﹦1／R，这样绘制的象素位置大约为一个单位间隔。此算法也被称为DDA圆的生成算法。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

圆的参数绘制方法演示圆的参数绘制方法C++实现 void ApplicationProceesing(HDC hdc) {
double xc=300,yc=200,R=150; double x,y,theta,delta; x=xc+R; y=yc; delta=1.0/R; for(theta=0;theta<=2*3.1416;theta=theta+delta) SetPixel(hdc,x,y,RGB(0,0,0)); x=x-(y-yc)*delta; y=y+(x-xc)*delta; Sleep(50); } 圆的参数绘制方法演示 2019/4/25 计算机图形学演示稿纪玉波制作(C)

圆的Bresenham生成算法圆的生成更有效的算法是Bresenham画圆算法。为了推导Bresenham圆的生成算法，考虑以坐标原点为圆心第一象限内的四分之一圆，如下图所示，可以看到，如果算法以点(x﹦0,y﹦R)为起点按顺时针方向生成圆时，在第一象限内y是x的单调递减函数。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

从圆上任意一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，对于下一象素的取法只有三种可能的选择，即右方象素、右下角象素和下方象素，并分别记为H，D和V, 如右图所示。要在这三者中决定一象素使其与圆的距离平方达到最小。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

此H、D、V三点同半径的平方差的绝对值分别为：
选取时，应以误差最小者为优。记右下角象素（xk﹢1,yk﹣1）同半径的平方差为： 2019/4/25 计算机图形学演示稿纪玉波制作(C)

如果 HD＜0，那么点D的距离大于点H的距离，这时应取H点。反之，如果HD＞0，应取D点。当两距离相等时，规定取H点。这样
如果k＜0 时，说明D（xk﹢1,yk﹣1）点在圆内，则V（xk,yk﹣1）点也必定在圆内且必有mV＞mD，显然这时只能取D点或H点，为此比较mH和 mD的大小如果 HD＜0，那么点D的距离大于点H的距离，这时应取H点。反之，如果HD＞0，应取D点。当两距离相等时，规定取H点。这样当 HD≤0时,取H（xk﹢1,yk）点 HD＞0 时取D（xk﹢1,yk﹣1）点 2019/4/25 计算机图形学演示稿纪玉波制作(C)

（xk﹢1)2﹢(yk)2﹣R2≥0 （H点在圆外） (xk﹢1)2﹢(yk-1)2﹣R2≤0 （D点在圆内）因此HD的表达式可简化为
此时有：（xk﹢1)2﹢(yk)2﹣R2≥0 （H点在圆外） (xk﹢1)2﹢(yk-1)2﹣R2≤0 （D点在圆内）因此HD的表达式可简化为 HD﹦(xk﹢1)2﹢(yk)2﹣R2﹢(xk﹢1)2﹢(yk-1)2 ﹣R2 ﹦2((xk﹢1)2 ﹢(yk-1)2 ﹣R2 ）﹢2yk﹣1 ﹦2（k﹢yk）﹣1 当 k＞0 时，说明D（xk﹢1,yk﹣1）点在圆外，此时H（xk﹢1,yk）点也必定在圆外且必有mH>mD，显然这时只能取D点或V点，为此比较mD和 mV的大小 2019/4/25 计算机图形学演示稿纪玉波制作(C)

如果DV＜0，那么点V的距离大于点D的距离，这时应取D点。反之，如果DV＞0，应取V点。当两距离相等时，规定取D点。这样
当 DV≤0 时取D（xk﹢1,yk﹣1）点 DV＞0 时取V（xk,yk﹣1）点此时有： (xk﹢1)2﹢(yk-1)2﹣R2≥0 （D点在圆外） (xk)2﹢(yk-1)2﹣R2≤0 （V点在圆内）因此DV的表达式可简化为 DV﹦(xk﹢1)2﹢(yk-1)2﹣R2﹢(xk)2﹢(yk-1)2﹣R2 ﹦2(（xk﹢1)2﹢(yk-1)2﹣R2）﹣2xk﹣1 ﹦2（k﹣xk）﹣1 当 k﹦0 时，表明D（xk﹢1,yk﹣1）点恰好在圆上，自然应取D点。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

上述结果可以归纳为当k＜0 时 HD≤0 时取H（xk﹢1,yk）点 HD＞ 0 时取D（xk﹢1,yk﹣1）点当 k＞0 时
DV≤0 时取D（xk﹢1,yk﹣1）点 DV＞0 时取V（xk,yk﹣1）点当 k﹦0 时取D（xk﹢1,yk﹣1）点。由此容易导出简单的增量算法递推关系。首先考虑水平移动到H（xk﹢1,yk）象素点，称此为第k+1个象素，新象素xk+1、yk+1值及误差计算公式k+1为: xk+1﹦xk﹢1 yk+1﹦yk k+1﹦(xk+1﹢1)2 ﹢(yk+1-1)2 ﹣R2 ﹦(xk+1)2 ﹢2xk+1﹢1﹢(yk-1)2﹣R2 ﹦(xk﹢1)2 ﹢2xk+1﹢1﹢(yk-1)2 ﹣R2 ﹦k﹢2 xk+1﹢1 2019/4/25 计算机图形学演示稿纪玉波制作(C)

类似地可以推出，当取 D（xk+1,,yk﹣1）象素点时 xk+1﹦xk+ 1 yk+1﹦yk﹣1
k+1﹦k﹢2xk+1﹣2yk+1﹢2 当取 V（xk,,yk﹣1）象素点时 xk+1﹦xk k+1﹦k﹣2yk+1﹢2 由于上面各个公式中，只涉及到整数的加减运算，所以基于这种方法设计的算法运算速度快。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

下面给出Bresenbam画圆算法描述（第一象限四分之一圆）：
begin xk﹦0 yk﹦R k﹦2(1﹣R) (k=(xk﹢1)﹢(yk﹣1)﹣R=1﹢(R﹣1) =2(1﹣R)) Limit﹦0 1 putpixel(xk,yk) if yk≤Limit then 4 if k＜0 then 2 if k＞0 then 3 if k﹦0 then 20 2 ﹦2k﹢2yk﹣1 if ≤0 then 10 if ＞0 then 20 3 ﹦2k﹣2xk﹣1 if ≤0 then 20 if ＞0 then 30 10 xk﹦xk﹢1 k﹦k﹢2xk﹢1 goto 1 20 xk﹦xk﹢1 yk﹦yk﹣1 k﹦k﹢2xk-2yk﹢2 30 yk﹦yk﹣1 k﹦k﹣2yk﹢1 4 finish end 2019/4/25 计算机图形学演示稿纪玉波制作(C)

如果圆心不在原点，设圆心坐标为（xc ,yc), 只需要改变初始化值： xk=xc yk=yc+R
k= (xc+1)2+(yc+R-1)2-R2 =xc2 +2xc+1+yc2 +2yc(R-1)-2R+1 由圆的对称性，很容易将上述方法转换到其它三个象限中。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

Bresenham圆的绘制算法例子：绘制以坐标原点为圆心，半径8的圆在第一象限的部分。 x0=0 y0=8 R=8
Δk=(xk+1)2+(yk-1)2-R2 当Δk<0时 δHD=2(Δk+yk)-1 δHD≤0时取H（xk+1,yk）点 Δk=Δk+2xk+1+1 δHD>0时取D（xk+1,yk-1）点 Δk=Δk+2xk+1-2yk+1+2 当Δk>0时 δDV=2(Δk-xk)-1 δDV≤0时取D（xk+1,yk-1）点 δDV>0时取V（xk,yk-1）点 Δk=Δk-2yk+1+2 当Δk=0时取D（xk+1,yk-1）点 2019/4/25 计算机图形学演示稿纪玉波制作(C)

由于各种其它二次曲线都有类似于圆的参数方程，因此其生成算法可以仿照圆的参数方程DDA生成算法设计。例如椭圆的参数方程为
3.2.2 其它二次曲线的绘制由于各种其它二次曲线都有类似于圆的参数方程，因此其生成算法可以仿照圆的参数方程DDA生成算法设计。例如椭圆的参数方程为 0≤θ≤2π 只有Rx和Ry两个半轴常数不同于圆的单一半径R，但它们并不影响算法设计。几乎可以不加改变地使用圆的DDA算法过程。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

线颜色由控制RGB监视器中三支电子枪的亮度的RGB分量来给出。
3.3线的属性基本的线属性是线型、线颜色和线宽度。对线型的指定包括实线、虚线和点划线等。线颜色由控制RGB监视器中三支电子枪的亮度的RGB分量来给出。常把图形设备能产生的最小直线宽度认为是1个点宽度，例如1个象素的宽度。以此作为基本线宽，再定义二倍或四倍线宽。线宽的默认值常选取基本线宽。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

一个区域是指一组相邻而又相连的象素，且具有同样的属性。根据边或轮廓线的描述，生成实区域的过程称为区域填充。
3.4区域填充一个区域是指一组相邻而又相连的象素，且具有同样的属性。根据边或轮廓线的描述，生成实区域的过程称为区域填充。区域填充算法可分为两大类：一是种子填充算法；二是扫描转换填充算法。种子填充算法首先假定封闭轮廓线内某点是已知的，然后算法开始搜索与种子点相邻且位于轮廓线内的点。种子填充算法只适用于光栅扫描设备。扫描转换填充算法则是按扫描线的顺序确定某一点是否位于多边形或轮廓线范围之内。这些算法一般从轮廓线的顶部开始进行到它的底部。区域填充的边界可以是直线也可以是曲线。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

区域的建立和定义通常可采用两种方式：一是内定义区域（Interior-Defined），用这种方式定义的区域内部所有象素具有同一种颜色或亮度值，而区域外的所有象素具有另－种颜色或亮度值。
另一种是边界定义区域（Boundary-Defined）这种方式定义的区域，其边界上所有象素均具有特定的颜色或亮度值，而在区域内的象素则具有不同于边界值的某种颜色或亮度值。较常使用的还是边界定义的方式。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

3.4.1 扫描转换填充算法一般的封闭轮廓线都是简单的多边形。而由曲线构成的轮廓线可用适当的多边形逼近之。有了对多边形轮廓的描述，要对此多边形内的区域进行填充，最本质的问题是要找出位于该多边形边界内的全部象素，即进行多边形对平面上点的包含性检查。然后，再将那些位于多边形内的全部象素的象素值置换成相应的数值。除边界线外，多边形中相邻象素几乎都具有相同的特性，这种性质称为空间连贯性。同样，光栅扫描图形显示的扫描线上相邻象素也具有连贯特性，扫描转换填充算法就是利用了这一特性。在给定的扫描线上，象素的这种特性只有在多边形的边和该扫描线交点处才会发生变化。这些交点把扫描线划分成一些段。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

扫描转换填充算法适用于规则边界的封闭区域，通常是将由顶点定义的多边形的边及其内部用预期的象素值予以填充，因此常称为多边形扫描变换。
右图所示是一简单多边形，各条扫描线与多边形有不同的交点个数，交点将扫描线分成了不同的区域。求出扫描线与多边形的交点后，将各条扫描线上的交点按X方向从小到大排序后两两配对。每对交点所确定的区间均取填充的光强或色彩，其它区间则取背景光强或色彩，即可完成填充。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

当扫描线与多边形顶点交于多边形的局部最高点或局部最低点时，交点应计2次，否则只计1次。确定多边形某顶点是否是局部最高点或最低点只需检查交于该顶点的两条边的另两个端点，如果它们的y值都大于顶点的y值，则该顶点是局部最低点，如果它们的y值都小于顶点的y值，则该顶点是局部最高点。如果一条边大于顶点的y值，而另一条边小于顶点的y值，则该顶点既不是局部最高点也不是局部最低点。前图中A和C是局部最高点，B和F是局部最低点，D 和E 既不是局部最高点也不是局部最低点。故扫描线在A、B、C和F处的交点应计两次，而在D 和E处只计一次。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

3．按（x1,y1）和(x2,y2)形式成对提取巳排序表的交点； 4．将每一对交点之间的象素置成填充的光强或颜色。
应用上述方法可得到几种有效的多边形扫描转换算法，这些算法是建立在按扫描顺序对多边形边与扫描线交点进行排序的基础上,故称为有序边表算法。下面给出一个简单的有序边表算法。有序边表算法： 1. 求出每一条扫描线与多边形各边的交点，把各个交点的坐标（xk,yk）存贮在表中； 2. 按扫描线以及扫描线上交点x值的递增顺序对该表进行排序。例如交点（x1,y1）和(x2,y2)，当y1＜y2或y1﹦y2而x1≤x2时，（x1,y1）将位于（x2,y2）的前面； 3．按（x1,y1）和(x2,y2)形式成对提取巳排序表的交点； 4．将每一对交点之间的象素置成填充的光强或颜色。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

2. 求出每一条扫描线与该边的交点坐标（xk,yk）； 3. 将（xk,yk）右边的全部象素取补；
3.4.2 边填充法另一种扫描转换方法即所谓的边填充算法。其基本思想是对每条扫描线和每条多边形的交点（xk,yk），将该扫描线上交点右方的所有象素取补。对多边形的每条边作此处理，就可以完成多边形区域填充。边填充算法描述如下： 1. 取多边形的一条边； 2. 求出每一条扫描线与该边的交点坐标（xk,yk）； 3. 将（xk,yk）右边的全部象素取补； 4．还有没处理的多边形边时转1，否则结束。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

下图示出了边填充算法的实现过程。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

上述算法的缺点是对于复杂的图形，一些象素可能被访问多次，一种改进的办法是引入栅栏。通过多边形设一栅栏，每次只对交点与栅栏之间的象素
点取补，可使访问象素的次数减少。下图示出了这一算法的原理。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

3.4.4 种子填充算法以上讨论的填充多边形的算法都是按扫描线顺序进行的。种子填充算法则来用完全不同的方法。种子填充算法假设在多边形或区域内部至少有一个象素是已知的。然后设法找到区域内所有其它象素，并对它们进行填充。区域可以由其内部点或边界来定义。如果区域是采用内部定义，那么该区域内部所有象素具有同一种颜色或值，而区域外的所有象素具有另一种颜色或值。如果区域是采用边界定义的，那么区域边界上所有象素均具有特定的值或颜色，区域内部所有的象素均不取这一特定值。然而边界外的象素则可具有与边界相同的值。填充内部定义的区域的算法称为泛填充算法（flood fill algorithm），填充边界定义的区域的算法称为边界填充算法。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

内部定义的或边界定义的区域可分为4连接或8连接两种。如果区域是4连接的，那么区域内每一象素可通过四个方向，即上、下、左、右移动到达相邻象素。对于8连接区域,区域内的每一象素可通过两个水平方向，两个垂直方向和四个对角线方向的移动到达相邻象素。下图是4连接和8连接内部定义区域的简单例子。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

对4连接算法，应用边界定义区域，可使用堆栈以建立简单的种子填充算法。使用的堆栈的种子填充算法如下：
1 种子象素压入堆栈； 2 当堆栈非空时做（1）栈顶象素出栈；（2）将出栈象素置成填充颜色；（3）检查每个与当前象素邻接的4连接象素，若其中有象素不为边界且没有设置成填充颜色，将该象素压入堆栈；（4）转2 2019/4/25 计算机图形学演示稿纪玉波制作(C)

算法可用伪语言描述如下：算法：seed(x,y) 作为种子 BV (BoundaryValue) 边界值
NV (NewValue) 填充值 begin pixel(x, y)=seed(x,y) push pixel(x,y) while (stack not empty) pop pixel(x,y) if pixel(x,y)<>NV then putpixel(x,y,NV) pixel(x,y)=NV endif if pixel(x+1,y)<>NV and pixel(x+1,y)<>BV then push pixel(x+1,y) if pixel(x,y+1)<>NV and pixel(x,y+1)<>BV then push pixel(x,y+1) if pixel(x-1,y)<>NV and pixel(x-1,y)<>BV then push pixel(x-1,y) if pixel(x,y-1)<>NV and pixel(x,y-1)<>BV then push pixel(x,y-1) endwhile end 2019/4/25 计算机图形学演示稿纪玉波制作(C)

如右图所示，种子的坐标为（2，3），以四连通顺时针左起点为例，其进出栈顺序为：种子（2，3）进栈，初始栈：（2，3）
种子填充算法例子如右图所示，种子的坐标为（2，3），以四连通顺时针左起点为例，其进出栈顺序为：种子（2，3）进栈，初始栈：（2，3）（1）种子（2，3）出栈，四个相邻点进栈；栈：（2，2），（3，3），（2，4），（1，3）（2）点（1，3）出栈，相邻点（1，2），（1，4）进栈；栈：（2，2），（3，3），（2，4），（1，2），（1，4）（3）点（1，4）出栈，相邻点（2，4）进栈；栈：（2，2），（3，3），（2，4），（1，2），（2，4）（4）点（2，4）出栈，相邻点进栈（无）；栈：（2，2），（3，3），（2，4），（1，2） 2019/4/25 计算机图形学演示稿纪玉波制作(C)

（6）点（2，2）出栈，相邻点（2，1），（3，2）进栈；栈：（2，2），（3，3），（2，4），（2，1），（3，2）
（5）点（1，2）出栈，相邻点（2，2）进栈；栈：（2，2），（3，3），（2，4），（2，2）（6）点（2，2）出栈，相邻点（2，1），（3，2）进栈；栈：（2，2），（3，3），（2，4），（2，1），（3，2）（7）点（3，2）出栈，相邻点（3，3）进栈；栈：（2，2），（3，3），（2，4），（2，1），（3，3）（8）点（3，3）出栈，相邻点进栈（无）；栈：（2，2），（3，3），（2，4），（2，1）（9）点（2，1）出栈，相邻点进栈（无）；栈：（2，2），（3，3），（2，4）（10）点（2，4）出栈，相邻点进栈（无）；栈：（2，2），（3，3）（11）点（3，3）出栈，相邻点进栈（无）；栈：（2，2）（12）点（2，2）出栈，相邻点进栈（无）；（13）栈空结束。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

种子填充算法主要实现子程序实例 void Seed_Fill_draw(HDC hdc) { int i;
COLORREF BoundColor; POINT triangle[]={300,275,280,325,320,325,300,275}; POINT fourline[]={250,340,300,375,350,340,300,350,250,340}; BoundColor=RGB(255,0,0); SetColor(BoundColor,hdc); Ellipse(hdc,180,200,420,400); Ellipse(hdc,230,230,270,310); Ellipse(hdc,330,230,370,310); Ellipse(hdc,245,264,255,296); Ellipse(hdc,345,264,355,296); for(i=0;i<3;i++) line(hdc,triangle[i],triangle[i+1]); for(i=0;i<4;i++) line(hdc,fourline[i],fourline[i+1]); Seed_Fill(hdc,300,300,RGB(0,0,255),BoundColor); Seed_Fill(hdc,250,280,RGB(0,255,0),BoundColor); Seed_Fill(hdc,350,280,RGB(0,255,0),BoundColor); Seed_Fill(hdc,300,360,RGB(0,255,255),BoundColor); Seed_Fill(hdc,235,270,RGB(0,0,0),BoundColor); Seed_Fill(hdc,335,270,RGB(0,0,0),BoundColor); } 2019/4/25 计算机图形学演示稿纪玉波制作(C)

void Seed_Fill(HDC hdc,int x1,int y1,COLORREF FillColor,COLORREF BoundColor)
{ int a[20000],b[20000]; int i,k,x,y,mx,my; COLORREF rgbColor; a[0]=x1; b[0]=y1; k=0; SetPixel(hdc,x,y,FillColor); while(k>=0) x=a[k]; y=b[k]; k--; rgbColor=GetPixel(hdc,x,y); if ((rgbColor!=FillColor)&&(rgbColor!=BoundColor)) Sleep(20); } mx=x; my=y; for(i=1;i<5;i++) x=mx; y=my; 2019/4/25 计算机图形学演示稿纪玉波制作(C)

for(i=1;i<5;i++) { x=mx; y=my; if (i==1) x++; else if (i==2) y++;
rgbColor=GetPixel(hdc,x,y); if ((rgbColor!=FillColor)&&(rgbColor!=BoundColor)) k++; a[k]=x; b[k]=y; } 2019/4/25 计算机图形学演示稿纪玉波制作(C)

种子填充算法演示 void line(HDC hdc,POINT point1,POINT point2) {
MoveToEx(hdc,point1.x,point1.y,NULL); LineTo(hdc,point2.x,point2.y); return; } //设置颜色 void SetColor(COLORREF color,HDC hdc) LOGPEN PenColor ={PS_SOLID,1,1,color}; HPEN rgbPen; rgbPen=CreatePenIndirect(&PenColor); SelectObject(hdc,rgbPen); 种子填充算法演示 2019/4/25 计算机图形学演示稿纪玉波制作(C)

上面的算法是一种深度优先搜索算法，采用堆栈实现。也可以改为广度优先搜索，采用队列实现。
扫描线种子填充算法种子填充算法的缺点是可能把太多的象素压入堆栈，有些象素甚至会入栈多次，降低算法的效率，存储空间需求大。解决的一种方法是对每一条扫描线实行种子算法。在任意不间断的扫描线象素段中，只取一个种子象素。象素段是指区域内相邻象素在水平方向的组合，它的两端以具有边界值的象素为界，其中间不包括具有新值的象素。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。
对于区域内的每一象素段，我们可以只保留其最右（或左）端的象素作为种子象素。因此，区域中每一个末被填充的部分，至少有一个象素段是保持在栈里的。扫描线种子填充算法适用于边界定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。算法叙述如下： 1 种子象素入栈； 2 当堆栈非空时做（1）栈顶象素出栈； 2019/4/25 计算机图形学演示稿纪玉波制作(C)

（2）沿扫描线对出栈象素的左右象素进行填充，直到遇到边界象素为止，即每出栈一个象素，便对包含该象素的整个区间进行填充；
（3）上述区间内最左最右的象素分别记为xLeft、xRight；（4）在区间[xLeft,xRight]中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或为已填充的象素，若存在非边界未填充的象素，则把每一区间的最右象素取作种子象素入栈；（5）转2 此算法可以有效地解决简单种子填充算法存在的堆栈可能过深的问题。 2019/4/25 计算机图形学演示稿纪玉波制作(C)

扫描线种子填充算法主要实现子程序实例 void push(int x,int y) { points[top][0]=x;
points[top][1]=y; top++; } void pop() x=points[top-1][0]; y=points[top-1][1]; top--; void Scanline_seed_fill_draw(HDC hdc) int i; COLORREF BoundColor; POINT triangle[]={300,275,280,325,320,325,300,275}; POINT fourline[]={250,340,300,375,350,340,300,350,250,340}; BoundColor=RGB(255,0,0); SetColor(BoundColor,hdc); 2019/4/25 计算机图形学演示稿纪玉波制作(C)

Ellipse(hdc,180,200,420,400); Ellipse(hdc,230,230,270,310); Ellipse(hdc,330,230,370,310); Ellipse(hdc,245,264,255,296); Ellipse(hdc,345,264,355,296); for(i=0;i<3;i++) line(hdc,triangle[i],triangle[i+1]); for(i=0;i<4;i++) line(hdc,fourline[i],fourline[i+1]); Scanline_seed_fill(hdc,300,300,RGB(0,0,255),BoundColor); Scanline_seed_fill(hdc,250,280,RGB(0,255,0),BoundColor); Scanline_seed_fill(hdc,350,280,RGB(0,255,0),BoundColor); Scanline_seed_fill(hdc,300,360,RGB(0,255,255),BoundColor); Scanline_seed_fill(hdc,235,270,RGB(0,0,0),BoundColor); Scanline_seed_fill(hdc,335,270,RGB(0,0,0),BoundColor); } void Scanline_seed_fill(HDC hdc,int seed_x,int seed_y,COLORREF FillColor,COLORREF BoundColor) { int active_x,active_y,Left_x,Right_x,flag,Nextspan_x; COLORREF rgbColor; push(seed_x,seed_y); while(top!=bottom) pop(); SetPixel(hdc,x,y,FillColor); 2019/4/25 计算机图形学演示稿纪玉波制作(C)

//填充扫描线右半部分 active_x=x+1; while(GetPixel(hdc,active_x,y)!=BoundColor) { SetPixel(hdc,active_x,y,FillColor); active_x++; Sleep(1); } Right_x=active_x-1; //填充扫描线左半部分 active_x=x-1; active_x--; Left_x=active_x+1; active_x=Left_x; //确定下一条扫描线的种子 y=y+1; while(active_x<Right_x) flag=0; while((GetPixel(hdc,active_x,y)!=FillColor) && (GetPixel(hdc,active_x,y)!= BoundColor) && (active_x<Right_x)) 2019/4/25 计算机图形学演示稿纪玉波制作(C)

if(flag==0) flag=1; active_x++; } if(flag==1) { if((active_x==Right_x)&& (GetPixel(hdc,active_x,y)!=FillColor) && (GetPixel(hdc,active_x,y)!=BoundColor)) push(active_x,y); else push(active_x-1,y); flag==0; Nextspan_x=active_x; while(((GetPixel(hdc,active_x,y)==BoundColor)||(GetPixel(hdc,active_x,y) ==FillColor))&&(active_x<Right_x)) if(Nextspan_x==active_x) active_x=Left_x; //确定上一条扫描线的种子 y=y-2; 2019/4/25 计算机图形学演示稿纪玉波制作(C)

扫描线种子填充算法演示 while(active_x<Right_x) { flag=0;
while((GetPixel(hdc,active_x,y)!=BoundColor)&&(GetPixel(hdc,active_x,y)!= FillColor)&&(active_x<Right_x)) if (flag==0) flag=1; active_x++; } if(flag==1) if((active_x==Right_x)&& (GetPixel(hdc,active_x,y)!=FillColor) && (GetPixel(hdc,active_x,y)!=BoundColor)) push(active_x,y); else push(active_x-1,y); flag==0; Nextspan_x=active_x; while(((GetPixel(hdc,active_x,y)==BoundColor)|| (GetPixel(hdc,active_x,y)==FillColor))&&(active_x<Right_x)) if(Nextspan_x==active_x) 扫描线种子填充算法演示 2019/4/25 计算机图形学演示稿纪玉波制作(C)

Similar presentations

Similar presentations

About project

反馈

请登录

Auth with social network:

Similar presentations

Similar presentations

About project

反馈